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