In this article, you will learn about deadlock prevention method –* Banker’s algorithm* and *Resource allocation graph*. You will also learn about 4 conditions for deadlock.

Let’s start with the resource allocation graph.

Resource Allocation graph describes the deadlock more precisely. It has a set of vertices V and set of edges E.

**Vertices types**

Vertices are divided into

P = {P1, P2, P3, . . . , Pn} set of active processes in the system.

R = { R1, R2, R3, …, Rm} set of vertices that represent the resources.

**Edge types**

Pi -> Rj means Pi has requested resource Ri and waiting for it is called request edge

Rj -> Pi means that the instance of resource Ri is allocated to process Pi called the assignment edge.

Resource Rj may have more than one instance.

**Example:**

**Vertices**

P = {P1, P2, P3}

R = {R1, R2, R3, R4}

**Instances of Resource**

R1 = 1

R2 = 2

R3 = 1

R4 = 0

**Edges **

**Request Edges: P1 -> R1, P2 -> R3**

**Assignment Edges: R1 -> P2, R3 -> P3, R2 -> P1, R2 -> P2**

**R2 -> P1 -> R1 -> P2 -> R3 -> P3 (No Cycle)**

**R2 -> P2 -> R3 -> P3 (No Cycle)**

***A CYCLE IN THE GRAPH IS BOTH A NECESSARY but not a SUFFICIENT CONDITION FOR A DEADLOCK.**

*** CYCLE INVOLVE A SET OF RESOURCES WHERE EACH RESOURCE HAS ONLY ONE INSTANCE.**

**THEN DEADLOCK OCCURS.**

**Methods for handling deadlock**

- First method is to prevent deadlock
- the Second method is to deadlock avoidance by managing system resources. This is done by giving additional information about process request and whether that request can be satisfied.
- Another way is to let deadlock occur and place an algorithm that recovers the system from deadlock.
- If no algorithm is available for recovery, then the system must be restarted manually.

Contents

#### Deadlock Prevention

There are 4 conditions that must hold for a deadlock to occur and if we prevent any one of them from occurring when there is no deadlock.

**Mutual exclusion**

A non-sharable resource must give mutual-exclusive right to access it for any process. A sharable resource such a read-only file has no problem sharing the resource and does not need mutual-exclusive rights.

Mutual exclusive rights do not have an effect on deadlock prevention.

**Hold and Wait**

There are two ways this can be done.

- First allocate all the resource to the system before it executes.
- Second way, the process can be allocated resource only when it has none and if it requires an additional resource, leave the existing one.

Example:

Suppose a process copies files from DVD and then sorts them and print the result.

DVD player/writer, disk drive and printer must be allocated at the beginning itself using the first approach.

In the second approach, the first DVD drive the given and when the process finished with the DVD drive and reads all the information, it releases the DVD drive.

Next to Disk drive is allocated before copying the files to the disk drive and when a task is over it is released. Similarly, the printer does the printing for process and process release the printer.

**No Preemption**

If a process fails to get all the resource it needs, then it must release the resource it is already holding.

It will only start when all the resources including the new one are available.

If a process is available, allocate them otherwise check if it is held by some waiting process, if yes then preempt the waiting process and allocate to the requesting process.

This technique cannot be applied to I/O devices.

**Circular Wait**

Allocate resource in increasing order of enumeration. R = {R1, R2 … Rn}. Each process gets a number. We can say that there is a one-to-one function from resource to natural number.

F: R -> N, where N is a set of natural numbers.

Suppose there are three resources

F (tape drive) = 1

F (disk drive) = 4

F (printer) = 10

First Process can request for any number of instance of the resource Ri and after that, the process can request an instance of resource Rj if and only if F (Rj) > F (Ri).

#### Deadlock Avoidance

Deadlock avoidance depends on additional information about how a request should be requested. The system can then make decisions based on currently available resource, the resource allocated to each process and future request & release of each process.

Each process must give prior information on the maximum resource of each type it needs. The system then uses deadlock-avoidance algorithms and checks the resource allocation state to check that a circular wait never occurs.

**Safe State**

A state is safe if the system can allocate resource to each process and still (to its maximum) in some order and still avoid deadlock. There exists a safe sequence.

Suppose there is a sequence of processes P = {P1, P2, P3, … Pn} is a safe sequence for current allocation state if for each process, Pi request for a resource can be satisfied by currently available resources plus resources held by Pj, where j < i.

If the resource for Pi is not available, then it must wait till all Pj have finished. Once a resource is obtained Pi can execute and terminate and release all the resources.

