Deadlock Avoidance

Deadlock Avoidance

AU: Dec.-17, May-19, 22 Dec-17, May-19, 22

• Deadlock avoidance depends on additional information about the long term resource needs of each process. The system must be able to decide whether granting a resource is safe or not and only make the allocation when it is safe.

• Fig. 3.5.1 shows safe and unsafe state.

• When a process is created, it must declare its maximum claim, i.e. the maximum number of unit resource. The resource manager can grant the request if the resources are available.

• For example, if process 1 requests a resource held by process 2 then make sure that process 2 is not waiting for resource head by first process 1.

Banker's Algorithm

• Banker's algorithm is the deadlock avoidance algorithm. Banker's is named because the algorithm is modeled after a banker who makes loads from a pool of capital and receives payments that are returned to that pool.

• Algorithm is check to see if granting the request leads to an unsafe state. If it does, the request is denied. If granting the request leads to a safe state, it is carried out.

• The Dijkstra proposed an algorithm to regulate resource allocation to avoid Hiwe deadlocks. The banker's algorithm is the best known of the avoidance method.

• By using avoidance method, the system is always kept in a safe state.

• It is easy to check if a deadlock is created by granting a request, deadlock analysis method is used for this.

• Deadlock avoidance uses the worst-case analysis method to check for future deadlocks.

• Safe state: There is at least one sequence of resource allocations to processes that does not result in a deadlock.

• System is in a safe state only if there exist a safe sequence. A safe state is not a deadlocked state.

• Deadlocked state is an unsafe state. It does mean the system is in a deadlock.

• As long as the state is safe, the resource manager can be guaranteed to avoid a deadlock.

• Initially the system is in a safe state. When process requests a resource and that resource is available then the system must decide whether the resources can be allocated immediately or process must wait.

• If system remains in safe state after allocating resource then only OS allocates resources to process.

• Banker algorithm uses following data structures.

1. Allocation: Allocation is a table in which row represents process and column represents resources (R).

alloc [i, j] = Number of unit of resource Rj held by process P_i.

2. Max: Max be the maximum number of resources that process requires during its execution.

• Need (claim): It is current claim of a process, where a process's claim is equal to its maximum need minus its current allocation.

Need Max - Allocation

• Available: There will be number of resources still available for allocation. This is equivalent to the total number of resources minus the sum of the allocation to all processes in the system.

Available = Number of resources - Sum of the allocation to all process

= Number of resources - ∑ⁿ_i=1 Allocation (P_i)

• Each process cannot request more that the total number of resources in the system. Each process must also guarantee that once allocated a resource, the process will return that resource to the system within a finite time.

Weakness of Banker's algorithm

1. It requires that there be a fixed number of resources to allocate.

2. The algorithm requires that users state their maximum needs (request) in advance.

3. Number of users must remain fixed.

4. The algorithm requires that the bankers grant all requests within a finite time. 5. Algorithm requires that process returns all resource within a finite time.

Examples on Banker's algorithm

1. System consists of five processes (P₁, P₂, P₃, P₄, P₅) and three resources (R₁, R₂, R₃). Resource type R1 has 10 instances, resource type R₂ has 5 instances and R₃ has 7 instances. The following snapshot of the system has been taken :

Currently the system is in safe state.

Safe sequence: Safe sequence is calculated as follows:

1) Need of each process is compared with available. If need_i ≤ available_i , then the resources are allocated to that process and process will release the resource.

2) If need is greater than available, next process need is taken for comparison.

3) In the above example, need of process P₁ is (7, 4, 3) and available is (3, 3, 2). need ≥ available → False

So system will move for next process.

4) Need for process P₂ is (1, 2, 2) and available (3, 3, 2), so

need ≤ available (work)

(1, 2, 2) ≤ (3, 3, 2) = True

then Finish [i] = True

Request of P₂ is granted and processes P₂ is release the resource to the system.

Work: Work + Allocation

Work: (3, 3, 2) + (2, 0, 0)

:= (5, 3, 2)

This procedure is continued for all processes.

5) Next process P3 need (6, 0, 0) is compared with new available (5, 3, 2).

Need > Available = False

(6 00) > (532)

6) Process P₄ need (0, 1, 1) is compared with available (5, 3, 2).

Need > Available

(0 1 1) < (532) = True

Available = Available + Allocation

= (532) + (2 1 1)

= (7 4 3) (New available)

7) Then process P₅ need (4 3 1) is compared with available (7 4 3)

Need < Available

(4 3 1) < (74 3) = True

Available = Available + Allocation

= (7 4 3) + (0 0 2) = (7 4 5) (New available)

8) One cycle is completed. Again system takes all remaining process in sequence. So process P₁ need (7 4 3) is compared with new available (7 4 5).

Need < Available = True

(7 4 3) < (745)

Available = Available + Allocation

= (7 4 5) + (0 1 0) = (755) (New available)

9) Process P₃ need is (6 0 0) is compared with new available (7 5 5).

Need < Available = True

(6 0 0) < (755) = True

Available = Available + Allocation

= (755) + (3 0 2)

= (10 5 7) = (New available)

Safe sequence is <P₂ P₄ P₅ P₁ P₃>

Solution :

i) Content of need matrix is

Safe state

a) Need of P₀ = (0, 0, 0, 0)

Available = (1, 5, 2, 0)

Need < Available

