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