银行家算法操作系统.docx

《银行家算法操作系统.docx》由会员分享，可在线阅读，更多相关《银行家算法操作系统.docx（19页珍藏版）》请在三一办公上搜索。

1、课程设计（论文）任务书 信息工程 学院 计算机专业 3 班 一、课程设计(论文)题目资源管理系统的设计与实现银行家算法实现二、课程设计(论文)工作自 2008 年 6 月 23 日起至 2008 年 6 月 28 日止。三、课程设计(论文) 地点: 5#204 四、课程设计(论文)内容要求：1本课程设计的目 配合计算机操作系统课程的教学，通过模拟操作系统原理的实现，使学生能更深刻地领会操作系统工作原理和操作系统实现方法的理解，并可练习程序设计， 特开设此课程设计。 2课程设计的任务及要求1）基本要求：用你熟悉语言编程实现一个资源管理系统，该系统必须包括资源的添加、删除和修改等功能，并且允许其它

2、进程来申请这里的资源，任何一个进程来申请资源时，必须先登记该进程对资源的申请要求，然后由系统检查当前资源的状况，并用银行家算法和安全性算法来检查是否允许分配资源给进程。每个进程申请资源的情况必须进行记录，并作为课程设计报告的一部分数据。2）创新要求： 在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面等。3）课程设计论文编写要求（1）要按照书稿的规格打印与写课程设计论文 （2）论文包括目录、功能描述、设计思路、具体实现、运行调试与分析讨论、设计体会与小结、参考文献、附录（源代码）等 （3）课程设计论文装订按学校的统一要求完成4）答辩与评分标准： （1）考勤与学习态度：20分； （

3、2）设计思路：20分；（3）代码实现：20分；（4）调试与分析：20分；（5）回答问题：10分；（6）论文规范性：10分。5）参考文献1汤子瀛，哲凤屏，汤小丹.计算机操作系统.西安电子科技大学出版社2谭浩强 C程序设计（第三版） 清华大学出版社3 6）课程设计进度安排内容 天数地点 1天 5#204 1天 5#204 1天 5#204学生签名： 2008年 6 月 28 日课程设计(论文)评审意见（1）考勤与态度 （20分）：优（）、良（）、中（）、一般（）、差（）； （2）设计思路（20分）：优（）、良（）、中（）、一般（）、差（）； （3）代码实现（20分）：优（）、良（）、中（）、一般（

4、）、差（）；（4）调试与分析（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（10分）：优（）、良（）、中（）、一般（）、差（）；（6）论文规范性 （10分）：优（）、良（）、中（）、一般（）、差（）；评阅人： 职称： 讲师 2008 年6月30日目 录绪 论- 3 -一、功能描述- 3 -二、设计思路- 3 -2.1银行家算法中的数据结构- 3 -2.2银行家算法- 3 -2.3安全性算法错误！未定义书签。三、具体实现- 3 -3.1实现过程错误！未定义书签。3.2流程图错误！未定义书签。四、运行调试及结果分析- 3 -五、设计体会与小结- 3 -六、参考文献- 3 -七

5、、附录(源代码)- 3 -绪 论这次课程设计要求完成一个资源管理系统，该系统必须包括资源的添加、删除和修改等功能，并且允许其它进程来申请这里的资源，任何一个进程来申请资源时，必须先登记该进程对资源的申请要求，然后由系统检查当前资源的状况，并用银行家算法和安全性算法来检查是否允许分配资源给进程。通过课程设计，加深我们对利用银行家算法避免死锁的理解。在设计中主要的难点是用语言编写银行家算法和安全性算法，使系统资源分配能安全进行，避免系统死锁。具体要求如下：（1）模拟一个银行家算法；（2）初始化时让系统拥有一定的资源；（3）如果预分配后，系统处于安全状态，则修改系统的资源分况；（4）如果预分配后，系

6、统处于不安全状态，则提示不能满足请求， 此次课程设计的主要内容时模拟实现动态资源分配。同时要求编写和调试一个系统动态资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。一、 功能描述在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用提高吞吐量，但可能发生一种危险死锁。所谓死锁，是指多个进程运行中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都无法再向前推进。虽然进程在运行过程中，可能发生死锁，但死锁的发生必须同时具备四个条件：互斥条件、请求和保持条件、不剥夺条件、环路等待条件；防止死锁的机构只须确保上述四个条件之一不

7、出现，则系统不会发生死锁。系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，便可避免死锁。所谓安全状态，是指系统能按某种进程顺序（P1，P2，Pn），来为每个进程Pi分配其所需分配，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到一个这样地安全系列，则称系统处于不安全状态。在操作系统中研究资源分配策略时也有类似的问题，系统中有限的资源要供多个进程使用，必须保证得到资源的进程能在有限的时间内归还资源，以供它进程使用资源。如果资源分配不得当就会发生进程循环等待资源，各进程都无法继续执行下去的死锁现象。而最有代表性的避免死锁的算法，是Dijkstra的银行家

