1Chapter 8: Deadlocks■System Model■Deadlock Characterization■Methods for Handling Deadlocks■Deadlock Prevention■Deadlock Avoidance■Deadlock Detection ■Recovery from Deadlock ■Combined Approach to Deadlock HandlingThe Deadlock Problem■A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.■Example ✦System has 2 tape drives.✦P1and P2each hold one tape drive and each needs another one.■Example ✦semaphores AandB, initialized to 1P0P1wait (A); wait(B)wait (B); wait(A)Bridge Crossing Example■Traffic only in one direction.■Each section of a bridge can be viewed as a resource.■If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback).■Several cars may have to be backed up if a deadlock occurs.■Starvation is possible.System Model■Resource types R1, R2, . . ., RmCPU cycles, memory space, I/O devices■Each resource type Rihas Wiinstances.■Each process utilizes a resource as follows:✦request ✦use ✦releaseDeadlock Characterization■Mutual exclusion:only one process at a time can use a (non-sharable) resource.■Hold and wait:a process holding at least one resource is waiting to acquire additional resources held by other processes.■No preemption:a resource can be released only voluntarily by the process holding it, after that process has completed its task.■Circular wait:there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1is waiting for a resource that is held by P2, …, Pn–1is waiting for a resource that is held by Pn, and P0is waiting for a resource that is held by P0.Deadlock can arise if four conditions hold simultaneously.Resource-Allocation Graph■V is partitioned into two types:✦P= {P1, P2, …, Pn}, the set consisting of all the processes in the system.✦R= {R1, R2, …, Rm}, the set consisting of all resource types in the system.■request edge – directed edge P1 →Rj■assignment edge – directed edge Rj→Pi• Deadlocks can be described more precisely in termsof the resource allocation graph• A set of vertices Vand a set of edges E.2Resource-Allocation Graph (Cont.)■Process■Resource Type with 4 instances■ Pirequests instance of Rj■ Piis holding an instance of RjPiPiRjRjExample of a Resource Allocation GraphResource Allocation Graph With A DeadlockResource Allocation Graph With A Cycle But No DeadlockBasic Facts■ If graph contains no cycles ⇒no deadlock.■ If graph contains a cycle ⇒✦if only one instance per resource type, then deadlock.✦if several instances per resource type, possibility of deadlock.Methods for Handling Deadlocks■ Never enter (prevention & avoidance), detect/recover, ignore…1.Ensure that the system will never enter a deadlock state.2.Allow the system to enter a deadlock state and then recover.3.Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.3Deadlock Prevention■Mutual Exclusion– not required for sharable resources; must hold for nonsharable resources.In general not possible to prevent deadlock by this, some resources are intrinsically non-sharable!■Hold and Wait– must guarantee that whenever a process requests a resource, it does not hold any other resources.✦Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none.✦Low resource utilization; starvation possible.The case of never enter.Restrain the ways request can be made (at least one of the necessary conditions should not be true).Deadlock Prevention (Cont.)■No Preemption–✦If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released.✦Preempted resources are added to the list of resources for which the process is waiting.✦Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.■Circular Wait– impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.Deadlock Avoidance■Simplest and most useful model requires that each process declare the maximum numberof resources of each type that it may need.■The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.■Resource-allocation stateis defined by the number of available and allocated resources, and the maximum demands of the processes.The case of a more fine-grained never enter (previous method can cause starvation, low device utilization). Requires that the system has some additional a priori informationavailable (supplied by user for example).Safe State■When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state.■System is in safe state if there exists a safe sequence of all processes. ■Sequence <P1, P2, …, Pn> is safe if for eachPi, the resources that Pican still request can be satisfied by currently available resources + resources held by all the Pj, with j<i.✦If Piresource needs are not immediately available, then Pican wait until all Pjhave finished.✦When Pjis finished, Pican obtain needed resources, execute, return allocated resources, and terminate. ✦When Piterminates, Pi+1can obtain its needed resources, and so on. Basic Facts■If a system is in safe state ⇒no deadlocks.■If a system is in unsafe state ⇒possibility of deadlock.■Avoidance ⇒ensure that a system will never enter an unsafe state. Safe, Unsafe , Deadlock State4Resource-Allocation Graph Algorithm■ Claim edge Pi→Rjindicated that process Pjmay request resource Rj; represented by a dashed line.(this is the difference compared to previous graph)■Claim edge converts to request edge when a process requests a resource.■When a resource is released by a process, assignment edge reconverts to a claim edge.■Resources must be claimed a prioriin the system.Resource-Allocation Graph For Deadlock AvoidanceUnsafe State In Resource-Allocation GraphDeadlock Detection■Allow system to enter deadlock state ■Detection algorithm■Recovery schemeSingle Instance of Each Resource Type■Maintain wait-forgraph✦Nodes are processes.✦Pi→Pj if