模拟通过银行家算法避免死锁一、银行家算法产生的背景及目的1 ：在多道程序系统中，虽然节奏、虽然借助于多个进程的并发执行来改善系统的利用率，提高系统的吞吐量，但可能发生一种危险—死锁。

，死锁就是多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，如无外力作用，他们将无法再向前进行，如再把信号量作为同步工具时，多个 Wait 和 Signal 操作顺序不当，会产生进程死锁。

然而产生死锁的必要条件有互斥条件，请求和保持条件，不剥夺条件和环路等待条件。

在预防死锁的几种方法中，都施加了较强的限制条件，在避免死锁的方法中，所施加的条件较弱，有可能获得令人满意的系统性能。

在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，便可避免死锁。

2：实验目的：让学生独立的使用编程语言编写和调试一个系统分配资源的简单模拟程序，了解死锁产生的原因及条件。

采用银行家算法及时避免死锁的产生，进一步理解课堂上老师讲的相关知识点。

银行家算法是从当前状态出发，逐个按安全序列检查各客户中谁能完成其工作，然后假定其完成工作且归还全部贷款，再进而检查下一个能完成工作的客户。

如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。

二：银行家算法中的数据结构1 :可利用资源向量Available。

这是一个含有m个元素的数组，其中的每个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态的改变。

如果 Available[j]=k ， z 则表示系统中现有 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 :需求矩阵Neec。

也是一个n*m的矩阵，Need[i,j]=k, 表示第i个进程还需 Rj 类资源 k 个。

三、银行家算法及安全性算法1 :银行家算法设 Request[i] 是进程 Pi 的请求向量，若 Request[i][j]=k; 表示进程需要 j 类资源k个。

当Pi发出资源请求时，系统按下属步骤进行检查；(1) 如果 Request[i][j]<=Need[i][j]; 便转向步骤( 2)，否则认为出错，因为它所需要的资源数已超过他所宣布的最大值。

(2) 如果 Request[i][j]<=Available[i][j], 便转向步骤( 3)，否则认为尚无足够资源，进程需等待。

（3）系统试探着把资源分配给进程，并修改下面数据结构的数据Available[i][j]=Available[i][j]-Request[i][j];Allocation[i][j]=Allocation[i][j]+Request[i][j];Need[i][j]=Need[i][j]-Request[i][j];（4）系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。

若安全，才正式将资源分配给进程 Pi ，已完成此次分配。

否则，将本次的试探分配作废，回复原来的资源分配状态，将进程 Pi 等待。

2：安全性算法（ 1）设置两个向量；1 :工作向量Work,表示系统可提供给进程运行所需的各类资源数目，它含有 m 个元素，初始时 Work=Available2 : Finish , 表示系统是否有足够的资源分配给进程，使之运行完成。

开始时先做 Finish[i]=true（2）从进程中找到一个能满需下属条件的进程1 ； Finish[i]=false ；2: Need[i][j]<=Work[j]; 若找到执行步骤（ 3），否则执行步骤（ 4）（3）当进程 Pi 顺利获得资源后，直至完成，并释放分配给它的资源，执行: Work[j]=Work[j]+Allocation[i][j];Finish[i]=true;Go to step （2）;（5）如果所有的进程 Finish[i] 都满足，则表示系统处于安全状态，否则，处于不安全状态。

四、模块设计与分析及整体功能概述模块设计与分析:整个银行家算法分为初始化函数Init （），安全性算法函数safe （），银行家算法函数bank （）三部分。

初始化函数生成开始时刻系统中的进程和资源情况，安全性算法判断当某进程申请资源时，系统能否处于安全状态。

在本实验中，若系统处于安全状态，便生成一个安全进程序列（安全序列可能有多个）。

银行家算法函数bank （）负责整体的检查与异常判断。

整体功能概述: 死锁会引起系统陷入僵局，操作系统必须防止此现象的发生。

本实验通过一个动态分配资源的模拟程序，更清楚的理解死锁产生的原因和条件。

Dijkstra 的银行家算法是最有代表性的避免死锁的方法。

