ICS 143 - Principles of Operating Systems Lectures 8 and 9 - Deadlocks Prof. Dmitri V. Kalashnikov dvk (@) ics.uci.edu Slides © Prof. Nalini Venkatasubramanian.Outline n System Model n Deadlock Characterization n Methods for handling deadlocks n Deadlock Prevention n Deadlock Avoidance n Deadlock Detection n Recovery from Deadlock n Combined Approach to Deadlock HandlingThe Deadlock Problem n A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. q Example 1 q System has 2 tape drives. P1 and P2 each hold one tape drive and each needs the other one. q Example 2 q Semaphores A and B each initialized to 1 P0 P1 wait(A) wait(B) wait(B) wait(A)Definitions n A process is deadlocked if it is waiting for an event that will never occur. Typically, more than one process will be involved in a deadlock (the deadly embrace). n A process is indefinitely postponed if it is delayed repeatedly over a long period of time while the attention of the system is given to other processes, n i.e. the process is ready to proceed but never gets the CPU.Example - Bridge Crossing q Assume traffic in one direction. n Each section of the bridge is viewed as a resource. q If a deadlock occurs, it can be resolved only if one car backs up (preempt resources and rollback). n Several cars may have to be backed up if a deadlock occurs. n Starvation is possibleResources n Resource n commodity required by a process to execute n Resources can be of several types n Serially Reusable Resources q CPU cycles, memory space, I/O devices, files q acquire -> use -> release n Consumable Resources q Produced by a process, needed by a process - e.g. Messages, buffers of information, interrupts q create ->acquire ->use q Resource ceases to exist after it has been usedSystem Model n Resource types q R1, R2,….Rm n Each resource type Ri has Wi instances n Assume serially reusable resources n request -> use -> releaseConditions for Deadlock q The following 4 conditions are necessary and sufficient for deadlock (must hold simultaneously) n Mutual Exclusion: q Only one process at a time can use the resource. n Hold and Wait: q Processes hold resources already allocated to them while waiting for other resources. n No preemption: q Resources are released by processes holding them only after that process has completed its task. n Circular wait: q A circular chain of processes exists in which each process waits for one or more resources held by the next process in the chain.n A set of vertices V and a set of edges E n V is partitioned into 2 types n P = {P1, P2,…,Pn} - the set of processes in the system n R = {R1, R2,…,Rn} - the set of resource types in the system n Two kinds of edges n Request edge - Directed edge Pi ---> Rj n Assignment edge - Directed edge Rj ----> Pi Resource Allocation GraphResource Allocation Graph n Process n Resource type with 4 instances n Pi requests instance of Rj n Pi is holding an instance of RjGraph with no cycles R4 R2 R1 R3 P1 P2 P3Graph with cycles R1 P1 R2 P2 P3 P4Graph with cycles and deadlock R4 R2 R1 R3 P1 P2 P3Basic facts n If graph contains no cycles q NO DEADLOCK n If graph contains a cycle q if only one instance per resource type, then deadlock q if several instances per resource type, possibility of deadlock.Methods for handling deadlocks n Ensure that the system will never enter a deadlock state. n Allow the system to potentially enter a deadlock state, detect it and then recover n Ignore the problem and pretend that deadlocks never occur in the system; q Used by many operating systems, e.g. UNIXDeadlock Management q Prevention q Design the system in such a way that deadlocks can never occur q Avoidance q Impose less stringent conditions than for prevention, allowing the possibility of deadlock but sidestepping it as it occurs. q Detection q Allow possibility of deadlock, determine if deadlock has occurred and which processes and resources are involved. q Recovery q After detection, clear the problem, allow processes to complete and resources to be reused. May involve destroying and restarting processes.Deadlock Prevention q If any one of the conditions for deadlock (with reusable resources) is denied, deadlock is impossible. q Restrain ways in which requests can be made n Mutual Exclusion q non-issue for sharable resources q cannot deny this for non-sharable resources (important) n Hold and Wait - guarantee that when a process requests a resource, it does not hold other resources. q Force each process to acquire all the required resources at once. Process cannot proceed until all resources have been acquired. q Low resource utilization, starvation possibleDeadlock Prevention (cont.) n No Preemption q If a process that is holding some resources requests another resource that cannot be immediately allocated to it, the process releases the resources currently being held. q Preempted resources are added to the list of resources for which the process is waiting. q Process will be restarted only when it can regain its old resources as well as the new ones that it is requesting. n Circular Wait q Impose a total ordering of all resource types. q Require that processes request resources in increasing order of enumeration; if a resource of type N is held, process can only request resources of types > N.Deadlock Avoidance n Set of resources, set of customers, banker n Rules q Each customer tells banker maximum number of resources it needs. q Customer borrows resources from banker. q Customer returns resources to banker. q Customer eventually pays back loan. n Banker only lends resources if the system will be in a safe state after the loan.Deadlock Avoidance n Requires that the system has some additional apriori information available. q Simplest and