Deadlocks in Operating System: Necessary Conditions for Deadlock

 

Deadlocks:

 

In a multiprogramming environment several processes may compete for finite number of resources.

 

A process request resources, if the resources are not available at that time then process enters a wait state.

 

Waiting processes may never again change state because the resources that they have requested are held by other waiting processes. This situation is called a deadlock.

 

System Model:

 

A system consists of 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 some number of identical instances. Memory space, CPU cycles, files and I/O devices are examples of resource types.

 

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

 

1.    Request: If request cannot be granted immediately, for example resource is being used by another process then the requesting process must wait until it can acquire the resource.

2.    Use: The process can operate on the resource for example if the resource is a printer the process can print on the printer.

3.    Release: The process releases the resource.

 

The request and release of resources are system calls. A system table records whether each resource is free or allocated and if resource is allocated to which process. If a process request resource that is currently allocated to another process it can be added to queue of processes waiting for this resource.

 

A set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set. The resources may be either physical resource (example printers, tape drives, memory space and CPU cycles) or logical resources (example files, semaphore and monitors).

 

 

 

Deadlock Characterization:

 

In a deadlock, processes never finish executing and system resources are tied up preventing other jobs from starting.

 

Necessary Conditions for Deadlock:

 

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

 

1.    Mutual exclusion: At least one resource must be held in a non-shareable mode that is only one process at a time can use the resource. If another process request that resource the requesting process must be delayed until the resource has been released.

2.    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.

3.    No pre-emption: Resources cannot be pre-empted i.e. a resource can be released only voluntarily by the process holding it after that process has completed its task.

4.    Circular wait: A set {P₀, P₁, P₂,..., P_n} of waiting processes must exist such that P₀ is a waiting for a resource that is held by P₁, P₁ is waiting for a resource that is held by P₂, …, P_{n -1} is a waiting for a resource that is held by P_n  and P_n  is waiting for a resource that is held by P₀.