Deadlock Characterization:Resource-Allocation Graph System resource-allocation graph:A directed graph oA set of vertices V and a set of edges E. V is partitioned into two types. P=(P1,P2,...,Pn),the set consisting of all the processes in the system. ★○Process R =(R1,R2,...,Rm),the set consisting of all resource types in the system. Resource Type with 4 instances 口⊙生年12月0C 陈香兰(C5,U5TO Operating System OS原理与设i计 March21,201913/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Deadlock Characterization: Resource-Allocation Graph System resource-allocation graph: A directed graph A set of vertices V and a set of edges E. V is partitioned into two types. ▶ P = {P1, P2, . . . , Pn}, the set consisting of all the processes in the system. ⋆ : Process ▶ R = {R1, R2, . . . , Rm}, the set consisting of all resource types in the system. ⋆ : Resource Type with 4 instances 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 13 / 45
Deadlock Characterization:Resource-Allocation Graph System resource-allocation graph:A directed graph oA set of vertices V and a set of edges E. oV is partitioned into two types. oE is partitioned into two types. ~request edge(请求边)-directed edge P,→R P 田 R:P;requests instance of Rj ~assignment edge(分配边)-directed edge R,→Pi 画 R:P;is holding an instance of Rj 口1回年走1,2月Q0 陈香兰(C5,USTO Operating System OS原理与设i计 March21,201913/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Deadlock Characterization: Resource-Allocation Graph System resource-allocation graph: A directed graph A set of vertices V and a set of edges E. V is partitioned into two types. E is partitioned into two types. ▶ request edge(请求边) – directed edge Pi→ Rj ⋆ Pi Rj : Pi requests instance of Rj ▶ assignment edge(分配边) – directed edge Rj →Pi ⋆ Pi Rj : Pi is holding an instance of Rj 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 13 / 45
Example of a Resource Allocation Graph R R3 P2 P3 R2 Ri Figure:example of a resource allocation graph 陈香兰(C5,U5TO Operating System OS原理与设计 March21,201914/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example of a Resource Allocation Graph P1 P2 P3 · R1 · · R2 · R3 · · · R4 Figure: example of a resource allocation graph 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 14 / 45
Example of a resource Allocation Graph With A Deadlock R R3 Q3 R2 R Figure:Example of a resource Allocation Graph With A Deadlock 陈香兰(C5,USTO Operating System OS原理与设计 March21,201915/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example of a resource Allocation Graph With A Deadlock P1 P2 P3 · R1 · · R2 · R3 · · · R4 Figure: Example of a resource Allocation Graph With A Deadlock 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 15 / 45
Graph With A Cycle But No Deadlock R P3 P4 Figure:Graph With A Cycle But No Deadlock 口1⊙注年”年2月00 陈香兰(C5,U5TO Operating System OS原理与设计 March21,201916/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graph With A Cycle But No Deadlock P1 · · R1 · · R2 P2 P3 P4 Figure: Graph With A Cycle But No Deadlock 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 16 / 45