Ch 7 Process Coordination (Deadlocks) - Mac 2024 (2).pdf

Chapter 7: Deadlocks Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 7: Deadlocks 7.1 System Model 7.2 Deadlock Char...

Chapter 7: Deadlocks Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 7: Deadlocks 7.1 System Model 7.2 Deadlock Characterization 7.3 Methods for Handling Deadlocks 7.4 Deadlock Prevention 7.8 Summary Operating System Concepts – 9th 8.2 Silberschatz, Galvin and Gagne ©2013  Chapter 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 system. Operating System Concepts – 9th 8.3 Silberschatz, Galvin and Gagne ©2013  7.1 System Model ▪ System consists of resources Overview ▪ Resource types R1, R2,..., RX ▪ CPU cycles, memory space, I/O devices ▪ Each resource type Ri has Wi instances. ▪ E.g.: If a system has two CPUs, then the resource type CPU has two instances. Resource type printer may have five instances. ▪ Each process utilizes a resource as follows: ▪ request ▪ use ▪ release Process request an instance, Process use an instance, Process release once finished. Operating System Concepts – 9th 8.4 Silberschatz, Galvin and Gagne ©2013  7.1 System Model Resources Resources can be: a physical (e.g. Printers, disk drives) or a logical (e.g. A record in a database, semaphores, monitors) Resources are partitioned into several types, R1, R2,..., Rm each consisting of some number of identical instances. Operating System Concepts – 9th 8.5 Silberschatz, 5 Galvin and Gagne ©2013  7.1 System Model …Resources A process may utilize a resource in only the following order: Request ▪ If the request cannot be granted immediately, then the requesting process must wait until it can acquire the resource. Use ▪ The process can operate on the resource Release ▪ The process releases the resource Operating System Concepts – 9th 8.6 Silberschatz, 6 Galvin and Gagne ©2013  7.1 System Model Deadlock Many programs competing for limited resources Deadlock : a state when every process in the set of processes is waiting for an event that can be caused only by another process in the set. Example 1: – System has 2 CD drives. CD1 CD2 – P1 and P2 each hold one CD drive and each needs another one. Operating System Concepts – 9th 8.7 Silberschatz, 7 Galvin and Gagne ©2013  7.1 System Model Figure Deadlock example Operating System Concepts – 9th 8.8 Silberschatz, Galvin and Gagne ©2013  7.2 Deadlock Characterization Necessary condition Deadlock can arise if four conditions hold simultaneously. 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, …, Pn} 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 Pn is waiting for a resource that is held by P0. Operating System Concepts – 9th 8.9 Silberschatz, Galvin and Gagne ©2013  7.2 Deadlock Characterization Resource-Allocation Graph (RAG) A set of vertices V and a set of edges E. 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 → R1 assignment edge – directed edge RA → PA Operating System Concepts – 9th 8.1 Silberschatz, Galvin and Gagne ©2013  7.2 Deadlock Characterization Process Resource Type with 4 instances P1 requests instance of RA = P1 has requested an instance of Resource RA and currently waiting that resource P1 RA P2 is holding / assign (use) an instance of RB = an instance of resource RB has been allocated to P2 P2 RB Operating System Concepts – 9th 8.1 Silberschatz, Galvin and Gagne ©2013  7.1 Deadlock Characterization Type of edges, E REQUEST EDGE ASSIGNMENT EDGE R1 PP 2 1 request assign P1 R2 P1 requests resource R1 P2 hold resource R2 Request edge: directed Assignment edge: directed edge P1→ R1 edge R2 → P2 Operating System Concepts – 9th 8.1 Silberschatz, 12 Galvin and Gagne ©2013  7.2 Deadlock Characterization Example of a Resource Allocation Graph - deadlock Operating System Concepts – 9th 8.1 Silberschatz, Galvin and Gagne ©2013  RAG R1 R3 Deadlock: x x Example 1 (Several Instances P1 of Resources) P P2 P P3 P 1 3 2 x x x x x R2 R4 Process state: Process state: – P1 holds R2 – P1 holds R2 and waits for R1 – P2 holds R1 and R2 – P2 holds R1 and R2, and waits for R3, – P3 holds R3 – P3 holds R3 Operating System Concepts – 9th 8.1 Silberschatz, 14 Galvin and Gagne ©2013  Deadlock Characterization Basic Facts (a) If graph contains no cycles ⇒ no deadlock (b) If graph contains a cycle ⇒ If only one instance per resource type, then deadlock exist If several instances per resource type, then possibility of deadlock Operating System Concepts – 9th 8.1 Silberschatz, Galvin and Gagne ©2013  7.2 Deadlock Characterization Is there a deadlock? Resource Allocation Graph With a Cycle Operating System Concepts – 9th 8.1 Silberschatz, Galvin and Gagne ©2013  R1 R3 RAG: x x Example 2 (Several Instances of Resources) P P1 1 P P2 2 PP3 3 x x x x x R2 R4 There exists 2 cycles: P1 > R1 > P2 > R3 > P3 > R2 > P1 P2 > R3 > P3 > R2 > P2 P1 , P2 and P3 are in a deadlock state Operating System Concepts – 9th 8.1 Silberschatz, 17 Galvin and Gagne ©2013 Operating System Concepts – 9th 8.1 Silberschatz, Galvin and Gagne ©2013  7.2 Deadlock Characterization Is there a deadlock? Resource Allocation Graph With a Cycle Operating System Concepts – 9th 8.1 Silberschatz, Galvin and Gagne ©2013  Question Operating System Concepts – 9th 8.2 Silberschatz, Galvin and Gagne ©2013  Question Operating System Concepts – 9th 8.2 Silberschatz, Galvin and Gagne ©2013  RAG: R1 P2 P2 x Example 3 x P1 P However, the system is P1 P33 not deadlock: x x – when P4 releases R2, this resource can be R2 P4 P 4 assigned to P3 The RAG has one cycle: P1 🡪 R1 🡪 P3 🡪 R2 🡪 P1 P1 and P3 are in a deadlock state Operating System Concepts – 9th 8.2 Silberschatz, 22 Galvin and Gagne ©2013  RAG: R1 P2 P2 x Example 3 x P1 P However, the system is P1 P33 not deadlock: x x – when P4 releases R2, this resource can be R2 P4 P 4 assigned to P3 No more cycle: Operating System Concepts – 9th 8.2 Silberschatz, 23 Galvin and Gagne ©2013  7.3 Methods for Handling Deadlocks 1. Ensure that the system will never enter a deadlock state: Deadlock prevention Deadlock avoidance 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 Operating System Concepts – 9th 8.2 Silberschatz, Galvin and Gagne ©2013  7.3 Methods for Handling Deadlocks Methods to handle deadlock Preventio Ignor Avoidance Detection Recovery n e If fails any of these: (4 conditions simultaneously arise Deadlock- Banker’s Process during deadlock): RAG RAG Detection Algorithm termination Algorithm Mutual Exclusion Resource Hold & Wait (Request) Preemption No Preemption Circular Wait Safety Resource-Request Algorithm Algorithm (Need) (Available) (Allocation) (Need) Operating System Concepts – 9th 8.2 Silberschatz, Galvin and Gagne ©2013  7.4 Deadlock Prevention Ensure that at least one of the necessary condition for deadlocks does not hold. Can be accomplished restraining the ways request can be made Mutual Exclusion – Must hold for non-sharable resources that can be accessed simultaneously by various processes. Therefore cannot be used for prevention. Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources 4 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 allocated to it. 4 Low resource utilization; starvation possible Operating System Concepts – 9th 8.2 Silberschatz, Galvin and Gagne ©2013  7.4 Deadlock Prevention No Preemption – not practical for most systems 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. Can be used in practice. Operating System Concepts – 9th 8.2 Silberschatz, Galvin and Gagne ©2013  7.8 Summary A deadlock state occurs when two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes. Three principal methods for dealing with deadlocks: 1. Use some protocol to prevent or avoid deadlocks. 2. Allow the system to enter a deadlock state, detect it, and then recover. 3. Ignore the problem altogether and pretend that deadlocks never occur in the system. Operating System Concepts – 9th 8.2 Silberschatz, Galvin and Gagne ©2013  End of Chapter 7 Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013