The methods to eliminate deadlock using resource preemption

This set of Operating System Questions and Answers for Experienced people focuses on “Deadlock Recovery” and will also be useful for interview preparations for experienced people.

1. A deadlock can be broken by ____________ a) abort one or more processes to break the circular wait b) abort all the process in the system c) preempt all resources from all processes d) none of the mentioned

View Answer

Answer: a
Explanation: None.

2. The two ways of aborting processes and eliminating deadlocks are ____________ a) Abort all deadlocked processes b) Abort all processes c) Abort one process at a time until the deadlock cycle is eliminated d) All of the mentioned

View Answer

Answer: c
Explanation: None.

3. Those processes should be aborted on occurrence of a deadlock, the termination of which? a) is more time consuming b) incurs minimum cost c) safety is not hampered d) all of the mentioned

View Answer

Answer: b
Explanation: None.

4. The process to be aborted is chosen on the basis of the following factors? a) priority of the process b) process is interactive or batch c) how long the process has computed d) all of the mentioned

View Answer

Answer: d
Explanation: None.

5. Cost factors for process termination include ____________ a) Number of resources the deadlock process is not holding b) CPU utilization at the time of deadlock c) Amount of time a deadlocked process has thus far consumed during its execution d) All of the mentioned

View Answer

Answer: c
Explanation: None.

Check this: BCA MCQs | Operating System Books

6. If we preempt a resource from a process, the process cannot continue with its normal execution and it must be ____________ a) aborted b) rolled back c) terminated d) queued

View Answer

Answer: b
Explanation: None.

7. To _______ to a safe state, the system needs to keep more information about the states of processes. a) abort the process b) roll back the process c) queue the process d) none of the mentioned

View Answer

Answer: b
Explanation: None.

8. If the resources are always preempted from the same process __________ can occur. a) deadlock b) system crash c) aging d) starvation

View Answer

Answer: d
Explanation: None.

9. What is the solution to starvation? a) the number of rollbacks must be included in the cost factor b) the number of resources must be included in resource preemption c) resource preemption be done instead d) all of the mentioned

View Answer

Answer: a
Explanation: None.

Sanfoundry Global Education & Learning Series – Operating System.

  • Get Free Certificate of Merit in Operating System
  • Participate in Operating System Certification Contest
  • Become a Top Ranker in Operating System
  • Take Operating System Tests
  • Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  • Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

The methods to eliminate deadlock using resource preemption

Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.

The methods to eliminate deadlock using resource preemption

New Sidebar in Ninth Edition

  • There are four conditions that are necessary to achieve deadlock:
    1. Mutual Exclusion - At least one resource must be held in a non-sharable mode; If any other process requests this resource, then that process must wait for the resource to be released.
    2. Hold and Wait - A process must be simultaneously holding at least one resource and waiting for at least one resource that is currently being held by some other process.
    3. No preemption - Once a process is holding a resource ( i.e. once its request has been granted ), then that resource cannot be taken away from that process until the process voluntarily releases it.
    4. Circular Wait - A set of processes { P0, P1, P2, . . ., PN } must exist such that every P[ i ] is waiting for P[ ( i + 1 ) % ( N + 1 ) ]. ( Note that this condition implies the hold-and-wait condition, but it is easier to deal with the conditions if the four are considered separately. )
  • In some cases deadlocks can be understood more clearly through the use of Resource-Allocation Graphs, having the following properties:
    • A set of resource categories, { R1, R2, R3, . . ., RN }, which appear as square nodes on the graph. Dots inside the resource nodes indicate specific instances of the resource. ( E.g. two dots might represent two laser printers. )
    • A set of processes, { P1, P2, P3, . . ., PN }
    • Request Edges - A set of directed arcs from Pi to Rj, indicating that process Pi has requested Rj, and is currently waiting for that resource to become available.
    • Assignment Edges - A set of directed arcs from Rj to Pi indicating that resource Rj has been allocated to process Pi, and that Pi is currently holding resource Rj.
    • Note that a request edge can be converted into an assignment edge by reversing the direction of the arc when the request is granted. ( However note also that request edges point to the category box, whereas assignment edges emanate from a particular instance dot within the box. )
    • For example:

