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.

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

Resource allocation graph
Figure2: Resource Allocation Graph

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)

PPT on Deadlock in Operating System


Note: Click within the slide area for animations. Clicking on the “next” slide button will not display any animation

Video on Deadlock in Operating System

Previous                                                  Next 
Process Synchronization                  Deadlock Prevention

13 thoughts on “Deadlock in Operating System

  1. ANS -Practice question -No Deadlock condition is there .
    Reason:-Because Process P2 and Process P4 are not satisfying hold and wait condition necessary for deadlock condition.

  2. yes there is a deadlock because the instance p3 needs is hold by p1 and vice versa which invokes the deadlock hold and wait and circular wait

  3. NO becouse Process P4 may release its instance of resource type R2. That
    resource can then be allocated to P3,

  4. Que 1-In deadlock each process holding a resource and trying to access the other resource and in starvation , when the process is in the ready state and have all resources that it needs but the short term scheduler did not choose that process because of priority and that process waiting for the execution for a long time this leads to starvation

Leave a Reply

Your email address will not be published. Required fields are marked *