What is a Deadlock?

In a multiprocessing environment, several processes compete for limited resources. A running process goes to waiting state when a resource is not available. The process could not change its state because some other process holds the resources. This is called a deadlock.

The operating system does not provide with deadlock prevention mechanism, the programmers must write deadlock-free programs.

Under normal circumstances a process utilizes resources in the following way:

  1. The process request for the resource, and must wait if the resource is not granted immediately.
  2. The process once allocated the resource, can operate on it.
  3. The process must release the resources once finished execution.

The list of system calls used to manage resources via system calls are:

  • request ()
  • release ()
  • open ()
  • close ()
  • allocate ()
  • free ()
  • wait ()
  • signal ()

Necessary Conditions for Deadlock

A deadlock happens if four of the following condition hold simultenously in a system:

  1. Mutual exclusion
  2. Hold and Wait
  3. No Preemption
  4. Circular wait

Mutual Exclusion

Only one process can use the resource at a time. The process must not share the resource with another process. If the resource is requested by another process then it has to wait until the resource is released.

Hold and Wait

A process must be holding at least one resource and waiting for additional resources that are held by other processes.

No Preemption

The resources held by the process cannot be preempted and it can only be released by that process after completing its tasks.

Circular Wait

A set \{ P_0, P_1, …, P_n \} of waiting processes exist such that P_0 is waiting for resource held by P_1, P_1 is waiting for P_2, P_{n-1} is waiting for resource held by P_n, and P_n waiting for resource held by P_0. This situation is called circular wait, and also known as hold-and-wait.

References

Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edn., : Wiley.

Tanenbaum, Andrew S. (March 3, 2001) Modern Operating Systems, 2nd edn., : Prentice Hall.


Skip to content