Basic Facts If graph contains no cycles=no deadlock. If graph contains a cycle= if only one instance per resource type,then deadlock. if several instances per resource type,possibility of deadlock. 口1⊙生年12月00 陈香兰(C5,U5TO Operating System OS原理与设i计 March21,201917/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Basic Facts If graph contains no cycles ⇒ no deadlock. If graph contains a cycle ⇒ ▶ if only one instance per resource type, then deadlock. ▶ if several instances per resource type, possibility of deadlock. 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 17 / 45
Outline 2 Deadlock Characterization o Necessary Conditions Resource-Allocation Graph Methods for Handling Deadlocks 口1⊙生年12月0C 陈香兰(C5,USTO Operating System OS原理与设i计 March21,201918/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 2 Deadlock Characterization Necessary Conditions Resource-Allocation Graph Methods for Handling Deadlocks 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 18 / 45
Methods for Handling Deadlocks Ensure that the system will never enter a deadlock state. Deadlock prevention Deadlock avoidance Allow the system to enter a deadlock state and then recover. Deadlock detection and recovery from deadlock Ignore the problem and pretend that deadlocks never occur in the system;used by most operating systems,including UNIX. request →allocation→ runtime 个 prevention avoidance detection and recovery 陈香兰(C5,U5TO Operating System OS原理与设计 March21,201919/45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Methods for Handling Deadlocks 1 Ensure that the system will never enter a deadlock state. 1 Deadlock prevention 2 Deadlock avoidance 2 Allow the system to enter a deadlock state and then recover. 1 Deadlock detection and recovery from deadlock 3 Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX. request → allocation → runtime ↑ ↑ ↑ prevention avoidance detection and recovery 陈香兰 (CS, USTC) Operating System OS原理与设计 March 21, 2019 19 / 45