1Lecture 6DeadlocksOctober 14, 2003Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2003 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapter 8 (on Deadlock)Midterm is on Tuesday of next week (Oct 21)• Covers all Lectures including this week• Covers Programming Assignment #1• Sample midterm posted on class web page3What is Deadlock?The state of a set of permanently blocked processes• Unblocking of one relies on progress of another• But none can make progress!Example• Processes A and B• Resources X and Y• A holding X, waiting for Y• B holding Y, waiting for X• Each is waiting for the other; will wait foreverAXYBwaitingforwaitingforholdingholding4Traffic Jam as Example of DeadlockAZBDWCY XResource AllocationGraphW XY ZCABDCars deadlockedin an intersection5More Examples of DeadlockMemory (a reusable resource)• total memory = 200KB• P1 requests 80KB• P2 requests 70KB• P1 requests 60KB (wait)• P2 requests 80KB (wait)Messages (a consumable resource)• P1: receive M2 from P2• P2: receive M1 from P1P1P2P1M1M2P26Conditions for DeadlockMutual Exclusion• Only one process may use a resource at a timeHold-and-Wait• Process holds resources while waiting for othersNo Preemption• Can’t take a resource away from a processCircular Wait• The waiting processes form a cycle7How to Attack the Deadlock ProblemDeadlock Prevention• Prevent any possibility of a deadlockDeadlock Avoidance• Avoid situations that lead to deadlockDeadlock Detection• Don’t try to stop deadlocks• Rather, if they happen, detect and resolve8Deadlock PreventionSimply prevent any one of the conditions for deadlock• Mutual exclusion– Relax where sharing is possible• Hold-and-wait– Get all resources simultaneously, wait until all free• No preemption– Allow resources to be taken away• Circular wait– Order all the resources, force ordered acquisition9Preventing a Traffic JamTo apply deadlockprevention to trafficjam problem, just adda traffic light!Which condition is beingprevented?CABD10Deadlock AvoidanceWorks with incremental resource requests• Resources are asked for in increments• Do not grant request that can lead to a deadlockRequires knowledge of maximum resource requirements11Banker’s Algorithm: ConceptsSystem has a fixed number of processes and resources• each process has zero or more resources allocatedSystem state: either safe or unsafe• depends on allocation of resources to processesSafe state• can avoid deadlock by certain order of executionUnsafe state• deadlock is possible (but not necessarily certain)12Safe, Unsafe, and Deadlock StatesUnsafeSafeDeadlockP13Banker’s AlgorithmGiven• a process/resource claim matrix• a process/resource allocation matrix• a resource availability vectorIs there a sequence of process executions such that• a process can run to completion, return resources• resources can then be used by another to complete• eventually, all the processes complete?14Example of a Safe StateCurrent state Claim AllocationP1P2P3P4 P1P2P3P4Avail TotalR13 6 3 4 1 6 2 0 0 9R22 1 1 2 0 1 1 0 1 3R32 3 4 2 0 2 1 2 1 6This is a Safe State• Who can run to completion? P2• After P2 completes, it’s resources are returned• Next select P1, then P3, then P415Example of an Unsafe StateCurrent state Claim AllocationP1P2P3P4 P1P2P3P4Avail TotalR13 6 3 4 1 5 2 0 1 9R22 1 1 2 0 1 1 0 1 3R32 3 4 2 0 1 1 2 2 6So far, this is a safe state, but …• if P2 asks for 1 unit of R1 and 1 unit of R3: safe• if P1 asks for 1 unit of R1 and 1 unit of R3: unsafe• no one may be able to complete: possible deadlock16Avoiding a Traffic JamTo apply deadlockavoidance to trafficjam problem, allow atmost 3 cars to enterintersectionWhat kind of request isbeing denied?CABD17Deadlock Detection and RecoveryDon’t do anything special to prevent or avoid deadlocks• If they happen, they happen• Periodically, try to detect if a deadlock occurred• Do something (or even nothing) about itReasoning• Deadlocks rarely happen• Cost of prevention or avoidance is not worth it• Deal with them in special way (may be very costly)Most systems take this approach!18Detecting DeadlocksConstruct “wait-for” graph• Construct resourceallocation graph• Remove resource nodes• If cycle, deadlockRequires• identifying all resourcesand tracking their use• periodically runningdetection algorithmAZBDWCY XA BD C19Recovery from DeadlockAbort all deadlocked processes• Will remove deadlock, but drastic and costlyAbort deadlocked processes one-at-at-time• Do so until deadlock goes away (need to detect)• What order should processes be aborted?What happens to resources in inconsistent states?• files partially written• interrupted message (e.g., file)
View Full Document