CSC 4320/6320 Operating Systems Lecture 7 DeadlocksChapter 7: DeadlocksChapter ObjectivesThe Deadlock ProblemBridge Crossing ExampleSystem ModelDeadlock CharacterizationResource-Allocation GraphResource-Allocation Graph (Cont.)Example of a Resource Allocation GraphResource Allocation Graph With A DeadlockGraph With A Cycle But No DeadlockBasic FactsMethods for Handling DeadlocksDeadlock PreventionDeadlock Prevention (Cont.)Slide 17Deadlock AvoidanceSafe StateSlide 20Safe, Unsafe , Deadlock StateAvoidance algorithmsResource-Allocation Graph SchemeResource-Allocation Graph AlgorithmSlide 25Unsafe State In Resource-Allocation GraphBanker’s AlgorithmData Structures for the Banker’s AlgorithmSafety AlgorithmResource-Request Algorithm for Process PiExample of Banker’s AlgorithmExample (Cont.)Example: P1 Request (1,0,2)Deadlock DetectionSingle Instance of Each Resource TypeResource-Allocation Graph and Wait-for GraphSeveral Instances of a Resource TypeDetection AlgorithmDetection Algorithm (Cont.)Example of Detection AlgorithmSlide 41Detection-Algorithm UsageRecovery from Deadlock: Process TerminationRecovery from Deadlock: Resource PreemptionEnd of Lecture 7Saurav KarmakarChapter 7: DeadlocksThe Deadlock ProblemSystem ModelDeadlock CharacterizationMethods for Handling DeadlocksDeadlock PreventionDeadlock AvoidanceDeadlock Detection Recovery from DeadlockChapter ObjectivesTo develop a description of deadlocks, which prevent sets of concurrent processes from completing their tasksTo present a number of different methods for preventing or avoiding deadlocks in a computer systemThe 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 disk drivesP1 and P2 each hold one disk drive and each needs another oneExample semaphores A and B, initialized to 1 P0 P1wait (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Note – Most OSes do not prevent or deal with deadlocksSystem ModelResource types R1, R2, . . ., RmCPU cycles, memory space, I/O devicesEach resource type Ri has Wi instances.Each process utilizes a resource as follows:request use releaseDeadlock CharacterizationMutual exclusion: only one process at a time can use a 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, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and P0 is 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 Pi  Rjassignment edge – directed edge Rj  PiA set of vertices V and a set of edges E.Resource-Allocation Graph (Cont.)ProcessResource Type with 4 instancesPi requests instance of RjPi is holding an instance of RjPiPiRjRjExample of a Resource Allocation GraphResource Allocation Graph With A DeadlockGraph 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 deadlockMethods for Handling DeadlocksEnsure that the system will never enter a deadlock stateAllow the system to enter a deadlock state, detect it and then recoverIgnore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIXDeadlock PreventionMutual Exclusion – not required for sharable resources; must hold for nonsharable resources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 possibleRestrain the ways request can be madeDeadlock 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 enumerationDeadlock PreventionBy restraining how requests can be made for resources.Probable side effects : Low device utilization Reduced system throughputDeadlock AvoidanceSimplest and most useful model requires that each process declare the maximum number of resources of each type that it may needThe deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never reach a circular-wait conditionResource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processesRequires that the system has some additional a priori information availableSafe 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 sequence <P1, P2, …, Pn> of ALL the processes is 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, with j < iThat is:If Pi resource needs are not immediately