操作系统实验_银行家算法.doc

学号P71514032 专业计算机科学与技术 姓名 实验日期2017.11.9 教师签字 成绩实验报告【实验名称】银行家算法【实验目的】掌握银行家算法，用银行家算法模拟操作系统避免死锁的方法【实验原理】银行家算法又称“资源分配拒绝”法，其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处于安全状态，可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待用C语言编写一个简单的银行家算法模拟程序，用银行家算法实现资源分配。程序能模拟多个进程共享多种资源的情形。进程可动态地申请资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况【数据结构和符号说明】可利用资源向量Available最大需求矩阵Max分配矩阵Allocation需求矩阵Need工作向量Work标记向量Finishchar name10010;/定义最大100个进程，每个大小为10int Max100100; /定义int Allocation100100;/可利用资源向量资源数int Need100100; /需求矩阵int avaiable100; /系统可利用资源int avaiable1100;int state100; /进程状态数组char name110010;/进程名int bigger; ;/是否大于int N; /进程数int n; /资源数int counter;函数：void Input()/输入函数void Init()/初始化void output()/输出安全序列或等待void insert_pcb()/请求进程或更新进程void show()/显示界面与选择int CmpRequestAvailable(int Pos,int n)/比较Request和Available的大小int CmpRequestNeed(int Pos,int n)/比较Request和Need的大小void Reset(int n,int Pos)/更新request之后的Need，Allocation，Available的值void Banker()/银行家算法【实验流程图及算法实现】用C语言编写一个简单的银行家算法模拟程序，用银行家算法实现资源分配。程序能模拟多个进程共享多种资源的情形。进程可动态地申请资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况【流程图】代码：#includeusing namespace std;char name10010;定义最大100个进程，每个大小为10int Max100100; /定义int Allocation100100;/可利用资源向量资源数int Need100100; /需求矩阵int avaiable100; /int state100; /进程状态数组int dayu; ;是否大于int N;int n;void input () cout输入进程个数N; cout输入资源个数n; cout系统现有的各资源的个数endl; for(int i=0; iavaiablei; for(int i=0; iN; i+)/输入 cout输入第i个进程的名字namei; cout输入第i所需要各进程的最大资源数endl; for(int j=0; jMaxij; cout输入第i现在所拥有的资源个数endl; for(int j=0; jAllocationij; statei=0; for(int i=0; iN; i+)for(int j=0; jn; j+) /寻找需求矩阵 Needij=Maxij-Allocationij;void yinhangjia() int i,j,k; for( i=0; iN; i+) for( j=0; jN; j+) if(statej=1) continue; dayu=0; for( k=0; k=Needjk) dayu=1; else dayu=0; break; if(dayu=1)/判断状态 statej=1; coutnamejendl; for(int m=0; mn; m+) avaiablem+=Allocationjm; break; int main()input();/输入yinhangjia();截图：带有resquest请求更新的银行家算法：描述：1）如果Requesti是进程Pi的请求向量，如果Requesti，j=K,表示进程Pi需要K个Rj类型的资源。当发出资源请求后，系统按下述步骤进行检查：如果Requestij=Needi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。2）如果Requestij=Availablej,便转向步骤3，否则，表示尚无足够资源，进程Pi须等待。3）系统试探着把资源分配给进程，并修改下面数据结构中的数值。4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进i，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程等待。流程图：代码：#include#includeusing namespace std;char name10010;/定义最大100个进程，每个大小为10int Max100100; /定义int Allocation100100;/可利用资源向量资源数int Need100100; /需求矩阵int avaiable100; /int avaiable1100;int state100; /进程状态数组char name110010;int bigger; ;/是否大于int N;int n;int counter;void input ()/输入函数 cout输入进程个数N; cout输入资源个数n; cout系统现有的各资源的个数endl; for(int i=0; iavaiablei; avaiable1i=avaiablei; for(int i=0; iN; i+)/输入 cout输入第i+1个进程的名字namei; cout输入第i+1所需要各进程的最大资源数endl; for(int j=0; jMaxij; cout输入第i+1现在所拥有的资源个数endl; for(int j=0; jAllocationij; statei=0; for(int i=0; iN; i+) for(int j=0; jn; j+) /寻找需求矩阵 Needij=Maxij-Allocationij;void Banker()/银行家算法 int i,j,k; counter=0; for(i=0; iN; i+) statei=0; for( i=0; iN; i+)/循环次数 for( j=0; jN; j+)/每次从头越查找 if(statej=1) continue; bigger=0; for( k=0; k=Needjk)/每一个大于需求 bigger =1; else bigger=0; break;/跳出需求循环 if( bigger=1)/判断状态，此时该进程所有need= avaiable statej=1; strcpy(name1counter+,namej); for(k=0; kn; k+) avaiablek+=Allocationjk;/更新avaiable向量 break; void output()/输出安全序列或等待 int i; if (counter=N) cout安全序列为:; for(i=0; iN-1; i+) cout name1i ; cout nameiendlendl; else cout不存在安全序列,插入失败endl;void insert_pcb()/请求进程或更新进程 char name110; int choose; int add100; cout1、增加新的进程endl; cout2、对原有进程增加资源申请choose; if(choose=1) int bigger=0; cout输入插入进程的名字nameN; cout输入该进程拥有的资源个数endl; for(int j=0; jAllocationNj; stateN=0; cout输入该所需要各资源最大数目endl; for(int j=0; jMaxNj; NeedNj=MaxNj-AllocationNj; stateN=0; for( int k=0; k=NeedNk)/每一个大于需求 bigger =1; else bigger=0; break;/跳出需求循环 if(bigger=1) cout插入成功endl; N=N+1; Banker(); output(); else cout插入失败，进程等待！endl; else int pos;/找到需更新进程的位置 cout输入原有进程的名字name110; for(int i=0; iN; i+) if(!strcmp(name1,namei) pos=i; break; cout输入该进程还需要的各资源数endl; for(int j=0; jaddj; for( int k=0; k=addk)/每一个大于需求 bigger =1; else bigger=0; break;/跳出需求循环 if(bigger=1) cout插入成功endl; for(int m=0; mn; m+) Maxposm+=addm; Needposm+=addm; avaiablem=avaiable1m; Banker(); output(); else cout插入失败，进程等待！endl; void show()/显示界面与选择 int i,j; coutendl*最大需求矩阵*endl; cout进程名t; for(i=0; in; i+) coutmaxit; coutendl; for(i=0; iN; i+) coutnameit; for(j=0; jn; j+) coutMaxijt; coutendl; cout*endlendl; cout*各进程已有资源数*endl; cout进程名t; for(i=0; in; i+) coutAllocationit; coutendl; for(i=0; iN; i+) coutnameitt; for(j=0; jn; j+) coutAllocationijtt; coutendl; cout*endlendl; cout*各进程需求资源数*endl; cout进程名t; for(i=0; in; i+) cout Needit; coutendl; for(i=0; iN; i+) coutnameitt; for(j=0; jn; j+) cout Needijtt; coutendl; cout*endlendl;int main() int select; cout银行家算法endl; cout初始化endl; input();/输入 show(); Banker(); output(); do cout1、更新endl; cout2、查看各进程的信息endl; cout3、结束select; if(select=3) break; else if(select=1) insert_pcb(); else show(); while(1);截图：输入资源种类数目，输入最大需求矩阵，输入分配矩阵，输入可用资源数目，得到安全序列对进程P1进行请求，此时会形成一个新的安全序列,p1进程的need和max发生相应的变化。继续修改进程4，插入各需求3 3 0，不存在安全序列，此时需要等待。请求一个新进程，所需求的最大资源为3 3 4，现有为2 2 3，形成新的安全序列。查看各进程信息，并输出安全序列。再请求一个新的大进程，此时资源不足，需要等待。资源数为4：更新P1进程，程序阻塞，进程等待。请求一个新进程，P5。插入成功，此时有安全序列。【小结或讨论】1、银行家算法名字源于该算法实际上是用于确保银行系统不会用尽系统资源，因为当银行系统不再满足所有客户的需求，系统将不会分配钱（看作资源）给客户，银行必须确保对钱的请求不会导致银行系统处于不安全状态。如果上述情况不会发生，则该情况下请求是被允许的，否则，客户必须等到其他客户往银行存进足够银行分配的资金。2、银行家算法就是当接收到一个系统资源的分配后找到一个安全序列，使得进程间不会发生死锁，若发生死锁则让进程等待。这次实验的核心问题在于试探分配，若试探分配得到的结果是系统不安全则分配作废，恢复原先资源分配状态，转而寻找其他可能的安全序列，