周二晚才知道第四章小作业还有一道难度及工作量不亚于一个大作业的编程题..晚上找了一些资料，周三肝了一天算是赶完了这突如其来的ddl...
银行家算法是一种经典的死锁问题，下面是ppt里对银行家算法的描述。
查阅网上资料时，发现对于算法的代码有不少，但基于多线程的linux编程实现却很少，偶然发现了班上一大佬的文章，参考了他的思路（linux多线程模拟银行家算法
)，结合了其他的一些资料，算是在ddl之前水完了这个作业...
这里记录一下一些细节和遇到的一些问题，以便日后回顾...（再次对上边的大佬进行无声的感谢..）
先贴代码为敬。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<pthread.h>
#include<unistd.h>
#define true 1
#define false 0
#define MAXTN 10
#define MAXSRC 50
typedef int bool;
int thnum; //线程数目
int res; //资源种类数
int leftnum; //结束的线程数
int Available[MAXSRC]; //Available[j]:系统中j类资源空闲个数
int Max[MAXTN][MAXSRC]; //Max[i][j]:线程i对j类资源的最大需求量
int Allocation[MAXTN][MAXSRC]; //Allocation[i][j]:线程i已分配j类资源的数量
int Need[MAXTN][MAXSRC]; //Need[i][j]:线程i还需要j类资源的数量 Need=Max-Allocation
int Work[MAXTN]; //工作向量
bool visited[MAXTN]; //线程是否被访问过
bool Finish[MAXTN]; //线程是否已结束
int Safeseries[MAXTN]; //安全序列
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;//初始化互斥锁
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;//初始化条件变量
void init() //初始化数据
{
printf("输入线程数目:\n");
scanf("%d",&thnum);
printf("输入资源种类数:\n");
scanf("%d",&res);
//init Available
printf("输入每类资源的可用数量:\n");
for(int i=0;i<res;i++)
scanf("%d",&Available[i]);
//init Max
printf("输入每个线程对每类资源的最大需求量:\n");
for(int i=0;i<thnum;i++)
{
printf("线程%d对每类资源的最大需求量分别为:\n",i);
for(int j=0;j<res;j++)
scanf("%d",&Max[i][j]);
}
//init Allocation,Need
printf("输入每个线程已分配各类资源的数量:\n");
for(int i=0;i<thnum;i++)
{
printf("线程%d已分配每类资源的数量分别为:\n",i);
for(int j=0;j<res;j++)
{
scanf("%d",&Allocation[i][j]);
Need[i][j]=Max[i][j]-Allocation[i][j];
}
}
}
bool compare(int* Work,int i,int (*Need)[res]) //判断某一线程是否满足资源条件
{
for(int j=0;j<res;j++)
if(Work[j]<Need[i][j]) return false; //线程i有某一类资源无法满足，则返回失败
return true;
}
bool safe(int id) //安全性检测算法要使用临时变量储存
{
memset(visited,0,sizeof(visited)); //标记线程是否已经满足条件访问过
for(int i=0;i<res;i++) //初始化工作向量（临时分配量）
Work[i]=Available[i];
int k=0; //安全序列元素个数
while(k<thnum) //安全序列中元素个数小于线程数，则循环执行
{
int find=0; //find==true表示找到一个可完成的线程
//寻找need<=work且未运行的线程
for(int i=0;i<thnum;i++)
{
if(!visited[i]&&Finish[i]==false&&compare(Work,i,Need))
{
for(int j=0;j<res;j++)
Work[j]+=Allocation[i][j]; //资源回收
find=1;
visited[i]=1;
Safeseries[k]=i;
k++;
//Finish[i]=true;
}
}
if(!find) break; //如果一次遍历未找到满足条件的线程，则跳出循环
}
//输出判断结果及返回值
if(k==(thnum-leftnum)) //当一个线程结束后，安全序列元素数目会减少，故不等于thunm
{
printf("系统处于安全状态，存在安全序列如下：\n");
for(int i=0;i<(thnum-leftnum);i++)
printf("%d-",Safeseries[i]);
printf("\n");
return true;
}
else
{
printf("系统处于不安全状态，试分配不满足，进程%d在等待!\n",id);
return false;
}
}
int banker(int id,int Request[res]) //线程id对res类资源的请求量 return 0分配成功
{
//step1 判断Request[i]是否小于Need[id][i]和Available[i]
for(int i=0;i<res;i++)
{
if(Request[i]<=Need[id][i])
{
if(Request[i]>Available[i])
{
printf("线程%d请求%d类资源数目大于该类资源剩余数量!\n",id,i);
return 1;
}
}
else
{
printf("线程%d请求%d类资源数目大于该线程所需资源数目!\n",id,i);
return 1;
}
}
//step2 试分配并修改数据结构
for(int i=0;i<res;i++)
{
int k=Request[i]; //储存试分配资源数目，若分配失败可恢复资源
Available[i]-=k;
Allocation[id][i]+=k;
Need[id][i]-=k;
}
//step3 执行安全性算法，若检测失败则恢复资源，否则成功分配
if(!safe(id)) //分配失败，恢复资源
{
for(int i=0;i<res;i++)
{
int k=Request[i];
Available[i]+=k;
Allocation[id][i]-=k;
Need[id][i]+=k;
}
return 1;
}
//step4 分配成功则输出信息并return 0
printf("线程%d获得资源：\n",id);
for(int i=0;i<res;i++)
printf("%d类资源%d个\n",i,Request[i]);
return 0;
}
void *threadprocess(void *arg)
{
int id=*(int*)arg;
//初始化Request，使用随机数来随机生成对每一类资源的请求数
int Request[res];
sleep(thnum-id); //等待所有进程创建完毕
while(true)
{
pthread_mutex_lock(&mutex);
printf("进程%d对各类资源的请求数为：\n",id);
for(int i=0;i<res;i++)
scanf("%d",&Request[i]);
switch(banker(id,Request[res]))
{
case 1: pthread_cond_wait(&cond,&mutex); break; //失败则阻塞等待
case 0: Request[res]=0; //将请求向量清零，重复上述操作随机赋值
for(int i=0;i<res;i++)
{
int k=(Need[id][i]==0)?0:(rand()%Need[id][i]+1);
Request[i]=k;
}
break;
}
//判断该线程是否已经获得所需全部资源
bool pfinish=true;
for(int i=0;i<res;i++)
if(Need[id][i]!=0) //找到有一类资源未满足需求，则更改标识为false
{
pfinish=false;
break;
}
if(pfinish)
{
printf("线程%d已得到所需全部资源！\n",id);
sleep(1);
printf("线程%d执行完毕。\n",id);
Finish[id]=1;
for(int i=0;i<res;i++) //资源回收
{
Available[i]+=Allocation[id][i];
Allocation[id][i]=0;
}
leftnum++;
pthread_cond_broadcast(&cond);
pthread_mutex_unlock(&mutex);
pthread_exit(NULL); //线程退出
}
pthread_mutex_unlock(&mutex);
sleep(1);
}
}
int main()
{
init();
pthread_t tid[thnum]; //线程标识符
pthread_mutex_init(&mutex,NULL);
pthread_cond_init(&cond,NULL);
int m[thnum]; //给创建线程传递id号信息
for(int i=0;i<thnum;i++) //创建线程
{
m[i]=i;
pthread_create(&tid[i],NULL,threadprocess,(void*)&m[i]);
}
for(int i=0;i<thnum;i++) //等待线程结束
pthread_join(tid[i],NULL);
sleep(3);
return 0;
}
运行截图如下：
整个代码的核心部分分为以下几个部分：
- init()初始化算法
- safe()安全性检测算法
- banker()银行家算法主体
- threadprocess()线程算法
程序运行过程大概就是：初始化（矩阵及数组信息、互斥锁及条件变量等）——创建线程——线程内部根据请求数执行银行家算法，进行安全性检测——线程条件满足结束或条件不满足等待——全部线程满足需求后程序退出。
把各个模块内部及模块间的关系理清一步一步做就很明确了。（这里再次感谢大佬的文章指导了我方向）
下面列举一下遇到的一些问题。
编译问题：
1.使用const int MAXTN=10; const int MAXSRC=50; 进行定义数组空间，编译会报错“Variably modified array at file scope”。
原因：使用const声明的对象是一个运行时对象，无法使用其作为某个量的初值、数组的长度等情形使用。详细原因参考 C语言编译错误：Variably modified array at file scope
使用#define宏定义即可解决。
2.在c语言中没有定义布尔类型，只有c++中有。C99标准后定义了bool类型变量，但需要引入头文件<stdbool.h>，所以只需使用typedef int bool #define true 1 #define false 0进行定义。
3.二维数组参数传递问题。compare函数中需要传递二维数组，但简单的使用int** Need编译会报错，错误原因好像是传递参数和函数所需参数类型不匹配，又吃了c语言基本功不扎实的亏...参数传递二维数组讲了几个方法，又引出了值传递、引用传递等不同传递方法，再次显示出当初给自己挖下的坑...值传递、地址传递、引用传递
4.若干语法错误...当在linux中用gcc编译后，一片的error吓懵我了，但其中很大一部分都是“缺少[]”或标点使用错误之类的低级错误..
算法问题：
1.对于资源请求Request数组的赋值。开始考虑使用随机数值来增加真实性，后来想想这个值应该是使用者输入决定的，如果随机产生可能会导致线程间死锁（很大概率）。
2.因为创建进程先后有顺序，导致进入互斥区的进程顺序固定，无法做到随机性。使用sleep()也不好掌握时机。（目前尚未解决）
3.以前没用到或很少用的函数：memset()用于初始化数组，使值清0。
4.一开始总是提示不安全状态，因为判断条件出错。当一个线程完成资源分配后结束，会使安全序列理论输出减少一个，故判断条件也应该是动态的，即使用一个leftnum记录剩余线程数，if(k==(thnum-leftnum))判断是否处于安全状态。
其他问题想到再补充吧，总之这个算法还不完善，有时间再回头看吧，毕竟是赶出来的...测试还有一些奇怪的地方没有解决...
网友评论