首页 > 代码库 > 银行家算法
银行家算法
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全,银行家规定:
(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2) 顾客可以分期贷款,但贷款的总数不能超过最大需求量;
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.
银行家算法数据结构
1）可利用资源向量Available
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。
4）需求矩阵Need。
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
算法 的实现
一、初始化
由用户输入数据，分别对可利用资源向量矩阵AVAILABLE 、 最大需求矩阵MAX 、分配矩阵ALLOCATION、 需求矩阵NEED 赋值。
二、银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前, 判断系统是否是安全的; 若是, 才分配。它是最具有 代表性的避免死锁的算法。
设进程cusneed 提出请求REQUEST [i] ，则银行家算法按如下规则进行判断。
(1) 如果REQUEST [cusneed] [i]<= NEED[cusneed][i] ，则转(2) ；否则，出错。
(2) 如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i] ，则转(3) ；否则，出错。
(3) 系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复 原状， 进程等待。
三、安全性检查算法
(1) 设置两个工作向量Work=AVAILABLE;FINISH
(2) 从进程集合中找到一个满足下述条件的进 程，
FINISH==false;
NEED<=Work;
如找到，执行(3) ； 否则，执行(4)
(3) 设进程获得资源，可顺利执行，直至完 成，从而释放资源。
Work+=ALLOCATION;
Finish=true;
GOTO 2
(4) 如所有的进程Finish= true ，则表 示安全；否则系统不安全。
操作系统安全状态和不安全状态：
安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源
量之和。
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不存在一个安全序列。不安全状态不一定导致死锁。
各算法流程图
初始化算法流程图：
银行家算法流程图：
安全性算法流程 图：
源程序
1 <pre class="cpp" name="code">#include <iostream> 2 using namespace std; 3 #define MAXPROCESS 50 /*最大进程数*/ 4 #define MAXRESOURCE 100 /*最大资源数*/ 5 int AVAILABLE[MAXRESOURCE]; /*可用资源数组*/ 6 int MAX[MAXPROCESS][MAXRESOURCE]; /*最大需求矩阵*/ 7 int ALLOCATION[MAXPROCESS][MAXRESOURCE]; /*分配矩阵*/ 8 int NEED[MAXPROCESS][MAXRESOURCE]; /*需求矩阵*/ 9 int REQUEST[MAXPROCESS][MAXRESOURCE]; /*进程需要资源数*/ 10 bool FINISH[MAXPROCESS]; /*系统是否有足够的资源分配*/ 11 int p[MAXPROCESS]; /*记录序列*/ 12 int m,n; /*m个进程,n个资源*/ 13 void Init(); 14 bool Safe(); 15 void Bank(); 16 void showdata(int,int); 17 int main() 18 { 19 Init(); 20 Safe(); 21 Bank(); 22 } 23 void Init() /*初始化算法*/ 24 { 25 int i,j; 26 cout<<"请输入进程的数目:"; 27 cin>>m; 28 cout<<"请输入资源的种类:"; 29 cin>>n; 30 cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩 阵输入"<<endl; 31 for(i=0;i<m;i++) 32 for(j=0;j<n;j++) 33 cin>>MAX[i][j]; 34 cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩 阵输入"<<endl; 35 for(i=0;i<m;i++) 36 { 37 for(j=0;j<n;j++) 38 { 39 cin>>ALLOCATION[i][j]; 40 NEED[i][j]=MAX[i][j]-ALLOCATION[i][j]; 41 if(NEED[i][j]<0) 42 { 43 cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数 错误,请重新输入:"<<endl; 44 j--; 45 continue; 46 } 47 } 48 } 49 cout<<"请输入各个资源现有的数目:"<<endl; 50 for(i=0;i<n;i++) 51 { 52 cin>>AVAILABLE[i]; 53 } 54 } 55 void Bank() /*银行家算法*/ 56 { 57 int i,cusneed,flag = 0; 58 char again; 59 while(1) 60 { 61 showdata(n,m);//////////////////////////////////////////////////////////////////// 62 cout<<endl; 63 input: 64 cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl; 65 cin>>cusneed; 66 if (cusneed > m) 67 { 68 cout<<"没有该进程，请重新输入"<<endl; 69 goto input; 70 } 71 cout<<"请输入进程所请求的各资源的数量"<<endl; 72 for(i=0;i<n;i++) 73 { 74 cin>>REQUEST[cusneed][i]; 75 } 76 for(i=0;i<n;i++) 77 { 78 if(REQUEST[cusneed][i]>NEED[cusneed][i])//如果用户选择的线程的第i个资源请求数＞该线程该资源所需的数量 79 { 80 cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl; 81 goto input; 82 } 83 if(REQUEST[cusneed][i]>AVAILABLE[i])//如果用户选择的线程的第i个资源请求数＞系统现有的第i个资源的数量 84 { 85 cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl; 86 goto input; 87 } 88 } 89 for(i=0;i<n;i++)//如果请求合理，那么下面 90 { 91 AVAILABLE[i]-=REQUEST[cusneed][i];//系统可用资源减去申请了的 92 ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];//线程被分配的资源加上已申请了的 93 NEED[cusneed][i]-=REQUEST[cusneed][i];//线程还需要的资源减去已申请得到的 94 } 95 if(Safe())//AVAILABLE ALLOCATION NEED变动之后，是否会导致不安全 96 { 97 cout<<"同意分配请求!"<<endl; 98 } 99 else100 {101 cout<<"您的请求被拒绝!"<<endl;102 for(i=0;i<n;i++)103 {104 AVAILABLE[i]+=REQUEST[cusneed][i];105 ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];106 NEED[cusneed][i]+=REQUEST[cusneed][i];107 }108 }109 for (i=0;i<n;i++)110 {111 if (NEED[cusneed][i] <= 0)112 {113 flag++;114 }115 }116 if (flag == n)//如果该进程各资源都已满足条件，则释放资源117 {118 for (i=0;i<n;i++)119 {120 AVAILABLE[i] += ALLOCATION[cusneed][i];121 ALLOCATION[cusneed][i] = 0;122 NEED[cusneed][i] = 0;123 }124 cout<<"线程"<<cusneed<<" 占有的资源被释放！"<<endl;125 flag = 0;126 }127 for(i=0;i<m;i++)//分配好了以后将进程的标识FINISH改成false128 {129 FINISH[i]=false;130 }131 cout<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl;132 cin>>again;133 if(again==‘y‘||again==‘Y‘)134 {135 continue;136 }137 break;138 }139 }140 bool Safe() /*安全性算法*/141 {142 int i,j,k,l=0;143 int Work[MAXRESOURCE]; /*工作数组*/144 for(i=0;i<n;i++)145 Work[i]=AVAILABLE[i];146 for(i=0;i<m;i++)147 {148 FINISH[i]=false;//FINISH记录每个进程是否安全149 }150 for(i=0;i<m;i++)151 { 152 for(j=0;j<n;j++)//循环查找第i个进程需要的各个资源数 是否 超过系统现有的对应的资源数153 {154 if(NEED[i][j]>Work[j])//第i个进程需要的第j个资源数 ＞ 系统现有的第j个资源数155 {156 break;157 }158 }159 if(j==n)//如果第i个进程所需的各个资源数都没有超过系统现有的对应资源数160 { 161 FINISH[i]=true;//给该进程的FINISH标记为true162 for(k=0;k<n;k++)163 {164 Work[k]+=ALLOCATION[i][k];//将Work赋值为 第i个进程各个已分配资源数＋系统现有的对应资源数(因为当改进程全部资源数都满足时线程结束并将资源返还给系统)165 }166 p[l++]=i;//记录进程号167 }168 else//如果超过继续循环下一个进程169 {170 continue; 171 }172 if(l==m)//当所有进程都能够被满足运行时173 {174 cout<<"系统是安全的"<<endl;175 cout<<"安全序列:"<<endl;176 for(i=0;i<l;i++)//改了146行的i值，显示资源分配给进程的顺序177 {178 cout<<p[i];179 if(i!=l-1)180 {181 cout<<"-->";182 }183 }184 cout<<""<<endl; 185 return true;186 }187 }//for循环188 cout<<"系统是不安全的"<<endl;189 return false;190 }191 192 void showdata(int n,int m) //显示193 {194 int i,j;195 cout<<endl; 196 cout<<"-------------------------------------------------------------"<<endl; 197 cout<<"系统可用的资源数为: ";198 for (j=0;j<n;j++) 199 cout<<" "<<AVAILABLE[j]; 200 cout<<endl; 201 cout<<"各进程还需要的资源量:"<<endl; 202 for (i=0;i<m;i++) 203 {204 cout<<" 进程"<<i<<":"; 205 206 for (j=0;j<n;j++)207 cout<<" "<<NEED[i][j]; 208 cout<<endl; 209 } 210 211 cout<<endl; 212 cout<<"各进程已经得到的资源量: "<<endl<<endl; 213 214 for (i=0;i<m;i++) 215 {216 cout<<" 进程"<<i<<":"; 217 218 for (j=0;j<n;j++)219 cout<<" "<<ALLOCATION[i][j];220 cout<<endl; 221 } 222 cout<<endl; 223 } </pre><br>224 <p></p>225 <pre></pre>226 <p></p>227 <p></p>228 <pre></pre>229 <p></p>230 <p></p>231 <pre></pre>232 <p></p>
银行家算法