第4章 死锁(第2讲)

《操作系统》 第四章死锁(第2讲) 主讲：黄伯虎 Xidian University Operating Systems -2- 上一讲内容回顾 死锁的基本概念  死锁的定义  死锁产生的必要条件 死锁的解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载  鸵鸟 政策 公共政策概论形成性考核册答案公共政策概论形成性考核册答案2018本科2018公共政策概论形成性考核册答案公共政策概论作业1答案公共政策概论形成考核册答案  让死锁发生，事后处理  不让死锁发生  死锁的预防  死锁的避免 Xidian University Operating Systems -3- 五、死锁的避免 多项资源银行家算法*  适用于一个进程申请多个资源的情况。  举例：系统中有以下资源：5台打印机，7个手写板，8台扫描仪，9个读卡 器，共有5个进程T1、T2、T3、T4、T5共享这些资源。各进程所需最大资源 量和当前各进程已经得到的资源数量如下图，问如果进程T2此时希望得到1 台打印机,1个手写板,2个读卡器是否可以满足? Xidian University Operating Systems -4- 五、死锁的避免 sum(1)=(2,4,3,1) sum(2)=(2,2,0,5) sum(3)=(1,5,5,0) sum(4)=(5,0,1,3) sum(5)=(0,3,3,3) allocation(1)=(0,1,2,1) allocation(2)=(1,1,0,2) allocation(3)=(0,3,4,0) allocation(4)=(2,0,0,1) allocation(5)=(0,0,1,3) claim(1)=(2,3,1,0) claim(2)=(1,1,0,3) claim(3)=(1,2,1,0) claim(4)=(3,0,1,2) claim(5)=(0,3,2,0) Xidian University Operating Systems -5- 五、死锁的避免 步骤：  比较claim(i)和available向量，寻找满足下列关系的进程: claim(i) < available claim(1)=(2,3,1,0) claim(2)=(1,1,0,3) claim(3)=(1,2,1,0) claim(4)=(3,0,1,2) claim(5)=(0,3,2,0) available=(2,2,1,2) allocation(1)=(0,1,2,1) allocation(2)=(1,1,0,2) allocation(3)=(0,3,4,0) allocation(4)=(2,0,0,1) allocation(5)=(0,0,1,3) available=(2,5,5,2)+ claim(1)=(2,3,1,0) claim(2)=(1,1,0,3) claim(3)=(x,x,x,x) claim(4)=(3,0,1,2) claim(5)=(0,3,2,0) Xidian University Operating Systems -6- 五、死锁的避免 claim(1)=(2,3,1,0) claim(2)=(1,1,0,3) claim(3)=(x,x,x,x) claim(4)=(3,0,1,2) claim(5)=(0,3,2,0) available=(2,5,5,2) allocation(1)=(0,1,2,1) allocation(2)=(1,1,0,2) allocation(3)=(0,3,4,0) allocation(4)=(2,0,0,1) allocation(5)=(0,0,1,3) available=(2,6,7,3)+ claim(1)=(x,x,x,x) claim(2)=(1,1,0,3) claim(3)=(x,x,x,x) claim(4)=(3,0,1,2) claim(5)=(0,3,2,0) Xidian University Operating Systems -7- 五、死锁的避免 claim(1)=(x,x,x,x) claim(2)=(1,1,0,3) claim(3)=(x,x,x,x) claim(4)=(3,0,1,2) claim(5)=(0,3,2,0) available=(2,6,7,3) allocation(1)=(0,1,2,1) allocation(2)=(1,1,0,2) allocation(3)=(0,3,4,0) allocation(4)=(2,0,0,1) allocation(5)=(0,0,1,3) available=(3,7,7,5)+ claim(1)=(x,x,x,x) claim(2)=(x,x,x,x) claim(3)=(x,x,x,x) claim(4)=(3,0,1,2) claim(5)=(0,3,2,0) Xidian University Operating Systems -8- 五、死锁的避免 claim(1)=(x,x,x,x) claim(2)=(x,x,x,x) claim(3)=(x,x,x,x) claim(4)=(3,0,1,2) claim(5)=(0,3,2,0) available=(3,7,7,5) claim(1)=(x,x,x,x) claim(2)=(x,x,x,x) claim(3)=(x,x,x,x) claim(4)=(x,x,x,x) claim(5)=(0,3,2,0) allocation(1)=(0,1,2,1) allocation(2)=(1,1,0,2) allocation(3)=(0,3,4,0) allocation(4)=(2,0,0,1) allocation(5)=(0,0,1,3) available=(5,7,7,6)+ Xidian University Operating Systems -9- 五、死锁的避免 claim(1)=(x,x,x,x) claim(2)=(x,x,x,x) claim(3)=(x,x,x,x) claim(4)=(x,x,x,x) claim(5)=(0,3,2,0) available=(5,7,7,6) claim(1)=(x,x,x,x) claim(2)=(x,x,x,x) claim(3)=(x,x,x,x) claim(4)=(x,x,x,x) claim(5)=(x,x,x,x) allocation(1)=(0,1,2,1) allocation(2)=(1,1,0,2) allocation(3)=(0,3,4,0) allocation(4)=(2,0,0,1) allocation(5)=(0,0,1,3) available=(5,7,8,9)+ Xidian University Operating Systems -10- 五、死锁的避免 单银行家算法和多银行家算法的异同  不同点:  多银行家算法使用向量进行计算，单银行家算法使用单个整数 值。  相同点  思想和算法流程完全一样。 Xidian University Operating Systems -11- 六、死锁的检测和解除 死锁的检测*  检测工具——资源分配图  资源分配图：是描述进程申请资源和资源分配情况的关系模型图。 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示系统中某个时刻进程对资源的申请和占有情况。 规则： （1）圆(椭圆)表示一个进程； （2）方块表示一个资源类，其中的圆点表示该类型资源中的单 个资源； （3）从资源指向进程的箭头表示资源被分配给了这个进程； （4）从进程指向资源的箭头表示进程申请一个这类资源； Xidian University Operating Systems -12- 六、死锁的检测和解除 Xidian University Operating Systems -13- 六、死锁的检测和解除 资源分配图中的所有进程如果都能化简成孤立 结点，则这个资源图就是可完全化简的 （completely reducible）；反之，就是不可完 全化简的（irrreducible）。 死锁定理：如果一个系统状态为死锁状态， 当且仅当资源分配图是不可完全化简。也 即，如果资源图中所有的进程都成为孤立结 点，则系统不会死锁；否则系统状态为死锁 状态。 结论：系统不会发生死锁 Xidian University Operating Systems -14- 六、死锁的检测和解除 举例  资源分配图如下，请分别化简并说明是否会发生死锁。 Xidian University Operating Systems -15- 六、死锁的检测和解除 Xidian University Operating Systems -16- 六、死锁的检测和解除 临时资源的死锁检测  临时性资源：即可消耗的资源。如信号、消息、邮件等。  特点：没有固定数目；不需要释放。  表述方式——重定义的资源分配图  规则： ① 圆表示一个进程； ② 方块表示一个资源类，其中的圆点表示该类型资源中的单个资源； ③ 由进程指向资源的箭头表示该进程申请这种资源，一个箭头只表示申 请一个资源； ④ 由资源类指向进程的箭头表示该进程产生这种资源，一个箭头可表示 产生一到多个资源，每个资源类至少有一个生产者进程。 Xidian University Operating Systems -17- 六、死锁的检测和解除  死锁判断标准  分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ： ① 对于临时性资源来讲，它有生产者，生产者会源源不断的生产资源， 因此只要生产者进程不被阻塞，可以认为资源最终一定是充分的，可 以满足各消费进程的需要。 ② 一个进程死锁意味着永久被阻塞。需要的资源可以满足则进程一定不 会死锁。  结论： 判断系统是否死锁的关键在于判断生产者进程的状态，若生产者 进程不被阻塞，则可以认为它总会生产出该类资源，也就是说， 申请这类资源的所有申请者进程都可以得到满足。 Xidian University Operating Systems -18- 六、死锁的检测和解除  检测 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ——化简  方法： ① 从那些没有阻塞的进程入手，删除那些没有阻塞的进程的请求边，并 使资源类中资源数（图中黑点的数目）减1。 ② 重复以上步骤直至： a. 图中所有的请求边都已经删除，则不会死锁 b. 图中仍然存在请求边但无法再化简，系统死锁。 Xidian University Operating Systems -19- 六、死锁的检测和解除 死锁检测举例  资源分配图如下（表示临时性资源），请分别化简并说明是否会发生 死锁： Xidian University Operating Systems -20- 六、死锁的检测和解除 Xidian University Operating Systems -21- 六、死锁的检测和解除 死锁的解除  重新启动  这是一种常用但比较粗暴的方法，虽然实现简单，但会使之前的 工作全部白费，造成很大的损失和浪费。  撤消进程  死锁发生时，系统撤消造成死锁的进程，解除死锁。  一次性撤消所有的死锁进程。损失较大。  逐个撤消，分别收回资源。具体做法：系统可以先撤消那些优先 级低的、已占有资源少或已运行时间短的、还需运行时间较长的 进程，尽量减少系统的损失。 Xidian University Operating Systems -22- 六、死锁的检测和解除  剥夺资源  死锁时，系统保留死锁进程，只剥夺死锁进程占有的资源，直到 解除死锁。选择被剥夺资源进程的方法和选择被撤消进程相同。  进程回退  死锁时，系统可以根据保留的历史信息，让死锁的进程从当前状 态向后退回到某种状态，直到死锁解除。  实现方法：可以通过结合检查点或回退（checkpoint/Rollback） 机制实现。进程某一时刻的瞬间状态叫做检查点，可以定期设置 检查点。系统保存所有的检查点。一旦系统检查到有某个进程卷 入了死锁，该进程就会被终止，剥夺它占有的所有资源。然后， 系统查看保存的检查点信息，重新建立该进程的状态，从上次检 查点的位置重新执行。目前发展已比较成熟，广泛用于DBMS 中。 Xidian University Operating Systems -23- 作业 P133 习题11，12