Chapter 3Chapter 3: DeadlocksChapter 32CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Overview Resources Why do deadlocks occur? Dealing with deadlocks Ignoring them: ostrich algorithm Detecting & recovering from deadlock Avoiding deadlock Preventing deadlockChapter 33CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Resources Resource: something a process uses Usually limited (at least somewhat) Examples of computer resources Printers Semaphores / locks Tables (in a database) Processes need access to resources in reasonable order Two types of resources: Preemptable resources: can be taken away from a process with no illeffects Nonpreemptable resources: will cause the process to fail if taken awayChapter 34CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)When do deadlocks happen? Suppose Process 1 holds resource Aand requests resource B Process 2 holds B andrequests A Both can be blocked, withneither able to proceed Deadlocks occur when … Processes are grantedexclusive access to devices orsoftware constructs(resources) Each deadlocked processneeds a resource held byanother deadlocked processABBAProcess 1Process 2DEADLOCK!Chapter 35CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Using resources Sequence of events required to use a resource Request the resource Use the resource Release the resource Can’t use the resource if request is denied Requesting process has options Block and wait for resource Continue (if possible) without it: may be able to use an alternateresource Process fails with error code Some of these may be able to prevent deadlock…Chapter 36CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)What is a deadlock? Formal definition:“A set of processes is deadlocked if each process inthe set is waiting for an event that only anotherprocess in the set can cause.” Usually, the event is release of a currently heldresource In deadlock, none of the processes can Run Release resources Be awakenedChapter 37CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Four conditions for deadlock Mutual exclusion Each resource is assigned to at most one process Hold and wait A process holding resources can request more resources No preemption Previously granted resources cannot be forcibly takenaway Circular wait There must be a circular chain of 2 or more processeswhere each is waiting for a resource held by the nextmember of the chainChapter 38CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Resource allocation graphs Resource allocationmodeled by directed graphs Example 1: Resource R assigned toprocess A Example 2: Process B is requesting /waiting for resource S Example 3: Process C holds T, waitingfor U Process D holds U, waitingfor T C and D are in deadlock!RASBUTDCChapter 39CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Dealing with deadlock How can the OS deal with deadlock? Ignore the problem altogether! Hopefully, it’ll never happen… Detect deadlock & recover from it Dynamically avoid deadlock Careful resource allocation Prevent deadlock Remove at least one of the four necessary conditions We’ll explore these tradeoffsChapter 310CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Getting into deadlockABCAcquire RAcquire SRelease RRelease SAcquire SAcquire TRelease SRelease TAcquire TAcquire RRelease TRelease RRASBTCAcquire RRASBTCAcquire SRASBTCAcquire TRASBTCAcquire SRASBTCAcquire TRASBTCAcquire RDeadlock!Chapter 311CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Not getting into deadlock… Many situations may result in deadlock (but don’thave to) In previous example, A could release R before C requestsR, resulting in no deadlock Can we always get out of it this way? Find ways to: Detect deadlock and reverse it Stop it from happening in the first placeChapter 312CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)The Ostrich Algorithm Pretend there’snoproblem Reasonable if Deadlocks occur very rarely Cost of prevention is high UNIX and Windows take this approach Resources (memory, CPU, disk space) are plentiful Deadlocks over such resources rarely occur Deadlocks typically handled by rebooting Trade off between convenience and correctnessChapter 313CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Detecting deadlocks using graphs Process holdings and requests in the table and in the graph(they’re equivalent) Graph contains a cycle => deadlock! Easy to pick out by looking at it (in this case) Need to mechanically detect deadlock Not all processes are deadlocked (A, C, F not in deadlock)RASFWCUVGSWFVTES,TUDSCTBSRAWantsHoldsProcessEDGBTVUChapter 314CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Deadlock detection algorithm General idea: try to findcycles in the resourceallocation graph Algorithm: depth-firstsearch at each node Mark arcs as they’retraversed Build list of visited nodes If node to be added is alreadyon the list, a cycle exists! Cycle == deadlockForeachnodeN inthe graph {SetL = em ptylistunm arkallarcsTraverse (N,L)}Ifno deadlock reported by now ,thereisn’tanydefine Traverse (C,L) {IfC inL,reportdeadlock!Add C toLForeach unm arked arcfrom C {Markthe arcSetA = arc destination/*NOTE:L isalocalvariable*/Traverse (A,L)}}Chapter 315CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Resources with multiple instances Previous algorithm only works if there’s oneinstance of each resource If there are multiple instances of each resource, weneed a different method Track current usage and requests for each process To detect deadlock, try to find a scenario where allprocesses can finish If no such scenario exists, we have deadlockChapter 316CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Deadlock detection