操作系统课程设计报告-银行家算法

操作系统课程设计报告题目：银行家算法 院 （系）： 专 业： 班 级： 学 生： 学 号： 指导教师： 操作系统课程设计报告摘 要Dijkstra提出的银行家算法，是最具代表性的避免死锁的算法。本文对如何用银行家算法来处理操作系统给进程分配资源做了详细的说明，包括需求分析、概要设计、详细设计、测试与分析、总结、源程序清单。首先做了需求分析，解释了什么是银行家算法，并指出它在资源分配中的重要作用。然后给出了银行家算法的概要设计，包括算法思路、步骤，以及要用到的主要数据结构、函数模块及其之间的调用关系等。在概要设计的基础上，又给出了详细的算法设计，实现概要设计中定义的所有函数,对每个函数写出核心算法，并画出了流程图。接着对编码进行了测试与分析（并在最后附上Java编写的程序代码）。最后对整个设计过程进行了总结。关键词：安全状态；安全序列；银行家算法；安全性算法；安全序列；流程图。目录摘要11绪论41.1前言51.2研究意义51.3结构安排52需求分析42.1题目描述52.2银行家算法52.3基本要求52.4目的53概要设计43.1基本思路53.2银行家算法步骤53.3安全型算法步骤53.4数据结构53.4.1主要用到的数据结构63.4.2程序模块63.4.3各模块间的调用关系64详细设计44.1主要函数的核心代码54.1程序流程图55测试45.1测试用例55.1测试结果分析和截图56总结4参考文献4附录：原程序清单41绪论11前言 ：Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。12研究意义 ：在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。13结构安排 ：一、绪论： 介绍了题目背景以及研究意义。二、需求分析： 介绍了题目描述、银行家算法、以及基本要求和所需达到的目的。三、概要设计：介绍了基本的算法思路、步骤，以及数据结构和主要的函数模块及其调用关系。四、详细设计：介绍了主要函数及其核心代码，以及程序流程图。五、测试六、总结参考文献附录：原程序清单 2 需求分析21题目描述 ：银行家算法是一种最具有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。所谓安全状态，是指系统能按照某种进程顺序P1,P2,，Pn（称P1,P2,，Pn 序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。那么，什么是安全序列呢？如果对每一个进程Pi(1in)，它以后尚需要的资源量不超过系统当前可利用的资源量与所有的进程Pj(jn)所占有的资源量之和，则称此进程序列P1,P2,，Pn是安全的，称作安全序列。22银行家算法 ：我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。23基本要求 ：（1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。（2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。（3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回。 B. 所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查： a. 预分配后系统是安全的，将该进程所申请的资源予以实际分配并打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 24目的：根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序要求实现的功能以及限制条件。明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。3 概要设计31算法思路： 先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。32银行家算法步骤（1）如果Requestior =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requestor=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available=Available-Requesti; Allocation=Allocation+Request; Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。33安全性算法步骤（1）设置两个向量工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finishi=false，当有足够资源分配给进程时，令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程：Finishi=falseNeedNeedb. 0 2 2 2 RequestAvailablec. 1 1 0 1 可以分配d. 0 1 0 1 系统不安全52测试结果截图：1. 开始界面2. 初始化并打印输出3. 用例测试a：进程1发出请求Request(2,1,2)RequestNeed，不予分配。4. 用例测试b：进程0发出请求Request(2,2,2)RequestAvailable， 不予分配。5. 用例测试c：进程1发出请求Request(1,0,1)可以分配。6. 用例测试d：进程0发出请求Request(1,0,1)系统不安全。7. 输入测试a：如果所输入的要分配资源的进程号不在存在的进程，则报错请求重新输入。8. 输入测试b：在选择继续分配还是退出中，如果输入不符合要求，则报错请求重新输入，连续错误5次后系统将自动关闭。6 总结6 总结在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如最大需求量Max、已分配资源数Allocation、仍需求资源数Need、以及系统可利用的资源数、申请各类资源等数组。数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。在本程序代码中，银行家算法用judge( )函数来实现。首先，输入欲申请资源的进程以及其所申请的资源数，存放在Request数组中。然后，判断进程请求的资源数是否大于其所需的资源数，若大于则报错并返回，若不大于则继续判断它是否大于系统在此时刻可利用的资源数，同样，如果大于则报错并反回，如果不大于则调用changedata( )函数来进行预分配，之后再调用安全型算法safty检查。最后，无论此次分配是否成功，我们都可以选择继续分配或者退出系统。安全性检测我们是用safty( )函数来实现的。首先，Finish为布尔型，默认是False，即该进程未完成。而Work即该系统中可以用来工作的资源数最开始为系统最初可以用的资源数。然后，我们从第一个进程开始判断该进程未完成且其所需求的资源量不大于该系统中可以用来工作的资源量这个条件是否成立，即Finish=False且Need=Work是否成立。成立的话则将当前在工作的资源量与该进程已分配的资源量相加，存放于当前可用来工作的资源量当中，即Work=Work+Allocation，并将Finish的值改为True。否则便将此进程的优先级减一，排在队位，然后开始往后循环。待所有的进程循环完毕，我们再次判断是否还存在进程的Finish=False，如果仍存在，则说明系统没有安全序列，处于不安全状态，不可以进行分配；否则，系统处于安全状态，将预分配变为实际分配，求出安全序列并且将实际分配后的资源分配情况打印输出。除此之外，在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些比如进程号本来设定就是整型，因此对输入的是字母的判别因比较复杂而未能加上。总之，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。参考文献1 汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统. 西安：西安电子科技大学出版社，2007.2 严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006.3 赵莉，杨国梁，孙喁喁，徐飞. Java程序设计教程. 西安：西安科技大学出版社，2009.4 (百度文库：银行家算法报告)5 （志文工作室： 银行家算法模拟实现）附录：源程序清单package bank;import java.util.Scanner;public class Test int no1, no2;static int Max; /最大需求static int Allocation; /已分配资源数static int Need; /仍需资源数static int Available; /可利用资源数static String name1; static String name2; static boolean Finish; static int temp = 0 ; /存放安全序列static int work;static int Request;Scanner input = new Scanner(System.in);public static void main(String args) Test t = new Test();t.printFrame();/t.print();t.Safty();t.judge();/* 输入初始化数据*/public void printFrame() System.out.println(*);System.out.println(* *);System.out.println(* 银行家算法设计与实现 *);System.out.println(* *);System.out.println(*);System.out.print(请输入系统中进程的个数:);no1 = input.nextInt();System.out.print(请输入资源的种类数：);no2 = input.nextInt();Max = new intno1no2;Allocation = new intno1no2;Need = new intno1no2;Available = new intno2;name1 = new Stringno1;name2 = new Stringno2;int sum = new int3;for (int i = 0; i no1; i+) System.out.print(请输入进程 + i + 的名字:);name1i = input.next();for (int i = 0; i no2; i+) System.out.print(请输入资源 + i + 的名字:);name2i = input.next();for (int i = 0; i no1; i+) for (int j = 0; j no2; j+)System.out.print(请输入进程 + name1i + 的 + name2j+ 类资源最大需求量:);Maxij = input.nextInt();for (int i = 0; i no1; i+)for (int j = 0; j no2; j+) System.out.print(请输入进程 + name1i + 的 + name2j+ 类资源已占有资源量:);Allocationij = input.nextInt();Needij = Maxij - Allocationij;for (int i = 0; i no2; i+)System.out.print(请输入类资源 + name2i + 的可利用资源数：);Availablei = input.nextInt();/for (int i = 0; i no2; i+) / 算出资源分配后，系统的可利用资源数/ /for (int j = 0; j no1; j+) /sumi += Allocationji; /for (int i = 0; i no2; i+) Availablei = Availablei - sumi;/*打印輸出*/public void print()System.out.println(*此时刻资源分配情况*);System.out.println( Number Name Max Allocation Need);for (int i = 0; i no1; i+)System.out.print( + i + );System.out.print(name1i+ ); for (int j = 0; j no2; j+) System.out.print(Maxij+ );for (int j = 0; j no2; j+) System.out.print( + Allocationij);for (int j = 0; j no2; j+) System.out.print( + Needij);System.out.println();System.out.print(各个类资源可利用的资源数分别为:);for (int j = 0; j no2; j+) System.out.print( + Availablej);System.out.println();/* * 进行安全性检测 */public void Safty() Finish = new booleanno1;temp = new intno1;int i, k = 0, m, apply,j;/k为安全序列的序列数int flag = 0;work = new intno2;for (i = 0; i no2; i+) worki = Availablei;for (i = 0; i no1; i+) /当前执行换后，重第一个开始检测 apply = 0;for (j = 0; j no2; j+) if (Finishi = false & Needij = workj) /apply+;if (apply = no2)for (m = 0; m no2; m+)workm = workm + Allocationim;/ 变分配数Finishi = true;tempk = i+1; /保存安全序列i = -1; /k+;flag+; for (i = 0; i no2; i+) if (Finishi = false) System.out.println(系统不安全！);else System.out.print(系统是安全的，安全序列为：); for (i = 0; i ); System.out.println(); print(); /* 进行资源分配 */public void changdata(int i) int j;for (j = 0; j no2; j+) Availablej = Availablej - Requestj;Allocationij = Allocationij + Requestj;Needij = Needij - Requestj;/* 利用银行家算法对申请资源对进行判定*/void judge() Request = new intno2;char ch=y;int i = 0, j = 0;System.out.print(请输入您要分配的资源进程号：); for(j=0;jno1) System.out.println(输入错误，请重新输入:);continue; else break; / System.out.println(错误次数太多，看来您今天不适合进行操作，系统退出！); / System.exit(0);System.out.println(请输入进程 + i + 申请的资源：);for (j = 0; j no2; j+)System.out.print(name2j + 类资源请求：);Requestj = input.nextInt();/ 输入需要申请的资源for (j = 0; j Needij) / 判断申请是否大于需求，若大于则出错System.out.println(进程 + i + 申请的资源大于它所需要的资源。);System.out.println(分配不合理，不予分配！);ch = n;break; else if (Requestj Availablej)/ 判断申请是否大于当前资源，若大于则System.out.println(进程 + i + 申请的资源大于系统现在可利用的资源。);System.out.println(分配不合理，不予分配！); ch = n;break; if (ch = y) changdata(i); / 根据进程需求量变换资源 Safty(); / 根据进程需求量进行银行家算法判断 System.out.println(请输入您所要进行的操作：1：继续分配 2：退出);for(i=0;i5;i+) int choice = input.nextInt(); if (choice = 1) judge(); else if (choice = 2) System.exit(0); else System.out.println(输入错误，请重新输入：);System.out.println(错误次数太多，看来您今天不适合进行操作，系统退出！);System.exit(0);