Deadlock

In multiprogramming environment, several processes compete to acquire some limited number of resources. When a process request resource and if it will not get the resource, it will enter into waiting state. Sometimes, the waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a deadlock in operating system.

It is the responsibility of programmer to avoid the situation of deadlock.

Necessary conditions for deadlock

A deadlock situation can arise if the following four conditions hold simultaneously in a system:

  • Mutual exclusion: At least one resource must be held in a non-sharable mode; that is, only one process at a time can use the resource.
  • Hold and wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
  • No preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
  • Circular wait: A set { P0 , P1, … , P11 } of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, … , Pn-1 is waiting for a resource held by P. and P11 is waiting for a resource held by P0.

All four conditions must hold for a deadlock to occur.

Methods for handling deadlocks

We can deal with the deadlock problem in one of three ways:

  • We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlocked state.
  • We can allow the system to enter a deadlocked state, detect it, and recover.
  • Ignore the problem and pretend that deadlocks never occur in the system. It is used by most operating systems, including UNIX and Windows.

To ensure that deadlock never occurs in the operating system, it can use either a deadlock-prevention or deadlock-avoidance scheme.

Deadlock Prevention

Deadlock prevention provides a set of methods for ensuring that at least one of the necessary conditions cannot hold. These methods prevent deadlocks by constraining how requests for resources can be made.

Deadlock Avoidance

Deadlock avoidance requires that the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime. With this additional knowledge, it can decide for each request whether or not the process should wait.

Recovery from Deadlock

When a detection algorithm determines that a deadlock exists, several alternatives are available. One possibility is to inform the operator that a deadlock has occurred and to let the operator deal with the deadlock manually. There are two options for breaking a deadlock.

  • Process Termination: To eliminate deadlocks by aborting a process, we use one of two methods: Abort all deadlocked processes and Abort one process at a time until the deadlock cycle is eliminated.
  • Preempt some resources from one or more of the deadlocked processes.

Download as PDF

Read next:  Memory Management ››

« Back to Course page