操作系统原理期末实验报告-银行家算法.docx

操作系统原理期末实验报告 银行家算法一、 实验目的在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（deadlyembrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。而最具代表性的避免死锁的算法，便是dijkstra的银行家算法。利用银行家算法，我们可以来检测cpu为进程分配资源的情况，决定cpu是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。此次实验的目的即是为了加深对银行家算法理解。在实践的基础上，把所学知识应用于实际应用，更深刻的理解了银行家算法以及操作系统设计原理的实际应用。二、 实验内容利用c语言以及visual c+ 6.0的编程环境，实现银行家算法，完成以下功能：（1） 添加进程作业；（2） 实现银行家算法，为进程分配资源，并进行安全性检验；（3） 查看当前资源分配情况（4） 撤销进程；三、 总体设计银行家算法是最具代表性的避免死锁的算法。在这个算法中，我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。但在系统进行资源分配之前，应先计算此次资源分配的安全性，即系统能按某种进程顺序为每个进程分配其所需资源，直至满足每个进程对资源的最大需求。若此次分配能使系统处于安全状态，则将资源分配给进程；否则，令进程等待。其具体设计如下：1. 数据结构设计（1） 可利用资源available数组。availablej=m，则表示系统中可用的j类资源有m个。（2） 定义client结构体类型数组：struct clientint maxmaxsize; /进程最大需求资源int allocationmaxsize; /进程已分得资源数int needmaxsize; /进程尚需资源; struct client clientmaxsize； 那么，clienti.maxj表示进程i所需的最大j类资源数； clienti.allocationj表示进程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 - clienti.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.needj，表示进程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;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类资源数超过它所宣布的最大值!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） 定义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获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：workj += clienti.allocationj; /释放资源finishi = true;safesequencetemp+ = i; /加入安全序列之后，再转回步骤（8）；（8） 因为未找到满足步骤（6）的进程，temp不再自增，此时total=temp，循环结束。之后判断temp是否等于n，若temp=n，说明finishi=true都满足，系统处于安全状态，资源分配成功，并输出安全序列safesequencetemp。否则，不存在安全序列，系统处于不安全状态，回收之前试探分配的资源：availablei += requesti;clientp.allocationi -= 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(total != 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） 用户输入需撤销的进程下标，赋值于p；（2） 判断进程p是否存在；（3） 若存在，银行家回收资源，执行availablej+=clientp.allocationj;（4） p之后的进程前移，clienti=clienti+1;（5） clientn-1的需求资源以及分得资源需归零；（6） 进程数减1；（7） 设计流程图图表 4 撤销函数流程图7. 主函数设计图表 5 主函数流程图四、 运行结果以下标的资源分配情况为例：maxallocationneedavailableabcabcabcabcp0753010743332p1322200122p2902302600p3222211011p4433002431（1） 初始化（2） 为进程申请资源a. 资源申请数不合要求b. p1发出请求向量request(1,0,2)查看此时资源占用情况：c. p0发出请求向量request(0,2,0)（3） 新加作业此时资源占用情况：（4） 撤销进程p3此时资源占用情况：五、 实践结果