银行家算法.doc

综合实践2（操作系统）实践报告题目：银行家算法班级: 计本057班姓名: 周薇 学号： 2005021182 指导教师：杜鹃 2007年12月综合实践2评分表班级计本057姓名周薇指导教师杜鹃题目：银行家算法评分标准评分标准分数权重评分的依据得分AC选题10选题符合大纲要求，题目较新颖，工作量大选题基本符合大纲要求，工作量适中工作态度10态度端正，能主动认真完成各个环节的工作，不迟到早退，出勤好。能够完成各环节基本工作，出勤较好。存储结构、算法描述20能正确选择存储结构，定义准确，算法流程图或类C语言描述的算法准确无误能正确选择存储结构，算法流程图或类C语言描述的算法基本准确独立解决问题的能力10具有独立分析、解决问题能力，有一定的创造性，能够独立完成软件的设计与调试工作，程序结构清晰，逻辑严谨，功能完善。有一定的分析、解决问题能力。能够在老师指导下完成软件的设计与调试工作，程序功能较完善。答辨问题回答20能准确回答老师提出的问题能基本准确回答老师提出的问题程序运行情况10程序运行正确、界面清晰，测试数据设计合理。程序运行正确、界面较清晰，能给出合适的测试数据。综合实践报告20格式规范，层次清晰，设计思想明确，解决问题方法合理，体会深刻。格式较规范，设计思想基本明确，解决问题方法较合理。总分指导教师（签字）：注：介于A和C之间为B级，低于C为D级和E级。按各项指标打分后，总分在90100为优，8089为良，7079为中，6069为及格，60分以下为不及格。目录一.绪论2二.设计目的3三.设计要求4四.原理分析44.1、银行家算法中的数据结构44.2、银行家算法54.3、安全性算法5五.具体设计和程序流程图6七.程序调试和程序实现7六.程序源代码9七.程序调试和程序实现7八.设计小结15九.谢辞16十.参考文献16一.绪论这次课程设计要求完成一个资源管理系统，该系统必须包括资源的添加、删除和修改等功能，并且允许其它进程来申请这里的资源，任何一个进程来申请资源时，必须先登记该进程对资源的申请要求，然后由系统检查当前资源的状况，并用银行家算法和安全性算法来检查是否允许分配资源给进程。通过课程设计，加深我们对利用银行家算法避免死锁的理解。在设计中主要的难点是用语言编写银行家算法和安全性算法，使系统资源分配能安全进行，避免系统死锁。二.设计目的在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用提高吞吐量，但可能发生一种危险死锁。所谓死锁，是指多个进程运行中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都无法再向前推进。虽然进程在运行过程中，可能发生死锁，但死锁的发生必须同时具备四个条件：互斥条件、请求和保持条件、不剥夺条件、环路等待条件；防止死锁的机构只须确保上述四个条件之一不出现，则系统不会发生死锁。系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，便可避免死锁。所谓安全状态，是指系统能按某种进程顺序（P1，P2，Pn），来为每个进程Pi分配其所需分配，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到一个这样地安全系列，则称系统处于不安全状态。在操作系统中研究资源分配策略时也有类似的问题，系统中有限的资源要供多个进程使用，必须保证得到资源的进程能在有限的时间内归还资源，以供它进程使用资源。如果资源分配不得当就会发生进程循环等待资源，各进程都无法继续执行下去的死锁现象。而最有代表性的避免死锁的算法，是Dijkstra的银行家算法。 银行家算法是避免死锁的一种重要方法，在课程设计中用C语言编写一个资源管理系统，并要用银行家算法和安全性算法检查是否允许分配资源给进程，避免死锁。通过课程设计，加深我们对了解有关资源申请、避免死锁等概念，并加深我们对银行家算法理解。提高了我们分析、解决问题的能力。三.设计要求用所学过的语言编程实现一个资源管理系统，该系统必须包括资源的添加、删除和修改等功能，并且允许其它进程来申请这里的资源，任何一个进程来申请资源时，必须先登记该进程对资源的申请要求，然后由系统检查当前资源的状况，并用银行家算法和安全性算法来检查是否允许分配资源给进程。四.原理分析在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。银行家算法是避免死锁的一种重要方法，为实现银行家算法，系统必须设置若干数据结构。4.1、银行家算法中的数据结构 1）可利用资源向量Available是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果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个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j 4.2、银行家算法设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布最大值。1）如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 2）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej=Availablej-Requestij;Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;3）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。4.3、安全性算法1）设置两个向量：工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; 工作向量Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。 2）从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj；若找到，执行 (3)，否则，执行 (4)3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Worki+Allocationi,j;Finishi=true;go to step 2; 4）如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态五.具体设计和程序流程图在程序中设计五个进程，分别为pr0,pr1,pr2,pr3,pr4。共享三类资源。在这个资源管理系统中对进程的所需最大资源(Max)、已分配给当前进程资源(Allocation)和系统可用资源(Available)分别进行了初始化了值。进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列，若分配不安全，则释放分配的资源，防止使系统进入不安全状态。显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。程序还可以实现对系统的修改。如果修改系统可用资源(Available)，和进程分配资源。程序具体的设计是：函数void showdata()用来显示资源矩阵，包括系统可用资源数目，进程对资源最大需求数，系统已分配给进程的资源数，进程还需求资源。通过以上显示，很直观的观察到资源分配和修改的过程。函数share()用来利用银行家算法对某个进程申请资源对进行判定。函数int changdata(int i)用来实现资源试探分配。主要执行的步骤是Avaliablej=Avaliablej-Requestj，Allocationij=Allocationij+Requestj, Needij=Needij-Requestj。函数safe()用来实现安全性算法，对分配后的资源进行计算，若分配资源后，系统是安全的，则资源完成本次分配。若不安全将本次的试探分配作废，调用shifang()函数恢复原来的资源分配状态。资源修改功能用 Revision()来实现。六.程序源代码#include#include#define M 5 /定义进程数 #define N 3 /定义资源数 #define False 0#define True 1char saf=t;int 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=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=0;iM;i+) printf(pr%d: ,i); for(j=0;jN;j+) printf(%d,Needij);/输出还需要资源数 printf(n); int shifang(int i)/释放资源 int j; for (j=0;jN;j+) Avaliablej=Avaliablej+Requestj; Allocationij=Allocationij-Requestj; Needij=Needij+Requestj; return 1;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 Work3,FinishM=0,tempM; int i,k=0,m,apply; int j; for(i=0;i3;i+) Worki=Avaliablei; 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);/如果不成功，输出系统不安全 saf=f; return saf; break; printf(系统资源分配成功!);/如果安全，输出成功 printf(分配的序列:n); for(i=0;iM;i+)/输出运行进程数组 printf(pr%d ,tempi);return 0;void share()/利用银行家算法对申请资源对进行判定char ch;int i=0,j=0;ch=y;char saf=t;printf(n请输入要求分配的资源进程号从(0 to 4):); scanf(%d,&i);/输入须申请的资源号 printf(请输入进程 %d 申请的资源:n,i);for(j=0;j3;j+)printf(第 %d 个资源:,j+1);scanf(%d,&Requestj);/输入需要申请的资源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();/根据进程需求量显示变换后的资源 safe();/根据进程需求量进行安全算法判断if(saf=f)shifang(i);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(%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()/主函数 int choice; showdata();/显示各种资源 safe();/用银行家算法判定系统是否安全 do printf(n*输入要进行的操作 1：分配资源 2： 修改资源 3:显示资源 4：离开*); scanf(%d,&choice); if(choice=1) share(); if(choice=2) Revision(); if(choice=3) showdata(); if(choice=4) break;while(choice=1)|(choice=2)|(choice=3); return 1;七.程序调试和程序实现为了便于检验程序的正确性，这里用了书上的数据进行了初始化。程序运行时选择1 ,输入进程pr1的请求向量（1,0,2）经过程序计算，资源分配成功。资源具体分配过程如下图所示。得出一个安全序列为pr1,pr3,pr0,pr2,pr4。这与书上的有点不同，但经过计算，这也是一个正确的安全序列。对进程提出的请求向量，系统可能存在多个安全序列。主要是在安全路径的找算法上。进程pr0请求资源：pr0发出请求向量(0,2,0)，由于Request0不大于Need0,Request0不大于Available0。系统试探着为它分配资源。由结果可知，系统不安全。则系统不分配资源，并回收系统预分配给pr0的资源。程序运行时选择2,进行系统资源的修改。这里选择修改系统可用资源。修改后的Available为(2,3,2)。资源修改成功。八.设计小结一周的操作系统课程设计终于结束了，虽然很忙碌很疲劳，但感觉收获还是蛮大的。我几乎每天的专注和辛劳，唤回了我对操作系统的重新的认识，在编写程序不断出现错误和改正的过程序中加深了我对银行家算法的理解。这个系统的功能基本能满足要求，完成了对资源的修改还有用银行家算法和安全性算法来检查是否允许分配资源给进程。在课程设计的过程中，通过与同组人的相互讨论，很多问题迎刃而解。让我从