Chapter 8: Deadlocks PDF

Chapter 8: Deadlocks Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018  Outline  System Model  Deadlock Characterization  Methods for Handling Deadlocks  Deadlock Prevention...

Chapter 8: Deadlocks Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018  Outline  System Model  Deadlock Characterization  Methods for Handling Deadlocks  Deadlock Prevention  Deadlock Avoidance  Deadlock Detection  Recovery from Deadlock Operating System Concepts – 10th Edition 8.2 Silberschatz, Galvin and Gagne ©2018  Chapter Objectives  Illustrate how deadlock can occur when mutex locks are used  Define the four necessary conditions that characterize deadlock  Identify a deadlock situation in a resource allocation graph  Evaluate the four different approaches for preventing deadlocks  Apply the banker’s algorithm for deadlock avoidance  Apply the deadlock detection algorithm  Evaluate approaches for recovering from deadlock Operating System Concepts – 10th Edition 8.3 Silberschatz, Galvin and Gagne ©2018  Deadlock  A law passed by the Kansas legislature early in the 20th century “When two trains approach each other at a crossing, both shall come to a full stop, and neither shall start up again until the other has gone.”  The law essentially introduces a deadlock situation where no progress can be made Operating System Concepts – 10th Edition 8.4 Silberschatz, Galvin and Gagne ©2018  Deadlock  Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes  Let S and Q be two semaphores both are initialized to 1. P0 P1 wait(S); wait(Q); wait(Q); wait(S);...... signal(S); signal(Q); signal(Q); signal(S);  Consider if P0 executes wait(S) and P1 wait(Q). When P0 executes wait(Q), it must wait until P1 executes signal(Q)  However, P1 is waiting until P0 execute signal(S).  Since these signal() operations will never be executed, P0 and P1 are deadlocked. Operating System Concepts – 10th Edition 8.5 Silberschatz, Galvin and Gagne ©2018  System Model  System consists of finite number of resources Distributed among threads Resource types can be denoted as R1, R2,..., Rm  Examples: CPU cycles, memory space, I/O devices Each resource type Ri has Wi instances.  A computer having 4 CPUs thus have 4 instances resource type CPU  A semaphore “spot” with value 5 is equivalent to have 5 instances of resource type semaphore Operating System Concepts – 10th Edition 8.6 Silberschatz, Galvin and Gagne ©2018  Resource utilization  Each process utilizes a resource as following cycles: Request: The thread requests the resource. If the request cannot be granted immediately then the requesting thread must wait until it can acquire the resource. Use: The thread can operate on the resource  for example, if the resource is a mutex lock, the thread can access its critical section. Release: The thread releases the resource Operating System Concepts – 10th Edition 8.7 Silberschatz, Galvin and Gagne ©2018  Resource utilization by System Calls  Request and release of resources may be done by system calls: Examples:  request () and release () of a device,  wait () and signal () on semaphores  acquire () and release () of a mutex lock  open () and close () of a file  allocate () and free () of a memory space Operating System Concepts – 10th Edition 8.8 Silberschatz, Galvin and Gagne ©2018  Deadlock Characterization Deadlock can arise if four conditions hold simultaneously.  Mutual exclusion: only one thread at a time can use a resource (no sharing!)  Hold and wait: a thread holding at least one resource is waiting to acquire additional resource(s) held by other threads  No preemption: a resource can be released only voluntarily by the thread holding it - usually after that thread has completed its task  Circular wait: there exists a set {T0, T1, …, Tn} of waiting threads such that T0 is waiting for a resource that is held by T1, T1 is waiting for a resource that is held by T2, …, Tn–1 is waiting for a resource that is held by Tn, and Tn is waiting for a resource that is held by T0. Operating System Concepts – 10th Edition 8.9 Silberschatz, Galvin and Gagne ©2018  Resource-Allocation Graph  Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph A set of vertices V  V is partitioned into two types: – T = {T1, T2, …, Tn}, the set consisting of all the threads in the system. – R = {R1, R2, …, Rm}, the set consisting of all resource types in the system a set of edges E  Request edge – directed edge Ti Rj  Assignment edge – directed edge Rj Ti Operating System Concepts – 10th Edition 8.10 Silberschatz, Galvin and Gagne ©2018  Resource Allocation Graph Example  Vertices (Resource Instances): One instance of R1 Two instances of R2 One instance of R3 Three instance of R4  Edges T1 holds one instance of R2 and is waiting for an instance of R1 T2 holds one instance of R1, one instance of R2, and is waiting for an instance of R3 T3 is holds one instance of R3 Operating System Concepts – 10th Edition 8.11 Silberschatz, Galvin and Gagne ©2018  Resource Allocation Graph with a Deadlock Is there any deadlock here? Operating System Concepts – 10th Edition 8.12 Silberschatz, Galvin and Gagne ©2018  Resource Allocation Graph with a Deadlock Two minimal cycles with deadlock 1. T1 → R1 → T2 → R3 → T3 → R2 → T1 2. T2 → R3 → T3 → R2 → T2 Operating System Concepts – 10th Edition 8.13 Silberschatz, Galvin and Gagne ©2018  Graph with a Cycle But no Deadlock Cycle but no deadlock: T1 → R1 → T3 → R2 → T1 WHY? Operating System Concepts – 10th Edition 8.14 Silberschatz, Galvin and Gagne ©2018  Graph with a Cycle But no Deadlock Cycle but no deadlock: T1 → R1 → T3 → R2 → T1 WHY? Answer: Thread T4 may release its instance of resource type R2. That resource can then be allocated to T3, breaking the cycle. Operating System Concepts – 10th Edition 8.15 Silberschatz, Galvin and Gagne ©2018  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 – 10th Edition 8.16 Silberschatz, Galvin and Gagne ©2018  Methods for Handling Deadlocks (1)  Three ways/methods/approaches to handle deadlock by OS: 1. Use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlocked state. 2. Allow the system to enter a deadlocked state, detect it, and recover 3. Ignore the problem altogether and pretend that deadlocks never occur in the system. Operating System Concepts – 10th Edition 8.17 Silberschatz, Galvin and Gagne ©2018  Methods for Handling Deadlocks (2)  First method: Ensure that the system will never enter a deadlock state.  Two techniques: A. Deadlock prevention provides a set of methods or protocols to ensure that at least one of the four necessary conditions cannot hold  prevent deadlocks by constraining how requests for resources can be made. B. Deadlock avoidance: the operating system be given additional information in advance to be used to decide whether the current request can be satisfied or must be delayed.  The information are: i. resources currently available, ii. the resources currently allocated to each thread, iii. the future requests (demands) and releases of each thread Operating System Concepts – 10th Edition 8.18 Silberschatz, Galvin and Gagne ©2018  Methods for Handling Deadlocks (3)  Second method: Allow the system to enter a deadlock state and then detect it and recover Needs a deadlock detection algorithm and a deadlock recovery algorithm Example: Banker’s Algorithm Operating System Concepts – 10th Edition 8.19 Silberschatz, Galvin and Gagne ©2018  Methods for Handling Deadlocks (4)  Third Method: Ignore the problem and pretend that deadlocks never occur in the system. Disadvantages are: The undetected deadlock will cause the system’s performance to deteriorate, More threads, as they make requests for resources, will enter a deadlocked state. Eventually, the system will stop functioning and will need to be restarted manually  Although not viable, it is used in most operating systems! Because expense is one important consideration. Ignoring the possibility of deadlocks is cheaper than the other approaches.  deadlocks occur infrequently in some system, detection and recovery is a costly process Operating System Concepts – 10th Edition 8.20 Silberschatz, Galvin and Gagne ©2018  Deadlock Prevention Invalidate one of the four necessary conditions for deadlock:  Mutual Exclusion  Hold and Wait  No Preemption  Circular Wait Operating System Concepts – 10th Edition 8.21 Silberschatz, Galvin and Gagne ©2018  1. Mutual Exclusion  Mutual Exclusion – To hold the mutual-exclusion condition, at least one resource must be non-sharable. Convert resources to be sharable if possible Sharable resources do not require mutually exclusive access and thus cannot be involved in a deadlock.  A thread never needs to wait for a sharable resource  Read-only files are a good example of a sharable resource.  However, some resources are intrinsically non-sharable. Example: a mutex lock Therefore, we cannot prevent deadlocks by denying the mutual- exclusion condition Operating System Concepts – 10th Edition 8.22 Silberschatz, Galvin and Gagne ©2018  2. Hold and Wait  Hold and Wait – must guarantee that whenever a thread requests a resource, it does not hold any other resources.  Two possible protocols: Require threads to request and be allocated all its resources before it begins execution, or Allow thread to request resources only when the thread has none allocated to it, so a thread must release its held resources before making a new request  Two disadvantages: 1. Low resource utilization: resources may be allocated but unused for a long period even during the period the resources is not required.  For example, a thread may be allocated a mutex lock in its entire execution, yet only require it for a short duration 2. Starvation: A thread requiring several popular resources may have to wait indefinitely  Since at least one of the popular resources may always be allocated to other thread Operating System Concepts – 10th Edition 8.23 Silberschatz, Galvin and Gagne ©2018  3. No Preemption  No Preemption: there be no pre-emption of resources that have already been allocated  One protocol to break the condition is that 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 other threads are waiting Thread will be restarted only when it can regain its old resources, as well as the new ones that it is requesting  Other protocol: If resource is not available, preempt resource from other waiting threads  This protocol is often applied to resources whose state can be easily saved and restored later, e.g., CPU registers and database transactions.  It cannot generally be applied to such resources as mutex locks and semaphores, precisely the type of resources where deadlock occurs most commonly. Operating System Concepts – 10th Edition 8.24 Silberschatz, Galvin and Gagne ©2018  4. Circular Wait  Invalidating the circular wait condition is the most common.  Circular Wait: Impose a total ordering of all resource types, and require that each thread requests resources in an increasing order of enumeration Simply assign each resource (i.e., mutex locks) a unique number. Operating System Concepts – 10th Edition 8.25 Silberschatz, Galvin and Gagne ©2018  4. Circular Wait (cont)  Resources must be acquired in order.  For example, if first_mutex = 1 second_mutex = 5  code for thread_two could not be written as follows: second mutex must not precede first mutex call Ordering the resources is not sufficient to prevent circular wait, but needs programmer’s action to implement the protocol in their code Operating System Concepts – 10th Edition 8.26 Silberschatz, Galvin and Gagne ©2018  Deadlock Avoidance Requires that the system has some additional a priori information available Used to avoid circular-wait condition  Simplest and most useful model requires that each thread 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 resources  the number of allocated resources, and  the maximum demands of the processes Operating System Concepts – 10th Edition 8.27 Silberschatz, Galvin and Gagne ©2018  Safe State  When a thread requests an available resource, system must decide if immediate allocation leaves the system in a safe state  A state is safe if the system can allocate resources to each thread (up to its maximum) in some order and still avoid a deadlock  Safe State: if there exists a (safe) sequence of ALL the threads in the systems such that for each Ti, the resources that Ti can still request can be satisfied by currently available resources plus resources held by all the Tj, with j < i  That is: If Ti resource needs are not immediately available, then Ti can wait until all Tj have finished When Tj is finished, Ti can obtain needed resources, execute, release allocated resources, and terminate When Ti terminates, Ti +1 can obtain its needed resources, and so on Operating System Concepts – 10th Edition 8.28 Silberschatz, Galvin and Gagne ©2018  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 – 10th Edition 8.29 Silberschatz, Galvin and Gagne ©2018  Safe, Unsafe, Deadlock State Operating System Concepts – 10th Edition 8.30 Silberschatz, Galvin and Gagne ©2018  Safe, Unsafe, Deadlock State Consider the system has 12 resources, 9 are already held by threads so 3 are left to be assigned Threads Maximum Need Currently held Balance T0 10 5 5 T1 4 2 2 T2 9 2 7  The sequence is a safe sequence  T1: T1 will be assigned 2 more (out of 3, one will be free afterwards) to meet its need, then it will use, complete, and release all 4, making total of 5 left (4+1).  T0: T0 will be assigned all 5 to meets its max demand of 10 and will eventually release all of the 10 after use.  T2 :Then, T2 can be safely assigned 7 of the 10 free resources to meet its max demand. When, T2 releases, there will be 12 free in total. Operating System Concepts – 10th Edition 8.31 Silberschatz, Galvin and Gagne ©2018  Safe, Unsafe, Deadlock State Total 12 resources, 9 are already held by threads, 3 are free Threads Max Need Currently held Balance T0 10 5 5 T1 4 2 2 T2 9 2 7  A system can go from a safe state to unsafe state  For example, lets at the current state, thread T2 requests one more resource and granted allocation, resulting only 2 free resources Threads Max Need Currently held Balance T0 10 5 5 T1 4 2 2 T2 9 3 6 Only T1 can proceed now. Once T1 has finished, there will be only 4 left, neither T0 (needs 5) nor T2 (needs 6) can proceed Operating System Concepts – 10th Edition 8.32 Silberschatz, Galvin and Gagne ©2018  Avoidance Algorithms  Single instance of a resource type Use a resource-allocation graph  Multiple instances of a resource type Use the Banker’s Algorithm Operating System Concepts – 10th Edition 8.33 Silberschatz, Galvin and Gagne ©2018  Resource-Allocation Graph Scheme  Claim edge Ti Rj indicated that process Tj may request resource Rj; represented by a dashed line “- - - - ->”  Request edge: Claim edge converts to request edge when a thread requests a resource  Assignment edge: Request edge converted to an assignment edge when the resource is allocated to the thread When a resource is released by a thread, assignment edge reconverts to a claim edge  Resources must be claimed a priori in the system Operating System Concepts – 10th Edition 8.34 Silberschatz, Galvin and Gagne ©2018  Resource-Allocation Graph Both T1 and T2 Operating System Concepts – 10th Edition 8.35 Silberschatz, Galvin and Gagne ©2018  Unsafe State In Resource-Allocation Graph Suppose T2 request R2 but allocating the currently free R2 to T2 creates a cycle, leading to an unsafe state Operating System Concepts – 10th Edition 8.36 Silberschatz, Galvin and Gagne ©2018  Resource-Allocation Graph Algorithm  Suppose that thread Ti requests a resource Rj  The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph cycle-detection algorithm can be used to detect cycles The complexity of this algorithm is n2 , where n represents number of threads  It does not work in system when resources can have multiple instances  Banker’s algorithm can solve this! Operating System Concepts – 10th Edition 8.37 Silberschatz, Galvin and Gagne ©2018  Banker’s Algorithm  Multiple instances of resources  Each thread must have a priori claim of maximum use  When a thread requests a resource, it may have to wait  When a thread gets all its resources it must return them in a finite amount of time Operating System Concepts – 10th Edition 8.38 Silberschatz, Galvin and Gagne ©2018  Data Structures for the Banker’s Algorithm Let n = number of processes, and m = number of resources types.  Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available  Max: n x m matrix. If Max [i, j] = k, then process Ti may request at most k instances of resource type Rj  Allocation: n x m matrix. If Allocation[i, j] = k then Ti is currently allocated k instances of Rj We can treat each row in the matrices Allocation as vectors. Refer to them as Allocationi The vector Allocationi specifies the resources currently allocated to thread Ti;  Need: n x m matrix. If Need[i, j] = k, then Ti may need k more instances of Rj to complete its task then vector Needi specifies the additional resources that thread Ti may still request Need [i, j] = Max[i, j] – Allocation [i, j] Operating System Concepts – 10th Edition 8.39 Silberschatz, Galvin and Gagne ©2018  Rules X ≤ Y  Let X and Y be vectors of length n.  We say that X ≤ Y if and only if X[i] ≤ Y[i] for all i = 1, 2,..., n.  Suppose, X = (1,7,3,2) and Y = (0,3,2,1),  Then, Y ≤ X since 1 > 0 and 7 > 3 and 3 > 2 and 2 > 1 Operating System Concepts – 10th Edition 8.40 Silberschatz, Galvin and Gagne ©2018  Safety Algorithm 1. Let Work and Finish be vectors of length m and n, respectively. Initialize: Work = Available Finish [i] = false for i = 0, 1, …, n- 1 2. Find an i such that both: (a) Finish [i] = false (b) Needi  Work If no such i exists, go to step 4 3. Work = Work + Allocationi Finish[i] = true go to step 2 4. If Finish [i] == true for all i, then the system is in a safe state Operating System Concepts – 10th Edition 8.41 Silberschatz, Galvin and Gagne ©2018  Resource-Request Algorithm for Process Pi Requesti = request vector for process Ti. If Requesti [j] = k then process Ti wants k instances of resource type Rj 1. If Requesti  Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim 2. If Requesti  Available, go to step 3. Otherwise Ti must wait, since resources are not available 3. Pretend to allocate requested resources to Ti by modifying the state as follows: Available = Available – Requesti; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti; If safe  the resources are allocated to Ti If unsafe  Ti must wait, and the old resource-allocation state is restored Operating System Concepts – 10th Edition 8.42 Silberschatz, Galvin and Gagne ©2018  Example of Banker’s Algorithm  Five threads T0 T1 T2 T3 T4;  Three resource types: A (10 instances), B (5 instances), and C (7 instances)  Snapshot at current time: Allocation Max Need Available ABC ABC ABC ABC T0 010 753 743 332 T1 200 322 122 T2 302 902 600 T3 211 222 011 T4 002 433 431  The system is in a safe state since the sequence < T1, T3, T4, T2, T0> satisfies safety criteria Operating System Concepts – 10th Edition 8.43 Silberschatz, Galvin and Gagne ©2018  Example: T1 Request (1,0,2)  Can request for (1,0,2) by T1 be granted? Check that Request  Available (that is, (1,0,2)  (3,3,2)  true Allocation Need Available ABC ABC ABC T0 010 743 230 T1 302 020 T2 302 600 T3 211 011 T4 002 431 Executing safety algorithm shows that sequence < T1, T3, T4, T0, T2> satisfies safety requirement  Can request for (3,3,0) by T4 be granted? Nope, not enough available resources  Can request for (0,2,0) by T0 be granted? Nope, enough available resources but still lead to an unsafe state. Operating System Concepts – 10th Edition 8.44 Silberschatz, Galvin and Gagne ©2018  Deadlock Detection  If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm then a deadlock situation may occur.  In this environment, the system may provide:  An algorithm that examines the state of the system to determine/detect whether a deadlock has occurred  An algorithm to recover from the deadlock Operating System Concepts – 10th Edition 8.45 Silberschatz, Galvin and Gagne ©2018  Detection Algorithm Single Instance of Each Resource Type  Require to do this: Maintain wait-for graph Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlock  Waif-for Graph: Obtain this graph from the resource-allocation graph by removing the resource nodes and collapsing the appropriate edges. an edge from Ti to Tj in a wait-for graph implies that thread Ti is waiting for thread Tj to release a resource that Ti needs. An edge Ti → Tj exists in a wait-for graph if and only if the corresponding resource-allocation graph contains two edges Ti → Rq and Rq → Tj for some resource Rq  An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph Operating System Concepts – 10th Edition 8.46 Silberschatz, Galvin and Gagne ©2018  Resource-Allocation Graph and Wait-for Graph Resource-Allocation Graph Corresponding wait-for graph Operating System Concepts – 10th Edition 8.47 Silberschatz, Galvin and Gagne ©2018  Several Instances of a Resource Type  Available: A vector of length m indicates the number of available resources of each type  Allocation: An n x m matrix defines the number of resources of each type currently allocated to each thread.  Request: An n x m matrix indicates the current request of each thread. If Request [i][j] = k, then thread Ti is requesting k more instances of resource type Rj. Operating System Concepts – 10th Edition 8.48 Silberschatz, Galvin and Gagne ©2018  Detection Algorithm 1. Let Work and Finish be vectors of length m and n, respectively Initialize: a) Work = Available b) For i = 1,2, …, n, if Allocationi  0, then Finish[i] = false; otherwise, Finish[i] = true 2. Find an index i such that both: a) Finish[i] == false b) Requesti  Work If no such i exists, go to step 4 3. Work = Work + Allocationi Finish[i] = true go to step 2 4. If Finish[i] == false, for some i, 1  i  n, then the system is in deadlock state. Moreover, if Finish[i] == false, then Ti is deadlocked Operating System Concepts – 10th Edition 8.49 Silberschatz, Galvin and Gagne ©2018  Detection Algorithm (Cont.) Algorithm requires an order of O(m x n2) operations to detect whether the system is in deadlocked state Operating System Concepts – 10th Edition 8.50 Silberschatz, Galvin and Gagne ©2018  Example of Detection Algorithm  Five threads T0 through T4;  Three resource types : A (7 instances), B (2 ins.), and C (6 ins.)  Snapshot at time T0: Allocation Request Available ABC ABC ABC T0 010 000 000 T1 200 202 T2 303 000 T3 211 100 T4 002 002  Sequence will result in Finish[i] = true for all i Operating System Concepts – 10th Edition 8.51 Silberschatz, Galvin and Gagne ©2018  Example (Cont.)  T2 requests an additional instance of type C Request ABC T0 000 T1 202 T2 001 T3 100 T4 002  State of system? Can reclaim resources held by thread T0, but insufficient resources to fulfill other processes; requests Deadlock exists, consisting of processes T1, T2, T3, and T4 Operating System Concepts – 10th Edition 8.52 Silberschatz, Galvin and Gagne ©2018  Detection-Algorithm Usage  When, and how often, to invoke depends on: How often a deadlock is likely to occur? How many processes will need to be rolled back?  one for each disjoint cycle  If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked threads “caused” the deadlock. Operating System Concepts – 10th Edition 8.53 Silberschatz, Galvin and Gagne ©2018  Recovery from Deadlock: Process Termination  Abort all deadlocked threads This method clearly will break the deadlock cycle, but at great expense. The deadlocked processes may have computed for a long time, and the results of these partial computations must be discarded and probably will have to be recomputed later.  Abort one process at a time until the deadlock cycle is eliminated This method incurs considerable overhead, since after each process is aborted, a deadlock-detection algorithm must be invoked to determine whether any processes are still deadlocked Operating System Concepts – 10th Edition 8.54 Silberschatz, Galvin and Gagne ©2018  Recovery from Deadlock: Process Termination  In which order should we choose to abort? 1. Priority of the thread 2. How long has the thread computed, and how much longer to completion 3. Resources that the thread has used 4. Resources that the thread needs to complete 5. How many threads will need to be terminated 6. Is the thread interactive or batch? Operating System Concepts – 10th Edition 8.55 Silberschatz, Galvin and Gagne ©2018  Recovery from Deadlock: Resource Preemption  Selecting a victim – Which resources and which processes are to be preempted? determine the order of pre-emption to minimize cost  Rollback – return to some safe state, restart the thread for that state it is difficult to determine what a safe state is, the simplest solution is a total rollback  Starvation – same thread may always be picked as victim, include number of rollback in cost factor Operating System Concepts – 10th Edition 8.56 Silberschatz, Galvin and Gagne ©2018  End of Chapter 8 Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018