中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)07 Deadlock

Objecttives o To develop a description of deadlocks,which prevent sets of concurrent processes from completing their tasks o To present a number of different methods for preventing or avoiding deadlocks in a compuer system. 口1⊙生年12月0C 陈香兰(C5,U5TO Operating System OS原理与设计 March21,20193/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Objecttives To develop a description of deadlocks, which prevent sets of concurrent processes from completing their tasks To present a number of different methods for preventing or avoiding deadlocks in a compuer system. 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 3 / 45

提纲 Background and System Model 2 Deadlock Characterization Necessary Conditions Resource-Allocation Graph o Methods for Handling Deadlocks 3 Deadlock Prevention(死锁预防) 4 Deadlock Avoidance(死锁避免) Safe State(安全状态) Resource-Allocation Graph Scheme ● Banker's Algorithm(银行家算法) Deadlock Detection(死锁检测)and Recovery 小结和作业 口1⊙,注,1,2月00 陈香兰(C5,U5TO Operating System OS原理与设i计 March21,20194/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 提纲 1 Background and System Model 2 Deadlock Characterization Necessary Conditions Resource-Allocation Graph Methods for Handling Deadlocks 3 Deadlock Prevention (死锁预防) 4 Deadlock Avoidance (死锁避免) Safe State (安全状态) Resource-Allocation Graph Scheme Banker’s Algorithm (银行家算法) 5 Deadlock Detection (死锁检测) and Recovery 6 小结和作业 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 4 / 45

Outline Background and System Model 口1⊙生年12月00 陈香兰(C5,U5TO Operating System OS原理与设计 March21,20195/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 1 Background and System Model 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 5 / 45

The Deadlock Problem deadlock situation A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. Example 1 o System has 2 disk drives. o P and P2 each hold one disk drive and each needs another one. Example 2 Po P o semaphores A and B,initialized to 1 wait(A); wait(B) wait(B); wait(A) 0Q0 陈香兰(C5,U5TO Operating System OS原理与设计 March21,20196/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Deadlock Problem deadlock situation A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. Example 1 System has 2 disk drives. P1 and P2 each hold one disk drive and each needs another one. Example 2 semaphores A and B, initialized to 1 P0 P1 wait (A); wait(B) wait (B); wait(A) 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 6 / 45

Bridge Crossing Example o Traffic is only in one direction. o Each section of a bridge can be viewed as a resource. o If a deadlock occurs,it can be resolved if one car backs up (preempt resources and rollback). o Several cars may have to be backed up if a deadlock occurs. o Starvation is possible. 口1回年走1,2月Q0 陈香兰(C5,U5TO Operating System OS原理与设i计 March21,20197/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bridge Crossing Example Traffic is only in one direction. Each section of a bridge can be viewed as a resource. If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). Several cars may have to be backed up if a deadlock occurs. Starvation is possible. 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 7 / 45

System Model o A system consists of a finite number of resources o The resources are partitioned into several types,each consisting of some number of identical(=equivalent) instances. physical resources:CPU cycles,memory space,l/O devices,.. logical resources:files,semaphores,monitors,.. ●System model Resource types R1,R2,...,Rm Each resource type R has Wi instances. Each process may utilize a resource only as follows: request:may wait until it can acquire the resource. ★use release System call examples:request(/release(devices,open()/ close()files,wait(/signal(,.. 口1回年走1,2月Q0 陈香兰(C5,U5TO Operating System OS原理与设i计 March21,20198/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . System Model A system consists of a finite number of resources The resources are partitioned into several types, each consisting of some number of identical(=equivalent) instances. ▶ physical resources: CPU cycles, memory space, I/O devices, ... ▶ logical resources: files, semaphores, monitors, ... System model ▶ Resource types R1, R2, . . . , Rm ▶ Each resource type Ri has Wi instances. ▶ Each process may utilize a resource only as follows: ⋆ request: may wait until it can acquire the resource. ⋆ use ⋆ release System call examples: request()/release() devices, open()/ close() files, wait()/signal(), ... 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 8 / 45

Outline 2Deadlock Characterization Necessary Conditions Resource-Allocation Graph Methods for Handling Deadlocks 口1⊙生年12月0C 陈香兰(C5,U5TO Operating System OS原理与设i计 March21,20199/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 2 Deadlock Characterization Necessary Conditions Resource-Allocation Graph Methods for Handling Deadlocks 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 9 / 45

Outline 2 Deadlock Characterization Necessary Conditions Resource-Allocation Graph Methods for Handling Deadlocks 口1⊙生年12月0C 陈香兰(C5,U5TO Operating System OS原理与设计 March21,201910/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 2 Deadlock Characterization Necessary Conditions Resource-Allocation Graph Methods for Handling Deadlocks 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 10 / 45

Deadlock Characterization:Necessary Conditions o Deadlock can arise if four conditions hold simultaneously[1]. Mutual exclusion(互斥): only one process at a time can use a resource. ②Hold and wait(特有并等待): a process holding at least one resource is waiting to acquire additional resources held by other processes. No preemption(不剥夺): a resource can be released only voluntarily by the process holding it,after that process has completed its task. ③Circular wait(循环等待): there exists a set (Po,P1,...,Po}of waiting processes such that Po is waiting for a resource that is held by P1,P1 is waiting for a resource that is held by P2,...,Pn-1 is waiting for a resource that is held by Pn,and Pn is waiting for a resource that is held by Po. 口1回年走1,2月Q0 陈香兰(C5,U5TQ Operating System OS原理与设计 March21,201911/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Deadlock Characterization: Necessary Conditions Deadlock can arise if four conditions hold simultaneously[1]. 1 Mutual exclusion(互斥): only one process at a time can use a resource. 2 Hold and wait(持有并等待): a process holding at least one resource is waiting to acquire additional resources held by other processes. 3 No preemption(不剥夺): a resource can be released only voluntarily by the process holding it, after that process has completed its task. 4 Circular wait(循环等待): there exists a set {P0, P1, . . . , P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, . . . , Pn−1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0. 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 11 / 45

Outline 2 Deadlock Characterization o Necessary Conditions o Resource-Allocation Graph Methods for Handling Deadlocks 口1⊙生年12月0C 陈香兰(C5,U5TO Operating System OS原理与设i计 March21,201912/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 2 Deadlock Characterization Necessary Conditions Resource-Allocation Graph Methods for Handling Deadlocks 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 12 / 45
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)06 Process Synchronization.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)05 Threads.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)04 CPU Scheduling.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)03 Processes.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)02 OS Structure.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)01 CS Structure.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)01 OS overview.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)课程简介(主讲:陈香兰).pdf
- 中国科学技术大学:《高级操作系统 Advanced Operating System》课程教学资源(PPT课件讲稿)第二章 分布式路由算法(2/2).ppt
- 中国科学技术大学:《高级操作系统 Advanced Operating System》课程教学资源(PPT课件讲稿)第二章 分布式路由算法主要内容(1/2,主讲:陈香兰).ppt
- 天津开放大学:《电子商务概论》课程教学资源(试卷习题)综合练习及答案.doc
- 国家开放大学:《计算机应用基础》课程教学资源(章节习题,含答案)计算机网络应用基础练习_第三章.doc
- 国家开放大学:《计算机应用基础》课程教学资源(章节习题,含答案)计算机安全练习_第七章.doc
- 国家开放大学:《计算机应用基础》课程教学资源(章节习题,含答案)计算机基础知识练习_第一章.doc
- 国家开放大学:《计算机应用基础》课程教学资源(章节习题,含答案)Word 2010文字处理系统练习_第四章.doc
- 国家开放大学:《计算机应用基础》课程教学资源(章节习题,含答案)Windows 7操作系统及应用练习_第二章.doc
- 国家开放大学:《计算机应用基础》课程教学资源(章节习题,含答案)PowerPoint 2010电子演示文稿系统练习_第六章.doc
- 国家开放大学:《计算机应用基础》课程教学资源(章节习题,含答案)Excel 2010电子表格系统练习_第五章.doc
- 国家开放大学:2016年秋季学期“开放专科”电子商务专业电子商务法律与法规期末试题(1月).pdf
- 国家开放大学:2016年秋季学期“开放专科”电子商务专业数据库基础期末试题(1月).pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)08 Main Memory.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)09 虚拟内存 Virtual Memory.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)10 文件系统接口 File System Interface.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)11 File 文件系统实现 File system implementation.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)12 外存 Mass Storage Systems.pdf
- 中国科学技术大学:《操作系统原理与设计 Operating System》课程教学资源(PPT课件讲稿)13 IO管理 IO systems.pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(课件讲义)GNU开发工具链简介 GNU Tools(主讲:陈香兰).pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(课件讲义)基于x86的Linux启动代码分析.pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(课件讲义)制作简单的Linux系统.pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(PPT课件讲稿)内存寻址.ppt
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(PPT课件讲稿)Linux进程管理(1/3).ppt
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(PPT课件讲稿)Linux进程管理(2/3).ppt
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(课件讲义)中断和异常.pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(课件讲义)系统调用.pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(PPT课件讲稿)Linux进程管理(3/3).ppt
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(课件讲义)内存管理.pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(课件讲义)Linux中的时钟和定时测量.pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(课件讲义)Linux中的进程地址空间.pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(课件讲义)程序的执行.pdf
- 中国科学技术大学:《Linux操作系统分析》课程教学资源(PPT课件讲稿)文件系统.ppt