Deadlock

Deadlock :

A process requests resources; and 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.

System Model :

        A system consists of a finite number of resources to be distributed among a number of competing processes. The resources are partitioned into several types, each consisting of some number of identical instances. Memory space, CPU cycles, files, and I/O devices (such as printers and DVD drives) are examples of resource types.

        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 designated task. Obviously, the number of resources requested may not exceed the total number of resources available in the system. In other words, a process cannot request three printers if the system has only two.

 Under the normal mode of operation, a process may utilize a resource in only the following sequence:

Request :

If the request cannot be granted immediately (for example, if the resource is being used by another process), then the requesting process must wait until it can acquire the resource.

Use :

The process can operate on the resource (for example, if the resource is a printer, the process can print on the printer).

Release :

The process releases the resource. 

Deadlock Prevention
We can prevent Deadlock by eliminating any one of the below four conditions.

Mutual exclusion

Hold and wait

No preemption

Circular wait

Mutual exclusion :

        At least one resource must be held in a non-sharable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.

Hold and wait :

A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.

No preemption :

Resources cannot be preempted.; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.

Circular wait :

 A set { P₁, P₂, ..., Pn } of waiting processes must exist such that P₁ is waiting for a resource held by R₂, P₂ is waiting for a resource held by R_{3 ,}P₃ is waiting for a resource held by R₄, and so on ... P_n is waiting for a resource held by R_m.

All the above four conditions must hold for a deadlock to occur.

Resource-Allocation Graph (RAG) :

       Deadlocks can be described more precisely 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.

 The set of vertices V is partitioned into two different types of nodes:

P = {P₁, P₂, . . .  P_n} the set consisting of all the active processes in the system, and

R = {R₁, R₂, ••• R_m}, the set consisting of all resource types in the system.

A directed edge from process P_i to resource type R_j is denoted by P_i -> R_j which signifies that process P_i has requested an instance of resource type R_j, and is currently waiting for that resource. A directed edge P_i —> R_j is called a Request Edge.

        A directed edge from resource type R_j to process P_i is denoted by R_j -> P_i and signifies that an instance of resource type R_j has been allocated to process P_i. A  directed edge R_j -> P_i  is called an Assignment Edge.

       Pictorially, we represent each process P_i as a circle and each resource type R_j as a rectangle. Since resource type R_j may have more than one instance, we represent each such instance as a dot within the rectangle as shown below

Process states :

Process P₁ is holding an instance of resource type R₂ and is waiting for an instance of resource type R₁.

Process P₂ 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.

When process P_i, requests an instance of resource type R_j, a request edge is inserted in the resource-allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge. When the process no longer needs access to the resource, it releases the resource; as a result, the assignment edge is deleted.

Given the definition of a resource-allocation graph, it can be shown that, if the graph contains no cycles, then no process in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist.

If each resource type has several instances, then a cycle does not necessarily imply that a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a sufficient condition for the existence of deadlock.

Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is held by process P3. Process P3 is waiting for either process P1 or process P2 to release resource R2. In addition, process P1 is waiting for process P2 to release resource R1.

Consider the resource-allocation graph as shown in above figure a cycle is formed but there is no deadlock.

From the above resource allocation graph Process P4 may release its instance of resource type R2 That resource can then be allocated to P3, breaking the cycle.

So we can say that  if a resource-allocation graph does not have a cycle, then the system is not in a deadlocked state. If there is a cycle, then the system may or may not be in a deadlocked state.

Deadlock Avoidance

1. The general idea behind deadlock avoidance is to prevent deadlocks from ever happening, by preventing at least one of the aforementioned conditions.
2. This requires more information about each process, AND tends to lead to low device utilization. ( I.e. it is a conservative approach. )
3. In some algorithms the scheduler only needs to know the maximum number of each resource that a process might potentially use. In more complex algorithms the scheduler can also take advantage of the schedule of exactly what resources may be needed in what order.
4. When a scheduler sees that starting a process or granting resource requests may lead to future deadlocks, then that process is just not started or the request is not granted.
5. A resource allocation state is defined by the number of available and allocated resources, and the maximum requirements of all processes in the system.

Safe and unsafe State

1. A state is safe if the system can allocate all resources requested by all processes without entering a deadlock state.
2. 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)
3. If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to deadlock.

Figure show Safe, unsafe, and deadlocked state spaces.

