Deadlock avoidance

PropellerAds

Given some additional information on how each process will request resources, it is possible to construct an algorithm that will avoid deadlock states. The algorithm will dynamically examine the resource allocation operations to ensure that there won’t be a circular wait on resources.

When a process requests a resource that is already available, the system must decide whether that resource can immediately be allocated or not. The resource is immediately  allocated only if it leaves the system in a safe state.

A state is safe if the system can allocate resources to each process in some order avoiding a deadlock. A deadlock state is an unsafe state.

Example
Consider a system with 12 tape drives. Assume there are three processes : p1, p2, p3.
Assume we know the maximum number of tape drives that each process may request:

p1 : 10, p2 : 4, p3 : 9

Suppose at time tnow, 9 tape drives are allocated as follows :
p1 : 5, p2 : 2, p3 : 2

So, we have three more tape drives which are free.

This system is in a safe state because it we sequence processes as: <p2, p1, p3>, then p2 can get two more tape drives and it finishes its job, and returns four tape drives to the system. Then the system will have 5 free tape drives. Allocate all of them to p1, it gets 10 tape drives and finishes its job. p1 then returns all 10 drives to the system. Then p3 can get 7 more tape drives and it does its job. It is possible to go from a safe state to an unsafe state:

Example
Consider the above example. At time tnow+1, p3 requests one more tape drive and gets it.
Now, the system is in an unsafe state.
There are two free tape drives, so only p2 can be allocated all its tape drives. When it
finishes and returns all 4 tape drives, the system will have four free tape drives.
example-5-5

We allocated p3 one more tape drive and this caused a deadlock.

 

Try Now – Operating Systems MCQs
Practice Now – Operating System Online Test