操作系统课程设计报告--基于计算机操作系统银行家算法实现.docx

《操作系统课程设计报告--基于计算机操作系统银行家算法实现.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计报告--基于计算机操作系统银行家算法实现.docx（22页珍藏版）》请在第一文库网上搜索。

1、操作系统课程设计报告题目：银行家算法的设计与实现院（系）：计算机科学与工程学院专业：信息对抗专业基于计算机操作系统银行家算法实现摘要此次课程设计的主要内容是模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生具体用银行家算法实现资源分配。要求如下：(1)设计一个3个并发进程共享3类不同资源的系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。(2)设计用银行家算法和随机分配算法，实现资源分配的两个资源分配程序，应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况。(3)确定一组各

2、进程依次申请资源数的序列，在相同的情况下分别运行上述两种资源分配程序，观察运行结果。银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占用：第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源：第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个

3、算法可用解决生活中的实际问题,如银行贷款等.通过对这个算法的设计,让学生能够对书本知识有更深的理解,在操作和其它方面有更高的提升.关键词：死锁；安全状态；安全序列；银行家算法；安全性检查目录1概述(3)1.1 设计目的(3)1.2 开发环境(3)2需求分析(4)2.1死锁概念(4)2.2死锁的结论(4)2.3资源分类(4)2. 4产生死锁的必要条件(4)2. 5死锁的解决方案(4)2. 5.1产生死锁的例子(4)3. 5.2(5)4. 53安全状态与不安全状态(5)3数据结构分析设计(6)3. 1可利用资源向量矩阵avai1ab1e1(6)3. 2最大需求矩阵max(6)3. 3分配矩阵a11

4、ocation(6)3. 4需求矩阵need(6)4算法的实现4.1U女口(7)4. 2专艮彳丁*(7)4. 3全性检查算法(7)4. 42/ft11(8)5测试与实例分析(10)6心得体会(14)7.参考文献与源程序清单(附录)(15)1概述11设计目的银行家算法是一种最有代表性的避免死锁的算法。把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进

5、程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。本次课程设计通过用JAVA语言编写和调试实现银行家算法的程序，达到进一步掌握银行家算法，理解系统产生死锁的原因以及系统避免死锁的方法，增强理论联系实际的能力的目的。1.2开发环境操作系统：WindowsXP编译工具：Myec1ipse8.6生成文件：.java源代码文件和xxx.c1ass编译文件2需求分析1. 1死锁概念死锁就是指多个进程在运行中因

6、争夺资源而造成的一种僵局，当进程出于这种僵持状态时，若无外力作用，它们都将无法再向前推进。2. 2死锁的结论产生死锁的原因是：竞争资源和进程间推进顺序不当。处理死锁的基本方法是：预防死锁避免思索检测死锁解除死锁3. 3资源分类1 .可剥夺性资源，某些进程在获得此类资源后，该资源可以再被其他进程或系统剥夺。CPU和内存均属于可剥夺性资源。2 .不可剥夺性资源，当系统把这类资源分配给进程后，再不能强行回收，只能在进程用完后自动释放，如磁带机，打印机。3 .非剥夺性资源，在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行构成中，因争夺这些资源而陷入僵局。4 .临时性

7、资源，它是指由一个进程产生，被另一个进程使用一短暂时间后便无用的资源，也称之为消耗性资源。2.4产生死锁的必要条件1 .互斥条件：进程对它所分配到的资源进行排他性使用，即在一段时间内某资源由一个进程占有。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。2 .请求和保持条件:进程已经保持了至少一个资源,但又提出新的资源请求,而该资源又被其他进程占有，此时请求进程阻塞，但又对自己获得的其他资源保持不放。3 .不剥夺条件：进程已经获得的资源，在未使用完之前，不能被剥夺，只有在使用完是由自己释放。4 .环路等待条件：发生死锁时，必然存在一个进程一资源的环形链。2.5死锁

