操作系统课程设计银行家算法.doc

课 程 设 计设计题目 银行家算法学生姓名号 学 号指导教师专业班级2011 年 6 月 课程设计任务书设 计题 目银行家算法成绩主要内容进程死锁的避免：银行家算法，教材P127-129页。（1人） l 建立银行家算法的数据结构描述；l 将初始数据放在文件中，算法运行时读出；l 对给定的资源请求，使用算法判断是否允许；l 输出每次判断产生的执行序列；指导教师意见该生能按时完成课程设计任务书所规定的程序设计，综合运用所学知识独立分析和解决问题的能力 。程序设计方案 。论文论述 ，文理 ，格式 。程序运行结果 。程序验收时回答问题 。 签名： 1前言 ：Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。第一章 开题报告（一） 该项课程设计的意义；（二） 课程设计的任务（三） 相关原理及算法描述；（四） 开发环境；（五） 预期设计目标；1、 该项课程设计的意义在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。2、 课程设计的任务一、将初始数据放在文件中，算法运行时读出；二、对给定的资源请求，使用算法判断是否允许；三、输出每次判断产生的执行序列；3、 相关原理及算法描述3.1 预备知识银行家算法是一种最具有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。所谓安全状态，是指系统能按照某种进程顺序P1,P2,，Pn（称P1,P2,，Pn 序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。如果对每一个进程Pi(1in)，它以后尚需要的资源量不超过系统当前可利用的资源量与所有的进程Pj(jn)所占有的资源量之和，则称此进程序列P1,P2,，Pn是安全的，称作安全序列。3.2银行家算法我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。3.3基本要求（1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。（2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。（3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回B. 所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查： a. 预分配后系统是安全的，将该进程所申请的资源予以实际分配并打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。3.4算法描述3.4.1算法思路： 先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。3.4.2银行家算法步骤（1）如果Requestior =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requestor=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available=Available-Requesti; Allocation=Allocation+Request; Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。3.4.3安全性算法步骤（1）设置两个向量工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finishi=false，当有足够资源分配给进程时，令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程：Finishi=falseNeedor=Work如找到，执行步骤（3）；否则，执行步骤（4）。（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work=Work+Allocation;Finishi=true; 转向步骤（2）。（4）如果所有进程的Finishi=true,则表示系统处于安全状态；否则，系统处于不安全状态。3.4.4数据结构：(1)最大需求矩阵Max(2)已分配矩阵Allocation(3)仍需求矩阵Need=Max-Allocation(4)可利用资源向量Available(5)申请各类资源向量Request(6)工作向量 work , Finish4、 开发环境Visual c+ 6.0 ;windows xp环境；5、 预期设计目标1、能成功的从文件读入最大需求矩阵和已分配矩阵，2、从键盘输入进程的资源请求，调用算法判断是否允许分配，3、若允许分配，则输出安全序列；反之则输出资源请求会导致系统处于不安全状态。3第二章 课程设计报告1、课程设计任务、要求、目的；l 建立银行家算法的数据结构描述；l 将初始数据放在文件中，算法运行时读出；l 对给定的资源请求，使用算法判断是否允许；l 输出每次判断产生的执行序列；2、原理及算法描述；注：基本原理和算法介绍请参照开题报告3、开发环境；Windows xp环境下 visual c+ 6.0；4、重要算法和设计思路描述； 4.1主要函数介绍1. void Init()：进行初始化函数：从文件读入最大需求矩阵和need矩阵；2. bool Safe()：利用安全性算法进行检测的函数；3. void Bank()：利用行家算法进行判定系统是否安全的函数； 4.2程序流程图1、系统主要过程流程图2、银行家算法流程图3、安全性算法流程图6、 程序实现-程序清单；#include#include#includeusing namespace std;int Sign100;/标记数组int Progress100;/进程执行顺序标记数组string Number100;/进程号class BankerArithmeticpublic:BankerArithmetic(int a,int b);/构造函数int Safe(int grac);/判断是否安全void Show();/显示相关信息void Bank();/计算剩余资源量BankerArithmetic();/析构函数private:BankerArithmetic();void Init(int a,int b);/初始化int ID;/记录成功申请资源的进程号 int n; /包含的进程数 int m; /资源种类数 int *Available;/可提供的资源总数 int * Allocation;/以分配的资源 int * Need;/仍需要的资源int *Left;/剩余的资源;BankerArithmetic:BankerArithmetic(int a,int b):n(a),m(b)Init(n,m);BankerArithmetic:BankerArithmetic()int i;deleteAvailable;deleteLeft;for(i=0;in;i+)deleteAllocationi;deleteAllocation;for(i=0;in;i+)deleteNeedi;deleteNeed;void BankerArithmetic:Init(int a,int b)int i,j;for(i=0;i100;i+)Signi=-1;Available=new intb;/Availablede的申请 Left=new intb;/Left的申请Allocation=new int*a;/Allocation的申请for(i=0;ia;i+)Allocationi=new intb;Need=new int*a;/Need的申请for(i=0;ia;i+)Needi=new intb;cout请输入可用资源Available:endl;for(i=0;iAvailablei;cout请输入进程号:endl;for(i=0;iNumberi;cout请输入分配资源矩阵Allocation:(a,b)endl;for(i=0;ia;i+)for(j=0;jAllocationij;cout请输入仍需要资源矩阵Need:(a,b)endl;for(i=0;ia;i+)for(j=0;jNeedij;/计算剩余的资源 for(i=0;im;i+) Lefti=Availablei; j=0; while(jm) for(i=0;in;i+) Leftj-=Allocationij; j+; int BankerArithmetic:Safe(int grac)/看是或安全int i,j,temp; for(i=0;in;i+) if(Signi!=1) temp=1; for(j=0;j=Needij) temp*=1; else temp*=0; if(temp=1) break; ID=i; Signi=1; Progressgrac=ID;if(temp)return ID;elsereturn -1;void BankerArithmetic:Bank()for(int i=0;im;i+)Lefti=Lefti+AllocationIDi;void BankerArithmetic:Show()int i,j; cout进程 Allocation Need n; for(i=0;in;i+) if(Signi!=1) coutNumberi ; for(j=0;jm;j+) cout Allocationij; cout ; for(j=0;jm;j+) cout Needij; coutendl; coutendl; for(i=0;im;i+) coutLefti ; coutendl;int main()int process,source,result,i=0,sum=1;char ans1,ans2;coutprocess;coutsource;BankerArithmetic banker(process,source);while(iprocess)coutans1;if(ans1=y|ans1=Y)banker.Show();result=banker.Safe(i);if(result=0)Progressi=result;else sum=0;cout处于不安全状态！程序将退出！n;exit(1);cout按空格键程序执行一次endl;while(cin.get(ans2)&ans2=n)banker.Bank();i+;if(sum=1)cout进程执行的顺序如下:;for(i=0;iprocess-1;i+)coutNumberProgressi ;coutNumberProgressprocess-1;return 0;7、 总结在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如最大需求量Max、已分配资源数Allocation、仍需求资源数Need、以及系统可利用的资源数、申请各类资源等数组。数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。在本程序代码中，银行家算法用judge( )函数来实现。首先，输入欲申请资源的进程以及其所申请的资源数，存放在Request数组中。然后，判断进程请求的资源数是否大于其所需的资源数，若大于则报错并返回，若不大于则继续判断它是否大于系统在此时刻可利用的资源数，同样，如果大于则报错并反回，如果不大于则调用changedata( )函数来进行预分配，之后再调用安全型算法safty检查。最后，无论此次分配是否成功，我们都可以选择继续分配或者退出系统。安全性检测我们是用safty( )函数来实现的。首先，Finish为布尔型，默认是False，即该进程未完成。而Work即该系统中可以用来工作的资源数最开始为系统最初可以用的资源数。然后，我们从第一个进程开始判断该进程未完成且其所需求的资