Deadlock Prevention with Banker's Algorithm

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.

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 = {P_1, P_2, P_3, \cdots , P_n}$ set of active processes in the system.

$R = { R_1, R_2, R_3, …, R_m}$ set of vertices that represent the resources.

Edge types

$P_i \rightarrow R_j$ means $P_i$ has requested resource $R_i$ and waiting for it is called request edge

$R_j \rightarrow P_i$ means that the instance of resource $R_i$ is allocated to process $P_i$ called the assignment edge.

Resource $R_j$ may have more than one instance.

Example:

Vertices

\begin{aligned} &P = {P_1, P_2, P_3}\\\\ &R = {R_1, R_2, R_3, R_4} \end{aligned}

Instances of Resource

\begin{aligned} &R_1 = 1\\ &R_2 = 2\\ &R_3 = 1\\ &R_4 = 0 \end{aligned}

Edges

\begin{aligned} &Request \hspace{3px}Edges: \hspace{3px}P_1 \rightarrow R_1, P_2 \rightarrow R_3\\\\ &Assignment \hspace{3px}Edges: R_1 \rightarrow P_2, R_3 \rightarrow P_3, R_2 \rightarrow P_1, R_2 \rightarrow P_2\\\\ &R_2 \rightarrow P_1 \rightarrow R_1 \rightarrow P_2 \rightarrow R_3 \rightarrow P_3 \hspace{3px}(No \hspace{3px} Cycle)\\\\ &R_2 \rightarrow P_2 \rightarrow R_3 \rightarrow P_3 (No \hspace{3px}Cycle) \end{aligned}

*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.

Figure 1 -Cycle from P1 to P1 and P2 to P2

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.

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 = {R_1, R_2, \cdots R_n}$ . 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 \hspace{3px}N \hspace{3px}is \hspace{3px}a \hspace{3px}set \hspace{3px}of \hspace{3px}natural \hspace{3px}numbers.

Suppose there are three resources

\begin{aligned} &F (tape \hspace{3px}drive) = 1\\ &F (disk \hspace{3px}drive) = 4\\ &F (printer) = 10 \end{aligned}

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

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 = {P_1, P_2, P_3, \cdots, P_n}$ is a safe sequence for current allocation state if for each process, $P_i$ request for a resource can be satisfied by currently available resources plus resources held by $P_j$ , where $j < i$ .

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

Then $P_i+1^{th}$ 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. $P_i \rightarrow R_j$ 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 $P_i$ will form a cycle that will lead the system to an unsafe state, then the process $P_i$ must wait till the resource is available.

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 banker’s algorithm where $n$ is the number of processes and $m$ is the number of resource types is as follows,

Available – number of available resources of each type of length $m$ . $Available[j] = k$ means $k$ instance of resource $R_j$ .
Max – It is $n \times m$ matrix for maximum number instance of resources required by the process. $Max[i][j] = k$ means $P_i$ process requires $k$ instance of resource $R_j$ .
Allocation – it is also $n \times m$ matrix for number of resources of each type allocated to each process. $Allocation [i] [j] = k$ means process $P_i$ is allocated $k$ instances of resources of $R_j$ .
Need – it is $n \times m$ matrix that remaining need for each process. $Need[i] [k] = k$ means that the process $P_i$ need $k$ instance of resource type $R_j$ to finish its 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] \le Y[i]$ for all $i = 1, 2, 3, n$ .

Conversely, $Y < X$ if $Y[i] \le X[i]$ and $Y ≠ X$ .

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

Safety Algorithm

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

If no such ‘i’ exists, then go to step 3.
6. Work = Work + Allocation (i)
7. Finish[i] = true
8. 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 $P_i$ . If $Request (i) [j] = k$ , then process $P_i$ wants $k$ instance of resource $R[j]$ . When a request for a resource is made, following activities take place

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

\begin{aligned} &Available = Available – Request (i)\\ &Allocation (i) = Allocation (i) + Request (i)\\ &Need (i) = Need (i) – Request (i) \end{aligned}

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

Example:

\begin{aligned} &P = \{P0, P1, P2, P3, P4\}\\\\ &R = \{A, B, C\} \end{aligned}

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
$P_0$	0	1	0	7	5	3	7	5	5
$P_1$	2	0	0	3	2	2	5	3	2
$P_2$	3	0	2	9	0	2	10	5	7
$P_3$	2	1	1	2	2	2	7	4	3
$P_4$	0	0	2	4	3	3	7	4	5

We know that $Need (i) = Max (i) - Allocation (i)$

NEED Matrix
	A	B	C
