Chapter 7: Deadlocks

1 , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionChapter 7: , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionChapter 7: DeadlocksnThe deadlock ProblemnSystem ModelnDeadlock CharacterizationnMethods for Handling DeadlocksnDeadlock PreventionnDeadlock AvoidancenDeadlock Detection nRecovery from deadlock , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionChapter ObjectivesnTo develop a description of Deadlocks , which prevent sets of concurrent processes from completing their tasksnTo present a number of different methods for preventing or avoiding Deadlocks in a computer , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionThe deadlock ProblemnA set of blocked processes each holdinga resource and waitingto acquire a resource held by another process in the setnExample lSystem has 2 disk driveslP1and P2each hold one disk drive and each needs another onenExample lsemaphores AandB, initialized to 1P0P1acquire(A);acquire(B)acquire(B).

2 Acquire (A) , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionBridge Crossing ExamplenTraffic only in one directionnEach section of a bridge can be viewed as a resourcenIf a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback)nSeveral cars may have to be backed up if a deadlock occursnStarvation is possiblenNote Most OSes do not prevent or deal with , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionSystem ModelnResource types R1, R2, .., RmCPU cycles, memory space, I/O devicesnEach resource type Rihas process utilizes a resource as follows:lrequest luse , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionDeadlock CharacterizationnMutual exclusion:only one process at a time can use a resourcenHold and wait:a process holding at least one resource is waiting to acquire additional resources held by other processesnNo preemption:a resource can be released only voluntarily by the process holding it, after that process has completed its tasknCircular wait:there exists a set {P0, P1.}

3 , Pn} 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 Pnis waiting for a resource that is held by can arise if four conditions hold , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionResource-Allocation GraphnV is partitioned into two types:lP= {P1, P2, .., Pn}, the set consisting of all the processes in the systemlR= {R1, R2, .., Rm}, the set consisting of all resource types in the systemnrequest edge directed edge Pi Rjnassignment edge directed edge Rj PiA set of vertices Vand a set of edges , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionResource-Allocation Graph (Cont.)nProcessnResource Type with 4 instancesnPirequests instance of RjnPiis holding an instance of , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionExample of a Resource Allocation GraphP = {P1, P2, P3}R = {R1, R2, R3, R4}E = {P1->R1, P2->R3, R1->P2, R2->P2,R2->P1, R3->P3}Resource instances: One instance of resource type R1, Two instances of resource type R2, One instance of resource type R3, Two instances of resource type R4 Process states P1 is holding an instance of R2 and waiting for an R1 P2 is holding an R1 and an R2 and is waiting for an R3 P3 is holding an , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionResource Allocation Graph With A DeadlockSuppose P3 requests an instance of resource type R2.

4 Two cycles exist in the system:P1->R1->P2->R3->P3->R2->P1P2->R3- >P3->R2->P2 Processes P1, P2, P3 are deadlocked. , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionGraph With A Cycle But No DeadlockWe have a cycle but no P4 may release its instance of resource type R2. R2 can then be allocated to P3, breaking the cycle. , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionBasic FactsnIf graph contains no cycles no deadlocknIf graph contains a cycle lif only ONEinstance per resource type, then deadlocklif SEVERAL instances per resource type, possibility of , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionMethods for Handling DeadlocksnEnsure that the system will neverenter a deadlock statenAllow the system to entera deadlock state and then recovernIgnorethe problem and pretend that Deadlocks never occur in the system; used by most operating systems, including , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionDeadlock PreventionnMutual Exclusion not required for sharable resources ( a printer).

5 Must hold for nonsharable resources ( read-only files)nHold and Wait must guarantee that whenever a process requests a resource, it does not hold any other resourceslRequire process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has nonelLow resource utilization; starvation possibleRestrain the ways request can be , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionDeadlock Prevention (Cont.)nNo Preemption lIfa process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are releasedlPreempted resources are added to the list of resources for which the process is waitinglProcess will be restarted only when it can regain its old resources, as well as the new ones that it is requestingnCircular Wait impose a total ordering of all resource types, and require that each process requests resources in an increasing order of , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionDeadlock AvoidancenSimplest and most useful model requires that each process declare the maximum numberof resources of each type that it may neednThe deadlock -avoidance algorithm dynamicallyexamines the resource-allocation state to ensure that there can never be a circular-wait conditionnResource-allocation stateis defined by the number of available and allocated resources.

6 And the maximum demands of the processesRequires that the system has some additional on how resources are to be requested. , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionSafe StatenWhen a process requests an available resource, system must decide if immediate allocation leaves the system in a safe statenSystem is in safe state if there exists a sequence <P1, P2, .., Pn> of ALL the processes in the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, withj < inThat is:lIf Piresource needs are not immediately available, then Pican wait until all Pjhave finishedlWhen Pjis finished, Pican obtain needed resources, execute, return allocated resources, and terminatelWhen Piterminates, Pi +1can obtain its needed resources, and so on , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionBasic FactsnIf a system is in safe state no deadlocksnIf a system is in unsafe state possibility of deadlocknAvoidance ensure that a system will never enter an unsafe , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionSafe, Unsafe , deadlock State , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionAvoidance algorithmsnSingle instance of a resource typelUse a resource-allocation graphnMultiple instances of a resource typelUse the banker s.

