UNIT-III
DEAD LOCKS
3.1 Deadlocks:
In a multiprogramming environment, several processes may compete for a finite number of resources.
A process requests resources; if the resources are not available at that time, the process enters a
waiting state. Sometimes, a waiting process is never again able to change state, because the resources
it has requested are held by other waiting processes. This situation is called a deadlock.
3.2 System Model:
A system consists of a finite number of resources to be distributed among a number of
competing processes. The resources may be partitioned into several types (or classes), each
consisting of some number of identical instances. CPU cycles, files, and I/O devices (such as
printers and DVD drives) are examples of resource types. If a system has two CPUs, then the
resource type CPU has two instances. Similarly, the resource type printer may have five
instances.
A process must request a resource before using it and must release the resource
after using it. A process may request as many resources as it requires to carry out its designated
task. Obviously, the number of resources requested may not exceed the total number of
resources available in the system. In other words, a process cannot request three printers if the
system has only two.
Under the normal mode of operation, a process may utilize a resource in only the following
sequence:
1.Request. The process requests the resource. If the request cannot be granted immediately (for
example, if the resource is being used by another process), then the requesting process must
wait until it can acquire the resource.
2.Use. The process can operate on the resource (for example, if the resource is a printer, the
process can print on the printer).
3.Release. The process releases the resource.
The request and release of resources may be system calls.
Examples: The request() and release() device, open() and close() file, and allocate() and free()
memory system calls.
⮚ A set of processes is in a deadlocked state when every process in the set is waiting for an
event that can be caused only by another process in the set.
⮚ The events with which we are mainly concerned here are resource acquisition and release.
⮚ The resources may be either physical resources (for example, printers, tape drives,
memory space, and CPU cycles) or logical resources (for example, semaphores, mutex
locks, and files).
⮚ However, other types of events may result in deadlocks.
This below example illustrates a deadlock involving the same resource type.
To illustrate a deadlocked state, consider a system with three CD RW drives.
Suppose each of three processes holds one of these CD RW drives. If each process now
requests another drive, the three processes will be in a deadlocked state. Each is waiting for
the event “CD RW is released,” which can be caused only by one of the other waiting
processes.
Deadlocks may also involve different resource types.
For example: consider a system with one printer and one DVD drive. Suppose that
process Pi is holding the DVD and process Pj is holding the printer. If Pi requests the
printer and Pj requests the DVD drive, a deadlock occurs.
1
,3.3 Deadlock Characterization:
Necessary Conditions:
A deadlock situation can arise if the following four conditions hold
simultaneously in a system:
1. 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.
2. 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.
3. 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.
4. Circular wait. A set P0, P1, {..., Pn of waiting
} processes must exist such that P0 is waiting for a
resource held by P1, P1 is waiting for a resource held by P2, ..., Pn−1 is waiting for a resource held
by Pn, and Pn is waiting for a resource held by P0.
Resource-Allocation Graph:
⮚ Deadlocks can be described more precisely in terms of a directed graph called a
system resource-allocation graph.
⮚ This graph{consists of a}set of vertices V and a set of edges E. The set of vertices
V is partitioned
{ into two different
} types of nodes: P = P1, P2, ..., Pn , the set
consisting of all the active processes in the system, and R = R1, R2, ..., Rm , the set
consisting of all resource types in the system.
→
⮚ A directed edge from process Pi to resource type Rj is denoted by Pi Rj ; it
signifies that process Pi has requested an instance of resource type Rj and is
currently waiting for that resource.
⮚ A directed edge from resource type Rj to process Pi is→denoted by Rj→Pi ; it
signifies that an instance of resource
→ type Rj has been allocated to process Pi .
⮚ A directed edge Pi→ Rj is called a request edge;
⮚ a directed edge Rj → Pi is called an assignment edge.
Pictorially, we represent each process Pi as a circle and each resource
type Rj as a rectangle. Since resource type Rj may have more than one instance, we
represent each such instance as a dot within the rectangle.
Note that a request edge points to only the rectangle Rj ,whereas an assignment edge must
also designate one of the dots in the rectangle.
When process Pi requests an instance of resource type Rj , a request edge is inserted in
the resource-allocation graph. When this request can be fulfilled, the request edge is
instantaneously transformed to an assignment edge. When the process no longer needs
access to the resource, it releases the resource. As a result, the assignment edge is deleted.
The resource-allocation graph shown in Figure. It depicts the following situation.
• The sets P, R, and E:
◦ P = {P1, P2, P3}
2
, R1 R3
P1 P2 P3
R2
R4
Figure : Resource-allocation graph.
◦ R = {R1, R2, R3, R4}
◦ E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}
• Resource instances:
◦ One instance of resource type R1
◦ Two instances of resource type R2
◦ One instance of resource type R3
◦ Three instances of resource type R4
• Process states:
◦ Process P1 is holding an instance of resource type R2 and is
waiting for an instance of resource type R1.
◦ Process P2 is holding an instance of R1 and an instance of R2
and is waiting for an instance of R3.
◦ Process P3 is holding an instance of R3.
Given the definition of a resource-allocation graph, it can be shown that, if the graph
contains no cycles, then no process in the system is deadlocked. If the graph does
contain a cycle, then a deadlock may exist.
If each resource type has exactly one instance, then a cycle implies that a deadlock has
occurred. If the cycle involves only a set of resource types, each of which has only a
single instance, then a deadlock has occurred. Each process involved in the cycle is
deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient
condition for the existence of deadlock.
If each resource type has several instances, then a cycle does not necessarily imply that
a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a
sufficient condition for the existence of deadlock.
To illustrate this concept, we return to the resource-allocation graph depicted in above
Figure. Suppose that process P3 requests an instance of resource
3
, R1 R3
P1 P2 P3
R2
R4
Figure 7.2 Resource-allocation graph with a deadlock.
type R2. Since no resource instance is currently available, we add a request edge P3 R2 to
→(Figure 7.2). At this point, two minimal cycles exist in the system:
the graph
P1 → R1 → P2 → R3 → P3 → R2 → P1 P2 →
R3 → P3 → R2 → P2
Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which
is held by process P3. Process P3 is waiting for either process P1 or process P2 to release
resource R2. In addition, process P1 is waiting for process P2 to release resource R1.
Now consider the resource-allocation graph in Figure 7.3. In this example, we also have
a cycle:
P1 → R1 → P3 → R2 → P1
P2
R1
P3
P1
R2
P4
Figure 7.3 Resource-allocation graph with a cycle but no deadlock
However, there is no deadlock. Observe that process P4 may release its instance of
resource type R2. That resource can then be allocated to P3, breaking the cycle.
In summary, if a resource-allocation graph does not have a cycle, then the system is
not in a deadlocked state. If there is a cycle, then the system may or may not be in a
deadlocked state. This observation is important when we deal with the deadlock
problem.
4
DEAD LOCKS
3.1 Deadlocks:
In a multiprogramming environment, several processes may compete for a finite number of resources.
A process requests resources; if the resources are not available at that time, the process enters a
waiting state. Sometimes, a waiting process is never again able to change state, because the resources
it has requested are held by other waiting processes. This situation is called a deadlock.
3.2 System Model:
A system consists of a finite number of resources to be distributed among a number of
competing processes. The resources may be partitioned into several types (or classes), each
consisting of some number of identical instances. CPU cycles, files, and I/O devices (such as
printers and DVD drives) are examples of resource types. If a system has two CPUs, then the
resource type CPU has two instances. Similarly, the resource type printer may have five
instances.
A process must request a resource before using it and must release the resource
after using it. A process may request as many resources as it requires to carry out its designated
task. Obviously, the number of resources requested may not exceed the total number of
resources available in the system. In other words, a process cannot request three printers if the
system has only two.
Under the normal mode of operation, a process may utilize a resource in only the following
sequence:
1.Request. The process requests the resource. If the request cannot be granted immediately (for
example, if the resource is being used by another process), then the requesting process must
wait until it can acquire the resource.
2.Use. The process can operate on the resource (for example, if the resource is a printer, the
process can print on the printer).
3.Release. The process releases the resource.
The request and release of resources may be system calls.
Examples: The request() and release() device, open() and close() file, and allocate() and free()
memory system calls.
⮚ A set of processes is in a deadlocked state when every process in the set is waiting for an
event that can be caused only by another process in the set.
⮚ The events with which we are mainly concerned here are resource acquisition and release.
⮚ The resources may be either physical resources (for example, printers, tape drives,
memory space, and CPU cycles) or logical resources (for example, semaphores, mutex
locks, and files).
⮚ However, other types of events may result in deadlocks.
This below example illustrates a deadlock involving the same resource type.
To illustrate a deadlocked state, consider a system with three CD RW drives.
Suppose each of three processes holds one of these CD RW drives. If each process now
requests another drive, the three processes will be in a deadlocked state. Each is waiting for
the event “CD RW is released,” which can be caused only by one of the other waiting
processes.
Deadlocks may also involve different resource types.
For example: consider a system with one printer and one DVD drive. Suppose that
process Pi is holding the DVD and process Pj is holding the printer. If Pi requests the
printer and Pj requests the DVD drive, a deadlock occurs.
1
,3.3 Deadlock Characterization:
Necessary Conditions:
A deadlock situation can arise if the following four conditions hold
simultaneously in a system:
1. 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.
2. 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.
3. 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.
4. Circular wait. A set P0, P1, {..., Pn of waiting
} processes must exist such that P0 is waiting for a
resource held by P1, P1 is waiting for a resource held by P2, ..., Pn−1 is waiting for a resource held
by Pn, and Pn is waiting for a resource held by P0.
Resource-Allocation Graph:
⮚ Deadlocks can be described more precisely in terms of a directed graph called a
system resource-allocation graph.
⮚ This graph{consists of a}set of vertices V and a set of edges E. The set of vertices
V is partitioned
{ into two different
} types of nodes: P = P1, P2, ..., Pn , the set
consisting of all the active processes in the system, and R = R1, R2, ..., Rm , the set
consisting of all resource types in the system.
→
⮚ A directed edge from process Pi to resource type Rj is denoted by Pi Rj ; it
signifies that process Pi has requested an instance of resource type Rj and is
currently waiting for that resource.
⮚ A directed edge from resource type Rj to process Pi is→denoted by Rj→Pi ; it
signifies that an instance of resource
→ type Rj has been allocated to process Pi .
⮚ A directed edge Pi→ Rj is called a request edge;
⮚ a directed edge Rj → Pi is called an assignment edge.
Pictorially, we represent each process Pi as a circle and each resource
type Rj as a rectangle. Since resource type Rj may have more than one instance, we
represent each such instance as a dot within the rectangle.
Note that a request edge points to only the rectangle Rj ,whereas an assignment edge must
also designate one of the dots in the rectangle.
When process Pi requests an instance of resource type Rj , a request edge is inserted in
the resource-allocation graph. When this request can be fulfilled, the request edge is
instantaneously transformed to an assignment edge. When the process no longer needs
access to the resource, it releases the resource. As a result, the assignment edge is deleted.
The resource-allocation graph shown in Figure. It depicts the following situation.
• The sets P, R, and E:
◦ P = {P1, P2, P3}
2
, R1 R3
P1 P2 P3
R2
R4
Figure : Resource-allocation graph.
◦ R = {R1, R2, R3, R4}
◦ E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}
• Resource instances:
◦ One instance of resource type R1
◦ Two instances of resource type R2
◦ One instance of resource type R3
◦ Three instances of resource type R4
• Process states:
◦ Process P1 is holding an instance of resource type R2 and is
waiting for an instance of resource type R1.
◦ Process P2 is holding an instance of R1 and an instance of R2
and is waiting for an instance of R3.
◦ Process P3 is holding an instance of R3.
Given the definition of a resource-allocation graph, it can be shown that, if the graph
contains no cycles, then no process in the system is deadlocked. If the graph does
contain a cycle, then a deadlock may exist.
If each resource type has exactly one instance, then a cycle implies that a deadlock has
occurred. If the cycle involves only a set of resource types, each of which has only a
single instance, then a deadlock has occurred. Each process involved in the cycle is
deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient
condition for the existence of deadlock.
If each resource type has several instances, then a cycle does not necessarily imply that
a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a
sufficient condition for the existence of deadlock.
To illustrate this concept, we return to the resource-allocation graph depicted in above
Figure. Suppose that process P3 requests an instance of resource
3
, R1 R3
P1 P2 P3
R2
R4
Figure 7.2 Resource-allocation graph with a deadlock.
type R2. Since no resource instance is currently available, we add a request edge P3 R2 to
→(Figure 7.2). At this point, two minimal cycles exist in the system:
the graph
P1 → R1 → P2 → R3 → P3 → R2 → P1 P2 →
R3 → P3 → R2 → P2
Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which
is held by process P3. Process P3 is waiting for either process P1 or process P2 to release
resource R2. In addition, process P1 is waiting for process P2 to release resource R1.
Now consider the resource-allocation graph in Figure 7.3. In this example, we also have
a cycle:
P1 → R1 → P3 → R2 → P1
P2
R1
P3
P1
R2
P4
Figure 7.3 Resource-allocation graph with a cycle but no deadlock
However, there is no deadlock. Observe that process P4 may release its instance of
resource type R2. That resource can then be allocated to P3, breaking the cycle.
In summary, if a resource-allocation graph does not have a cycle, then the system is
not in a deadlocked state. If there is a cycle, then the system may or may not be in a
deadlocked state. This observation is important when we deal with the deadlock
problem.
4