8、的解决方案2.5.1产生死锁的例子该例子是由于进程推进顺序非法引发的死锁：进程P和Pz并发执行,如果按顺序执行：Pi：Request(R1)Pi：Request(R2)Pi：Re1ease(R1)P1：ReIease(R2)P2:Request(R2)P2:Request(R1)P2:ReIease(R2)P2:Re1ease(R1),两个进程可顺利完成。如果按曲线执行：Pi和P2将进入不安全区D,PI保持了资源R1,P2保持了R2,接下来P2将申请不到R1,P1申请不到R2,系统处于不安全状态，往前推进将发生死锁。P1Req(Ri)PIReq(R力PIReI(RI)PIRei(R力图3-15

9、2. 5.2死锁预防预防死锁的方法是使产生死锁的四个必要条件中的2、3、4条件之一不能成立。即：1、摒弃“请求和保持”条件。系统规定所有进程在开始运行之前，都必须一次性申请其在整个运行过程中所需的全部资源。使该进程再整个运行过程中不会提出资源请求，因而摒弃了请求条件。又由于进程在等待期间没有占有任何资源,所以也摒弃了保持条件。2、摒弃“不剥夺”条件。系统规定，进程逐个提出对资源的要求，当一个已经保持了某些资源的进程，再提出新的资源请求而未被满足时，必须释放已经保持的所有资源，待以后需要是在再重新申请。3、摒弃“环路等待”条件。系统规定所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源

10、的请求都必须严格按资源序号递增的顺序提出。2. 5.3安全状态与不安全状态在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前,应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程；否则，令进程等待所谓安全状态是指，系统能按某种进程顺序(P1,P2,P3,，Pn),来为每个进程分配所需资源，直至满足每个进程对资源的最大需求，是每个进曾都可以顺利完成。如果系统找不到这样一个序列，系统就处于不安全状态。虽然并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态。只要系统处于安全状态，系统便可以避免进入不安全状态。因此，避免死

11、锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态安全序列：一个进程序列P1,，Pn是安全的，如果对于每一个进程Pi(1in),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(jvi)当前占有资源量之和。银行家算发就是用具避免死锁的一个有效方法3数据结构分析设计3. 1可利用资源向量矩阵avai1ab1e这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果avai1ab1ej=K,则表示系统中现有R类资源K个3.2 最大需求矩阵max这是一个n*m的矩阵，用以

12、表示每一个进程对In类资源的最大需求。如果maxi,j=K,则表示进程i需要R类资源的数目为K。3.3 分配矩阵a11ocation这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果a11ocationi,j=K,则表示进程i当前已分得R类资源的数目为K。3.4 需求矩阵need这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果needi,j=K,则表示进程i还需要R类资源K个，才能完成其任务。上述矩阵存在下述关系：needi,j=maxi,j-a11ocationi,j4算法的实现4.1初始化1 .创建avai1ab1e数组，用以存放系统中可用的

13、资源数目；2 .创建max数组，用以存放各个进程对各类资源的最大需求数目；3 .创建a11ocation!；数组，用以存放各个进程已经分得的各类资源数目；4 .创建need数组，用以存放各个进程还需要的各类资源数目；5 .创建a11ocation1口；need1；avai1ab1e1,用以存放系统试分配资源前系统资源分配情况；4.2银行家算法设Requesti是进程P1的请求向量，Requesti=K表示进程Pi需要K个j类资源。Pi发出资源请求后，按下列步骤进行检查：1 .如果requestijneedi,j,转向步骤;否则报错，所需要的资源数已超过它所宣布的最大值；2 .如果request

14、ijavai1ab1ej,转向步骤；否则报错，尚无足够资源Pi需等待；3 .尝试将资源分配给进程Pi,并修改下面数据结构中的数值：avaiIab1ej：=avaiIab1ej-raquestij；a11ocationi,j：=a11ocationi,j+raquestij；needi,j：=needi,j-raquestij；4 .执行安全性算法，检查此次资源分配后，系统是否出于安全状态。若安全，才正式将资源分配给进程Pi,已完成本次分配；否则，将本次试探分配作废,恢复原来的资源分配状态，让Pi等待。4.3安全性检查算法1设置两个向量：一、工作向量work：表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时WOrk：=avai1ab1e;二、finish标志：表示系统是否有足够的资源分配给进程，使之运行完成。初始化finishi:=fa1se;有足够资源分配给进程时,令finishi：=trueo2.从进程集合中找到一个能满足下述条件的进程finishi=fa1se;Needi,jworkj;找到执行步骤，否则执行步骤3.当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj：=worki+a11ocationi,j；Finishi：=true；Gotostep；4.如果所有进程的finishi=truc都满足