一、实验目的

　　通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。

二、实验内容

（1）模拟一个银行家算法： 设置数据结构 设计安全性算法（2） 初始化时让系统拥有一定的资源
（3） 用键盘输入的方式申请资源
（4）如果预分配后，系统处于安全状态，则修改系统的资源分配情况
（5）如果预分配后，系统处于不安全状态，则提示不能满足请求

三、实验要点说明

数据结构

可利用资源向量 int Available[m] m为资源种类
最大需求矩阵 int Max[n][m] n为进程的数量
分配矩阵 int Allocation[n][m]
还需资源矩阵 int need[i][j]=Max[i][j]- Allocation[i][j]
申请资源数量 int Request [m]
工作向量 int Work[m] int Finish[n]
银行家算法bank()函数

Requesti：进程Pi的请求向量。 0<=j<=m-1

(1) 若 Requesti[j] ≤ Need[i,j]，转向(2)，否则出错。
(2) 若 Requesti[j] ≤ Available[j]，转向(3)，否则等待。
(3) 系统试探着把资源分配给进程Pi，修改下面内容：
Available[j] = Available[j] – Requesti[j];
Allocation[i,j] = Allocation[i,j] + Requesti[j];
Need[i,j] = Need[i,j] –Requesti[j];
(4) 试分配后，执行安全性算法，检查此次分配后系统是否处于安全状态。若安全，才正式分配；否则，此次试探性分配作废，进程Pi等待。

安全性算法safe()函数

(1) 初始化：设置两个向量Work(1×m)和Finish(1×n)
Work – 系统可提供给进程继续运行所需各类资源数，初态赋值Available
Finish – 系统是否有足够资源分配给进程，初值false.
(2) 从进程集合中满足下面条件进程：
Finish[i] = false; Need[i,j] ≤ Work[j];
若找到，执行(3)，否则，执行(4)。
(3) 进程Pi获得资源，可顺利执行，完成释放所分配的资源。
Work[j] = Work[j]+Allocation[i,j]; Finish[i] = true; go to (2).
(4) 若所有进程Finish[i] = true，表示系统处于安全状态，否则处于不安全状态。
先对用户提出的请求进行合法性检查，即检查请求的是否不大于需要的，是否不大于可利用的。 若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。 若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。

银行家算法实例

假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型资源{A、B、C}，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下所示。

试问：

①T0时刻是否安全？
② T0之后的T1时刻P1请求资源Request1(1,0,2)是否允许？
③ T1之后的T2时刻P4请求资源Request4(3,3,0)是否允许？
④ T2之后的T3时刻P0请求资源Request0(0,2,0)是否允许？
解：

① T0时刻是否安全？ 工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目

(1) T0时刻安全性分析

存在安全序列{P1, P3, P4, P0, P2}，系统安全。

(2) T0之后的T1时刻P1请求资源Request1(1,0,2)可否允许？

①Request1(1,0,2) ≤ Need1(1,2,2)，P1请求在最大需求范围内
②Request1(1,0,2) ≤ Available1(3,3,2)，可用资源可满足P1请求需要
③假定可为P1分配，修改Available,Allocation1,Need1向量
Available(2,3,0) = Available(3,3,2)-Request1(1,0,2);
Need1(0,2,0) = Need1(1,2,2)-Request1(1,0,2);
Allocation1(3,0,2) =Allocation1(2,0,0)+Request1(1,0,2);
④利用安全性算法检查试探将资源分配后状态的安全性

存在安全序列{P1, P3, P4, P0, P2}，所以试探将资源分配给进程P1后的状态是安全的，可将资源分配给进程P1。

③ T1之后的T2时刻P4请求资源Request4(3,3,0)是否允许？

Request4(3,3,0)≤Need4(4,3,1)，P4请求在最大需求范围内。
Request4(3,3,0)≤Available(2,3,0)不成立，即可用资源暂不能满足P4请求资源需要，P4阻塞等待。
P4请求资源Request4(3,3,0)不允许。

④ T2之后的T3时刻P0请求资源Request0(0,2,0)是否允许？

Request0(0，2，0)≤Need0(7，4，3)；
Request0(0，2，0)≤Available(2，3，0)；
系统暂时先假定可为P0分配资源，并修改有关数据，如下图所示：

进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

程序结构

程序共有以下五个部分：

(1).初始化init()：输入进程数量、资源种类、资源可利用量、进程资源已分配量、进程最大需求量
(2).当前安全性检查safe()：用于判断当前状态安全
(3).银行家算法bank()：进行银行家算法模拟实现的模块
(4).显示当前状态show()：显示当前资源分配详细情况
(5).主程序main()：逐个调用初始化、显示状态、安全性检查、银行家算法函数，使程序有序的进行

