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