Hi Manjunath A.
Recall that one definition of an operating system is a resource allocator. There are many resources that can be allocated to only one process at a time, and we have seen several operating system features that allow this, such as mutexes, semaphores or file locks.
Sometimes a process has to reserve more than one resource. For example, a process which copies files from one tape to another generally requires two tape drives. A process which deals with databases may need to lock multiple records in a database.
In general, resources allocated to a process are not preemptable; this means that once a resource has been allocated to a process, there is no simple mechanism by which the system can take the resource back from the process unless the process voluntarily gives it up or the system administrator kills the process. This can lead to a situation called deadlock. A set of processes or threads is deadlocked when each process or thread is waiting for a resource to be freed which is controlled by another process. Here is an example of a situation where deadlock can occur.
Mutex M1, M2;
/* Thread 1 */
while (1) {
NonCriticalSection()
Mutex_lock(&M1);
Mutex_lock(&M2);
CriticalSection();
Mutex_unlock(&M2);
Mutex_unlock(&M1);
}
/* Thread 2 */
while (1) {
NonCriticalSection()
Mutex_lock(&M2);
Mutex_lock(&M1);
CriticalSection();
Mutex_unlock(&M1);
Mutex_unlock(&M2);
}
Suppose thread 1 is running and locks M1, but before it can lock M2, it is interrupted. Thread 2 starts running; it locks M2, when it tries to obtain and lock M1, it is blocked because M1 is already locked (by thread 1). Eventually thread 1 starts running again, and it tries to obtain and lock M2, but it is blocked because M2 is already locked by thread 2. Both threads are blocked; each is waiting for an event which will never occur.
Traffic gridlock is an everyday example of a deadlock situation.
In order for deadlock to occur, four conditions must be true.
Mutual exclusion - Each resource is either currently allocated to exactly one process or it is available. (Two processes cannot simultaneously control the same resource or be in their critical section).
Hold and Wait - processes currently holding resources can request new resources
No preemption - Once a process holds a resource, it cannot be taken away by another process or the kernel.
Circular wait - Each process is waiting to obtain a resource which is held by another process.
The dining philosophers problem discussed in an earlier section is a classic example of deadlock. Each philosopher picks up his or her left fork and waits for the right fork to become available, but it never does.
Deadlock can be modeled with a directed graph. In a deadlock graph, vertices represent either processes (circles) or resources (squares). A process which has acquired a resource is show with an arrow (edge) from the resource to the process. A process which has requested a resource which has not yet been assigned to it is modeled with an arrow from the process to the resource. If these create a cycle, there is deadlock.
Please visit http://www.cs.rpi.edu/academics/courses/fall04/os/c10/index.html for more information.