四、实验代码

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3  
  4 #define False 0
  5 #define True 1
  6  
  7 /********主要数据结构********/
  8 char NAME[100]={0};//资源的名称
  9 int Max[100][100]={0};//最大需求矩阵
 10 int Allocation[100][100]={0};//系统已分配矩阵
 11 int Need[100][100]={0};//还需要资源矩阵
 12 int Available[100]={0};//可用资源矩阵
 13 int Request[100]={0};//请求资源向量    
 14 int Work[100]={0};//存放系统可提供资源量 
 15 int Finish[100]={0}; //标记系统是否有足够的资源分配给各个进程 
 16 int Security[100]={0};//存放安全序列
 17  
 18 int M=100;//进程的最大数
 19 int N=100;//资源的最大数
 20  
 21 /********初始化数据：输入进程数量、资源种类、各种资源可利用数量、
 22 各进程对资源最大需求量、各进程的资源已分配数量等。********/
 23 void init()
 24 {
 25     /* m为进程个数，即矩阵行数，n为资源种类，即矩阵列数。*/
 26     int i,j,m,n;
 27     int number,flag;
 28     char name;//输入资源名称
 29     int temp[100]={0};//统计已经分配的资源
 30     //输入系统资源数目及各资源初试个数 
 31     printf("系统可用资源种类为:");
 32     scanf("%d",&n);
 33     N=n;
 34     for(i=0;i<n;i++)
 35     {
 36         printf("资源%d的名称:",i);
 37         fflush(stdin);  //清空输入流缓冲区的字符，注意必须引入#include<stdlib.h>头文件
 38         scanf("%c",&name);
 39         NAME[i]=name;
 40         printf("资源%c的初始个数为:",name);    
 41         scanf("%d",&number);
 42         Available[i]=number;
 43     }
 44     
 45     //输入进程数及各进程的最大需求矩阵 
 46     printf("\n请输入进程的数量:");    
 47     scanf("%d",&m);
 48     M=m;
 49     printf("请输入各进程的最大需求矩阵的值[Max]:\n");
 50     do{
 51         flag = False;
 52         for(i=0;i<M;i++)
 53             for(j=0;j<N;j++)
 54             {
 55                 scanf("%d",&Max[i][j]);
 56                 if(Max[i][j]>Available[j])
 57                     flag = True;                
 58             }
 59         if(flag)
 60             printf("资源最大需求量大于系统中资源最大量，请重新输入!\n");                                
 61     } while(flag);
 62     
 63             
 64     //输入各进程已经分配的资源量，并求得还需要的资源量 
 65     do{
 66         flag=False;
 67         printf("请输入各进程已经分配的资源量[Allocation]:\n");
 68         for(i=0;i<M;i++)
 69         {
 70             for(j=0;j<N;j++)
 71               {
 72                 scanf("%d",&Allocation[i][j]);
 73                 if(Allocation[i][j]>Max[i][j])  
 74                     flag=True;                
 75                 Need[i][j]=Max[i][j]-Allocation[i][j];
 76                 temp[j]+=Allocation[i][j];//统计已经分配给进程的资源数目
 77               }
 78         }
 79         if(flag)
 80             printf("分配的资源大于最大量，请重新输入!\n");        
 81     }while(flag);
 82     
 83     //求得系统中可利用的资源量 
 84     for(j=0;j<N;j++)
 85         Available[j]=Available[j]-temp[j];
 86 }
 87  
 88 /********显示资源分配矩阵********/
 89 void showdata()
 90 {
 91     int i,j;
 92     printf("*************************************************************\n");
 93     printf("系统目前可用的资源[Available]:\n");
 94     for(i=0;i<N;i++)
 95         printf("%c  ",NAME[i]);
 96     printf("\n");
 97     for(j=0;j<N;j++)
 98         printf("%d  ",Available[j]);
 99     printf("\n");
100     printf("系统当前的资源分配情况如下：\n");
101     printf("            Max        Allocation    Need\n");
102     printf("进程名     ");
103     //输出与进程名同行的资源名，Max、Allocation、Need下分别对应 
104     for(j=0;j<3;j++){
105         for(i=0;i<N;i++)
106             printf("%c  ",NAME[i]);
107         printf("     ");
108     }
109     printf("\n");
110     //输出每个进程的Max、Allocation、Need 
111     for(i=0;i<M;i++){
112         printf(" P%d        ",i);
113         for(j=0;j<N;j++)
114             printf("%d  ",Max[i][j]);
115         printf("     "); 
116         for(j=0;j<N;j++)
117             printf("%d  ",Allocation[i][j]);
118         printf("     "); 
119         for(j=0;j<N;j++)
120             printf("%d  ",Need[i][j]);
121         printf("\n");
122     }
123 }
124  
125 /********尝试分配资源********/
126 int test(int i) //试探性的将资源分配给第i个进程 
127 { 
128     for(int j=0;j<N;j++)
129     {
130         Available[j]=Available[j]-Request[j];
131         Allocation[i][j]=Allocation[i][j]+Request[j];
132         Need[i][j]=Need[i][j]-Request[j];
133     }
134     return True;
135 }
136  
137 /********试探性分配资源作废********/
138 int Retest(int i) //与test操作相反 
139 { 
140     for(int j=0; j<N; j++)
141     {
142         Available[j] = Available[j] + Request[j];
143         Allocation[i][j] = Allocation[i][j] - Request[j];
144         Need[i][j] = Need[i][j] + Request[j];
145     }
146     return True;
147 }
148  
149 /********安全性算法********/
150 int safe()
151 {
152     int i,j,k=0,m,apply;
153     //初始化work 
154     for(j=0;j<N;j++)
155         Work[j] = Available[j];
156     //初始化Finish 
157     for(i=0;i<M;i++) 
158         Finish[i] = False;
159     //求安全序列 
160     for(i=0;i<M;i++){ 
161         apply=0;
162         for(j=0;j<N;j++){
163             if(Finish[i]==False && Need[i][j]<=Work[j])
164             {   
165                 apply++;
166                 //直到每类资源尚需数都小于系统可利用资源数才可分配
167                 if(apply==N)
168                 {  
169                     for(m=0;m<N;m++)
170                         Work[m]=Work[m]+Allocation[i][m];//更改当前可分配资源
171                     Finish[i]=True;
172                     Security[k++]=i;
173                     i=-1; //保证每次查询均从第一个进程开始        
174                 }
175             }
176         }
177     }
178     
179     for(i=0;i<M;i++){
180         if(Finish[i]==False){
181             printf("系统不安全\n");//不成功系统不安全
182             return False;
183         }
184     }
185     printf("系统是安全的!\n");//如果安全，输出成功
186     printf("存在一个安全序列:");
187     for(i=0;i<M;i++){//输出运行进程数组
188         printf("P%d",Security[i]);
189         if(i<M-1) 
190             printf("->");
191     }
192     printf("\n");
193     return True;
194 }
195  
196 /********利用银行家算法对申请资源进行试分********/
197 void bank()
198 {
199     int flag = True;//标志变量，判断能否进入银行家算法的下一步 
200     int i,j;
201  
202     printf("请输入请求分配资源的进程号(0-%d):",M-1); 
203     scanf("%d",&i);//输入须申请资源的进程号
204     
205     printf("请输入进程P%d要申请的资源个数:\n",i);
206     for(j=0;j<N;j++)
207     {
208         printf("%c:",NAME[j]);
209         scanf("%d",&Request[j]);//输入需要申请的资源
210     }
211     
212     //判断银行家算法的前两条件是否成立 
213     for (j=0;j<N;j++)
214     {
215         if(Request[j]>Need[i][j])//判断申请是否大于需求，若大于则出错
216         { 
217             printf("进程P%d申请的资源大于它需要的资源",i);
218             printf("分配不合理，不予分配！\n");
219             flag = False;
220             break;
221         }
222         else 
223         {
224             if(Request[j]>Available[j])//判断申请是否大于当前可分配资源，若大于则出错
225             {                         
226                 printf("进程%d申请的资源大于系统现在可利用的资源",i);
227                 printf("\n");
228                 printf("系统尚无足够资源，不予分配!\n");
229                 flag = False;
230                 break;
231             }
232         }
233     }
234     //前两个条件成立，试分配资源，寻找安全序列 
235     if(flag) {
236         test(i); //根据进程需求量,试分配资源 
237         showdata(); //根据进程需求量，显示试分配后的资源量 
238         if(!safe()) //寻找安全序列
239         {
240             Retest(i);
241             showdata();
242         }
243     }
244 }
245  
246  
247 int main()//主函数
248 {    
249     char choice;
250     printf("\t---------------------------------------------------\n");
251     printf("\t||                                               ||\n");
252     printf("\t||               银行家算法的实现                ||\n");
253     printf("\t||                                               ||\n");
254     printf("\t||                                               ||\n");
255     printf("\t||                     在此输入个人姓名：******  ||\n");
256     printf("\t||                                               ||\n");
257     printf("\t---------------------------------------------------\n");
258     init();//初始化数据
259     showdata();//显示各种资源
260     //用银行家算法判定系统当前时刻是否安全，不安全就不再继续分配资源 
261     if(!safe()) exit(0);
262     
263     do{
264         printf("*************************************************************\n");
265         printf("\n");
266         printf("\n");
267         printf("\t-------------------银行家算法演示------------------\n");
268         printf("                     R(r):请求分配   \n");    
269         printf("                     E(e):退出       \n");
270         printf("\t---------------------------------------------------\n");
271         printf("请选择：");
272         fflush(stdin);  //清空输入流缓冲区的字符，注意必须引入#include<stdlib.h>头文件
273         scanf("%c",&choice);
274         switch(choice)
275         {
276             case 'r':
277             case 'R':
278                 bank();break;            
279             case 'e':
280             case 'E':
281                 exit(0);
282             default: printf("请正确选择!\n");break;
283         }
284     } while(choice);
285 }
286  
287