Ch5 Deadlock Princess Nora University PDF

Princess Nora University Computer Sciences Department Operating Systems CS 340 1  Chapter-5 Deadlocks (covered in chapter 7 of textbook) Introduction Chapter 5: Deadlocks 1. The Deadlock Problem 2. Deadlock Characterization 3. Methods for Han...

Princess Nora University Computer Sciences Department Operating Systems CS 340 1  Chapter-5 Deadlocks (covered in chapter 7 of textbook) Introduction Chapter 5: Deadlocks 1. The Deadlock Problem 2. Deadlock Characterization 3. Methods for Handling Deadlocks 3  OBJECTIVES:  To develop a description of deadlocks, which prevent sets of concurrent processes from completing their tasks  To present methods for Handling Deadlocks 4 The Deadlock Problem 5 The Deadlock Problem  In a multiprogramming environment, several processes may compete for a finite number of resources.  A process requests resources; if the resources are not available at that time, the process enters a waiting state.  Sometimes, a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a DEADLOCK. 6 The Deadlock Problem (cont..)  What is a deadlock problem?? o A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.  Example o System has 2 disk drives o P1 and P2 each hold one disk drive and each needs the other one  Note :– Most OSs do not prevent or deal with deadlocks 7 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 8  System Model  The resources are partitioned into several types (R1, R2,..., Rm ) o E.g.: CPU cycles, memory space, I/O devices Instances are  Each resource type Ri has Wi instances. identical o E.g :  If a system has (2) CPUs, then the resource type CPU has (2) instances.  The resource type printer may have (5) instances. 9 System Model (cont.)  A process must request a resource before using it and must release the resource after using it.  A process may request as many resources as it requires to carry out its task.  The number of requested resources MUST not exceed the total number of available resources in the system.  Each process utilizes a resource as follows: 1. Request >> If the request cannot be granted immediately because it is used by another process, then the requesting process must wait until it can acquire the resource. 2. Use 3. Release 10 System Model (cont.) A set of processes is in a deadlocked state when every process in the set is waiting for an event that can be caused only by another process in the set. 11 System Model (cont.)  Resource forms: Physical resources Logical resources e.g. printers, DVD drives, e.g. files memory space, and CPU cycles  Example:  consider a system with one printer and one DVD drive. Suppose that process Pi is holding the DVD and process Pj is holding the printer. If Pi requests the printer and Pj requests the DVD drive, a deadlock occurs. 12  The Deadlock Characterization 13  Deadlock Characterization Deadlock can arise if four conditions hold simultaneously: 1. Mutual exclusion: the resources are sharable or non sharable  mutual exclusion happens when only one process at a time can use a resource…(i.e. No resource sharing) 2. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes 14 Deadlock Characterization (cont..) 3. No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task 4. Circular wait:  There exists a set {P0, P1, …, Pn} of waiting processes such that : o P0 is waiting for a resource that is held by P1, o P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, o Pn is waiting for a resource that is held by P0. P0 P1 P2 Pn 15 Resource-Allocation Graph 16 Resource-Allocation Graph  Deadlocks can be described in terms of a directed graph called a system resource-allocation graph.  This graph consists of a set of vertices V and a set of edges E. V is partitioned into two types: E is partitioned into two types: P = {P1, P2, …, Pn}, the set Request edge – directed edge consisting of all the Pi R j processes in the system R = {R1, R2, …, Rm}, the set Assignment edge – directed edge consisting of all resource R j Pi (An instance of Rj has been allocated to Pi ) types in the system 17 Resource-Allocation Graph (Cont.)  Process  Resource Type with 4 instances  Pi requests instance of Rj Pi Rj  Pi is holding an instance of Rj Pi Rj 18 Example of a Resource Allocation Graph The sets P, R, and E:  P = {P1, P2, P3}  R = {R1, R2, R3, R4}  E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3} Resource instances:  (1) instance of resource type R1  (2) instances of resource type R2  (1) instance of resource type R3 (3) instances of resource type R4 19 Example of a Resource Allocation Graph Process states:  Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource type R1.  Process P2 is holding an instance of R1 and an instance of R2 and is waiting for an instance of R3.  Process P3 is holding an instance of R3. 20  How To Detect Deadlocks Using Resource Allocation Graph  How we recognize deadlock by using a Resource Allocation Graph??  If graph contains no cycles  no deadlock  If graph contains a cycle   If only one instance per resource type, then there is a deadlock  If several instances per resource type:  If cycle is breakable  no deadlock  If cycle is NOT breakable  deadlock 21  How To Detect Deadlocks Using Resource Allocation Graph (as a Flowchart) Is there is a cycle? y N Is all R’s has NO D.L. only one instance? y N It is a D.L. Is cycle breakable? y N NO D.L. It is a D.L. 22 Resource Allocation Graph - Example (1) Example (1):  NO deadlock because the graph contains NO cycles 23 Resource Allocation Graph - Example (2) Example (2):  The graph contains (2) cycles  Cycle (1) : P1 → R1 → P2 → R3 → P3 → R2 → P1  Cycle (2) : P2 → R3 → P3 → R2 → P2  It ‘s a dead lock situation …….why??  There is no chance to break the cycles (cycle1 & cycle2). 24 Resource Allocation Graph - Example (3) Example (3):  The graph contains one cycle Cycle : P1 → R1 → P3 → R2 → P1  NO dead lock situation.....WHY????  process P4 may release its instance of resource type R2…… That resource can then be allocated to P3, breaking the cycle. 25 Methods for Handling Deadlocks 26  Methods for Handling Deadlocks  OS can deal with the deadlock problem in one of three ways 1-prevent or avoid 2- Detect & 3-Ignore deadlocks Recover ensuring that the Allow the system to Ignore the problem and pretend system will never enter enter a deadlocked that the deadlock never occurs in a deadlocked state. state, detect it, and the system. recover.  Used by most operating systems, including Unix & windows  This method is cheaper than 1 or 2.  Solution: The system must be restarted manually 27  Method (1) for Handling Deadlocks  To ensure that deadlocks never occur, the system can use either 1. a deadlock prevention or 2. a deadlock-avoidance scheme 28  Method(1) for Handling Deadlocks Deadlock prevention Deadlock avoidance provides a set of methods to ensure that requires that the operating system be given at least one of the necessary 4 conditions additional information in advance concerning (explained before ) cannot hold. which resources a process will request and use during its lifetime. These methods prevent deadlocks by constraining how requests for resources With this additional knowledge, the can be made. operating system can decide for each request whether or not the process should wait. If a system did not employ either a deadlock prevention or deadlock avoidance, then a deadlock situation may arise 29 1- Deadlock Prevention 30  Deadlock Prevention Remove the possibility of deadlock occurring by denying one of the four necessary conditions: 1- Mutual Exclusion – not required for sharable resources; must hold for non-sharable resources.  That is, at least one resource must be non-sharable. Sharable resources, in contrast, do not require mutually exclusive access and thus cannot be involved in a deadlock 2- Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources by using one of the following protocols: The process must request all its or allow process to request resources resources before execution. only when the process has none  Problems-> Low resource utilization; starvation possible 31  Deadlock Prevention (Cont.) 3- 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  Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting  It is applied to resources whose state easily saved and restored later, such as CPU registers and memory space but it not applicable for resources such as printers  The main advantages is more better resource utilization  Problems  The cost of removing a process's resources  starvation possible  It is not applicable for all resource types such as printers 32  Deadlock Prevention (Cont.) 4- Circular Wait -  One way to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration.  let R = {R1, R2,..., Rm} be the set of resource types. We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering.  Formally, we define a one-to-one function F: R→N, where N is the set of natural numbers. 33  Deadlock Prevention (Cont.) 4- Circular Wait – cont..  Example : if the set of resource types R includes tape drives, disk drives, and printers,  then the function F might be defined as follows: F(tape drive) = 1 F(disk drive) = 5 F(printer) = 12  We can now consider the following protocol to prevent deadlocks:  Each process can request resources only in an increasing order of enumeration.  That is, a process can initially request any number of instances of a resource type —say, Ri. After that, the process can request instances of resource type Rj if and only if F(Rj ) > F(Ri ). …………..(Protocol#1) 34  Deadlock Prevention (Cont.) 4- Circular Wait – cont..  EX: a process that wants to use the tape drive and printer at the same time must first request the tape drive and then request the printer.  Alternatively, we can require that a process requesting an instance of resource type Rj must have released any resources Ri such that F(Ri ) ≥ F(Rj ). …..(Protocol#2)  Problems  Resources must be requested in ascending order of resource number rather than as needed 35 Thank you End of Chapter 5