The methods to eliminate deadlock using resource preemption

Figure 7.1 - Resource allocation graph

  • If a resource-allocation graph contains no cycles, then the system is not deadlocked. ( When looking for cycles, remember that these are directed graphs. ) See the example in Figure 7.2 above.
  • If a resource-allocation graph does contain cycles AND each resource category contains only a single instance, then a deadlock exists.
  • If a resource category contains more than one instance, then the presence of a cycle in the resource-allocation graph indicates the possibility of a deadlock, but does not guarantee one. Consider, for example, Figures 7.3 and 7.4 below:

The methods to eliminate deadlock using resource preemption

Figure 7.2 - Resource allocation graph with a deadlock

The methods to eliminate deadlock using resource preemption

Figure 7.3 - Resource allocation graph with a cycle but no deadlock

  • A state is safe if the system can allocate all resources requested by all processes ( up to their stated maximums ) without entering a deadlock state.
  • More formally, a state is safe if there exists a safe sequence of processes { P0, P1, P2, ..., PN } such that all of the resource requests for Pi can be granted using the resources currently allocated to Pi and all processes Pj where j < i. ( I.e. if all the processes prior to Pi finish and free up their resources, then Pi will be able to finish also, using the resources that they have freed up. )
  • If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to deadlock. ( All safe states are deadlock free, but not all unsafe states lead to deadlocks. )

The methods to eliminate deadlock using resource preemption

Figure 7.6 - Safe, unsafe, and deadlocked state spaces.

  • For example, consider a system with 12 tape drives, allocated as follows. Is this a safe state? What is the safe sequence?
  Maximum Needs Current Allocation
P0

10

5

P1

4

2

P2

9

2

  • What happens to the above table if process P2 requests and is granted one more tape drive?
  • Key to the safe state approach is that when a request is made for resources, the request is granted only if the resulting allocation state is a safe one.

7.5.2 Resource-Allocation Graph Algorithm

  • If resource categories have only single instances of their resources, then deadlock states can be detected by cycles in the resource-allocation graphs.
  • In this case, unsafe states can be recognized and avoided by augmenting the resource-allocation graph with claim edges, noted by dashed lines, which point from a process to a resource that it may request in the future.
  • In order for this technique to work, all claim edges must be added to the graph for any particular process before that process is allowed to request any resources. ( Alternatively, processes may only make requests for resources for which they have already established claim edges, and claim edges cannot be added to any process that is currently holding resources. )
  • When a process makes a request, the claim edge Pi->Rj is converted to a request edge. Similarly when a resource is released, the assignment reverts back to a claim edge.
  • This approach works by denying requests that would produce cycles in the resource-allocation graph, taking claim edges into effect.
  • Consider for example what happens when process P2 requests resource R2:

The methods to eliminate deadlock using resource preemption

Figure 7.7 - Resource allocation graph for deadlock avoidance

  • The resulting resource-allocation graph would have a cycle in it, and so the request cannot be granted.

The methods to eliminate deadlock using resource preemption

Figure 7.8 - An unsafe state in a resource allocation graph