For example
consider a system with 9 tape drives, allocated as follows. Is this a safe state? What is the safe sequence?

States	Current Allocation	Maximum Needs	Availability
Process A	0	3	2
Process B	3	5
Process C	4	7

1. Since only 7 (0+3+4) tape drives are currently on allocation, two (2) tape drives are still available.
2. Process B can finish with only two additional tape drives.
3. Once Process B is done, it will release all 5 tape drives, making the number of available tape drives = 5.
4. With only three of these tape drives, either Process A or Process C may complete and release its tape drives.
5. This means that there are two possible safe sequences:
6. <Process B, Process A, Process C> and <Process B, Process C, Process A>.
7. Thus, we say that this is a safe state. 

For example
consider a system with 9 tape drives, allocated as follows. Is this a safe state? What is the safe sequence?

States	Current Allocation	Maximum Needs	Availability
Process A	5	7	1
Process B	2	5
Process C	1	3

1. Since 8 (5+2+1) tape drives are current allocation, only one tape drive is still available.
2. None of the three processes can complete with only one additional tape drive.
3. This means that there are no safe sequences possible.
4. Thus, we say that this is an unsafe state.

Resource-Allocation Graph Algorithm

1. If resource categories have only single instances of their resources, then deadlock states can be detected by cycles in the resource-allocation graphs.
2. 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.
3. 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. )
4. 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.
5. This approach works by denying requests that would produce cycles in the resource-allocation graph, taking claim edges into effect.
6. Consider for example what happens when process P2 requests resource R2:

Fig: Resource allocation graph for deadlock avoidance

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

Fig :An unsafe state in a resource allocation graph

Banker’s Algorithm

Bankers’s Algorithm is resource allocation and deadlock avoidance algorithm which test all the request made by processes for resources, it checks for the safe state, if after granting request system remains in the safe state it allows the request and if there is no safe state it doesn’t allow the request made by the process.

Inputs to Banker’s Algorithm:

1. Max need of resources by each process.
2. Currently allocated resources by each process.
3. Max free available resources in the system.

The request will only be granted under the below condition:

1. If the request made by the process is less than equal to max need to that process.
2. If the request made by the process is less than equal to the freely available resource in the system.

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:
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.
Safety Algorithm
In order to apply the Banker's algorithm, we first need an algorithm for determining whether a particular state is safe or not.

1. Let Work is a working copy of the available resources, which will be modified during the analysis and Finish is a vector of booleans indicating whether a particular process can finish. 
2. Initialize Work to Available, and Finish to false for all elements.
3. Find an i such that both
4. Finish[ i ] == false, and Need[ i ] <= Work. This process has not finished, but could with the given available working set. If no such i exists, go to step 6.
5. Set Work = Work + Allocation[ i ] or New availability  = availability + 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 4.
6. If finish[ i ] == true for all i, then the state is a safe state, because a safe sequence has been found.

Example for single instance :
consider a system with 12 tape drives, allocated as follows. Is this a safe state? What is the safe sequence?

States	Current Allocation	Maximum Needs	Availability
Process A	5	10	3
Process B	2	4
Process C	2	9

Step 1: Need = Max – Allocation

States	Maximum Needs - Current Allocation
Need A	5
Need B	2
Need C	7

Step 2: check whether the Need value of every process is <= Availability or not

• case 1: If it is true process the need value with the process state and find the new availability .
• case 2: If it is false stop processing the need value.

Need A = 5 <= 3 (false)
Need B = 2 <= 3 (true) Process B is processed
Step 3: Now find the New Availability by using the formula 
New Availability =  Availability of the process + Allocation 
New Availability  =  3 + 2 

New Availability  =  5

Step 4: Repeat the above process for all the process states and check whether it is safe or unsafe 

Need C = 7 <= 5 (false)
Need A = 5 <= 5 (true) Process A is processed

Step 5: Now find the New Availability by using the formula 
New Availability =  Availability of the process + Allocation  
New Availability  =  5 + 5 
New Availability  =  10

Need C = 7 <= 10 (true) Process C is processed

Step 6: Now if once all the states finished in checking there process states then the New Availability is equal to the given instance(12)
Now find the New Availability by using the formula 
New Availability =  Availability of the process + Allocation 
New Availability  = 10 + 2
New Availability  = 12
Therefore the safe sequence is 
<Process B ,Process A, Process C >

