Deadlock, Examples of Deadlock & Deadlock characterization

Deadlock, Examples of Deadlock & Deadlock characterization

In a multi-programming environment, several processes competes for  resources. A situation may arise where a process is waiting for a resource that is held by other waiting processes.This situation is called deadlock.A system has finite set of resources such as memory, i/o, devices etc.It also has finite set of processes that need to use these resources.A Process that wishes to use any of these resources make a request to use these resources. If the resource is free the process gets it  and if it is hold by any other process then it waits for resource to be free.

A set of processes is in deadlock state when every process in the set is waiting for an event that can only be caused by another process in the set.

suppose we have two tap drives and two processes. Each process has got one tape drive for each process but both need two such tape drives to proceed with execution. Each is waiting for other process to release the other tape  drive to proceed with execution. Each is waiting for resource hold by another that situation is called deadlock.

Examaples

Two trains/cars reaching at a crossing point at same time.

Printer and Tape drives.

Traffic deadlock.

Deadlock Characterization

Deadlock occurs if following four necessary conditions occur.

1. Mutual Exclusion

2. Hold and Wait

3. No Preemption

4. Circular Wait

Deadlock characterization 

Mutual exclusion 

At least one resource must be held in a non shareable mode. It means that only one process at a time can use the resource. If another process request the 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 in waiting to acquire additional resources that are currently being held by other processes. 

No Preemption 

Resources cannot be preempted. Resource can be released on the voluntary by the process folding it after that process has completed its task. 

Circular wait 

A set of processes p0,p1,p2...pn waiting processes must exist such that p0 is waiting for a resource that is is held by p1, and p1 is waiting for a process that is is held by p2  an and so on. All four conditions must hold for a deadlock to occur.