Deadlocks

Deadlocks

Deadlock

Deadlocks

A set of the process is in a deadlocks state if each process in the set is waiting for an event that can be caused by only another process in the set. In other words, each member of the set of deadlock processes is waiting for a resource that can be released only by a deadlock process. None of the processes can run, none of them can release any resources, and none of them can be awakened.

The resources may be either physical or logical. Examples of physical resources are Printers, Hard Disc Drives, Memory Space, and CPU Cycles. Examples of logical resources are Files, Semaphores, and Monitors.

The simplest example of deadlock is where process 1 has been allocated non-shareable resources A (say a Hard Disc drive) and process 2 has be allocated non-sharable resource B (say a printer). Now, if it turns out that process 1 needs resource B (printer) to proceed and process 2 needs resource A (Hard Disc drive) to proceed and these are the only two processes in the system, each is blocked the other and all useful work in the system stops. This situation is termed deadlock. The system is in deadlock state because each process holds a resource being requested by the other process neither process is willing to release the resource it holds.

Preemptable and Nonpreemptable Resources

Resources come in two flavors: preemptable and nonpreemptable.

  • A preemptable resource is one that can be taken away from the process with no ill effects. Memory is an example of a preemptable resource.
  • A nonpreemptable resource is one that cannot be taken away from the process (without causing ill effect). For example, CD resources are not preemptable at an arbitrary moment.
  • Reallocating resources can resolve deadlocks that involve preemptable resources. Deadlocks that involve nonpreemptable resources are difficult to deal with.

Under the normal mode of operation, a process may utilize a resource in only the following sequence:

  1. Request: If the request cannot be granted immediately, then the requesting process must wait until it can acquire the resource.
  2. Use: The process can operate on the resource.
  3. Release: The process releases the resource.

Deadlock

Necessary Conditions for Deadlock

 Coffman (1971) identified four conditions that must hold simultaneously for there to be a deadlock.

  1. Mutual Exclusion Condition: The resources involved are non-shareable.

Explanation: At least one resource must be held in a non-shareable mode, that is, only one process at a time claims exclusive control of the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.

  1. Hold and Wait Condition:

    Requesting process hold already the resources while waiting for requested resources.

Explanation: There must exist a process that is holding a resource already allocated to it while waiting for an additional resource that is currently being held by other processes.

  1. No-Preemptive Condition:

    Resources already allocated to a process cannot be preempted.

Explanation: Resources cannot be removed from the processes are used to completion or released voluntarily by the process holding it.

  1. Circular Wait Condition: The processes in the system form a circular list or chain where each process in the list is waiting for a resource held by the next process in the list. There exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and P0 is waiting for a resource that is held by P0.

Note: It is not possible to have a deadlock involving only one single process. The deadlock involves a circular “hold-and-wait” condition between two or more processes, so “one” process cannot hold a resource, yet be waiting for another resource that it is holding. In addition, deadlock is not possible between two threads in a process, because it is the process that holds resources, not the thread that is, each thread has access to the resources held by the process.

 

METHODS OF HANDLING DEADLOCK

In general, there are four strategies of dealing with deadlock problem:

  1. Deadlock Prevention: Prevent deadlock by resource scheduling so as to negate at least one of the four conditions.
  2. Deadlock Avoidance: Avoid deadlock by careful resource scheduling.
  3. Deadlock Detection and Recovery: Detect deadlock and when it occurs, take steps to recover.
  4. The Ostrich Approach: Just ignore the deadlock problem altogether.
basicittopic

basicittopic

A Computer Science Study for IT students and people of IT community