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

操作系统课程设计报告题目：银行家算法操作系统课程设计报告题目：银行家算法摘要 在多道操作系统中，可以利用多个进程并发执行来改善系统资源利用率，提高系统的吞吐量，但也可能发生人们不想看到的危险死锁。为了解决这个问题，人们引入了多种机制处理死锁问题。本文主要介绍了操作系统如何运用银行家算法和安全性算法避免死锁的产生。同时运用Java编程语言模拟计算机内部资源分配的过程。让读者对银行家算法有更深刻的认识。关键字：死锁 银行家算法 安全性算法 资源分配 IAbstractIn much road OS, improve the systematic handling capacity, but also may people happened not thinking of dangerous dead lock seeing that to come to improve system resource utilization ratio being able to make use of many course concurrency to carry out. Have led into various mechanism for problem , people resolving this handle lock fast problem. The main body of a book has been introduced mainly how to apply the banker algorithm and the security algorithm to avoid lock fast creation. Wield Java programming language analog computer inside resource assignment process at the same time. Let reader have deeper cognition to banker algorithm.Key words: Algorithmic algorithmic security of dead lock banker resource assignmentII目 录中文摘要.（I）英文摘要（II）1绪论.（1）2需求分析.（2）3概要设计.（3） 4详细设计.（4）5测试与分析.（6）6总结（11）7参考文献（12）附录（13） 操作系统课程设计报告-19 1绪论银行家算法诞生的背景：操作系统作为裸机上安装的第一层软件，起着控制和管理计算机内部软硬件资源，合理组织计算机工作流程，提高计算机工作效率，用户和计算机硬件接口的重要作用。因此操作系统即要保证系统资源的合理分配提高系统资源利用率，同时又要避免死锁等不安全状况的出现，如果这些不安全状况出现操作系统还要解决这些问题，让系统回到安全状态。银行家算法就是在这样的背景下应运而生的。银行家算法的核心： 银行家算法的核心它通过自己特有的算法，在每次奉陪给进程系统资源前，先试探性的“假设”分配资源给进程Pi，再通过安全性算法检测此次分配是否会导致系统进入不安全状态，如果分配后系统依然安全则系统将资源正是分配给进程Pi；如果此次分配导致系统进入不安全状态，则暂不分配资源给进程Pi。通过这种机制，系统可以有效的避免死锁的产生，确保系统时时刻刻都处在安全状态。2需求分析2.1死锁2.1.1死锁：指的是多个进程在运行过程中因为争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，他们都将无法再向前推进的状态。2.1.2死锁产生的原因：（1）竞争非可剥夺性资源（2）进程推进不当。 2.13产生死锁的必要条件：（1）互斥条件（2）请求和保持条件（3）不可剥夺条件（4）环路等待。2.1.4处理死锁的基本发法：（1）预防死锁：属于事前预防的策略，通过设置某些限制条件，去破坏产生死锁的四个必要条件或其中的几个条件。预防死锁比较容易实现，所以被广泛使用，但是由于施加的限制条件过于严格可能会导致系统资源利用率和系统吞吐量降低。（2）避免死锁：属于事前预防的策略，但它并不需要事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的产生。但实现有一定的难度。目前较完善的系统中常用此法来避免死锁。（3）检测死锁：这种方法不需要事前采取任何限制措施，也不用检查是否进入不安全状态，而是允许系统在运行的过程中发生死锁。但是通过系统所设置的检测机构，及时的检测出死锁的发生，并精确的测出与死锁有关的进程和资源，然后，采取适当的措施，从系统中将已发生的死锁清楚掉。（4）解除死锁：这是与检测死锁相配套的一套措施。当检测到系统已经产生死锁时，须将进程从死锁中解放出来。通常用到的实施方法是撤销或挂起一些进程，以便收回一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施，有可能使系统获得较好的资源和吞吐量，但在现实上难度也最大。预防死锁和避免死锁的区别：预防死锁和避免死锁实质上都是通过施加某种相知条件的方法，来预防发生死锁。两者的主要区别：为了预防死锁所施加的限制条件较为严格，这往往会影响到进程的并发执行，而避免死锁所施加的限制条件则较为宽松，有利于进程的并发执行。2.2为什么引入银行家算法：由上文可以看出，预防死锁虽然可以预防死锁的产生，但是以牺牲进程的执行效率为代价，而死锁的避免由于施加的限制条件较弱，对进程的影响较小，有可能使用户获得满意的系统性能。在该方法中把系统状态分成安全状态和不安全状态，只要能使系统出于安全状态，便可避免死锁。因此，死锁的避免对防止系统进入不安全状态用重要意义。最具代表性的避免死锁算法是Dijkstra的银行家算法。银行家算法是通过自己特有的算法，在每次奉陪给进程系统资源前，先试探性的“假设”分配资源给进程Pi，再通过安全性算法检测此次分配是否会导致系统进入不安全状态，如果分配后系统依然安全则系统将资源正是分配给进程Pi；如果此次分配导致系统进入不安全状态，则暂不分配资源给进程Pi。通过这种机制，系统可以有效的避免死锁的产生，确保系统时时刻刻都处在安全状态。所以，要想深入了解避免死锁机制的，就必须掌握银行家算法的原理，及算法实现过程。3概要设计3.1避免死锁避免死锁将系统状态分为安全状态和不安全状态两种。所谓安全状态指的是系统按某进程顺序（P1,P2,P3,Pn）（称序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。如果系统无法找到一个这样的安全序列，则称系统处于不安全状态。避免死锁就是通过一套完整的机制，让系统时时刻刻都处于安全状态。3.2银行家算法的实现过程：（1） t0时刻系统通过算法检测当前系统是否安全，即是否可以找到一个安全序列使当前所有进程顺利完成，若找到则称系统安全，并按照序列继续进程的执行，并执行步骤（2）；若找不到则称系统不安全即系统已进入死锁状态，立刻停止进程的执行，通过挂起一些进程来让系统重新进入安全状态，当系统处于安全状态后转向执行步骤（2）。（2） 当t1时刻有进程对系统提出资源请求时，系统先先检测当前进程资源请求是否大于此进程最大需求，若大于则不执行；若不大于，再检测当前的资源要求是否大于系统当前可分配数，若大于则不予分配，若不大于则进行步骤（3）。（3） 系统假设将进程Pi要求的资源分配给Pi，通过安全性算法检测将资源分配给进程后系统是否还处于安全状态，若处于则分配资源，若不处于则不予分配。194详细设计4.1银行家算法的数据结构：（1） Avaliable可利用资源向量。这是一个含有m个元素的数组，每个元素代表一类可利用资源数目，其初值是系统中所配置的该类全部可用资源数目，其数值随该类资源的分配和回收而动态地改变。（2） Max最大需求矩阵。这是一个m*n的矩阵，它定义了系统中n个进程中的每一个进程对n类资源的最大需求。（3） Allocation分配矩阵。这是一个m*n的矩阵，它定义了当前系统的n个进程得到每一类资源的数目。（4） Request请求向量。这是一个含有m个元素的向量，它表示进程i对各类资源的需求情况。（5） Need需求矩阵。这是一个n*m的矩阵，它定义了当前系统的n个进程要想完成工作，还需要各类资源的数目。因此有以下关系：Needi,j=Maxi,j-Allocationi,j4.2安全性算法数据结构：（1） Work工作向量。这是一个含有m个元素的向量，表示系统可以提供给进程继续运行所需的各类资源数目，其初值Work=Avaliable。（2） Finish结束向量。表示系统是否有足够的资源分配给进程，使之运行完成。开始时Finishi=false，当有足够资源分配给进程时，Finishi=turned。4.3银行家算法：假设进程Pi提出资源请求Request ij=k（1） 若Request ij=Needi,j,便转向执行步骤（2）；否则认为出错。 （2） 若Request ij=Availablej便转向执行步骤(3)；否则表示系统尚无足够的资源分配，让Pi等待。（3） 系统假设将Pi所要求的资源分配给Pi，并对数据结构做如下修改： Avaliablej=Availablej-Request ij ;Allocationi,j=Allocationi,j -Request ij; Needi,j=Needi,j- Request ij； （4） 系统执行安全性算法，检测此次资源分配后，系统是否处于安全状态。若安全才正式将资源分配给进程Pi，以完成本次分配；否则，本次试探分配作废，恢复原来的资源分配状态，让Pi等待。4.4安全性算法：（1） 从进程集合中找到一个能满足一下条件的进程： Finishi=false Needi,j=Workj ;若找到执行步骤（2）否则执行步骤（3）。（2） 进程Pi获得资源后，可以顺利执行，直至完成，并释放分配给它们的资源，故应执行：Workj=Worki+Allocationi,j;Finishi=true;转向执行步骤2;（3）若所有的进程的Finishi=true都满足，则表示系统处于安全状态；否则系统处于不安全状态。由此可见，安全性算法实际是银行家算法的一部分，为当前系统找到一个安全序列，却保此刻的系统的分配状态能够保证内存中的进程全部顺利完成。资源请求Request ijRequest ij是否大于Needi,j?Request ij是否大于Avaliablej试探将资源分配给Pi，并修改相应数据结构能否找到安全序列？进行安全性检测正是分配资源请求出错，不予分配！资源不足，暂时等待！4.5算法流程图 是 否 是 否5测试与分析按照算法编写java源程序，并进行运行，过程如下：请输入进程数！5请输入资源种类数！3请输入各种资源的总量1057请输入第0个进程对各种资源的最大需求量753请输入第1个进程对各种资源的最大需求量322请输入第2个进程对各种资源的最大需求量902请输入第3个进程对各种资源的最大需求量222请输入第4个进程对各种资源的最大需求量433请输入第0个进程对各种资源的分配量情况010请输入第1个进程对各种资源的分配量情况200请输入第2个进程对各种资源的分配量情况302请输入第3个进程对各种资源的分配量情况211请输入第4个进程对各种资源的分配量情况002进程最大需求矩阵 /通过输入数值生成各种矩阵07531322290232224433进程分配矩阵00101200230232114002进程需求矩阵07431122260030114431各类资源总数1057各类资源剩余数332开始进行安全性检验系统安全,安全序列为： /检测当前资源分配是否安全/13402第几个进程有请求？1第1个进程的各个资源有什么请求？ /输入进程Pi对各资源的需求量/102已经进行了试分配开始进行安全性检验 /进行安全性检测/系统安全,安全序列为： /寻找安全序列/13402进程最大需求矩阵 /若找到安全序列则将资源分配给进程Pi/0753 /对相关数据进行修改，得到新的矩阵/1322290232224433进程分配矩阵00101302230232114002进程需求矩阵07431020260030114431各类资源总数1057各类资源剩余数230第几个进程有请求？4第4个进程的各个资源有什么请求？330尚无足够资源，需等待 /无法通过安全性检测，不分配资源给进程Pi/进程最大需求矩阵 /返回原矩阵/07531322290232224433进程分配矩阵00101302230232114002进程需求矩阵07431020260030114431各类资源总数1057各类资源剩余数230第几个进程有请求？0第0个进程的各个资源有什么请求？020已经进行了试分配开始进行安全性检验系统安全,安全序列为：13402进程最大需求矩阵07531322290232224433进程分配矩阵00301302230232114002进程需求矩阵07231020260030114431各类资源总数1057各类资源剩余数210第几个进程有请求？6总结本次课程设计利用面向对象语言Java编写和调试一个动态资源分配程序，报告中阐述了死锁及产生原因，并说明了解决死锁的几种方法，介绍了银行家算法的由来，和利用银行家算法解决问题的一般步骤，最后，通过编写程序模拟计算机内部利用银行家算法资源分配的过程。操作系统作为裸机上安装的第一层软件，起着控制和管理计算机内部软硬件资源，合理组织计算机工作流程，提高计算机工作效率，用户和计算机硬件接口的重要作用。因此操作系统即要保证系统资源的合理分配提高系统资源利用率，同时又要避免死锁等不安全状况的出现，如果这些不安全状况出现操作系统还要解决这些问题，让系统回到安全状态。银行家算法就是在这样的背景下应运而生的。它通过自己特有的算法，在每次奉陪给进程系统资源前，先试探性的“假设”分配资源给进程Pi，再通过安全性算法检测此次分配是否会导致系统进入不安全状态，如果分配后系统依然安全则系统将资源正是分配给进程Pi；如果此次分配导致系统进入不安全状态，则暂不分配资源给进程Pi。通过这种机制，系统可以有效的避免死锁的产生，确保系统时时刻刻都处在安全状态，但银行家算法要不断检测各类进程对系统资源的占用情况，费时较多，这也是它不可忽略的一个劣势。参考文献：1计算机操作系统（第三版）编著：汤子瀛，哲凤屏，汤小丹 出版：西安电子科技大学出版社2操作系统：精髓与设计原理编著：（美）斯托林斯，陈向群出版：机械工业出版社3Java程序设计教程编著：赵莉，杨国梁，徐飞出版：西安电子科技大学出版社附录源程序清单 package com.han;import java.util.Scanner;public class Bank public static void main(String args) Enter i=new Enter();i.shuru();i.shuchu();i.Anquan();for(int x=0;x10;x+)i.Qingqiu();i.Suanfa();i.Anquan();i.shuchu();class Enterstatic int x=100,y=100,i,j,k,q,a,l;int Zong=new inty; /定义总资源向量int Available=new inty; /定义可用资源向量int Max=new intxy;/定义最大需求矩阵int Allocation=new intxy;/定义分配矩阵int Need=new intxy;/定义需求矩阵int Request=new intxy;/定义请求向量boolean Finish=new booleanx;/定义判断是否有足够的资源分配int Work=new inty;/定义工作向量int Shu=new intx;/记录安全序列的数组public Enter()Scanner s=new Scanner(System.in);System.out.println(请输入进程数！);x=s.nextInt();System.out.println(请输入资源种类数！);y=s.nextInt();public void shuru()Scanner s=new Scanner(System.in);System.out.println(请输入各种资源的总量);for(j=0;jy;j+)Zongj=s.nextInt();Availablej=Zongj;for(i=0;ix;i+)System.out.println(请输入第+i+个进程对各种资源的最大需求量n);for(j=0;jy;j+)/stem.out.println(请输入第+i+个进程对各种资源的最大需求量);Maxij=s.nextInt();for(i=0;ix;i+)System.out.println(请输入第+i+个进程对各种资源的分配量情况n);for(j=0;jy;j+)/stem.out.println(请输入第+i+个进程对各种资源的分配量);Allocationij=s.nextInt();Availablej=Availablej-Allocationij;for(i=0;ix;i+)/System.out.println(请输入第+i+个进程的情况n);for(j=0;jy;j+)Needij=Maxij-Allocationij;public void shuchu()System.out.println(进程+t+最大需求矩阵);for(i=0;ix;i+)System.out.print(i+t);for(j=0;jy;j+)System.out.print(Maxij+t);System.out.print(n);System.out.println(进程+t+分配矩阵);for(i=0;ix;i+)System.out.print(i+t);for(j=0;jy;j+)System.out.print(Allocationij+t);System.out.print(n);System.out.println(进程+t+需求矩阵);for(i=0;ix;i+)System.out.print(i+t);for(j=0;jy;j+)System.out.print(Needij+t);System.out.print(n);System.out.println(t+各类资源总数);System.out.print(t);for(j=0;jy;j+)System.out.print(Zongj+t);System.out.println(n+t+各类资源剩余数);System.out.print(t);for(j=0;jy;j+)System.out.print(Availablej+t);public void Qingqiu()Scanner s=new Scanner(System.in);System.out.println(n第几个进程有请求？);k=s.nextInt();System.out.println(第+k+个进程的各个资源有什么请求？);for(j=0;jy;j+)/System.out.println(第+k+个进程的第+j+个资源的请求？);Requestkj=s.nextInt();public void Suanfa()for(j=0;j