7.5.3 Banker's Algorithm

  • For resource categories that contain more than one instance the resource-allocation graph method does not work, and more complex ( and less efficient ) methods must be chosen.
  • The Banker's Algorithm gets its name because it is a method that bankers could use to assure that when they lend out resources they will still be able to satisfy all their clients. ( A banker won't loan out a little money to start building a house unless they are assured that they will later be able to loan out the rest of the money to finish the house. )
  • When a process starts up, it must state in advance the maximum allocation of resources it may request, up to the amount available on the system.
  • When a request is made, the scheduler determines whether granting the request would leave the system in a safe state. If not, then the process must wait until the request can be granted safely.
  • The banker's algorithm relies on several key data structures: ( where n is the number of processes and m is the number of resource categories. )
    • Available[ m ] indicates how many resources are currently available of each type.
    • Max[ n ][ m ] indicates the maximum demand of each process of each resource.
    • Allocation[ n ][ m ] indicates the number of each resource category allocated to each process.
    • Need[ n ][ m ] indicates the remaining resources needed of each type for each process. ( Note that Need[ i ][ j ] = Max[ i ][ j ] - Allocation[ i ][ j ] for all i, j. )
  • For simplification of discussions, we make the following notations / observations:
    • One row of the Need vector, Need[ i ], can be treated as a vector corresponding to the needs of process i, and similarly for Allocation and Max.
    • A vector X is considered to be <= a vector Y if X[ i ] <= Y[ i ] for all i.
  • In order to apply the Banker's algorithm, we first need an algorithm for determining whether or not a particular state is safe.
  • This algorithm determines if the current state of a system is safe, according to the following steps:
    1. Let Work and Finish be vectors of length m and n respectively.
      • Work is a working copy of the available resources, which will be modified during the analysis.
      • Finish is a vector of booleans indicating whether a particular process can finish. ( or has finished so far in the analysis. )
      • Initialize Work to Available, and Finish to false for all elements.
    2. Find an i such that both (A) Finish[ i ] == false, and (B) Need[ i ] < Work. This process has not finished, but could with the given available working set. If no such i exists, go to step 4.
    3. Set Work = Work + Allocation[ i ], and set Finish[ i ] to true. This corresponds to process i finishing up and releasing its resources back into the work pool. Then loop back to step 2.
    4. If finish[ i ] == true for all i, then the state is a safe state, because a safe sequence has been found.
  • ( JTB's Modification:
    1. In step 1. instead of making Finish an array of booleans initialized to false, make it an array of ints initialized to 0. Also initialize an int s = 0 as a step counter.
    2. In step 2, look for Finish[ i ] == 0.
    3. In step 3, set Finish[ i ] to ++s. S is counting the number of finished processes.
    4. For step 4, the test can be either Finish[ i ] > 0 for all i, or s >= n. The benefit of this method is that if a safe state exists, then Finish[ ] indicates one safe sequence ( of possibly many. ) )
  • Now that we have a tool for determining if a particular state is safe or not, we are now ready to look at the Banker's algorithm itself.
  • This algorithm determines if a new request is safe, and grants it only if it is safe to do so.
  • When a request is made ( that does not exceed currently available resources ), pretend it has been granted, and then see if the resulting state is a safe one. If so, grant the request, and if not, deny the request, as follows:
    1. Let Request[ n ][ m ] indicate the number of resources of each type currently requested by processes. If Request[ i ] > Need[ i ] for any process i, raise an error condition.
    2. If Request[ i ] > Available for any process i, then that process must wait for resources to become available. Otherwise the process can continue to step 3.
    3. Check to see if the request can be granted safely, by pretending it has been granted and then seeing if the resulting state is safe. If so, grant the request, and if not, then the process must wait until its request can be granted safely.The procedure for granting a request ( or pretending to for testing purposes ) is:
      • Available = Available - Request
      • Allocation = Allocation + Request
      • Need = Need - Request
  • Consider the following situation:

The methods to eliminate deadlock using resource preemption

  • And now consider what happens if process P1 requests 1 instance of A and 2 instances of C. ( Request[ 1 ] = ( 1, 0, 2 ) )