$P_0$	7	4	3
$P_1$	1	2	2
$P_2$	6	0	0
$P_3$	0	1	1
$P_4$	4	3	1

\begin{aligned} &Add \hspace{3px}P_1 \hspace{3px}safety \hspace{3px}sequence\\\\ &Safety \hspace{3px}sequence = \{P_1, P_3, P_4, P_0, P_2\} \end{aligned}

Handling a Request

Suppose process $P_1$ 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 $P_i$ will leave the system in an UNSAFE state.

Example:

Suppose $P_0$ requested for $<strong>(0, 2, 0)</strong>$ , then we find that $Request (0) < Available.$ Adjust the following

\begin{aligned} &Available:= Available - Request;\\\\ &Allocation; =Allocation +Request;;\\\\ &Need; =Need- Request; \end{aligned}

	Allocation	Maximum	Available
	A	B	C	A	B	C	A	B	C
$P_0$	0	3	0	7	5	3	3,7	1,5	2,5
$P_1$	2	0	0	3	2	2	5	1	2
$P_2$	3	0	2	9	0	2
$P_3$	2	1	1	2	2	2	7	2	3
$P_4$	0	0	2	4	3	3	7	2	5

We then run the Safety Algorithm

NEED Matrix
	A	B	C
$P_0$	7	2	3
$P_1$	1	2	2
$P_2$	6	0	0
$P_3$	0	1	1
$P_4$	4	3	1

Iteration 1

Step 1:

\begin{aligned} &Need (i) <= Available, \hspace{3px}if \hspace{3px}True \hspace{3px}then,\\\\ &Need (1) <= Available => (1, 2, 2) < (3, 1, 2)\\\\ \end{aligned}

Step 2:

\begin{aligned} &Work = Work + Allocation (i)\\\\ &Work = (3, 1, 2) + (2, 0, 0) = (5, 1, 2) \end{aligned}

Step 3:

\begin{aligned} &Add \hspace{3px}P_1 \hspace{3px}to \hspace{3px} safety \hspace{3px}sequence\\\\ &Safety \hspace{3px} sequence = {P1} \end{aligned}

Iteration 2

Step 1:

\begin{aligned} &Need (i) <= Available, \hspace{3px} if \hspace{3px}True \hspace{3px}then,\\\\ &Need (2) > Available => (6, 0, 0) > (5, 1, 2)\\\\ &Need (3) <= Available => (0, 1, 1) < (5, 1, 2) \end{aligned}

Step 2:

\begin{aligned} &Work = Work + Allocation (i)\\\\ &Work = (5, 1, 2) + (2, 1, 1) = (7, 2, 3) \end{aligned}

Step 3:

\begin{aligned} &Add \hspace{3px}P_3 \hspace{3px} to \hspace{3px} safety \hspace{3px} sequence\\\\ &Safety \hspace {3px} sequence = \{P_1, P_3\} \end{aligned}

Iteration 3

Step 1:

\begin{aligned} &Need (i) <= Available, \hspace{3px}if \hspace{3px}True \hspace{3px} then,\\\\ &Need (4) <= Available => (4, 3, 1) < (7, 2, 3)\\\\\end{aligned}

Step 2:

\begin{aligned} &Work = Work + Allocation (i)\\\\ &Work = (7, 2, 3) + (0, 0, 2) = ( 7, 2, 5 ) \end{aligned}

Step 3:

\begin{aligned} &Add \hspace{3px} P_1 \hspace{3px} to \hspace{3px} safety \hspace{3px} sequence\\\\ &Safety \hspace{3px}sequence = \{P_1, P_3, P_4 = not \hspace{3px} safe\} \end{aligned}

References

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

CLAIM EDGE	CONVERT TO REQUEST EDGE	CONVERT TO ASSIGNMENT EDGE
$P_1 \rightarrow R_1$	YES	YES
$P_2 \rightarrow R_2$	YES	YES
$P_1 \rightarrow R_2$	NO (Make a cycle)	NO
$P_2 \rightarrow R_1$	YES	NO (P1 using R1)

Resource Allocation Graph

Vertices types

Edge types

Example:

Methods for handling deadlock

Deadlock Prevention

Mutual exclusion

Hold and Wait

No Preemption

Circular Wait

Deadlock Avoidance

Safe State

Resource-Allocation-Graph Algorithm

Banker’s Algorithm

Banker’s Algorithm Procedure

Safety Algorithm

Resource-Request Algorithm

Instances of Resources

Check if the System is in Safe State

Iteration 1

Iteration 2

Iteration 3

Iteration 4

Iteration 5

Handling a Request

Iteration 1

Iteration 2

Iteration 3

References

Ads Blocker Detected!!!