CS241 System Programming Deadlock Issues (2)ContentAdministrative NotesDeadlock Modeling (1)Deadlock Modeling (2)Deadlock Modeling (3)Deadlock Modeling (4)Resource Allocation Graph (multiple resource types)Deadlock ModelStrategiesThe Ostrich AlgorithmAlgorithms to deal with DeadlockDeadlock DetectionDetection with One Resource of Each Type (1)Wait for GraphsRecovery from Deadlock (1)Recovery from Deadlock (2)Deadlock Prevention: Havender's AlgorithmsSummary: Deadlock PreventionReminderCS241 System ProgrammingDeadlock Issues (2)Klara NahrstedtLecture 172/27/200601/14/19 CS 241 - System Programming, Klara Nahrstedt2ContentDeadlock ModelingDeadlock Detection and RecoveryDeadlock Prevention01/14/19 CS 241 - System Programming, Klara Nahrstedt3Administrative NotesMP2 on Monday, February 27Homework 1 – Deadline March 6 – Individual Effort (No Collaboration with your MP partner or other pairs partners)Quiz 5 – March 3, 2006–Covers Signals, Timers and Deadlock Tanenbaum 3.3.1, 3.3.2, 3.3.3, 3.3.4 and 3.3.5R&R: Signals 8.1-8.5, R&R: Signal Handling and Threads 13.5R&R: 9.1, 9.2, 9.3, 9.4, 9.5Lecture Notes: lec13-sched, lec14-sched, lec15-sched, lec16-deadlock, lec17-deadlock01/14/19 CS 241 - System Programming, Klara Nahrstedt4Deadlock Modeling (1) 1972 – Holt showed that the four conditions can be modeled using directed graphs Graph have two kinds of nodes–Processes –Resources Graph’s arcs have two meanings:–Arc from resource node to process node = process holds resource (i.e., resource has been assigned to process and process is holding it)–Arc from process node to resource node = process requests resource (i.e., process is currently blocked waiting for that resource)01/14/19 CS 241 - System Programming, Klara Nahrstedt5Deadlock Modeling (2)Modeled with directed graphs–resource R assigned to process A–process B is requesting/waiting for resource S–process C and D are in deadlock over resources T and U01/14/19 CS 241 - System Programming, Klara Nahrstedt6How deadlock occursA B CDeadlock Modeling (3)01/14/19 CS 241 - System Programming, Klara Nahrstedt7Deadlock Modeling (4)How deadlock can be avoided(o) (p) (q)01/14/19 CS 241 - System Programming, Klara Nahrstedt8Resource Allocation Graph(multiple resource types)01/14/19 CS 241 - System Programming, Klara Nahrstedt9Deadlock Model01/14/19 CS 241 - System Programming, Klara Nahrstedt10StrategiesStrategies for dealing with Deadlocks1. just ignore the problem altogether2. detection and recovery3. dynamic avoidance •careful resource allocation4. prevention •negating one of the four necessary conditions01/14/19 CS 241 - System Programming, Klara Nahrstedt11The Ostrich AlgorithmPretend there is no problemReasonable if –deadlocks occur very rarely –cost of prevention is highUNIX and Windows takes this approachIt is a trade off between –convenience–correctness01/14/19 CS 241 - System Programming, Klara Nahrstedt12Algorithms to deal with DeadlockPrevention–design a system in such a way that deadlocks cannot occur, at least with respect to serially reusable resources. Avoidance– impose less stringent conditions than for prevention, allowing the possibility of deadlock, but sidestepping it as it approaches. Detection– in a system that allows the possibility of deadlock, determine if deadlock has occurred, and which processes and resources are involved. Recovery–after a deadlock has been detected, clear the problem, allowing the deadlocked processes to complete and the resources to be reused. Usually involves destroying the affected processes and starting them over.01/14/19 CS 241 - System Programming, Klara Nahrstedt13Deadlock DetectionCheck to see if a deadlock has occurred!Single resource per type–Can use wait-for graph–Check for cycles–O(n2)01/14/19 CS 241 - System Programming, Klara Nahrstedt14Detection with One Resource of Each Type (1)Note the resource ownership and requestsA cycle can be found within the graph, denoting deadlockTT01/14/19 CS 241 - System Programming, Klara Nahrstedt15Wait for GraphsResource Allocation Graph Corresponding Wait For Graph01/14/19 CS 241 - System Programming, Klara Nahrstedt16Recovery from Deadlock (1)Recovery through preemption–take a resource from some other process–depends on nature of the resourceRecovery through rollback–checkpoint a process periodically–use this saved state –restart the process if it is found deadlocked01/14/19 CS 241 - System Programming, Klara Nahrstedt17Recovery from Deadlock (2)Recovery through killing processes–crudest but simplest way to break a deadlock–kill one of the processes in the deadlock cycle–the other processes get its resources –choose process that can be rerun from the beginning01/14/19 CS 241 - System Programming, Klara Nahrstedt18Deadlock Prevention: Havender's Algorithms Break one of the deadlock conditions. –Mutual exclusionSolution: exclusive use of resources is an important feature, but for some resources (virtual memory, virtual disks, CPU), it is possible.–Hold-and-Wait conditionSolution: Force each process to request all required resources at once. It cannot proceed until all resources have been acquired. –No preemption conditionSolution: If a process holding some reusable resources makes a further request which is denied, and it wishes to wait for the new resources to become available, it must release all resources currently held and, if necessary, request them again along with the new resources. Thus, resources are removed from a process holding them. –Circular wait conditionSolution: All resource types are numbered. Processes must request resources in numerical order01/14/19 CS 241 - System Programming, Klara Nahrstedt19Summary: Deadlock Preventioncondition How to break itMutual Exclusion Spool everythingHold and wait Request all resources initiallyNo preemption Take resources awayCircular wait Order resources numerically01/14/19 CS 241 - System Programming, Klara Nahrstedt20ReminderHomework 1 due 3/6/06Quiz 5 –
View Full Document