操作系统课程设计---银行家算法.docVIP

课 程 设 计 银行家算法 2011 年 6 月  课程设计任务书 设 计 题 目 银行家算法 成绩 主 要 内 容 进程死锁的避免：银行家算法，教材P127-129页。（1人） 建立银行家算法的数据结构描述； 将初始数据放在文件中，算法运行时读出； 对给定的资源请求，使用算法判断是否允许； 输出每次判断产生的执行序列； 指 导 教 师 意 见 该生能按时完成课程设计任务书所规定的程序设计，综合运用所学知识独立分析和解决问题的能力 。程序设计方案 。论文论述 ，文理 ，格式 。程序运行结果 。程序验收时回答问题 。 签名： 1前言 ： Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。 它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留单位的资金来为客户服务，而不是单位。 这里将客户比作进程，贷款比作设备，银行家比作系统。 客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所的贷款如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。 银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。 检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。 如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。 但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。 而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。 利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。 课程设计的任务 一、将初始数据放在文件中，算法运行时读出； 二、对给定的资源请求，使用算法判断是否允许； 三、输出每次判断产生的执行序列； 相关原理及算法描述 3.1 预备知识 银行家算法是一种最具有代表性的避免死锁的算法。 要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。 所谓安全状态，是指系统能按照某种进程顺序{P1,P2,…，Pn}（称{P1,P2,…，Pn }序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。 如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 如果对每一个进程Pi(1in)，它以后尚需要的资源量不超过系统当前可利用的资源量与所有的进程Pj(jn)所占有的资源量之和，则称此进程序列{P1,P2,…，Pn}是安全的，称作安全序列。 3.2银行家算法 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。 操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 3.3基本要求 （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预