Deadlock in Operating
System
Definition
A set of two or more processes are deadlocked if they are blocked (i.e., in the waiting state) each
holding a resource and waiting to acquire a resource held by another process in the set.
or
A process is deadlocked if it is waiting for an event which is never going to happen.
Example:
a system has two tape drives
two processes are deadlocked if each holds one tape drive and has requested the other
Example: semaphores A and B, each initialized to 1:
P_0 P_1
--- ---
A. wait(); B.wait();
B. wait(); A.wait();
A. signal(); B.signal();
B. signal(); A.signal();
Deadlock depends on the dynamics of the execution.
Illustrates that it is difficult to identify and test for deadlocks which may occur only under certain
circumstances.
System model:
resource types: R1, R2, ..., Rn
each resource R has Wi instances
each process utilizes a resource as follows:
// request (e.g., open() system call)
// use
// release (e.g., close() system call)
1/14
, Any instance of a resource type can be used to satisfy a request of that resource.
Conditions Necessary for Deadlock
All of the following four necessary conditions must hold simultaneously for deadlock to occur:
mutual exclusion: only one process can use a resource at a time.
2/14
System
Definition
A set of two or more processes are deadlocked if they are blocked (i.e., in the waiting state) each
holding a resource and waiting to acquire a resource held by another process in the set.
or
A process is deadlocked if it is waiting for an event which is never going to happen.
Example:
a system has two tape drives
two processes are deadlocked if each holds one tape drive and has requested the other
Example: semaphores A and B, each initialized to 1:
P_0 P_1
--- ---
A. wait(); B.wait();
B. wait(); A.wait();
A. signal(); B.signal();
B. signal(); A.signal();
Deadlock depends on the dynamics of the execution.
Illustrates that it is difficult to identify and test for deadlocks which may occur only under certain
circumstances.
System model:
resource types: R1, R2, ..., Rn
each resource R has Wi instances
each process utilizes a resource as follows:
// request (e.g., open() system call)
// use
// release (e.g., close() system call)
1/14
, Any instance of a resource type can be used to satisfy a request of that resource.
Conditions Necessary for Deadlock
All of the following four necessary conditions must hold simultaneously for deadlock to occur:
mutual exclusion: only one process can use a resource at a time.
2/14
