Deadlock

Deadlock

In computer there is a lots of tasks that is to be carried out in CPU there task as a part is known as the process. For the completion of the process there is need of the resources through which the process is to be completed. And there may contain many process that need to share same resource. Due to one process should wait until it gets the chance to finish the process. But if the process remain unterminated due not getting  share to resource due to other process in the way show the condition that the deadlock occur.

For example, take a system with one tape drive and one plotter. Process P1 request the tape drive and process P2 requests the plotter. Both requests are granted. Now P1 requests the plotter (without giving up the tape drive) and P2 requests the tape drive (without giving up the plotter). Neither request can be granted so both processes enter a deadlock situation.

A deadlock is a situation where a group of processes is permanently blocked as a result of each process having acquired a set of resources needed for its completion and having to wait for release of the remaining resources held by others thus making it impossible for any of the deadlocked processes to proceed.

 Deadlocks can occur in concurrent environments as a result of the uncontrolled granting of the system resources to the requesting processes.

System Model:

Deadlocks can occur when processes have been granted exclusive access to devices, files and so forth. A system consists of a finite number of resources to be distributed among a number of competing processes.

 The resources can be divided into several types, each of which consists of some number of identical instances. CPU cycles, memory space, files and I/O devices (such as printers and tape drives) are examples of resource types. If a system has two tape drives then the resource type tape drive has two instances. 

Whenever a process wants to utilize any resource, it must make a request for it. It may request as many resources as it wants but it should not exceed the total number of resources available with the system. Once the process has utilized the resource it must release it. Therefore, a sequence of events to use a resource is:

i. Request the resource:

ii. Use the resource:

iii. Release the resource:

Request and release of resources can be accomplished through the wait and signal operations on semaphores.

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

Deadlock Characterization (Condition for Deadlock):

Deadlocks are undesirable features. In the most of deadlock situation process is waiting for the release of some resource concurrently possessed by some deadlocked process. A deadlock situation can arise if the following four conditions hold simultaneously in a system:

• Mutual exclusion

• Hold and wait

• No preemption

• Circular wait

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. If another process requests that resource, the requesting process must be delayed until the resource has been released.

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, …, Pn} of waiting processes must exist 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 Pn is waiting for a resource that is held by P0.