《操作系统原理期末实验报告-银行家算法.docx》由会员分享，可在线阅读，更多相关《操作系统原理期末实验报告-银行家算法.docx（15页珍藏版）》请在三一文库上搜索。
1、操作系统原理期末实验报告 银行家算法一、 实验目的在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。此次实验的目的即是为了加深对银行家算法理解。在实践的基础上，把所学知识应用于实际应
2、用，更深刻的理解了银行家算法以及操作系统设计原理的实际应用。二、 实验内容利用C语言以及Visual C+ 6.0的编程环境，实现银行家算法，完成以下功能：（1） 添加进程作业；（2） 实现银行家算法，为进程分配资源，并进行安全性检验；（3） 查看当前资源分配情况（4） 撤销进程；三、 总体设计银行家算法是最具代表性的避免死锁的算法。在这个算法中，我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。但在系统进行资源分配之前，应先计算此次资源分配的安全性，即系统能按某种进程顺序为每个进程分配其所需资源，直至满足每个进程对资源
3、的最大需求。若此次分配能使系统处于安全状态，则将资源分配给进程；否则，令进程等待。其具体设计如下：1. 数据结构设计（1） 可利用资源Available数组。Availablej=M，则表示系统中可用的j类资源有M个。（2） 定义client结构体类型数组：struct clientint MaxMAXSIZE; /进程最大需求资源int AllocationMAXSIZE; /进程已分得资源数int NeedMAXSIZE; /进程尚需资源; struct client ClientMAXSIZE； 那么，Clienti.Maxj表示进程i所需的最大j类资源数； Clienti.Alloca
4、tionj表示进程i已分得的j类资源数； Clienti.Needj表示进程i尚需j类资源数。2. 初始化initial()函数设计（1） 用户输入进程数N，以及资源种类数M；（2） 用户输入数据，为Availablej赋值；（3） 用户输入数据，为Clienti.Maxj赋值；（4） 用户输入输入，为Clienti.Allocationj赋值，并判断i进程的已分得j资源数是否大于其对j资源的最大需求，即Clienti.AllocationjClienti.Maxj。若大于，需重新输入；若小于等于，转向步骤（5）；（5） 根据Clienti.Needj = Clienti.Maxj - Cli
5、enti.Allocationj，为Clienti.Needj赋值。（6） 流程图设计如下： 图表 1 initial()函数流程图3. 添加进程add()函数设计（1） 进程数加1；（2） 用户输入新加作业的对j类资源的最大需求数ClientN-1.Maxj；（3） 那么ClientN-1.Needj=ClientN-1.Maxj；ClientN-1.Allocationj=0;4. 银行家算法设计（1） 定义请求向量RequestMAXSIZE;（2） 用户输入请求资源进程的小标p，并检验是否存在该下标；（3） 用户输入数据，初始化请求向量；（4） 如果Requestj Clientp.N
6、eedj，表示进程p所需的j类资源数超过它所宣布的最大值，令flag=0;（5） 如果Requesti Availablei，表示目前尚无足够资源进行分配，进程p需等待，令flag=0;（6） 判断flag是否为0。若不为0，则尝试将资源分配给进程pAvailablei -= Requesti;Clientp.Allocationi += Requesti;Clientp.Needi -= Requesti;若为0，跳出此函数；（7） 执行安全性算法，检查此次资源分配后系统是否处于安全状态。（8） 流程图设计如下：图表 2 银行家算法流程图（9） 算法实现如下： void bid()int p
7、;int flag=1;int RequestMAXSIZE; /请求向量printf(为作业申请资源:n); printf(n);printf(输入请求资源的进程下标:);scanf(%d,&p);if(p=N) printf(不存在进程P%dn,p); return;else /初始化请求向量 printf(进程P%d请求n,p); for(i=0; iM; i+) printf(t%c类资源:,65+i); scanf(%d,&Requesti); /检查Request = Need for(i=0; i Clientp.Needi) printf(t请求的%c类资源数超过它所宣布的最大
8、值!n,65+i); flag=0; /检查Request = Availableif(i = M) for(i=0; i Availablei) printf(t尚无足够%c类资源,P%d须等待!n,65+i,p); flag=0; /试探分配 if(flag) for(i=0; iM; i+) Availablei -= Requesti; Clientp.Allocationi += Requesti; Clientp.Needi -= Requesti; else return;5. 安全性算法设计（1） 定义工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数；（2） 定
9、义Finish数组，它表示系统是否有足够的资源分配给进程，使之运行完成；（3） 定义SafeSequence数组，用以存放安全序列；（4） 初始化Work，Finish向量。Worki = Availablei; Finishi = false;（5） 设计do-while语句，令total!=temp时结束循环。（6） 寻找安全序列：在do-while循环语句中，先令total=temp，之后从进程集合中找到Finishi=false; 且Clienti.Needj=Workj的进程i，若找到则执行步骤（7）；否则，执行步骤（8）；（7） 当进程p获得资源后，可顺利执行，直至完成，并释放出分
10、配给它的资源，故应执行：Workj += Clienti.Allocationj; /释放资源Finishi = true;SafeSequencetemp+ = i; /加入安全序列之后，再转回步骤（8）；（8） 因为未找到满足步骤（6）的进程，temp不再自增，此时total=temp，循环结束。之后判断temp是否等于N，若temp=N，说明Finishi=true都满足，系统处于安全状态，资源分配成功，并输出安全序列SafeSequencetemp。否则，不存在安全序列，系统处于不安全状态，回收之前试探分配的资源：Availablei += Requesti;Clientp.Alloc
11、ationi -= Requesti;Clientp.Needi += Requesti;（9） 设计流程图：图表 3 安全性算法流程图（10） 步骤（5）至部步骤（8）代码实现：do total = temp;for(i=0; iN; i+) if(Finishi = false) for(j=0; j Workj)break;if(j = M) /各类资源都满足Need = Workfor(j=0; jM; j+)Workj += Clienti.Allocationj; /释放资源 Finishi = true;SafeSequencetemp+ = i; /加入安全序列 while(t
12、otal != temp); /找出安全序列if(temp = N) /存在安全序列printf(存在安全序列:);for(temp=0; tempN; temp+)printf(P%d ,SafeSequencetemp); printf(资源分配成功！n);else /不存在安全序列，试探分配作废printf(系统处于不安全状态!不能分配!n);for(i=0; iM; i+)Availablei += Requesti; Clientp.Allocationi -= Requesti; Clientp.Needi += Requesti; 6. 撤销进程destroy()函数设计（1）
13、用户输入需撤销的进程下标，赋值于p；（2） 判断进程p是否存在；（3） 若存在，银行家回收资源，执行Availablej+=Clientp.Allocationj;（4） P之后的进程前移，Clienti=Clienti+1;（5） ClientN-1的需求资源以及分得资源需归零；（6） 进程数减1；（7） 设计流程图图表 4 撤销函数流程图7. 主函数设计图表 5 主函数流程图四、 运行结果以下标的资源分配情况为例：MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P443
14、3002431（1） 初始化（2） 为进程申请资源a. 资源申请数不合要求b. P1发出请求向量Request(1,0,2)查看此时资源占用情况：c. P0发出请求向量Request(0,2,0)（3） 新加作业此时资源占用情况：（4） 撤销进程P3此时资源占用情况：五、 实践结果分析此次实验，较成功的完成了银行家算法的实现，达到了实验目的，完成了实验内容。其中，资源分配以及系统安全性检验的算法主要由bid（）函数实现，另外，add（）、view（）、destroy（）函数又分别实现了添加进程、查看资源、撤销进程的功能，使整个设计更为全面、完善。通过银行家算法，我们可以在资源动态分配的过程中来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。