Example for multiple instance :
consider a system with 3,12,9 tape drives, allocated as follows. Is this a safe state? What is the safe sequence?

States	Current Allocation	Maximum Needs	Availability
Process A	1,4,2	2,7,4	1,3,2
Process B	0,3,1	0,5,6
Process C	1,2,4	3,4,7

Step 1: Need = Max – Allocation

States	Maximum Needs - Current Allocation
Need A	1,3,2
Need B	0,2,5
Need C	2,2,3

Step 2: check whether the Need value of every process is <= Availability or not

• case 1: If it is true process the need value with the process state and find the new availability .
• case 2: If it is false stop processing the need value.

Need A = 1,3,2 <= 1,3,2 (true) Process A is processed
Step 3: Now find the New Availability by using the formula 
New Availability =  Availability of the process + Allocation 
New Availability  =  1,3,2 + 1,4,2 

New Availability  =  2,7,4

Step 4: Repeat the above process for all the process states and check whether it is safe or unsafe 

Need B = 0,2,5 <= 2,7,4 (false)
Need C = 2,2,3 <= 2,7,4 (true) Process C is processed

Step 5: Now find the New Availability by using the formula 
New Availability =  Availability of the process + Allocation  
New Availability  =  2,7,4 + 1,2,4
New Availability  =  3,9,8

Need B = 0,2,5 <= 3,9,8 (true) Process B is processed

Step 6: Now if once all the states finished in checking there process states then the New Availability is equal to the given instance(12)
Now find the New Availability by using the formula 
New Availability =  Availability of the process + Allocation  
New Availability  = 3,9,8 + 0,3,1
New Availability  = 3,12,9
Therefore the safe sequence is

 <Process A ,Process C, Process B >

Disadvantages of the Banker's Algorithm:

1. It requires the number of processes to be fixed; no additional processes can start while it is executing.
2. It requires that the number of resources remain fixed; no resource may go down for any reason without the possibility of deadlock occurring.
3. Similarly, all of the processes guarantee that the resources loaned to them will be repaid in a finite amount of time. While this prevents absolute starvation, some pretty hungry processes might develop.
4. All processes must know and state their maximum resource need in advance.

Deadlock Detection

1. If deadlocks are not avoided, then another approach is to detect when they have occurred and recover somehow.
2. In addition to the performance hit of constantly checking for deadlocks, a policy / algorithm must be in place for recovering from deadlocks, and there is potential for lost work when processes must be aborted or have their resources preempted.

Single Instance of Each Resource Type
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.

Figure : (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.

Recovery From Deadlock

There are three basic approaches to recovery from deadlock:

1. Inform the system operator, and allow him/her to take manual intervention.
2. Terminate one or more processes involved in the deadlock
3. Preempt resources.

Process Termination

Two basic approaches, both of which recover resources allocated to terminated processes:

1. Terminate all processes involved in the deadlock. This definitely solves the deadlock, but at the expense of terminating more processes than would be absolutely necessary.
2. Terminate processes one by one until the deadlock is broken. This is more conservative, but requires doing deadlock detection after each step.

In the latter case there are many factors that can go into deciding which processes to terminate next:

• Process priorities.
• How long the process has been running, and how close it is to finishing.
• How many and what type of resources is the process holding. ( Are they easy to preempt and restore? )
• How many more resources does the process need to complete.
• How many processes will need to be terminated
• Whether the process is interactive or batch.

Resource Preemption

When preempting resources to relieve deadlock, there are three important issues to be addressed:

1. Selecting a victim - Deciding which resources to preempt from which processes involves many of the same decision criteria outlined above.
2. Rollback - Ideally one would like to roll back a preempted process to a safe state prior to the point at which that resource was originally allocated to the process. Unfortunately it can be difficult or impossible to determine what such a safe state is, and so the only safe rollback is to roll back all the way back to the beginning. ( I.e. abort the process and make it start over. )
3. Starvation - How do you guarantee that a process won't starve because its resources are constantly being preempted? One option would be to use a priority system, and increase the priority of a process every time its resources get preempted. Eventually it should get a high enough priority that it won't get preempted any more.

Deadlock Ignorance:

It is the most widely used approach among all the mechanism. This is being used by many operating systems mainly for end user uses. In this approach, the Operating system assumes that deadlock never occurs. ... In these types of systems, the user has to simply restart the computer in the case of deadlock.