CAOS 04

Now let's talk about the different methods we can use to handle deadlocks. In this case, we have three:
Deadlock Prevention
Deadlock Avoidance
Deadlock Detection and Recovery

We'll first look at Deadlock Prevention. Recall that a Deadlock requires four conditions to occur: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. The focus of Deadlock Prevention is to make sure that all of these conditions do not hold true at the same time.

In Mutual Exclusion, the protocol should try its best to make all resources sharable. Certain non-sharable resources, such as a printer, should still retain Mutual Exclusion.

In Hold and Wait, we make sure that a process can only make a request if it does not hold any other resource. What this means is that a process can only request for multiple resources in a single request. Every time it requests for another set, it must release them.

In No Preemption, we make sure that all resources held by a particular process is preempted if the resource it is requesting is not available. Alternatively, when a process requests for a resource, and it is free, it is given to it. If it is not available, and it is given to another waiting process, then that resource is preempted. If it is not available, and it is currently being used by a Running process, then the process waits.

In Circular Wait, each process is given a unique number. If the process does not currently hold any resource, it can request for any resource. However, if it already does, we need to make sure that the processes can only request for another resource with a higher number. For a process to use a lower resource, it must first release the higher resource.

To prove the above does handle Circular Wait problems, assume that a Deadlock has occurred in a system of 6 processes and 6 resources. Let's assume in this case P1 is waiting for P2 which holds R1. P2 is then waiting for P1 which holds R2.

If P2 is able to request for R1, that would mean that R1 < R2.

On the other hand, if P1 requests for R2, it would mean R2 < R1.

This would mean that R1 < R2 < R1, which transitively means R1 < R1 which is not possible.

R1 < R2
R2 < R1

Therefore

R1 < R2 < R1
R1 < R1

Now we'll move on to Deadlock Avoidance. In Deadlock Avoidance, the system attempts to arrive at a Safe State. A Safe State can only exist if there exists a Safe Sequence. A Safe Sequence is a sequence of execution whereby ALL the resource held by a PREVIOUS process can satisfy the NEEDS of a FOLLOWING process.

In a Safe State system, there can exist no Deadlock. In an Unsafe State system, there MAY be a Deadlock. A system in Deadlock is definitely in an Unsafe State.

Let us look at a single resource example taken from the textbook where 12 magnetic tape drives are shared among 3 processes:

 Maximum Needs  Current Allocated May Need
P0 10   5   5
P1 4   2   2
P2 9   2   7

At the time instant, 9 tapes are allocated to the three processes, leaving only 3 free. We should derive a safe sequence where:
CURRENT + P.i.ALLOCATED >= P.(i+1).NEED

In this case, the only thing that is able to use 3 tape drives is P1. Therefore, we give P1 the tapes first. When P1 is done, we assume that P1 releases ALL tapes, so we end up with (CURRENT-P1.NEED)+P1.MAX = CURRENT+P1.ALLOCATED = 5 tapes.

Now, at this point, we can only satisfy P0. Following the equation, we'll have CURRENT+P0.ALLOCATED = 5+5 = 10 tapes left.

Finally, we can satisfy P2, which requires 7 tapes. In the end, we'll have our CURRENT+P2.ALLOCATED = 10+2 = 12 tapes back.

The sequence we have derived is P1,P0,P2. Let's check if P.i.MAX+P.i.NEED > P.(i+1).NEED is true.

At first, CURRENT is 3.
CURRENT + P1.ALLOCATED >= P0.NEED
3 + 2 >= 5 (TRUE)
At the end of P1, CURRENT is 5.

At this point, CURRENT is 5.
CURRENT + P0.ALLOCATED >= P2.NEED
5 + 5 >= 7 (TRUE)
At the end of P0, CURRENT is 10.

At this point, CURRENT is 10.
CURRENT + P2.ALLOCATED == TOTAL
10 + 2 == 12
At the end, we have 12 tapes back.

What we just went through is a simple Banker's Algorithm example. Let us look at a complex Banker's Algorithm example with three resources and 5 processes (taken from the textbook).

 Allocation Max Need
 A B C  A B C A B C
P0 0 1 0  7 5 3 7 4 3
P1 2 0 0  3 2 2 1 2 2
P2 3 0 2  9 0 2 6 0 0
P3 2 1 1  2 2 2 0 1 1
P4 0 0 2  4 3 3 4 3 1

Each of these are arrays of int[numberOfProcesses][numberOfResources]. In other words, where n is the number of processes, and m is the number of resources, we have matrices of n*m.

Now, assume that at this point, we're still left with:

A B C
3 3 2

We would need to derive a Safe Sequence where the rule holds true. At this point, we can have P1 or P3 go first. We would use a table as such to derive the safe sequence:

Available = [3, 3, 2]

 Work Finished
P1 5  3 2 True
P3 7  4 3 True
P4 7  4 5 True
P2 10 4 7 True
P0 10 5 7 True

Sequence  satisfies the safety criteria
and the final state of the resources as above.

We finally move into detection and recovery. For Single Instance deadlock detection, a Wait-For graph is derived from a Resource-Allocation Graph. A Wait-For graph is simply a graph that omits all resources, with the arrow pointing to the process a process is waiting for.

Resource-Allocation Graph


Wait-For Graph


Detection for multiple instances of each resource type uses the Banker's algorithm. If the matrix has a False for any entry in the Finished matrix, then a deadlock has occurred.

The usage of the detection algorithm is dependent on how OFTEN a deadlock is likely to occur, and how MANY processes will be affected by deadlock when it happens.

Recovery from deadlock involves:
Process Termination - All deadlocked processes are terminated, or one at a time until a deadlock is resolved
Resource Preemption - A resource is PREEMPTED from a selected victim. The process is ROLLED BACK. We should also make sure that the preempted process is not STARVED.