CS241 System ProgrammingDeadlock 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/20062/26/2006CS 241 - System Programming, Klara Nahrstedt2Contentz Deadlock Modelingz Deadlock Detection and Recoveryz Deadlock Prevention2/26/2006CS 241 - System Programming, Klara Nahrstedt3Administrative NoteszMP2 on Monday, February 27z Homework 1 – Deadline March 6 –Individual Effort (No Collaboration with your MP partner or other pairs partners)z Quiz 5 – March 3, 2006–Covers Signals, Timers and Deadlock zTanenbaum 3.3.1, 3.3.2, 3.3.3, 3.3.4 and 3.3.5zR&R: Signals 8.1-8.5, zR&R: Signal Handling and Threads 13.5zR&R: 9.1, 9.2, 9.3, 9.4, 9.5zLecture Notes: lec13-sched, lec14-sched, lec15-sched, lec16-deadlock, lec17-deadlock2/26/2006CS 241 - System Programming, Klara Nahrstedt4Deadlock Modeling (1) z1972 – Holt showed that the four conditions can be modeled using directed graphszGraph have two kinds of nodes–Processes –Resources zGraph’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)2/26/2006CS 241 - System Programming, Klara Nahrstedt5Deadlock Modeling (2)zModeled 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 U2/26/2006CS 241 - System Programming, Klara Nahrstedt6A B CDeadlock Modeling (3)How deadlock occurs2/26/2006CS 241 - System Programming, Klara Nahrstedt7Deadlock Modeling (4)(o) (p) (q)How deadlock can be avoided2/26/2006CS 241 - System Programming, Klara Nahrstedt8Resource Allocation Graph(multiple resource types)2/26/2006CS 241 - System Programming, Klara Nahrstedt9Deadlock Model2/26/2006CS 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 conditions2/26/2006CS 241 - System Programming, Klara Nahrstedt11The Ostrich AlgorithmzPretend there is no problemz Reasonable if –deadlocks occur very rarely –cost of prevention is highzUNIX and Windows takes this approachz It is a trade off between –convenience–correctness2/26/2006CS 241 - System Programming, Klara Nahrstedt12Algorithms to deal with DeadlockzPrevention–design a system in such a way that deadlocks cannot occur, at least with respect to serially reusable resources. zAvoidance–impose less stringent conditions than for prevention, allowing the possibility of deadlock, but sidestepping it as it approaches. zDetection–in a system that allows the possibility of deadlock, determine if deadlock has occurred, and which processes and resources are involved. zRecovery–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.2/26/2006CS 241 - System Programming, Klara Nahrstedt13Deadlock DetectionzCheck to see if a deadlock has occurred!z Single resource per type–Can use wait-for graph–Check for cycles–O(n2)2/26/2006CS 241 - System Programming, Klara Nahrstedt14Detection with One Resource of Each Type (1)TTzNote the resource ownership and requestszA cycle can be found within the graph, denoting deadlock2/26/2006CS 241 - System Programming, Klara Nahrstedt15Wait for GraphsResource Allocation Graph Corresponding Wait For Graph2/26/2006CS 241 - System Programming, Klara Nahrstedt16Recovery from Deadlock (1)zRecovery through preemption–take a resource from some other process–depends on nature of the resourcezRecovery through rollback–checkpoint a process periodically–use this saved state –restart the process if it is found deadlocked2/26/2006CS 241 - System Programming, Klara Nahrstedt17Recovery from Deadlock (2)zRecovery 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 beginning2/26/2006CS 241 - System Programming, Klara Nahrstedt18Deadlock Prevention: Havender's Algorithms zBreak one of the deadlock conditions. –Mutual exclusionz Solution: exclusive use of resources is an important feature, but for some resources (virtual memory, virtual disks, CPU), it is possible.–Hold-and-Wait conditionz Solution: Force each process to request all required resources at once. It cannot proceed until all resources have been acquired. –No preemption conditionz Solution: 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 conditionz Solution: All resource types are numbered. Processes must request resources in numerical order2/26/2006CS 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 numerically2/26/2006CS 241 - System Programming, Klara Nahrstedt20ReminderzHomework 1 due 3/6/06z Quiz 5 –
View Full Document
Unlocking...