Deadlock Prevention

Deadlock Prevention

AU May-22, Marks 6

To prevent a deadlock, the OS must eliminate one of the four necessary conditions.

1. Mutual exclusion

2. Hold and wait

3. No preemption

4. Circular wait

1. Mutual exclusion: It is necessary in any computer system because some resources (memory, CPU) must be exclusively allocated to one user at a time. No other process can use a resource while it is allocated to a process.

2. Hold and wait: If a process holding certain resources is denied a further request, it must release its original resources and if required request them again.

3. No preemption: It could be bypassed by allowing the operating system to deallocate resources from process.

4. Circular wait: Circular wait can be bypassed if the operating system prevents the formation of a circle.

• A deadlock is possible only if all four of these conditions simultaneously hold in the system.

• Prevention strategies ensure that at least one of the conditions is always false. Example 3.4.1 Consider a system consisting of 'm' resources of the same type being shared by 'n' processes. Resource can be requested and released by processes only one at a time. Show that the system is deadlock free if the following two conditions hold :

i) The maximum need of each process is between 1 and m resources.

ii) The sum of all maximum needs is less than m+n.    AU: May-18, Marks 15

Solution:

• By contradiction, assume that the 4 conditions for deadlock exist in the system and thus there is a group of processes involved in a circular wait.

• Let these processes be P₁, …., P_k, k≤ n, their current demands be D₁,...,D_k and the number of resources each of them holds be H₁,...,H_k.

• The circular wait condition should look like: P₁ -> P₂->... -> P_k -> P₁, but in fact it is simpler Let M₁,…., M_n be total (maximum) demands of processes P₁, ..., P_n.

• Then a circular wait can occur only if all resources are in use and every process hasn't acquired all its resources: H₁+...+H_k = m and D; > = 1 for 1 ≤ i ≤ k.

Since M_i = H_i + D_i, the sum of maximum demands of the processes involved in a circular wait is: M₁+...+M_k ≥ m+k.

• Note that the remaining processes' P_k+1,…, P_n maximum demands are at least 1 : M_i ≥ 1, k+1 ≤ i ≤ n and thus M_k+1+...+ M_n ≥ n-k..

• The total sum of maximum demands is thus:

M₁+...+M_n = M₁+...+M_k +M_k+1+...+M_n ≥ m+k+ (n-k) = m +n.

• It is defined that sum of all maximal needs is strictly less than m+n, thus we have a contradiction.

• If we have a deadlock all resources are held by the various processes, otherwise some process can take a resource and "advance" and we are not in a deadlock.

• Therefore, every process needs at least 1 resource more, or else we don't have a so deadlock. So the total sum of maximum demands is:

• This contradicts the assumption total sum of maximum demands is less than m+n.

University Question

1. What is deadlock? What are the necessary conditions for deadlock to occur? Explain the bio deadlock prevention method of handling deadlock.

Consider the following information about resources in a system.

i) There are two classes of allocatable resource labeled R1 and R2

ii) There are two instances of each resource

iii) There are four processes labeled p1 through p4

iv) There are some resource instances already allocated to processes as follows:

One instance of R1 held by p2, another held by p3

One instance of R2 held by p1, another held by p4

v) Some processes have requested additional resources, as follows:

pl wants one instance of R1

p3 wants one instance of R2

1) Draw the resource allocation graph for this system

2) What is the state (runnable, waiting) of each process? For each process that is waiting indicate what it is waiting for.

3) In this system deadlocked? If so, state which processes are involved. If not, give an execution sequence that eventually ends, showing resource acquisition and release at each step. AU May-17, Marks 15

Ans.

1. Resource allocation graph

2. Runnable state process = P4, P2

Waiting state process = P1, P3

• Process P1 is waiting for one instance of R1 and process P3 is waiting for instance of R2.

3. System is not in deadlock state.

Execution sequence is P4, P2, P3, P1 or P2, P4, P1, P3.

• P2 and P4 have all resources for completing so safe sequence is P2, P4, P1, P3.