Then Pi+1th process competes for the resources and so on. If such a safe state does not exist then the system is said to be in an unsafe state.

An unsafe state does not mean a deadlock state but it may lead to a deadlock state.

Deadlock-avoidance algorithm makes sure that resource is allocated to process only when it leaves the system in a safe state. Otherwise, it has to wait.

#### Resource-Allocation-Graph Algorithm

A new edge is introduced in the resource allocation graph called the Claim edge. Pi -> Rj means that it is a claim edge and shown as a dashed line in the resource allocation graph.

A claim edge shows “Future requests” or “Future Assignments” and converted to request edge and assignment edge respectively.

The request is granted only if converting request edge to an assignment edge does not lead to the formation of a cycle in the graph, if the allocation to Pi will form a cycle that will lead the system to an unsafe state, then the process Pi must wait till the resource is available.

**Example:**

**P = {P1, P2}**

**R = {R1, R2}**

CLAIM EDGE | CONVERT TO REQUEST EDGE | CONVERT TO ASSIGNMENT EDGE |

P1 -> R1 | YES | YES |

P2 -> R2 | YES | YES |

P1 -> R2 | NO ( Make a cycle) | NO |

P2 -> R1 | YES | NO (P1 using R1) |

**Banker’s Algorithm**

The algorithm works like a bank hence the name. Any new process must declare the maximum number of instance of each resource type that it needs. It must not exceed the total resource.

Before allocating the system must make sure that after allocation it is not leaving the system in the unsafe state.

The data structures used in bankers algorithm where n is the number of processes and m is the number of resource types is as follows,

**Available**– number of available resource of each type of length m. Available[j] = k means k instance of resource Rj.**Max**– It is n x m matrix for maximum number instance of resources required by the process. Max[i][j] = k means Pi process requires k instance of resource Rj.**Allocation**– it is also n x m matrix for number of resources of each type allocated to each process. Allocation [i] [j] = k means process Pi is allocated k instances of resources of Rj.**Need**– it is n x m matrix that remaining need for each process. Need[i] [k] = k means that the process Pi need k instance of resource type Rj to finish it’s tasks.

**Need[i] [j] = Max[i] [j] – Allocation[i] [j]**

#### Banker’s Algorithm Procedure

If X and Y are two vectors, then X < Y only if X[i] ≤ Y[i] for all I = 1, 2, 3, n.

Conversely, Y < X if Y[i] ≤ X[i] and Y ≠ X.

Allocation (i) means resource currently allocated to process Pi and need (i) means additional resource required by process Pi.

**Safety Algorithm**

- Let Work and Finish be two vectors of length m and n respectively. Initialize
**Work = Available and Finish[i] = false for I = 0, 1, 2, . . . , n-1.** - Find an index ‘i’ such that
**Finish[i] = false****Need(i) <= Work**

If no such ‘i’ exists then go to step 4.

**Work = Work + Allocation (i)**

**Finish[i] = true **

Go to step 2

- If
**Finish[i] = true**for all i then the system is in safe state.

Order of the above algorithm is **O (mn ^{2}).**

#### Resource-Request Algorithm

This algorithm determines whether the request can be safely granted.

Request (i) is a request vector for process Pi. If Request (i) [j] = k, then process Pi wants k instance of resource R[j]. When a request for a resource is made, following activities take place

- If
**Request (i) ≤ Need (i)**, go to step 2, otherwise raise error because process has exceeded its maximum claim. - If
**Request (i) ≤ Available,**go to step 3. Otherwise Pi must wait, since the resources are not available. - Let system pretend that it has allocated the resources to Pi as follows

** Available = Available – Request (i)**

** Allocation (i) = Allocation (i) + Request (i)**

** Need (i) = Need (i) – Request (i)**

If the resulting resource-allocation state is in a safe state, the transaction is completed and process Pi gets the resource. If not then Pi must wait and old resource-allocation state is restored.

**Example: **

P = {P0, P1, P2, P3, P4}

R = {A, B, C}

#### Instances of Resources

A = 10, B = 5, C = 7

At t_{0} time following snapshot of system is captured.

Allocation | Maximum | Available | |||||||

A | B | C | A | B | C | A | B | C | |

P0 | 0 | 1 | 0 | 7 | 5 | 3 | 7 | 5 | 5 |

P1 | 2 | 0 | 0 | 3 | 2 | 2 | 5 | 3 | 2 |

P2 | 3 | 0 | 2 | 9 | 0 | 2 | 10 | 5 | 7 |

P3 | 2 | 1 | 1 | 2 | 2 | 2 | 7 | 4 | 3 |