(Required resources are allocated to P₀)

New available = Allocation + Available

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

= (1, 5, 3, 2)

b) For P₁ process

Need = (0, 7, 5, 0)

Available = (1, 5, 3, 2)

Need > Available

(Request is not granted)

New available = Available = (1, 5, 3, 2)

c) For P₂ process

Need = (1, 0, 0, 2)

Available = (1, 5, 3, 2)

Need < Available

(Request is granted)

New available = Allocation + Available = (1, 3, 5, 4) + (1, 5, 3, 2)

= (2, 8, 8, 6)

d) For process P₃ = (2, 8, 8, 6)

Need of P₃ = (0, 0, 2, 0)

Available = (2, 8, 8, 6)

Need < Available

New available = (2, 14, 11, 8)

e) Process P₄

Need of P₄ = (0, 6, 4, 2)

Available = (2, 14, 11, 8)

Need < Available

New available = (2, 14, 11, 8) + (0, 0, 1, 4)

= (2, 14, 12, 12)

f) Again for P₁ process

Need of P₁ = (0, 7, 5, 0), Available = (2, 14, 12, 12)

Need < Available

New available = (1, 0, 0, 0) + (2, 14, 12, 12)

= (3, 14, 12, 12)

So the safe sequence is P₀, P₂, P₃, P₄, P₁

Request from P₁= (0, 4, 2, 0)

Available = (1, 5, 2, 0)

After granting the request of P₁, available resource is (1, 1, 0, 0))

a) Need of P₀ = (0, 0, 0, 0)

New available = (1, 1, 0, 0) + (0, 0, 1, 2)

= (1, 1, 1, 2)

b) P₁ need is greater than available.

c) P₂ need is (1, 0, 0, 2)

Need < Available

New available = (1, 1, 1, 2) + (1, 3, 5, 4)

= (2, 4, 6, 6)

d) P₃ Need is (0, 0, 2, 0)

Need < Available

New available = (2, 4, 6, 6) + (0, 6, 3, 2)

= (2, 10, 9, 8)

e) P₄ Need is (0, 6, 4, 2)

Available (2, 10, 9, 8)

Need < Available

New available = (2, 10, 9, 8) + (0, 0, 1, 4)

= (2, 10, 10, 12)

f) Again P₁ need (0, 7, 5, 0)

Need < Available

If a request from P₁ arrives for (0, 4, 2, 0), then the request is granted immediately. 

Example 3.5.2 The operating system contains 3 resources, the number of instance of each resource type are 7, 7, 10. The current resource allocation state is as shown below.

i) Is the current allocation in a safe state?

ii) Can the request made by process P₁ (1 1 0) be granted?

Solution:

i) First find the available resource in the system.

Available = Number of instance - Sum of allocation

Available = (7 7 10) – (5 4 10)

Available resource = (2, 3, 0)

Content of need matrix is

Safe sequence< P₃, P₂, P₁ >

The system is in safe state.

ii) Process P₁ request (1 1 0), this request is less than need. Need for process P₁ is (1 4 5). Available resource is (2, 3, 0) and request is (1 1 0).

Request < Available

(110) < (230)

After allocating (1 1 0) to process P₁ the need becomes as follows.

And available resource is (1 2 0)

Need of any process is never satisfied after granting the process P₁ request (1 1 0). So the system will be blocked. Therefore request of process P₁ (1 1 0) cannot be granted.

Example 3.5.3 Consider the following system snapshot using data structures in the Banker's algorithm, with resources A, B, C and D and process P_o to P₄.

Using Banker's algorithm, answer the following questions:

a) How many resources of type A, B, C and D are there? [2]

b) What are the contents of the need matrix? [3]

c) Is the system in a safe state? Why?  [3]

d) If a request from process P4 arrives for additional resources of (1, 2, 0, 0), can the Banker's algorithm grant the request immediately? Show the new system state and other criteria.  [7]                AU: Dec.-17, Marks 15

Solution: a) Resource types of A, B, C and D :

b) Need Matrix :

c) Safe State :

Safe sequence: P₀, P₂, P₃, P₄, P₁

d) Request from process P₄ (1, 2, 0, 0)

We assume that, requested is granted immediately. So calculate need matrix :

Available (2, 0, 1, 1)

Calculate safe sequence :

Safe sequence: P₂ P₃ P₄ P₀, P₁.

So requested is granted immediately.

Example 3.5.4 Consider the following snapshot of a system.

Answer the following question using Bankers algorithm.

i) Illustrate that the system is in safe state by demonstrating an order in which the processes may complete?

ii) If a request from a process P₁ arrives for (1, 1, 0, 0), can the request be granted immediately?

iii) If the request from P₄ arrives for (0, 0, 2, 0), can the request be granted immediately? AU: May 19, Marks 13

Solution: Need Matrix :

i) Safe State :

Safe sequence: P₀, P₃, P₄, P₁, P₂

ii) Request from process P₁ (1, 1, 0, 0)

We assume that, requested is granted immediately. So calculate need matrix :

Available = (2, 2, 2, 1)

Calculate safe sequence :

There is no safe sequence, so request is not granted immediately.

iii) Request from process P₄ (0, 0, 2, 0)

We assume that, request is granted immediately. So calculate need matrix :

Available = (3, 3, 0, 1)

There is no safe sequence, so request is not granted immediately.