计算机操作系统-银行家算法

1、操作系统课程设计题目：银行家算法的设计与实现系 别： 计算机信息与技术系 专 业： 计算机科学与技术 班 级： B130601 姓 名： 伏海龙 学 号： B13060105 指导教师 ： 魏少华 2016年01月摘要此次课程设计的主要内容是模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并用适当的算法，有效的防止和避免死锁的发生。银行家算法是一个避免死锁的一种重要方法，通过高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一

2、个进程占用；第二个为等待条件，即一个进程请求资源不能满足时，他必须等待，但他仍继续保持已得到的所有其他资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待他前一个进程所持有的资源。当不满足以上条件时就能防止系统的死锁，让系统流畅运行。通过该算法可以解决生活中的实际问题，如银行贷款等。通过对该算法的设计，让学生能够对书本的知识有更深刻的理解，在操作和其他方面有大幅度的提高。目录 TOC o 1-3 h z u HYPERLINK l _Toc439675935 1. 概述 PAGEREF _Toc439675935 h 1 HYPERLINK l _Toc4396

3、75936 1.1设计目的 PAGEREF _Toc439675936 h 1 HYPERLINK l _Toc439675937 2. 需求分析 PAGEREF _Toc439675937 h 1 HYPERLINK l _Toc439675938 2.1死锁概念 PAGEREF _Toc439675938 h 1 HYPERLINK l _Toc439675939 2.2死锁的结论 PAGEREF _Toc439675939 h 2 HYPERLINK l _Toc439675940 2.3资源分类 PAGEREF _Toc439675940 h 2 HYPERLINK l _Toc439

4、675941 2.4产生死锁的必要条件 PAGEREF _Toc439675941 h 2 HYPERLINK l _Toc439675942 2.5银行家算发的意义 PAGEREF _Toc439675942 h 3 HYPERLINK l _Toc439675943 3. 数据结构分析设计 PAGEREF _Toc439675943 h 3 HYPERLINK l _Toc439675944 3.1可利用资源向量矩阵available PAGEREF _Toc439675944 h 3 HYPERLINK l _Toc439675945 3.2最大需求矩阵max PAGEREF _Toc4

5、39675945 h 3 HYPERLINK l _Toc439675946 3.3分配矩阵allocation PAGEREF _Toc439675946 h 3 HYPERLINK l _Toc439675947 3.4需求矩阵need PAGEREF _Toc439675947 h 3 HYPERLINK l _Toc439675948 4. 算法的实现 PAGEREF _Toc439675948 h 4 HYPERLINK l _Toc439675949 4.1初始化 PAGEREF _Toc439675949 h 4 HYPERLINK l _Toc439675950 4.2银行家算

6、法 PAGEREF _Toc439675950 h 4 HYPERLINK l _Toc439675951 4.3算法流程图 PAGEREF _Toc439675951 h 6 HYPERLINK l _Toc439675952 4.3.1.初始化算法流程图： PAGEREF _Toc439675952 h 6 HYPERLINK l _Toc439675953 4.3.2银行家算法流程图： PAGEREF _Toc439675953 h 7 HYPERLINK l _Toc439675954 5.测试与实例分析 PAGEREF _Toc439675954 h 8 HYPERLINK l _T

7、oc439675955 6.实验总结 PAGEREF _Toc439675955 h 9 HYPERLINK l _Toc439675956 参考文献 PAGEREF _Toc439675956 h 101. 概述1.1设计目的银行家算法是一种最具代表性的避免死锁的算法。把笑傲作死同看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次分配资源时，要测试进程对资源的最大需求量，如果系统现存的资源可以满足他的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先

8、测试该进程已占用的子元素与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，反之则在测试系统现存的资源是否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配本次课程设计通过C语言编写和调试实现银行家算法的程序，达到进一步掌握银行家算法，理解系统产生死锁的原因以及避免死锁的方法，增强联系实际能力的目的。2. 需求分析2.1死锁概念死锁就是指多个进程在运行中因争夺资源而造成的一种僵局，当进程出这中僵持状态时，若无外力作用，他们就我无法进行运作。2.2死锁的结论产生死锁的原因是：竞争资源和进程推进顺序不当处理死锁的基本方法是：预防死锁，避免死锁

9、，检测死锁，解除死锁。2.3资源分类1.可剥夺性资源，某些进程在获得此类资源后，该资源可以被其他进程或系统比多。CPU和每寸均属于可剥夺性资源。2.不可剥夺性资源，当系统把类资源分配给进程后，不能强行收回，只能在进程用完后自动释放，如磁带机，打印机3.非剥夺性资源，在系统中所配置的非剥夺性资源，由于他们的数量不能满足诸进程的需要，会使进程在运行中，因争夺这些资源而陷入僵局。4.临时资源，他是指由一个进程产生，倍另一个进程使用短暂时间后便无用的资源，也称之为消耗性资源。2.4产生死锁的必要条件1.互斥条件：进程对他所分配的资源进行排他性使用，即在一段时间内摸个资源由一个进程占有。如果此时还有其他

10、进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。2.请求和保持条件：进程已经保持了至少一个资源，但又提出新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但有对自己获得的其他资源保持不放。3.不剥夺条件：进程已获得的资源，在未使用完之前，不能剥夺，只有在使用完由自己释放。4环路等待条件：发生死锁时，必然存在一个进程一资源的环形链。2.5银行家算发的意义依次对进程测试，直到每一进程能够运行并释放，从而实现了避免死锁的功能。也能提供多种序列可完美实现要求。3. 数据结构分析设计3.1可利用资源向量矩阵available 这是一个含有m个元素的数组，其中每一个元素代表一类可利

11、用的资源数目，其初始值是系统中所配置的该类全部可用资源数目，起数值随该类资源的分配和回收而动态地改变。如果availablej=k，则表示系统中现有R类资源K个3.2最大需求矩阵max 这是一个n*m的矩阵，用以表示每一个进程对m类资源的最大需求。如果maxi,j=K，则表示进程i需要R类资源的数目为K。3.3分配矩阵allocation这也是一个n*m的矩阵，他/她定义了系统中每一类资源当前已分配给每一进程的资源数。如果allocationi，j=K，则表示进程i当前已分得R类资源的数目为K。3.4需求矩阵need这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果need i

12、，j =K，则表示进程i 还需要R类资源K个，才能完成其任务。上述矩阵存在下述关系:Needi,j=maxi,j-allocationi,j4. 算法的实现4.1初始化1.创建available数组，用以存放系统中可用的资源数目；2.创建max数组，用以存放各个进程对各类资源的最大需求数目；3.创建allocation数组，用以存放各个进程已经分得的各类资源数目；4.创建need 数组，用以存放个各个进程还需要的各类资源数目；5.创建allocationl；need;availablel，用以存放系统试分配资源前系统资源分配情况；4.2银行家算法设Request是请求P的请求向量，Request=K表示进程P需要K个j类资源。P发出资源请求后，按下列步骤进行检查：如果reques j=needi,j，转向步骤；否则报错，所需要的资源数已超过它所宣布的最大值；如果requestjNEEDi或者REQUESTiAVAILABLEi报错，重新输入AVAILABLEi-=REQUEST i;ALLOCATIONi+=REQUEST i;NEEDi-=REQUESTi;初始化安全性检查安全AVAILABLEi+=REQUEST i;ALLOCATIONi-=REQUEST i;NEEDi+=REQUESTi;保持原分配进程执行完释放资源继续分