8、算法。 银行家算法是避免死锁的一种重要方法，在课程设计中用C语言编写一个资源管理系统，并要用银行家算法和安全性算法检查是否允许分配资源给进程，避免死锁。通过课程设计，加深我们对了解有关资源申请、避免死锁等概念，并加深我们对银行家算法理解。提高了我们分析、解决问题的能力。二、 设计思路在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。银行家算法是避免死锁的一种重要方法，为实现银行家算法，系统必须设置若干数据结构。2.1银行家算法中的数据结构 1）可利用资源向量Available是个含有m个元素的数组

9、，其中的每一个元素代表一类可利用的资源数目。如果Availablej=K，则表示系统中现有Rj类资源K个。 2）最大需求矩阵Max这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。3）分配矩阵Allocation这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。4）需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方

10、能完成其任务。 Needi,j=Maxi,j-Allocationi,j 2.2、银行家算法设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布最大值。1）如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 2）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej=Availablej-Requestij;Allocati

11、oni,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;3）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。2.3、安全性算法1）设置两个向量：工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; 工作向量Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足

12、够资源分配给进程时， 再令Finishi=true。 2）从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj；若找到，执行 (3)，否则，执行 (4)3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Worki+Allocationi,j;Finishi=true;go to step 2; 4）如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态三、 具体实现3.1、实现过程在程序中设计五个进程，分别为pr0,pr1,pr2,pr3,pr4。共享三类资源。在

13、这个资源管理系统中对进程的所需最大资源(Max)、已分配给当前进程资源(Allocation)和系统可用资源(Available)分别进行了初始化了值。进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列，若分配不安全，则释放分配的资源，防止使系统进入不安全状态。显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。程序还可以实现对系统的修改。如果修改系统可用资源(Available)，和进程分配资源。程序具体的设计是：函数void showdata()用来显示资源矩阵，包括系统可用资源数目，进程对资

14、源最大需求数，系统已分配给进程的资源数，进程还需求资源。通过以上显示，很直观的观察到资源分配和修改的过程。函数share()用来利用银行家算法对某个进程申请资源对进行判定。函数int changdata(int i)用来实现资源试探分配。主要执行的步骤是 ： Avaliablej=Avaliablej-Requestj；Allocationij=Allocationij+Requestj；Needij=Needij-Requestj。函数safe()用来实现安全性算法，对分配后的资源进行计算，若分配资源后，系统是安全的，则资源完成本次分配。若不安全将本次的试探分配作废，调用shifang()函

15、数恢复原来的资源分配状态。资源修改功能用 Revision()来实现。 3.2流程图四、 运行调试及结果分析为了便于检验程序的正确性，这里用了书上的数据进行了初始化。程序运行时选择1 ,输入进程pr1的请求向量（1,0,2）经过程序计算，资源分配成功。资源具体分配过程如下图所示。得出一个安全序列为pr1,pr3,pr0,pr2,pr4。这与书上的有点不同，但经过计算，这也是一个正确的安全序列。对进程提出的请求向量，系统可能存在多个安全序列。主要是在安全路径的找算法上。进程pr0请求资源：pr0发出请求向量(0,2,0)，由于Request0不大于Need0,Request0不大于Availab

16、le0。系统试探着为它分配资源。由结果可知，系统不安全。则系统不分配资源，并回收系统预分配给pr0的资源。程序运行时选择2,进行系统资源的修改。这里选择修改系统可用资源。修改后的Available为(2,3,2)。资源修改成功。五、 设计体会与小结一周的操作系统课程设计终于结束了，虽然很忙碌很疲劳，但感觉收获还是蛮大的。我几乎每天的专注和辛劳，唤回了我对操作系统的重新的认识，在编写程序不断出现错误和改正的过程序中加深了我对银行家算法的理解。这个系统的功能基本能满足要求，完成了对资源的修改还有用银行家算法和安全性算法来检查是否允许分配资源给进程。在课程设计的过程中，通过与同组人的相互讨论，很多问

