[理学]第5章_并发性：死锁和饥饿.ppt

第5章 并发性:死锁和饥饿 Outline 死锁原理 死锁预防 死锁避免 死锁检测和恢复 死锁图示 死锁的概念 死锁：一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件（释放占有资源/进行某项操作） 死锁是多个进程因竞争资源且推进顺序不合理而造成的一种僵局，若无外力作用，这些进程将永远不能再向前推进 可重用资源与可消费资源 可重用资源 一次只能供一个进程安全地使用，且不会由于使用而耗尽 例如： 处理器, I/O通道, 主存和辅存, 设备, 文件、数据库、信号量等数据结构 可重用资源与可消费资源 可消费资源 可以创建(生产)并且可以销毁(消费)的资源 数目没有限制, 当一个进程得到一个可消费资源时，这个资源就不再存在了 例如： 中断, 信号, 消息, I/O缓冲区中的信息 死锁的例子(1) 死锁的例子(2) 设共有200KB可用的分配空间 死锁的例子（3） 死锁的条件(续) 不可剥夺 进程已获得的资源在未使用完之前不能被剥夺，只能在使用完时由自己释放 环路等待 资源分配图中存在封闭的进程链，即进程集合 {P0, P1, P2, …, Pn}(n=2) 中的 P0 正在等待一个 P1 占用的资源； P1 正在等待 P2 占用的资源, ……, Pn 正在等待已被 P0 占用的资源. 处理死锁的基本方法 预防死锁 避免死锁 检测死锁 排除死锁 鸵鸟算法 对死锁视而不见 死锁预防 通过破坏产生死锁的四个条件中的一个或多个条件，保证不会发生死锁 破坏互斥条件 方法 允许多个进程同时使用资源 适用条件 资源的固有特性允许多个进程同时使用（如文件允许多个进程同时读） 借助特殊技术允许多个进程同时使用（如打印机借助Spooling技术） 缺点 不适用于绝大多数资源 破坏占有及等待条件 方法 禁止已拥有资源的进程再申请其他资源，如要求所有进程在开始时一次性地申请在整个运行过程所需的全部资源，或申请资源时要先释放其占有资源再一次性申请所需全部资源 优点 简单、易于实现、安全 缺点 进程延迟运行 资源严重浪费 破坏不可剥夺条件 方法 一个已经占有了某些资源的进程, 当它再提出新的资源请求而不能立即得到满足时, 必须释放它已经占有的所有资源, 待以后需要时再重新申请 OS可以剥夺一个进程占有的资源, 分配给其他进程 适用条件 资源的状态可以很容易地保存和恢复(如CPU) 缺点 实现复杂、代价大, 反复申请/释放资源, 系统开销大, 降低系统吞吐量 破坏环路等待条件 方法 要求每个进程任何时刻只能占有一个资源，如果要申请第二个则必须先释放第一个（不现实） 对所有资源按类型进行线性排队，进程申请资源必须严格按资源序号递增的顺序 缺点 很难找到令每个人都满意的编号次序，类型序号的安排只能考虑一般作业的情况, 限制用户简单、自主地编程，易造成资源浪费 死锁避免 不需事先采取限制措施破坏产生死锁的条件，而是在资源的动态分配过程中， 采用某种策略防止系统进入不安全状态， 从而避免发生死锁。 安全状态和不安全状态 安全状态 系统能按某种顺序, 如P1, P2, …, Pn, 为每个进程分配所需资源, 直到最大需求, 使每个进程都可顺利完成, 称系统处于安全状态 安全序列 上述的资源分配顺序，如P1, P2, …, Pn 安全序列可以不唯一！ 不安全状态 系统中不存在安全序列 安全状态和不安全状态（续1） 安全状态例子（一种资源） 安全状态和不安全状态（续2） 不安全状态例子（一种资源） 死锁避免 只要系统处于安全状态，必定不会进入死锁状态 不安全状态不一定是死锁状态，但不保证不进入死锁状态 死锁避免的实质：如何使系统不进入不安全状态 如果一个新的进程的资源请求会导致不安全状态, 则拒绝启动这个进程 如果满足一个进程新提出的一项资源请求会导致不安全状态, 则拒绝分配资源给这个进程 ?拒绝启动进程策略 在启动一个新的进程时, 首先检查它的资源请求,仅当当前所有进程的最大资源请求量 + 新进程的请求量 = 系统资源量才启动新进程. 考虑所有进程的最大请求, 条件过于严格 拒绝资源请求策略—银行家算法 对进程的每一个资源请求进行检查，如果满足它会引起不安全状态，则不满足该请求，否则就满足该请求。 银行贷款问题的描述 银行有一笔数目有限的现金可供借贷，以及一批借贷客户 每个客户有各自的借款限额（最大借款额）；客户可在借款限额范围内一次借贷一部分现金，且不保证在获得最大贷款额之前做出任何偿付 如果在满足一个客户的一次借贷请求之后，银行可能没有足够的资金以保证所有客户最终偿还所有贷款，那么银行可以拒绝这项请求 银行贷款问题的描述 例: 某银行共有资金100万元和三个借贷客户甲、乙、丙 他们的最大借款额分别为100, 80,