Deadlocks_Lec2 PDF

Chapter 7: Deadlocks Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 7: Deadlocks System Model Deadlock Characterization Methods for Handling Deadlocks Deadlock Prev...

Chapter 7: Deadlocks Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 7: Deadlocks System Model Deadlock Characterization Methods for Handling Deadlocks Deadlock Prevention Deadlock Avoidance Deadlock Detection Recovery from Deadlock Operating System Concepts – 9th Edition 7.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 Edition 7.3 Silberschatz, Galvin and Gagne ©2013  System Model System consists of resources Resource types R1, R2,..., Rm CPU cycles, memory space, I/O devices Each resource type Ri has Wi instances. Each process utilizes a resource as follows:  request  use  release Operating System Concepts – 9th Edition 7.4 Silberschatz, Galvin and Gagne ©2013  Deadlocks A deadlock happens in operating system when two or more processes need some resource to complete their execution that is held by the other process. Operating System Concepts – 9th Edition 7.5 Silberschatz, Galvin and Gagne ©2013  Mutual Exclusion A deadlock occurs if the four Coffman conditions hold true. The Coffman conditions are given as follows − 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 Edition 7.6 Silberschatz, Galvin and Gagne ©2013  Mutual Exclusion There should be a resource that can only be held by one process at a time. In the diagram below, there is a single instance of Resource 1 and it is held by Process 1 only. Operating System Concepts – 9th Edition 7.7 Silberschatz, Galvin and Gagne ©2013  Hold and Wait A process can hold multiple resources and still request more resources from other processes which are holding them. In the diagram given below, Process 2 holds Resource 2 and Resource 3 and is requesting the Resource 1 which is held by Process 1. Operating System Concepts – 9th Edition 7.8 Silberschatz, Galvin and Gagne ©2013  No Preemption A resource cannot be preempted from a process by force. A process can only release a resource voluntarily. In the diagram below, Process 2 cannot preempt Resource 1 from Process 1. It will only be released when Process 1 relinquishes it voluntarily after its execution is complete. Operating System Concepts – 9th Edition 7.9 Silberschatz, Galvin and Gagne ©2013  Circular Wait A process is waiting for the resource held by the second process, which is waiting for the resource held by the third process and so on, till the last process is waiting for a resource held by the first process. This forms a circular chain. For example: Process 1 is allocated Resource2 and it is requesting Resource 1. Similarly, Process 2 is allocated Resource 1 and it is requesting Resource 2. This forms a circular wait loop. Operating System Concepts – 9th Edition 7.10 Silberschatz, Galvin and Gagne ©2013  Resource-Allocation Graph 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 Pi Rj assignment edge – directed edge Rj Pi Operating System Concepts – 9th Edition 7.11 Silberschatz, Galvin and Gagne ©2013  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 Operating System Concepts – 9th Edition 7.12 Silberschatz, Galvin and Gagne ©2013  Basic 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 deadlock Operating System Concepts – 9th Edition 7.13 Silberschatz, Galvin and Gagne ©2013  Example of a Resource Allocation Graph Operating System Concepts – 9th Edition 7.14 Silberschatz, Galvin and Gagne ©2013  Resource Allocation Graph With A Deadlock Operating System Concepts – 9th Edition 7.15 Silberschatz, Galvin and Gagne ©2013  Graph With A Cycle But No Deadlock Operating System Concepts – 9th Edition 7.16 Silberschatz, Galvin and Gagne ©2013  Methods for Handling Deadlocks Ensure that the system will never enter a deadlock state:  Deadlock prevention  Deadlock avoidance Allow the system to enter a deadlock state and then recover (Deadlock detection and recovery) Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX (Deadlock ignorance) Operating System Concepts – 9th Edition 7.17 Silberschatz, Galvin and Gagne ©2013  Deadlock Prevention Restrain the ways request can be made Mutual Exclusion – not required for sharable resources (e.g., read-only files); must hold for non-sharable resources  share the resources  But some resources are not sharable like printer 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 allocated to it.  Low resource utilization; starvation possible  Try to give all the resources needed by the process before it started Operating System Concepts – 9th Edition 7.18 Silberschatz, Galvin and Gagne ©2013  Deadlock 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  Make preemption true by using time quantum Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration  To remove circular wait just give the numbering to all resource so that the process can request resources in order. Operating System Concepts – 9th Edition 7.19 Silberschatz, Galvin and Gagne ©2013  Deadlock Avoidance Requires that the system has some additional a priori information available 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 be a circular-wait condition Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes Operating System Concepts – 9th Edition 7.20 Silberschatz, Galvin and Gagne ©2013  Basic Facts If a system is in safe state  no deadlocks If a system is in unsafe state  possibility of deadlock Avoidance  ensure that a system will never enter an unsafe state. Operating System Concepts – 9th Edition 7.21 Silberschatz, Galvin and Gagne ©2013  Safe State When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state A state of the system is called safe if the system can allocate all the resources requested by all the processes without entering into deadlock. Operating System Concepts – 9th Edition 7.22 Silberschatz, Galvin and Gagne ©2013  Safe, Unsafe, Deadlock State Operating System Concepts – 9th Edition 7.23 Silberschatz, Galvin and Gagne ©2013  Avoidance Algorithms Multiple instances of a resource type  Use the banker’s algorithm Single instance of a resource type  Use a resource-allocation graph Operating System Concepts – 9th Edition 7.24 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.25 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.26 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.27 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.28 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.29 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.30 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.31 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.32 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.33 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.34 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.35 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.36 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.37 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.38 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.39 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.40 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.41 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.42 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.43 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.44 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.45 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.46 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.47 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.48 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.49 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.50 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.51 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.52 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.53 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.54 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.55 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.56 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.57 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.58 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.59 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.60 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.61 Silberschatz, Galvin and Gagne ©2013  Banker’s Algorithm Operating System Concepts – 9th Edition 7.62 Silberschatz, Galvin and Gagne ©2013  End of Chapter 7 Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Additional References https://www.tutorialspoint.com/process-deadlocks-in- operating-system https://www.youtube.com/watch?v=0rs57wImGHk https://www.youtube.com/watch?v=qPuf5B5xPCs&list=PLdo5 W4Nhv31a5ucW_S1K3-x6ztBRD-PNa&index=19 https://www.youtube.com/watch?v=BAvtF6MCdgo https://www.youtube.com/watch?v=ekmFulGNMpo Operating System Concepts – 9th Edition 7.64 Silberschatz, Galvin and Gagne ©2013