17、题迎刃而解。让我从中体会到是小组合作的力量。设计主要由两部分组成：第一部分:银行家算法(扫描)1.如果Request=Need,则转向2;否则,出错2.如果Request=Available,则转向3,否则等待3.系统试探分配请求的资源给进程4.系统执行安全性算法安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目) (2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False 2.若Finishi=False&Need=Work,则执行3;否则执行4(I为资源类别) 3.进程

18、P获得第i类资源,则顺利执行直至完成!并释放资源: Work=Work+Allocation; Finishi=true; 转2 4. 若所有进程的Finishi=true,则表示系统安全;否则,不安全!第二部分主要是进行资源的修改。在这里可以修改资源的可用资源和资源还需求资源。由于时间有限，还不是很完善，系统还有许多不尽人意的地方。这些都有待进一步改善六、 参考文献1汤子瀛，哲凤屏，汤小丹.计算机操作系统.西安：西安电子科技大学出版社，20052 谭浩强 C程序设计（第三版） 清华大学出版社3 七、 附录(源代码)#include#include#define M 5 /定义进程数 #def

19、ine N 3 /定义资源数 #define False 0#define True 1int Max3=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;int Avaliable=3,3,2; /系统可用资源int Allocation3=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2;/系统已分配资源int Need3=7,4,3,1,2,2,6,0,0,0,1,1,4,3,1;/还需要资源int Request3;void showdata()/显示资源矩阵 int i,j; printf(系统可用的资源:n); printf(resouce:); for (j=

20、0;jN;j+) printf(%d,Avaliablej);/输出分配资源 printf(n); printf(各进程的资源需求:n); for (i=0;iM;i+) printf(pr%d: ,i); for (j=0;jN;j+) printf(%d,Maxij);/输出最大需求资源数 printf(n); printf(各进程得到资源:n); for (i=0;iM;i+) printf(pr%d: ,i); for (j=0;jN;j+) printf(%d,Allocationij);/输出已分配资源数 printf(n); printf(各进程还需求资源:n); for (i=

21、0;iM;i+) printf(pr%d: ,i); for(j=0;jN;j+) printf(%d,Needij);/输出还需要资源数 printf(n); int changdata(int i)/进行资源分配 int j; for (j=0;jM;j+) Avaliablej=Avaliablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj; return 1;int chkerr()/安全性算法 int Work3,FinishM=0,tempM; int i,k=0,m,apply; in

22、t j; Work0=Avaliable0; Work1=Avaliable1; Work2=Avaliable2; for(i=0;iM;i+) apply=0;for(j=0;j3;j+)if (Finishi=False&Needij=Workj) apply+;if(apply=3)for(m=0;m3;m+)Workm=Workm+Allocationim;/变分配数Finishi=True;tempk=i;i=-1; k+; else if(Finishi=False) if(i=M-1) printf(系统不安全n);/不成功系统不安全 return -1; break; pri

23、ntf(系统资源分配成功!);/如果安全，输出成功 printf(分配的序列:n); for(i=0;iM;i+)/输出运行进程数组 printf(pr%d ,tempi);return 0;void share()/利用银行家算法对申请资源对进行判定char ch;int i=0,j=0;ch=y;printf(n请输入要求分配的资源进程号从(0 to 4):); scanf(%d,&i);/输入须申请的资源号 printf(请输入进程 %d 申请的资源:n,i);for(j=0;j3;j+)printf(第 %d 个资源:,j+1);scanf(%d,&Requestj);/输入需要申请的

24、资源 for (j=0;jNeedij)/判断申请是否大于需求，若大于则出错 printf(进程 %d 申请的资源大于它需要的资源,i); printf( error!n); ch=n; break; else if(RequestjAvaliablej)/判断申请是否大于当前资源，若大于则 /出错printf(进程 %d 申请的资源大于available,i); printf( error!n); ch=n; break; if(ch=y) changdata(i);/根据进程需求量变换资源 showdata();/根据进程需求量显示变换后的资源 chkerr();/根据进程需求量进行银行家

25、算法判断 void Revision()printf(请选择: 1：修改进程还需要的资源 2：修改进程可用资源);int choice1;scanf(%d,&choice1); if(choice1=1)printf(输入要修改的资源号(04);int p; scanf(%d,&p);printf(输入修改后进程还需要的资源(1,1,1)n);scanf(%d,%d,%d,&Needp0,&Needp1,&Needp2); printf(经修改后各进程还需求资源:n); for (int a=0;aM;a+) printf(pr%d:,a); for(int b=0;bN;b+) printf

26、(%d, ,Needab);/输出还需要资源数 printf(n); if(choice1=2)printf(输入系统可用资源EX(1,1,1)n);scanf(%d,%d,%d,&Avaliable0,&Avaliable1,&Avaliable2);printf(经修改后的系统可用资源为n); for (int k=0;kN;k+) printf(%d,Avaliablek);int main()/主函数printf(*银行家算法演示*n);printf(*曾金路&雍虎*n); int choice; showdata();/显示各种资源 chkerr();/用银行家算法判定系统是否安全 do printf(n输入要进行的操作 1：分配资源 2： 修改资源 3：离开); scanf(%d,&choice); if(choice=1) share(); if(choice=2) Revision(); if(choice=3) break; while(choice=1)|(choice=2); return 1;