操作系统避免死锁的银行家算法课程设计.pdf

目录1、概述 12、需求分析 23、数据结构设计54、算法的实现65、结束语176、参考文献 181、概述一、设计目的1、了解多道程序系统中，多个进程并发执行的资源分配。2、掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。3、掌握预防死锁的方法，系统安全状态的基本概念。4、掌握银行家算法，了解资源在进程并发执行中的资源分配策略。5、理解死锁避免在当前计算机系统不常使用的原因二、开发环境源文件：Bank.cpp操作系统编译环境生成文件RedFlag 5.0g+Bank for LinuxWindows Vista BusinessBorland C+Compiler 5.5Bank For Windows.exe2、需求分析避免多道程序系统中程序的死锁。一、死锁概念：在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统 的资源利用率，提高系统的吞吐量，但可能发生一种危险一死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种 僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它 们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进 程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称 为进程死锁，这一组进程就称为死锁进程。二、关于死锁的一些结论：0 参与死锁的进程最少是两个(两个以上进程才会出现死锁)0 参与死锁的进程至少有两个已经占有资源0 参与死锁的所有进程都在等待资源0 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。三、资源分类：永久性资源：可以被多个进程多次使川（可再川资源）I 可抢占资源I 不可抢占资源临时性资源：只可使用一次的资源；如信号量，中断信号，同步信号等（可消 耗性资源）“申请-分配-使川-释放”模式四、产生死锁的四个必要条件：1、互斥使川（资源独占）一个资源每次只能给一个进程使川2、不可强占（不可剥夺）资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿 释放3、请求和保持（部分分配，占有申请）一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态 申请，动态分配）4、循环等待存在一个进程等待队列P1,P2,，Pn,其中Pl等待P2占有的资源，P2等待P3占有的资源，Pn等待P1占有 的资源，形成一个进程等待环路5、死锁的解决方案5.1产生死锁的例子申请不同类型资源产生死锁P1:中请打印机申请扫描仪使用释放打印机释放扫描仪P2：申请扫描仪申请打印机使用释放打印机释放扫描仪申请同类资源产生死锁(如内存)设有资源R,R有m个分配单位，由n个进程Pl7P2,.7Pn(n m)共享。假 设每个进程对R的申请和释放符合下列原则：*一次只能中请一个单位*满足总申请后才能使川*使川完后一次性释放m=2,n=3资源分配不当导致死锁产生5.2死锁预防:定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一破坏“不可剥夺”条件在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得 到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请破坏“请求和保持”条件要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程 所要资源均可满足时才给予一次性分配破坏“循环等待”条件采用资源有序分配法：把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次 序进行，否则操作系统不予分配。6.安全状态与不安全状态安全状态：如果存在一个由系统中所有进程构成的安全序列PLPn,则系统处于安 全状态。一个进程序列PL，Pn是安全的，如果对于每一个进程Pi(lWWn),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(ji)当前占有 资源量之和，系统处于安全状态(安全状态一定是没有死锁发生的)不安全状态:不存在一个安全序列，不安全状态一定导致死锁。3、数据结构设计一、可利用资源向量矩阵AV AILABLE。这是一个含有m个元素的数组，其中 的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类 全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 AV AILABLE j=K,则表示系统中现有R类资源K个二、最大需求矩阵M AX。这是一个n*m的矩阵，用以表示每一个进程对m类资源的最大需求。如果M AX i,j=K,则表示进程i需要R 类资源的数目为K。三、分配矩阵ALLOCATION。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果ALLOCATION：i,j=K,则表示进程i当前已分得R类资源的数目为K。四、需求矩阵NEED。这也是一个n*m的矩阵，川以表示每一个进 程尚需的各类资源数。如果NEED i,j=K,则表示进程i还需要R类 资源K个，才能完成其任务。上述矩阵存在下述关系：NEED i,j=M AXi,j-ALLOCATIONi,j4、算法的实现一、初始化由用户输入数据，分别对可利用资源向量矩阵AV AILABLE、最大需 求矩阵M AX、分配矩阵ALLOCATION、需求矩阵NEED赋值。二、银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统 性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终 都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分 配。它是最具有代表性的避免死锁的算法。设进程cusneed提出请求REQUEST：i,则银行家算法按如下规则进行判断。如果 REQUEST cusneed i=NEEDcusneed i,则转(2)；否则，出 错。(2)如果 REQUEST cusneed i=AV AILABLEcusneed i,则转(3)；否 则,出错。(3)系统试探分配资源，修改相关数据：AV AILABLEi-=REQUESTcusneed i;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneed i;系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废,系统恢复原状，进程等待。三、安全性检查算法(1)设置两个工作向量Work=AV AILABLE;F INISH(2)从进程集合中找到一个满足下述条件的进程，F INISH=false;NEED=ffork;如找到,执行;否则，执行(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;F inish=true;G OTO 2(4)如所有的进程F inish二true,则表示安全；否则系统不安全。四、各算法流程图初始化算法流程图:银行家算法流程图:安全性算法流程图:四、源程序清单ttinclude using namespace std;define M AXPROCESS 50 ftdefine M AXRESOURCE 100/*最大进程数*/*最大资源数*/int AV AILABLE M AXRESOURCE;/*可用资源数组*/int M AX M AXPROCESS M AXRESOURCE;/*最大需求矩阵*/int ALLOCATION M AXPROCESS M AXRESOURCE;/*分配矩阵*/int NEED:M AXPROCESS:M AXRESOURCE;/*需求矩阵*/int REQUEST M AXPROCESS M AXRESOURCE;/*进程需要资源数*/bool F INISHM AXPROCESS;/*系统是否有足够的资源分配*/int pM AXPROCESS;int m,n;void Init();bool Safe();void Bank();int main()Init();Safe();Bank();)void Init()int i,j;coutt-dl;couttI I dl;couttI I法couttI I dl;couttI I 宏 I I/zendl;coutt|dl;/*初始化算法*/银行家算|/zendl;couttI/*记录序列*/*m个进程,n个资源*/-en|/zen|/zen计科04151李|/zen0415084211|z，endl;cout/zt-z，endl;coutm;coutn;cout请输入每个进程最多所需的各资源数，按照00水矩阵输 入endl;for(i=0;im;i+)for(j=0;jn;j+)cinM AXi j;cout请输入每个进程已分配的各资源数,也按照水0水矩阵输 入endl;for(i=0;im;i+)for(j=0;jn;j+)cinALLOCATIONi j;NEED：i j=M AXi j-ALLOCATION：1 j;if(NEEDijO)cout您输入的第i+l个进程所拥有的第个 资源数错误,请重新输入：/zendl;J；continue;cout请输入各个资源现有的数目：/zendl;for(i=0;in;i+)cinAV AILABLEi;)void Bank()/*银行家算法*/int i,cusneed;char again;while(1)cout请输入要中请资源的进程号(注:第1个进程号为0,依次类 推)cusneed;cout请输入进程所请求的各资源的数量endl;for(i=0;iREQUESTcusneed i;)for(i=0;iNEEDcusneedi)cout 您输入的请求数超过进程的需求量!请重新输入！endl;continue;if(REQUESTcusneediAV AILABLEi)cout 您输入的请求数超过系统有的资源数!请重新输 入！endl;continue;)for(i=0;in;i+)(AV AILABLEi-=REQUESTcusneed i;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi;)if(Safe()cout同意分配请求!z/endl;)else(cout您的请求被拒绝!/zendl;for(i=0;in;i+)AV AILABLEi+=REQUESTcusneedi;ALLOCATIONcusneedi-=REQUESTcusneedi;NEEDcusneedi+=REQUESTcusneedi;for(i=0;im;i+)F INISHi=false;)cout您还想再次请求分配吗?是请按y/Y,否请按其它键again;if(again二二,y?|again二二,Y，)continue;)break;)bool Safe()/*安全性算法*/int i,j,k,1=0;int Work M AXRESOURCE;/*工作数组*/for(i=0;in;i+)Worki=AV AILABLEi;for(i=0;im;i+)F INISH：i=false;)for(i=0;im;i+)if(F INISHi=true)continue;elsefor(j=0;jWorkj)break;)if(j=n)F INISH i=true;for(k=0;kn;k+)(Workk+=ALLOCATIONik;)pl+=i；i=-l；)elsecontinue;)if(l=m)coutX系统是安全的endl;cout安全序列：endl;for(i=0;il;i+)coutpi;if(i!=l-l)COUt;)cout/zzzendl;return true;)cout1-3状态b不安全，只剩1个可用资源，收不回已分配资源。(2)考虑下列系统状态分配矩阵 最大需求矩阵 可用资源矩阵00120012152010001750135423560632065200140656问系统是否安全？若安全就给出所有的安全序列。若进程2请求(0420),可否立 即分配？答：安全。安全序列为：1-3-2-5-4O若进程2请求(0420),可立即分配。分配后可用资源为1100,回收1 进程资源,可用资源数为:1112,然后执行3254序列。3、任爱华、王雷编：操作系统实用教程，清华大学.2、张尧学、史美林编：计算机操作系统教程，清华大学.1、汤子嬴编：计算机操作系统，西安电子科技大学.6、参考文献