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