Deadlock in Operating System

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 in operating system 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 of Deadlock:

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 by Pn 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(.)
Example:

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

Practice Question on Deadlock

Q1. What is the difference between deadlock and starvation?

Q2. Is there a deadlock in the scenario below?

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)

Previous                                                  Next 
Process Synchronization                  Deadlock Prevention