Deadlock PreventionAnnouncementsFrom last time...DeadlockDeadlockDeadlock DetectionDeadlock DetectionDeadlock DetectionDeadlock DetectionDeadlock DetectionNecessary Conditions for DeadlockApproaches to Handling DeadlocksDeadlock PreventionDeadlock PreventionDeadlock PreventionDeadlock PreventionDeadlock PreventionDeadlock PreventionDeadlock PreventionDeadlock PreventionCSCI 3753 Operating SystemsSpring 2005Prof. Rick HanAnnouncements• HW #3 is due Friday Feb. 25– extra office hours Thursday 1 pm - post this• PA #2 assigned, due Thursday March 17• Midterm is Thursday March 10– Midterm review is Tuesday March 8• Read chapter 10From last time...• We discussed:– Dining Philosophers Problem - deadlock!– monitors• high-level synchronization primitives• don’t have to explicitly P() and V()• augmented with condition variables– monitor-based solution to Dining Philosophers problemDeadlock• saw earlier that semaphores provide mutual exclusion, but can introduce deadlock– 2 process, each desires a resource locked by the other process– can occur easily due to programming errors, e.g. by switching order of P and V, etc.• Even if no obvious programming errors, deadlock can occur– deadlock is difficult to anticipate by a single thread, because the code looks fine, and deadlock is a higher-level concept that involves the distributed behavior of multiple processes/threads– deadlock is difficult to anticipate, detect, reproduce, prevent,avoid, and recover fromDeadlock• A set of processes is in a deadlock state when every process in the set is waiting for an event (e.g. release of a resource) that can only be caused by another process in the set• multithreaded programs are good candidates for deadlock– thread-thread deadlock within a process– thread-thread deadlock across processesDeadlock DetectionResources• Modeling deadlock:– to use a resource, a process must1. request() a resource --must wait until it’s available2. use() or hold() a resource3. release() a resource– thus, we have resources and processes– Most of the following discussion will focus on reusable resourcesBuffer1 BufferN File F Disk D...P1 P2 P3ProcessesP1 holds Buffer 1 and File FP2 holds Buffer NP3 holds Disk DDeadlock Detection•a resource allocation graph can be used to model deadlock– try to represent deadlock by a directed graphD(V,E), consisting of• vertices V: namely processes and resources• and edges E:– a request() for a resource Rjby a process Piis signified by a directed arrow from process Pi→ Rj– a process Piwill hold() a resource Rjvia a directed arrow Rj→ PiDeadlock Detection• Example 1:– P1 holds an instanceof resource R2, and is requesting resource R1– P2 holds R1 and an instance of R2, and requests R3– P3 holds R3– There is no deadlock• if the graph contains no cycles or loops, then there is no deadlockR1P3P1 P2R3R2R4Deadlock Detection•Example 2:– same graph as before, except now P3 requests an instance of R2– Deadlock occurs!• P3 requests R2, which is held by P2, which requests R3, which is held by P3 - this is a loop–P3→ R2→ P2→ R3→ P3– If P1 could somehow release an instance of R2, then we could break the deadlock• But P1 is part of a second loop:–P3→ R2→ P1→ R1→ P2→ R3→ P3– So P1 can’t release its instance of R2– if the graph contains cycles or loops, then there may be the possibility of deadlock• but does a loop guarantee that there is deadlock?R1P3P1 P2R3R2Deadlock Detection•Example 3:– there is a loop:•P1→ R1→ P3→ R2→ P1– In this case, there is no deadlock• either P2 can release an instance of R1, or P4 can release an instance of R2– this breaks any possible deadlock cycle– if the graph contains cycles or loops, then there may be the possibility of deadlock, but this is not a guarantee of deadlockP2P1 P3R2R1P4Necessary Conditions for Deadlock• Deadlock can arise if the following 4 conditions hold simultaneously:1. Mutual exclusion• at least 1 resource is held in a non-sharable mode. Other requesting processes must wait until the resource is released2. Hold and wait• a process may hold a resource while request (and waiting for) another one3. No preemption• resources cannot be preempted and can only be released by the process holding it, after the process is finished. No OS intervention is allowed. A process cannot withdraw its request.4. Circular wait• A set of waiting processes {P0, ..., Pn-1} must exist such that Pi waits for a resource held by P(i+1)%nApproaches to Handling Deadlocks•Prevention– provide methods to guarantee that at least 1 of the 4 necessary conditions for deadlock does not hold• Avoidance– the OS is given advanced information about which process requests which resource when• this is used to determine whether the OS can satisfy the resource requests without causing deadlock• Detection and Recovery• Ignore and Pretend– this is the most common approach, based on the assumption that deadlock is relatively infrequent– UNIX and Windows use this approachDeadlock Prevention• Prevent the mutual exclusion condition from coming true– This is opposite of our original goal, which was to provide mutual exclusion.– Also, many resources are non-sharable and must be accessed in a mutually exclusive way• example: a printer should print a file X to completion before printing a file Y. a printer should not print half of file X, and then print the first half of file Y on the same paper– thus, it is unrealistic to prevent mutual exclusionDeadlock Prevention• Prevent the hold and wait condition from coming true– prevent a process from holding resources and requesting others– Solution I: request all resources at process creation– Solution II: release all held resources before requesting a set of new ones simultaneously– Example: a process reads from the DVD drive and writes the file to disk, sorts the file, then sends the file to the printer• Solution I: request the DVD drive, disk, and printer at process creation• Solution II: break the task down into wholly contained non-dependent pieces– obtain the DVD and disk together for the file transfer, then release both together– next obtain the disk and printer together for the printing operation, then release both togetherDeadlock Prevention• Disadvantages of Hold-and-wait solutions– don’t know in advance all resources needed– poor resource