银行家算法

一、算法思想：在进程请求资源之前

1、实际资源检测：

　　Request < Need

　　Request < Available

2、假分配检测：

　　假设进行分配，预测是否会产生死锁。

3、程序结构：

 1 if(Request > Need[i])    error; 2 if(Request > Available)    sleep(); 3 //假设分配 4 Available -= Request; 5 Allocation[i] += Request; 6 Need[i] -=Request; 7 //检测分配后是否死锁 8 if(!isSafe()) { 9     //不分配，还原假设分配操作10 }else11     //分配

二、实例：参考这里

　　假设系统中有A、B、C三种资源，P1~P5共5个进程，某时刻三种资源数量Available =（3，3，2）。其他状态如下：

　　某时刻P2发出请求向量Request =（1,0,2），根据银行家算法：

　　　　Request < Need (P2) 且 Request < Available;

　　假设预分配给P2，则得到如下状态：Available = （2，3，0）

　　此时根据isSafy()判断，先将Available分配给P2，P2执行结束后Available = （5，3，2）；在分配给P4，执行结束后Available = （7，4，3）；分配给P5，结束后Available = （7，4，5）；分配给P1，结束后Available = （7，5，5）；分配给P3，执行后Available = （10，5，7）。最后所有进程全部执行结束，不会死锁，isSafy为真，可以分配。

三、银行家算法C++实现：

 1 #include<iostream> 2 using namespace std; 3 int numR,numP,*Max,*Allocation,*Need,*Available,*Request; 4  5  6 void banker(int p); 7 int main(){ 8     Max = (int *)malloc(sizeof(int)*numR*numP); 9     Allocation = (int *)malloc(sizeof(int)*numR*numP);10     Need = (int *)malloc(sizeof(int)*numR*numP);11     Available = (int *)malloc(sizeof(int)*numR);12     Request = (int *)malloc(sizeof(int)*numR);13     cin>>numR>>numP;14     for(int i=0; i<numP; i++){15         for(int j=0; j<numR; j++){16             cin>>Max[i*numR + j];17         }18     }19     for(i=0; i<numP; i++){20         for(int j=0; j<numR; j++){21             cin>>Allocation[i*numR + j];22             Need[i*numR + j] = Max[i*numR + j] - Allocation[i*numR + j];23         }24     }25     for(i=0; i<numR; i++)26         cin>>Available[i];27     while(1){28         int p;29         cin>>p;30         for(int i=0; i<numR; i++){31             cin>>Request[i];32         }33         banker(p);34     }35 }36 bool compare(int *a,int *b){37     for(int i=0; i<numR; i++){38         if(a[i] < b[i]){39             return false;40         }41     }42     return true;43 }44 bool isSafy(){45     int *flags = (int *)malloc(sizeof(int)*numP);46     memset(flags,0,sizeof(int)*numP);47     int num=0;48     while(num<=numP){49         if(!flags[num]&&compare(Available, &Need[num*numR])){50             for(int i=0;i<numR;i++){51                 Available[i] +=Allocation[num*numR+i];52             }53             flags[num] = 1;54             num=0;55         }else{56             num++;57         }58     }59     for(int i=0; i<numP; i++){60         if(!flags[i])61             return false;62     }63     return true;    64 }65 void banker(int p){66     if(compare(Request,&Need[p*numR])){67         cout<<"Error!"<<endl;68         return;69     }70     if(compare(Request,Available)){71         cout<<"Block!"<<endl;72         return;73     }74     for(int i=0;i<numR;i++){75         Available[i] -=Request[i];76     }77     for(i=0;i<numR;i++){78         Need[i] -=Request[i];79     }80     for(i=0;i<numR;i++){81         Allocation[i] +=Request[i];82     }83     if(isSafy()){84         cout<<"可以分配！"<<endl;85         return ;86     }else{87         cout<<"产生死锁！"<<endl;88         for(int i=0;i<numR;i++){89             Available[i] +=Request[i];90         }91         for(i=0;i<numR;i++){92             Need[i] +=Request[i];93         }94         for(i=0;i<numR;i++){95             Allocation[i] -=Request[i];96         }97     }98 }