Deadlocks

A process is said to be deadlocked when it is waiting for an event which will never occur. A deadlock is a situation where a group of processes is permanently blocked as a result of each process having acquired a subset of the resources needed for its completion and waiting for release of remaining resources held by others in the group- thus making it impossible for any of the process to proceed.

A deadlock involving a set of processes D is said to have occurred if

·         Every process Pi in D is blocked on some event ei, and

·         Event ei can only be caused by some process(es) in D.

Deadlocks can occur in concurrent environments as a result of uncontrolled granting of system resources to requesting processes. As an example, consider a system consisting of one printer and a file F on a tape and two processes Pi and Pj. Both pi and pj requires the tape and printer devices for their functioning. Suppose that the processes make their resources requests in the following order.

1.      Pi requests the file on the tape

2.      Pj requests the printer

3.      Pi requests the printer

4.      Pj requests the file on the tape

The first two resources requests can be granted because a tape cartridge and a printer exist in the system. Now, pi holds the file on the tape and pj holds the printer. When pi asks for the printer. It is blocked by the operating system since the printer is currently not available for allocation. Pj is similarly blocked when it asks for the file on the tape. Pi must release the file on the tape for Pj to come out of the blocked state and Pj must release the printer for Pi to come out of the blocked state. Both will never occur, hence the set of processes {Pi, Pj} is deadlocked.

Conditions for Deadlock

A deadlock in a system can occur only if the following four conditions exist in a system.

·        Mutual exclusion: the shared resources are acquired in a mutually exclusive manner. If a resource can be shared simultaneously by all processes, it cannot cause a deadlock.

·        Hold and Wait: Each process continues to hold resources allocated to it while waiting to acquire other resources. If a process requests and obtains all the resources it needs at one time, it cannot lead to a deadlock.

·        No Preemption: Resources granted to a process can be released back to the system only as a result of the voluntary action of that processes; the system cannot forcefully revoke them. If one process could remove resources from another, it would not need to wait for resources and hence a deadlock could not occur.

·        Circular Wait: Deadlocked processes are involved in a circular chain such that each process holds one or more resources being required by the next process in the chain.

      NEXT: Deadlock Handling

Previous: Semaphore 

           Index : Operating System