P4 | 0 | 0 | 2 | 4 | 3 | 3 | 7 | 4 | 5 |

We know that Need (i) = Max (i) – Allocation (i)

NEED Matrix | |||

A | B | C | |

P0 | 7 | 4 | 3 |

P1 | 1 | 2 | 2 |

P2 | 6 | 0 | 0 |

P3 | 0 | 1 | 1 |

P4 | 4 | 3 | 1 |

**Check if the System is in Safe State **

**Iteration 1**

Step 1: Need (i) <= Available, if True then,

Need (0) > Available => (7, 4, 3) > (3, 3, 2)

Need (1) < Available => (1, 2, 2) < (3, 3, 2)

Step 2: Work = Work + Allocation (i)

Work = (3, 3, 2) + (2, 0, 0) = (5, 3, 2)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1}

**Iteration 2 **

Step 1: Need (i) <= Available, if True then,

Need (2) > Available => (6, 0, 0) > (5, 3, 2)

Need (3) < Available => (0, 1, 1) < (5, 3, 2)

Step 2: Work = Work + Allocation (i)

Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3}

**Iteration 3 **

Step 1: Need (i) <= Available, if True then,

Need (4) <= Available => (4, 3, 1) < (7, 4, 3)

Step 2: Work = Work + Allocation (i)

Work = (7, 4, 3) + (0, 0, 2) = (7, 4, 5)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3, P4}

**Iteration 4**

Step 1: Need (i) <= Available, if True then,

Need (0) <= Available => (7, 4, 3) < (7, 4, 5)

Step 2: Work = Work + Allocation (i)

Work = (7, 4, 5) + (0, 1, 0) = (7, 5, 5)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3, P4, P0}

**Iteration 4**

Step 1: Need (i) <= Available, if True then,

Need (2) <= Available => (6, 0, 0) < (7, 5, 5)

Step 2: Work = Work + Allocation (i)

Work = (7, 5, 5) + (3, 0, 2) = (10, 5, 7)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3, P4, P0, P2}

Handling a Request

Suppose process P1 requested resource (1, 0, 2) which is less than the available resources (3, 3, 2).

Request (i) <= Available => (1, 0, 2) < (3, 3, 2).

The system will pretend that the resource is allocated successfully, but will run the Safety Algorithm demonstrated above and verify if whether allocation to Pi will leave the system in an UNSAFE state.

Example:

Suppose P0 requested for **(0, 2, 0)**, then we find that **Request (0) < Available**. Adjust the following

*Available= Available – Request;;*

*Allocation; =Allocation +Request;;*

*Need; =Need- Request;*

Allocation | Maximum | Available | |||||||

A | B | C | A | B | C | A | B | C | |

P0 | 0 | 3 | 0 | 7 | 5 | 3 | 3,7 | 1,5 | 2,5 |

P1 | 2 | 0 | 0 | 3 | 2 | 2 | 5 | 1 | 2 |

P2 | 3 | 0 | 2 | 9 | 0 | 2 | |||

P3 | 2 | 1 | 1 | 2 | 2 | 2 | 7 | 2 | 3 |

P4 | 0 | 0 | 2 | 4 | 3 | 3 | 7 | 2 | 5 |

We then run the Safety Algorithm

NEED Matrix | |||

A | B | C | |

P0 | 7 | 2 | 3 |

P1 | 1 | 2 | 2 |

P2 | 6 | 0 | 0 |

P3 | 0 | 1 | 1 |

P4 | 4 | 3 | 1 |

**Iteration 2**

Step 1: Need (i) <= Available, if True then,

Need (2) > Available => (6, 0, 0) > (5, 1, 2)

Need (3) <= Available => (0, 1, 1) < (5, 1, 2)

Step 2: Work = Work + Allocation (i)

Work = (5, 1, 2) + (2, 1, 1) = (7, 2, 3)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3}

**Iteration 1**

Step 1: Need (i) <= Available, if True then,

Need (0) > Available => (7, 2, 3) > (3, 1, 2)

Need (1) <= Available => (1, 2, 2) < (3, 1, 2)

Step 2: Work = Work + Allocation (i)

Work = (3, 1, 2) + (2, 0, 0) = (5, 1, 2)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1}

**Iteration 3**

Step 1: Need (i) <= Available, if True then,

**Need (4) > Available => (4, 3, 1) < (7, 2, 3)**

Step 2: Work = Work + Allocation (i)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3, P4 = not safe}

#### Bibliography

- Abraham Silberschatz, Peter B. Galvin, Greg Gagne, A Silberschatz. 2012.
*Operating System Concepts, 9th Edition.*Wiley.