操作系统课程设计报告.doc

OS课程设计.银行家算法模拟

操作系统
课程设计报告
题目：银行家算法模拟

所在学院：信息工程学院
班级：计科1001
学号：101304116
姓名：陆佳林
指导教师：邹姝稚
成绩：

2013年1月13日
1序言
Dijkstra(1965)提出了一种能够避免死锁的调度算法，称为银行家算法。
它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。
这里将客户比作进程，贷款比作设备，银行家比作系统。
客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。
银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。
检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。
2设计目的
进行该课程设计主要是在掌握了采用银行家算法避免死锁的基础上，设计一个程序来模拟操作系统在避免死锁时采用的银行家算法策略，加深对银行家算法的理解，掌握银行家算法避免死锁的全过程及其原理。同时提高运用操作系统理论知识解决实际问题的能力，并锻炼实际的编程能力、创新能力，以及提高调查研究、查阅技术文档、编写软件设计文档的实践动手能力。

3算法分析与设计
3.1算法原理及基本要求
3.1.1银行家算法原理
我们可以把HYPERLINK"http://baike.baidu.com/view/880.htm"\t"_blank"操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全,银行家规定:
(1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2)顾客可以分期贷款,但贷款的总数不能超过最大需求量;
(3)当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4)当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。3.1.2死锁产生的条件
银行家算法是用来避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。
死锁的产生，必须同时满足四个条件：
A、即一个资源每次只能由一个进程使用；
B、第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，单它仍继续宝石已得到的所有其他资源；
C、第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；
D、第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。
防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。银行家算法是避免死锁的方法中，施加的限制条件较弱的，有利于获得令人满意的系统性能的方法。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。3.1.3基本要求
（1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。
（2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。
（3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况：
A.所申请的资源大于其所需资源，提示分配不合理不予分配并返回
B.所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回。
C.所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查：
a.预分配后系统是