操作系统银行家算法

《操作系统银行家算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计课程名称操作系统学生学院计算机学院专业班级2011级计算机科学与技术7班学号3111006002学生姓名谢佳旭2014年1月07日一、设计目的通过银行家算法设计与实现，可以加深学生对死锁的理解，掌握死锁的预防、避免、检测和解除的基本原理，重点掌握死锁的避免方法—银行家算法。使学生初步具有研究、设计、编制和调试操作系统模块的能力。二、死锁概念在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险━━死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Dead

2、ly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。三、关于死锁的一些结论1、参与死锁的进程最少是两个（两个以上进程才会出现死锁）2、参与死锁的进程至少有两个已经占有资源3、参与死锁的所有进程都在等待资源4、参与死锁的进程是当前系统中所有进程的子集四、产生死锁的四个必要条件：1、互斥使用（资源独占）一个资源每次只能给一个进程使用2、不可强占（不可剥夺）资源申请者不能强行的从资源占

3、有者手中夺取资源，资源只能由占有者自愿释放3、请求和保持（部分分配，占有申请）一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）4、循环等待存在一个进程等待队列{P1,P2,…,Pn},其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路五、死锁的解决方案5.1产生死锁的例子申请不同类型资源产生死锁P1：…申请打印机申请扫描仪使用释放打印机释放扫描仪…P2：…申请扫描仪申请打印机使用释放打印机释放扫描仪…申请同类资源产生死锁（如内存）设有资源R，R有m个分配单位，由n个

4、进程P1,P2,…,Pn（n>m）共享。假设每个进程对R的申请和释放符合下列原则：*一次只能申请一个单位*满足总申请后才能使用*使用完后一次性释放m=2，n=3资源分配不当导致死锁产生5.2死锁预防:定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一①破坏“不可剥夺”条件在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请②破坏“请求和保持”条件要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满

5、足时才给予一次性分配③破坏“循环等待”条件采用资源有序分配法：把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。六、设计思想我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否

6、超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。七、算法：n：系统中进程的总数m：资源类总数Available:ARRAY[1..m]ofinteger;Max:ARRAY[1..n,1..m]ofinteger;Allocation:ARRAY[1..n,1..m]ofinteger;Need:ARRAY[1..n,1..m]ofinteger;Request:ARRAY[1..n,1..m]ofinteger;符号说明：Av

7、ailable可用剩余资源Max最大需求Allocation已分配资源Need需求资源Request请求资源当进程pi提出资源申请时，系统执行下列步骤：(“=”为赋值符号，“==”为等号)（1）若Request<=Need,gotostep（2）；否则错误返回（2）若Request<=Available,gotostep（3）；否则进程等待（3）假设系统分配了资源，则有：Available=Available-Request;Allocation=Allocation+Request;Need=Need-Request若系统新状态是安全的，则分配完

8、成若系统新状态是不安全的，则恢复原状态，进程等待为进行安全性检查，定义数据结构：Work:ARRAY[1..m]ofint