The methods to eliminate deadlock using resource preemption

  • What about requests of ( 3, 3,0 ) by P4? or ( 0, 2, 0 ) by P0? Can these be safely granted? Why or why not?
  • If each resource category has a single instance, then we can use a variation of the resource-allocation graph known as a wait-for graph.
  • A wait-for graph can be constructed from a resource-allocation graph by eliminating the resources and collapsing the associated edges, as shown in the figure below.
  • An arc from Pi to Pj in a wait-for graph indicates that process Pi is waiting for a resource that process Pj is currently holding.

The methods to eliminate deadlock using resource preemption

Figure 7.9 - (a) Resource allocation graph. (b) Corresponding wait-for graph

  • As before, cycles in the wait-for graph indicate deadlocks.
  • This algorithm must maintain the wait-for graph, and periodically search it for cycles.

7.6.2 Several Instances of a Resource Type

  • The detection algorithm outlined here is essentially the same as the Banker's algorithm, with two subtle differences:
    • In step 1, the Banker's Algorithm sets Finish[ i ] to false for all i. The algorithm presented here sets Finish[ i ] to false only if Allocation[ i ] is not zero. If the currently allocated resources for this process are zero, the algorithm sets Finish[ i ] to true. This is essentially assuming that IF all of the other processes can finish, then this process can finish also. Furthermore, this algorithm is specifically looking for which processes are involved in a deadlock situation, and a process that does not have any resources allocated cannot be involved in a deadlock, and so can be removed from any further consideration.
    • Steps 2 and 3 are unchanged
    • In step 4, the basic Banker's Algorithm says that if Finish[ i ] == true for all i, that there is no deadlock. This algorithm is more specific, by stating that if Finish[ i ] == false for any process Pi, then that process is specifically involved in the deadlock which has been detected.
  • ( Note: An alternative method was presented above, in which Finish held integers instead of booleans. This vector would be initialized to all zeros, and then filled with increasing integers as processes are detected which can finish. If any processes are left at zero when the algorithm completes, then there is a deadlock, and if not, then the integers in finish describe a safe sequence. To modify this algorithm to match this section of the text, processes with allocation = zero could be filled in with N, N - 1, N - 2, etc. in step 1, and any processes left with Finish = 0 in step 4 are the deadlocked processes. )
  • Consider, for example, the following state, and determine if it is currently deadlocked:

The methods to eliminate deadlock using resource preemption

  • Now suppose that process P2 makes a request for an additional instance of type C, yielding the state shown below. Is the system now deadlocked?

The methods to eliminate deadlock using resource preemption

7.6.3 Detection-Algorithm Usage

  • When should the deadlock detection be done? Frequently, or infrequently?
  • The answer may depend on how frequently deadlocks are expected to occur, as well as the possible consequences of not catching them immediately. ( If deadlocks are not removed immediately when they occur, then more and more processes can "back up" behind the deadlock, making the eventual task of unblocking the system more difficult and possibly damaging to more processes. )
  • There are two obvious approaches, each with trade-offs:
    1. Do deadlock detection after every resource allocation which cannot be immediately granted. This has the advantage of detecting the deadlock right away, while the minimum number of processes are involved in the deadlock. ( One might consider that the process whose request triggered the deadlock condition is the "cause" of the deadlock, but realistically all of the processes in the cycle are equally responsible for the resulting deadlock. ) The down side of this approach is the extensive overhead and performance hit caused by checking for deadlocks so frequently.
    2. Do deadlock detection only when there is some clue that a deadlock may have occurred, such as when CPU utilization reduces to 40% or some other magic number. The advantage is that deadlock detection is done much less frequently, but the down side is that it becomes impossible to detect the processes involved in the original deadlock, and so deadlock recovery can be more complicated and damaging to more processes.
    3. ( As I write this, a third alternative comes to mind: Keep a historical log of resource allocations, since that last known time of no deadlocks. Do deadlock checks periodically ( once an hour or when CPU usage is low?), and then use the historical log to trace through and determine when the deadlock occurred and what processes caused the initial deadlock. Unfortunately I'm not certain that breaking the original deadlock would then free up the resulting log jam. )