7 Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionResource-Allocation Graph SchemenClaim edge Pi Rjindicated that process Pjmay request resource Rj; represented by a dashed linenClaim edge converts to request edgewhen a process requests a resourcenRequest edge converted to an assignment edge when the resource is allocated to the processnWhen a resource is released by a process, assignment edge reconverts to a claim edgenResources must be claimed a prioriin the , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionResource-Allocation GraphUnsafe State In Resource-Allocation GraphSuppose that P2 requests R2. although R2 is currently free, we can not allocate it to P2, since this action may create a cycle if P1 requests R2 as well. , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionResource-Allocation Graph AlgorithmnSuppose that processPirequests a resource RjnThe request can be granted only if convertingthe request edge to an assignment edge does not result in the formation of a cycle in the resource allocation , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionBanker s AlgorithmnMultiple instancesnEach process must a priori claim maximum usenWhen a process requests a resource it may have to wait nWhen a process gets all its resources it must returnthem in a finite amount of , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionData Structures for the Banker s Algorithm nAvailable:# of available resources of each type.

8 Vector of length m. If available [j] = k, there arekinstances of resource type RjavailablenMax: maximum demand of each process. n x mmatrix. If Max [i,j] = k, then process Pimay request at mostk instances of resource type RjnAllocation: # of resources of each type currently allocated to each process. n xmmatrix. If Allocation[i,j] = kthenPiis currently allocated kinstances of RjnNeed: the remaining resource need of each process. n xmmatrix. If Need[i,j] =k, thenPimay need kmore instances of Rjto complete its taskNeed[i,j]= Max[i,j] Allocation[i,j]Let n= number of processes, and m = number of resources types. , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionSafety Workand Finishbe vectors of lengthmandn, respectively. Initialize:Work = AvailableFinish [i] =false fori= 0, 1, .., an index i such that both: (a) Finish[i] = false(b) Needi WorkIf no such i exists, go to step Work + AllocationiFinish[i] =truego to step Finish[i] == true for all i, then the system is in a safe , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionResource-Request Algorithm for Process PiRequest= request vector for process Pi.

9 If Requesti[j] = kthen process Piwants kinstances of resource type Requesti Needigo to step 2. Otherwise, raise error condition, since process has exceeded its maximum Requesti Available, go to step 3. Otherwise Pimust wait, since resources are not to allocate requested resources to Piby modifying the state as follows:Available= Available Request;Allocationi= Allocationi+ Requesti;Needi=Needi Requesti;!If safe the resources are allocated to Pi!If unsafe Pi must wait, and the old resource-allocation state is , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionExample of Banker s Algorithmn5 processes P0 through P4; 3 resource types:A(10 instances), B(5instances), and C(7 instances)Snapshot at time T0:AllocationMaxAvailableA B CA B C A B CP00 1 07 5 3 3 3 2P12 0 0 3 2 2 P23 0 2 9 0 2P32 1 1 2 2 2P40 0 24 3 3 , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionExample (Cont.)nThe content of the matrix Needis defined to be Max AllocationNeedA B CP07 4 3 P11 2 2 P26 0 0 P30 1 1P44 3 1 nThe system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionExample: P1 Request (1,0,2)nCheck that Request Available (that is, (1,0,2) (3,3,2) trueAllocationNeedAvailableA B CA B CA B C P00 1 07 4 3 2 3 0P13 0 2 0 2 0 P23 0 1 6 0 0 P32 1 1 0 1 1P40 0 2 4 3 1 nExecuting safety algorithm shows that sequence < P1, P3, P4, P0, P2> satisfies safety requirementnCan request for (3,3,0) by P4be granted?)

10 NCan request for (0,2,0) by P0be granted? , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionDeadlock DetectionnAllow system to enter deadlock state nDetection algorithmnRecovery , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionSingle Instance of Each Resource TypenMaintain wait-forgraphlNodes are processeslPi Pj if Piis waiting forPjnPeriodicallyinvoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlocknAn algorithm to detect a cycle in a graph requires an order ofn2operations, where nis the number of vertices in the , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionResource-Allocation Graph and Wait-for GraphResource-Allocation GraphCorresponding wait-for , Galvin and Gagne 2009 Operating System Concepts with Java 8thEditionSeveral Instances of a Resource TypenAvailable:A vector of length mindicates the number of available resources of each :An n xmmatrix defines the number of resources of each type currently allocated to each :An n xmmatrix indicates the current request of each process.