银行家算法.doc

。操作系统银行家算法课后作业一、实验目的加深对多实例资源分配系统中死锁避免方法银行家算法的理解，掌握 Windows 环境下银行家算法的实现方法。强调对于资源的管理、申请、比较来避免出现死锁的情况，保证系统的正常运行。 二、实验内容1.在 Windows 操作系统上，利用DEVC+编写应用程序实现银行家算法。2.创建 n 个线程来申请或释放资源，只有保证系统安全，才会批准资源申请。三、实验步骤（一）设计思路：银行家算法可分为个主要的功能模块，其描述如下：1.初始化由用户输入数据，分别对运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量（Max），已分配的资源数量赋值。2.安全性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH=false;(2)从进程集合中找到一个满足下述条件的进程，FINISH=false;NEED=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;(4).如所有的进程Finish= true，则表示安全；否则系统不安全。 3. 银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程j提出请求REQUEST i，则银行家算法按如下规则进行判断。(1).如果REQUEST j i= NEEDji，则转(2)；否则，出错。(2).如果REQUEST j i= AVAILABLEji，则转(3)；否则，出错。(3).系统试探分配资源，修改相关数据： AVAILABLEi-=REQUESTji; ALLOCATIONji+=REQUESTji;NEEDji-=REQUESTji;用到的数据结构：实现银行家算法要有若干数据结构，它们用来表示资源分配系统的状态。令n表示系统中进程的数目，m表示资源的分类数。还需要以下数据结构：1).Available是一个长度为m的向量，它表示每类资源可用的数量。Available j=k，表示j类资源可用的数量为k。2).Max是一个nm矩阵，它表示每个进程对资源的最大需求。Max i，j=k，表示进程pi至多可以申请k个j类资源单位。3).Allocation是一个nm矩阵，它表示当前分给每个进程的资源数目。Allocation i，j=k，表示进程i当前分到k个j类资源。4).Need是一个nm矩阵，它表示每个进程还缺少多少资源。Needi，j=k，表示进程pi尚需k个j类资源才能完成其任务。显然Needi，j= Max i，j- Allocation i，j。（二）流程图四、运行结果示例这里以书上的例子为例，初值如下表：AllocationMaxAvailableA B CA B CA B CP00 1 07 5 33 3 2P12 0 03 2 2P23 0 19 0 0P32 1 12 2 2P40 0 24 3 3将Available数列输入，每个资源的数量，线程的数目输入每个进程的最大资源需求量输入每个线程的资源量仅输入一个例子再输入一个不安全的状态申请资源量大于最大需求资源量输入一个申请资源大于资源系统现有可分配资源的情况成功触发银行家算法的条件系统显示不安全以上实例，很好证明了对于银行家算法的实例。代码附录：/感谢CSDN论坛的代码资源#include#include#includeint Available10; /可使用资源向量int Max1010; /最大需求矩阵int Allocation1010=0; /分配矩阵int Need1010=0; /需求矩阵int Work10; /工作向量int Finish10; /状态标志int Request1010; /进程申请资源向量int Pause10;int List10;int i,j;int n; /系统资源总数int m; /总的进程数int a; /当前申请的进程号int l,e; /计数器int b=0,c=0,f=0,g; /计数器void mainenter()/主要的输入部分代码 printf(请输入系统总共有的资源数：); scanf(%d,&n); printf(请输入总共有多少个进程：); scanf(%d,&m); for(i=1;i=n;i+) printf(第%d类资源有的资源实例：,i); scanf(%d,&Availablei); for(i=1;i=m;i+) for(j=1;j=n;j+) printf(进程P%d对第%d类资源的最大需求量：,i,j); scanf(%d,&Maxij); Needij=Maxij; void mainrequest() /进程提出新申请的代码部分 printf(请输入申请资源的进程：); scanf(%d,&a); for(i=1;iNeedai) printf(n出错！进程申请的资源数多于它自己申报的最大量n); if(RequestaiAvailablei) printf(nP%d必须等待n,a);/以下是试探性分配 Availablei=Availablei-Requestai; Allocationai=Allocationai+Requestai; Needai=Needai-Requestai; Worki=Availablei; for(i=1;i=m;i+) Pausei=Availablei;/Pausei只是一个暂时寄存的中间变量，为防止在下面 /安全性检查时修改到Availablei而代替的一维数组 Finishi=false; for(g=1;g=m;g+) for(i=1;i=m;i+) b=0; /计数器初始化 for(j=1;j=n;j+) if(Needij=Pausej) b=b+1; if(Finishi=false&b=n) for(l=1;l=n;l+) Pausel=Pausel+Allocationil; Finishi=true; printf($ %d ,i);/依次输出进程安全序列之一中每个元素 printf(n); for(i=1;i=m;i+) if(Finishi=true) f=f+1;/统计Finishitrue的个数 if (f=m) printf(safe static); f=0;/将计数器f重新初始化，为下一次提出新的进程申请做准备 else printf( unsafe static );/以下代码为当系统被判定为不安全状态时 /返回提出申请前的状态 for(i=1;i=n;i+) Availablei=Availablei+Requestai; Allocationai=Allocationai-Requestai; Needai=Needai+Requestai; void mainprint() printf(当前的系统状态n); printf( 目前占有量 最大需求量 尚需要量 n进程); for(i=1;i=n;i+) for(j=1;j=n;j+) printf( %d类,j); for(i=1;i=m;i+) printf(nP%d,i); for(j=1;j=n;j+) printf( %d ,Allocationij); for(j=1;j=n;j+) printf( %d ,Maxij); for(j=1;j=n;j+) printf( %d ,Needij); printf(nn系统剩余资源量： ); for(i=1;i=n;i+) printf( %d ,Availablei); printf(n);int main() int k,h=1; while(h) system(cls); printf(nn 1:输入系统的资源数、申请进程数、每个类资源的实例数); printf(n 2: 输入进程的资源申请); printf(n 3: 输出系统状态); printf(n 4: 退出程序); printf(nn 请选择 ); scanf(%d,&k); switch(k) case 1:mainenter(); break; case 2:mainrequest(); break; case 3:mainprint(); break; case 4:h=0; break; printf(n); system(pause); system(cls); printf(nn 谢谢使用 n); printf(nn See you next time