Deadlock Prevention

Prevent at least one of the necessary conditions from occurring 

1.      Mutual exclusion

·         Can not be denied since its an intrinsic property of the resource. E.g. printer is non sharable

2.      Hold and wait

·         Whenever a process request a resource, it must not be holding any resource.

Every process must be allocated all the resources before it begins execution.

Whenever a process request for resources, it must release all the currently held resources (if any).

Disadvantage 

·         Low resource utilization

·         Starvation is possible

No preemption 

·         If the requested resources can not be allocated then the resources that are currently held by the process are preempted.

·         Can be applied to resources like CPU registers and memory space but not to printers and tape drives.

Circular wait

·         Process can request for resources in some order only.

·         E.g. Suppose each process is numbered like P0, P1, p2,. .., Pn. Then they can request for resources held by higher numbered process only i.e. P0 can request from P1, P2 and so on, p1 from P2, P3 and so on but not P0, P2 from P3, P4 and so on but not P0 and P1.

Deadlock

Have you ever faced any of these problems?
1. PC/Laptop hanged
2. Mobile hanged

If yes, your system was in a DEADLOCK state.

Deadlock is a situation which occurs when a process or thread enters a waiting state because a resource requested is being held by another waiting process, which in turn is waiting for another resource held by another waiting process.

In a deadlock state a process is unable to change its state(waiting) indefinitely because the resources requested by it are being used by another waiting process.

Example:
Let there be 2 processes P1 and P2 and 2 resources R1 and R2. Both P1 and P2 require Both R1 and R2 to complete their tasks. Suppose P1 acquires R1 first. In the mean time P2 acquires R2. Now when P1 requests for R2 it will have to wait (because R2 is being held by P2). Similarly, when P2 requests for R1 it will also have to wait. Neither P1 nor P2 will not be able to change their waiting state since both are holding the resource required by the other process and none will release its resource until their allocated task is over.  Hence the system will be in deadlock. 

Necessary Conditions for Deadlock

From the above discussion we can identify 4 conditions that must be true together for the deadlock to occur.

1. Mutual Exclusion

2. Hold and Wait

3. No Preemption

4. Circular Wait

Mutual Exclusion means that the resource can be used by only one process at any given point of time i.e. the resource is non sharable. e.g. Printer. Two processes can not print a document at the same time from a printer. Hence printer is a non sharable resource.

Hold and Wait means that the process must be holding at least one resource and requesting for at least one resource. e.g. Process P1 is holding resource R1 and waiting for the resource R2.

No Preemption means that non of the processes involved in the deadlock is ready to release (preempt)  the resource it is currently holding. 

Circular wait means —A set {P0, P1,..Pn} of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 waiting for resource held by P2, …Pn-1 is waiting for resource held byPn and Pn waiting for a resource held by P0. 

Resource Allocation Graph

Resource allocation graphs are used to describe a deadlock. 

Resource allocation graph consists of

·         Vertices (V) - that represent Processes (in circle) and Resources (in rectangles)

·         Edges (E) - Request edge (from process towards resource) and Assignment edge (from resource towards process)

·         Instances of a resource are represented by a dot(.)

 Important Points

·         No cycle in resource allocation graph - no deadlock

·         Cycle in resource allocation graph and single instance of every resource - deadlock

·         Cycle in resource allocation graph and multiple instances of one or more resource - possibility of deadlock

Deadlock Handling Methods

·         Deadlock Prevention - ensure that one of the necessary conditions never occurs.

·         Deadlock Avoidance - ensure that the system is always in safe state

·         Deadlock Detection - Let the system enter into deadlock state and then recover from it

·         Do Nothing - Just ignore the issue and let the user decide how to handle (used by Windows and UNIX)