2022年操作系统实验二-银行家算法 .pdf

操作系统实验二银行家算法1 实验二银行家算法一、实验目的 : 运用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因， 并采用银行家算法有效地避免死锁的发生，以加深对课堂上所讲授的知识的理解。二、实验内容：完成银行家算法的模拟实现： 设计有 m 个进程共享 n个系统资源的系统， 进程可动态的申请和释放资源。 系统按各进程的申请动态的分配资源时，采用银行家算法有效地避免死锁的发生。三、实验准备：1. 相关理论知识：（1）银行家算法的思路对进程的资源请求进行合法性检查； 若请求合法，则进行试分配。试分配后，调用安全性检查算法进行安全性检查。若安全，则满足该进程请求，分配资源；若不安全，则拒绝该进程申请，不分配资源，并恢复系统试分配前的资源状态。（2）银行家算法中用到的主要数据结构可利用资源向量 int Availablej / j为资源的种类。最大需求矩阵 int Maxij / i为进程的数量。分配矩阵 int Allocationij 需求矩阵 int Needij= Maxij- Allocationij 申请各类资源数量 int Requestij /i进程申请 j 资源的数量工作向量 int Workx int Finishy （3）银行家算法 Bank() 进程i 发出请求申请 k个j 资源， Requestij=k 检查申请量是否小于等于需求量：Requestij=Needi,j,若条件不符重新输入，不允许申请大于需求量。 检查申请量是否小于等于系统中的可利用资源量：Requestij=Availablej，若条件不符就申请失败， 阻塞该进程， 用goto语句跳转至重新申请资源。 若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：Availablej= Availablej- Requestij；Allocationij= Allocationij+ Requestij；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法2 Needij= Needij- Request ij； 试分配后，执行安全性检查，调用Safe() 函数检查此次资源分配后系统是否处于安全状态。 若安全，才正式将资源分配给进程； 否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。 用while 循环实现输入字符 Y/y判断是否继续请求资源分配。（4）安全性检查算法（ Safe() 函数） 设置两个向量：工作向量 Work：表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，令Work= Available。Finish ：表示系统是否有足够的资源分配给进程，使之运行完成。 开始时先做Finishi=false；当有足够的资源分配给进程时，再令Finishi=true。 在进程集合中查找符合以下条件的进程：条件 1：Finishi=0 条件 2：Needij=Workj 若找到，则执行步骤；否则，执行步骤 当进程获得资源后， 可顺利执行， 直至完成， 并释放出分配给它的资源，故应执行：Workj= Workj+ Allocationij Finishi=true 跳至 若所有进程的 Finishi=true都满足，则表示已找到安全序列，系统处于安全状态，试分配成功；否则，系统处于不安全状态，不予分配。2. 测试数据：系统有 5 个进程（ p0,p1,p2,p3,p4）和 4 类资源（ A，B，C ，D ），在 T0时刻的资源分配情况如下表所示：（课本 P115 22）Process Max Allocation Need Available P0 0 0 4 4 0 0 3 2 0 0 1 2 1 6 2 2 P1 2 7 5 0 1 0 0 0 1 7 5 0 P2 3 6 10 10 1 3 5 4 2 3 5 6 P3 0 9 8 4 0 3 3 2 0 6 5 2 P4 0 6 6 10 0 0 1 4 0 6 5 6 试问： （1）该状态是否安全？（2）如果进程 P2提出请求 Request2（1，2，2，2）后，系统能否将资源分配给它？四、实验过程：1.流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法3 系统安全吗？N 开 始输入进程数目m 输入资源种类数n， 及各进程对各类资源的最大需求量Max 和已分配到的资源量Allocation 调用安全性算法输入系统可用资源数Available初始化 need 矩阵Y Y N N 输入进程 i 的资源请求量Requestij Request ij=needi,jY Request ij=Availablei,j资源试分配：Availablej= Availablej- Requestij；Allocationij= Allocationij+ Requestij ；Needij= Needij- Request ij；调用安全性算法系统安全吗？N 撤销资源试分配： 修改Availablej Allocationij Needij值Y 是否继续请求资源分配？Y 结束N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法4 2. 源代码#include #include #include #define False 0 #define True 1 int Max100100=0;/各进程所需各类资源的最大需求int Avaliable100=0;/ 系统可用资源char name100=0;/ 资源的名称int Allocation100100=0;/系统已分配资源int Need100100=0;/ 还需要资源int Request100=0;/ 请求资源向量int temp100=0;/ 存放安全序列int Work100=0;/ 存放系统可提供资源int M=100;/作业的最大数为 100 int N=100;/资源的最大数为100 void showdata()/显示资源矩阵 int i,j; cout系统目前可用的资源 Avaliable:endl; for(i=0;iN;i+) coutnamei ; coutendl; for (j=0;jN;j+) coutAvaliablej ;/ 输出分配资源coutendl; cout Max Allocation Needendl; cout进程名; for(j=0;j3;j+) for(i=0;iN;i+) coutnamei ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法5 cout ; coutendl; for(i=0;iM;i+) cout i ; for(j=0;jN;j+) coutMaxij ; cout ; for(j=0;jN;j+) coutAllocationij ; cout ; for(j=0;jN;j+) coutNeedij ; coutendl; int changdata(int i)/进行资源分配 int j; for (j=0;jM;j+) Avaliablej=Avaliablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj; return 1; int safe()/安全性算法 int i,k=0,m,apply,Finish100=0; int j; int flag=0; Work0=Avaliable0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法6 Work1=Avaliable1; Work2=Avaliable2; for(i=0;iM;i+) apply=0; for(j=0;jN;j+) if (Finishi=False&Needij=Workj) apply+; if(apply=N) for(m=0;mN;m+) Workm=Workm+Allocationim;/变分配数Finishi=True; tempk=i; i=-1; k+; flag+; for(i=0;iM;i+) if(Finishi=False) cout系统不安全 endl;/不成功系统不安全return -1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法7 cout系统是安全的 !endl;/ 如果安全，输出成功cout分配的序列 :; for(i=0;iM;i+)/ 输出运行进程数组couttempi; if(iM-1) cout; coutendl; return 0; void share()/利用银行家算法对申请资源对进行判定 char ch; int i=0,j=0; ch=y; cout请输入要求分配的资源进程号(0-M-1i;/ 输入须申请的资源号cout请输入进程i 申请的资源:endl; for(j=0;jN;j+) coutnamejRequestj;/输入需要申请的资源 for (j=0;jNeedij)/ 判断申请是否大于需求，若大于则出错 cout进程 i 申请的资源大于它需要的资源; cout 分配不合理，不予分配！Avaliablej)/ 判断申请是否大于当前资源，若大于则 /出错cout进程 i 申请的资源大于系统现在可利用的资源; cout 分配出错，不予分配 !endl; ch=n; break; if(ch=y) changdata(i);/根据进程需求量变换资源showdata();/ 根据进程需求量显示变换后的资源safe();/根据进程需求量进行银行家算法判断 void addresources()/添加资源int n,flag; coutn; flag=N; N=N+n; for(int i=0;in;i+) coutnameflag; coutAvaliableflag+; showdata(); safe(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法9 void delresources()/删除资源char ming; int i,flag=1; coutming; for(i=0;iN;i+) if(ming=namei) flag=0; break; if(i=N) cout该资源名称不存在，请重新输入：; while(flag); for(int j=i;jN-1;j+) namej=namej+1; Avaliablej=Avaliablej+1; N=N-1; showdata(); safe(); void changeresources()/ 修改资源函数cout系统目前可用的资源 Avaliable:endl; for(int i=0;iN;i+) coutnamei:Avaliableiendl; cout 输 入 系 统 可 用 资 源Avaliable:Avaliable0Avaliable1Avaliable2; cout经修改后的系统可用资源为endl; for (int k=0;kN;k+) coutnamek:Avaliablekendl; showdata(); safe(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法10 void addprocess()/添加作业int flag=M; M=M+1; cout请输入该作业的最打需求量Maxendl; for(int i=0;iN;i+) coutnameiMaxflagi; Needflagi=Maxflagi-Allocationflagi; showdata(); safe(); int main()/主函数 int i,j,number,choice,m,n,flag; char ming; cout*单处理机系统进程调度实现*endl; coutn; N=n; for(i=0;in;i+) cout资源i+1ming; namei=ming; coutnumber; Avaliablei=number; coutendl; coutm; M=m; cout 请 输 入 各 进 程 的 最 大 需 求 量 (m*n 矩 阵 )Max:endl; for(i=0;im;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法11 for(j=0;jMaxij; do flag=0; cout 请 输 入 各 进 程 已 经 申 请 的 资 源 量 (m*n矩阵)Allocation:endl; for(i=0;im;i+) for(j=0;jAllocationij; if(AllocationijMaxij) flag=1; Needij=Maxij-Allocationij; if(flag) cout申请的资源大于最大需求量，请重新输入!n; while(flag); showdata();/显示各种资源safe();/用银行家算法判定系统是否安全while(choice) cout*银行家算法演示 *endl; cout 1:增加资源endl; cout 2:删除资源endl; cout 3:修改资源endl; cout 4:分配资源endl; cout 5:增加作业endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法12 cout 0:离开endl; cout*endl; coutchoice; switch(choice) case 1: addresources();break; case 2: delresources();break; case 3: changeresources();break; case 4: share();break; case 5: addprocess();break; case 0: choice=0;break; default: cout请正确选择功能号 (0-5)!endl;break; return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法13 3. 运行界面：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 操作系统实验二银行家算法14 五、实验心得：通过本次实验， 我知道了可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金， 进程向操作系统请求分配资源相当于用户向银行家贷款。多个进程同时运行时， 系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列， 使得系统能快速且安全地运行进程， 不至发生死锁。银行家算法是避免死锁的主要方法， 其思路在很多方面都非常值得我们来学习借鉴。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -