What is Deadlock

⏪Previous Next⏩

In a multiprogramming environment several processes may compete for a finite number of resources. A process request resources; if the resource is available at that time a process enters the wait state. Waiting process may never change its state because the resources requested are held by other waiting process. This situation is known as deadlock.

Example

· Traffic only in one direction.

· Each section of a bridge can be viewed as a resource.
· If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback).
· Several cars may have to be backed up if a deadlock occurs.
· Starvation is possible

System Model:

A system consists of a finite number of resources to be distributed among a number of competing processes. The resources are partitioned into several types each of which consists of a number of identical instances. A process may utilized a resources in the following sequence

· Request: In this state one can request a resource.

· Use: In this state the process operates on the resource.

· Release: In this state the process releases the resources.

Deadlock Characteristics:

In a deadlock process never finish executing and system resources are tied up. A deadlock situation can arise if the following four conditions hold simultaneously in a system.

· Mutual Exclusion: At a time only one process can use the resources. If another process requests that resource, requesting process must wait until the resource has been released.

· Hold and wait: A process must be holding at least one resource and waiting to additional resource that is currently held by other processes.

· No Preemption: Resources allocated to a process can’t be forcibly taken out from it unless it releases that resource after completing the task.

· Circular Wait: A set {P₀, P₁, …….P_n} of waiting state/ process must exists such that P₀ is waiting for a resource that is held by P₁, P₁ is waiting for the resource that is held by P₂ ….. P_(n _– ₁₎ is waiting for the resource that is held by P_n and P_n is waiting for the resources that is held by P₄.