运行程序时用户设定系统中进程和可利用资源的种类数目。

输入各进程的可利用资源 Available，最大需求MAX已分配资源Allocation ，需求资源Need之后各系统发出资源请求 Request，利用实验中的安全性算法判断能否产生一个安全性队列，若能，则给该进程分配成功，否则，不予分配。

五、流程图设计[i, j]>Available7j]/申请资源大于Available 讦始初始仇rfo生成安全序列退出// 定义最大进程数 //定义最大资源数//最大需求矩阵//已分配矩阵 //可用资源数组//需求矩阵 //请求矩阵//存储完成资源分配的进程 //模拟的资源分配序列 //系统是否有足够的资源分配给进程〃m 个进程,n 个资源 初始化算法 ****************\n";cout<<" ************************************\n";六、源代码及调试分析 #include<iostream.h> #define MAXm 50 #defineMAXn 100 int MAX[MAXm][MAXn]; int Allocation[MAXm][MAXn]; int Available[MAXn]; int Need[MAXm][MAXn]; int Request[MAXm][MAXn]; intFinish[MAXm]; intSequence[MAXm]; intWork[MAXn]; int m,n;#define False 0#define True 1 void input(); //数据输入函数 int safealg(); //安全性算法函数 void banker(); //银行家算法函数void main() {input();safealg();banker();}cout<<"* cout<<"请输入进程的数目cin>>m;cout<<"请输入资源的种类 cin>>n;//***** 输入每个进程对每种资源的最大需求、已经获得的数 量、每种类型资源的数目cout<<"各进程资源最大需求 (Max), 按照 "<<m<<"x"<<n<<矩阵输入 :\n";for(i=0;i<m;i++){cout<<"P"<<i<<":";for(j=0;j<n;j++) cin>>MAX[i][j];if(j==n) cout<<"资源种类数匹配出现错误！ ";// 当资源配置的种 类数大于预先输入的数值时，出错}//************ int i,j; 自定义进程数目与资源种类void input(){cout<<"********************************** *\n"; cout<<"* 利用银行家算法避免死锁 *\n";}cout<<"各进程当前获得资源 (Allocation), 按照"<<m<<"x"<<n<<"矩阵输入 "<<endl;for(i=0;i<m;i++){cout<<"P"<<i<<":"; for(j=0;j<n;j++){ cin>>Allocation[i][j];if(j==n) cout<<"资源种类数匹配出现错误！ ";// 当资源配置的种类数大于预先输入的数值时，出错Need[i][j]=MAX[i][j]-Allocation[i][j];// 需求数等于最大需求减去已经分配数}}cout<<"系统可用资源 (Available):"<<endl;for(j=0;j<n;j++){cin>>Available[j];// 输入各种资源的可利用数}cout<<"当前时刻的进程分配情况如图： \n";cout<<"进程号-"<<"MAX"<<"Allocation---"<<"Need--"<<"Available---\n";// 显示各进程的资源情况for(i=0;i<m;i++){cout<<"P"<<i<<": ";for(j=0;j<n;j++)cout<<""<<MAX[i][j];for(j=0;j<n;j++)cout<<""<<Allocation[i][j];cout<<"";for(j=0;j<n;j++)cout<<""<<Need[i][j];for(j=0;j<n;j++)cout<<""<<Available[j]; cout<<endl;// 回车换行}}//***************** 银行家算法，为进程分配资源***********// void banker(){int i,j; int choice;while(1){cout<<endl; cout<<"输入要进行的操作 (1:分配资源 2:离开) :"; //用户选择待!"<<e ndl;continue; for(j=0;j<n;j++)// 资源申请得到允许时， 变换各个资源数 {Available[j]=Available[j]-Request[i][j]; // 可用资源{cout«"从P0到P"vvm-1<v"之间选择要分配资源的进程号:\n";cin>>i; if(i>=m){cout<<"无此进程号 !请重新输入 :\n";cin>>i;// 重新输入进程号}cout<<"请输入进程申请的资源 (Request):"<<endl; for(j=0;j<n;j++) cin>>Request[i][j];//********** 银行家算法进行检查 *************// for(j=0;j<n;j++){if(Request[i][j]>Need[i][j]) {cout<<"申请的资源大于它需要的资源数,请重cin>>choice; if(choice==1) //分配资源 新输入 !\n";// 资源申请不合理continue; }if(Request[i][j]>Available[j]){//资源申请数目大于可利用数，无法分配，得等待cout<<"当 前 系 统 可 用 资 源 不 够 ， 请 等减少Allocation[i][j]=Allocation[i][j]+Request[i][j];// 所得资源增加Need[i][j]=Need[i][j]-Request[i][j]; //仍需资源减少}if(safealg()<0)// 安全性算法的返回值{cout<<"分配不成功，请等待！ ";for (j=0;j<n;j++) //把资源恢复成分配之前的状态{Available[j]=Available[j]+Request[i][j];Allocation[i][j]=Allocation[i][j]-Request[i][j];Need[i][j]=Need[i][j]+Request[i][j];}for(i=0;i<m;i++){Finish[i]=False;// 没有足够的资源分配给该进程}}//if(safealg()<0)else{cout<<"同意分配请求 !"<<endl;for(j=0;j<n;j++)Work[j]=Available[j];cout<<"进程号-"<<"--Work - "<<"Need---"<<"Allocation---"<<"Work+Allocation--"<<"Finish--"<<endl;for(i=0;i<m;i++)// 按模拟分配序列进行分配{cout<<"进程 P"<<Sequence[i]<<": ";for(j=0;j<n;j++)cout<<Work[j]<<"";cout<<"";for(j=0;j<n;j++)cout<<Need[Sequence[i]][j]<<"";cout<<"";for(j=0;j<n;j++)cout<<Allocation[Sequence[i]][j]<<"";}}//if(safealg()>=0) }// if(choice=1)else if(choice==2) break;else cout<<"请输入//离开————1或2!";//只认可1或2安全性算法int safealg(){int i,j,k,l=0;//int Work[MAXn];//工作组//记录序列for(i=0;i<n;i++)Work[i]=Available[i];for(i=0;i<m;i++)所有进程不能运行{Finish[i]=False;}for(i=0;i<m;i++){ //if(Finish[i]==True){continue; //工作分配初始化为系统可用资源//扫描所有进程，预设cout<<"";for(j=0;j<n;j++)cout<<Allocation[Sequence[i]][j]+Work[j]<<"";cout<<"";cout<<Finish[Sequence[i]]<<"";// 完成该进程for(j=0;j<n;j++)Work[j]=Allocation[Sequence[i]][j]+Work[j];// 回收该进程所分配的资源cout<<endl;}//while(1)}else //对于未运行的进程，进行如下处理{///for(j=0;j<n;j++)// 找到一个满足 Finish[i]=false 且 Need[i][j]<=Work[j] 的进程{if(Need[i][j]>Work[j])// 由于部分资源得不到满足，}进程 i 无法运行break;}}if(j==n)// 进程各类资源全部得到满足{Finish[i]=True;for(k=0;k<n;k++)// 进程 i 正常运行后, 释放其占有的资源{Work[k]+=Allocation[i][k]; // 工作分配加上可用资源}Sequence[l++]=i; //模拟资源分配序列生成 i=-1;//重新扫描所有进程从 i=0 开始} else{ // 某一资源得不到满足 continue; // 试探下一个进程}}// if(l==m)// 都试探完毕{cout<<"系统安全 !"<<endl; cout<<"安全序列： ";for(i=0;i<l;i++) // 输出安全序列cout<<"进程 P"<<Sequence[i]<<"-->"; cout<<endl;return 0;}}// cout<<"系统进入不安全状态！ "<<endl; return -1;}分析：输入各进程的可利用资源Available ，最大需求MAX已分配资源Allocation ，需求资源Need,之后各系统发出资源请求Request，利用实验中的安全性算法判断能否产生一个安全性队列，若能，则给该进程分配成功，否则，不予分配。