Page 134 - DCAP103_Principle of operating system

Unit 4: Process Management-III

deadlocks. To illustrate a deadlock state, we consider a system with three tape drives. Suppose Notes
each of three processes holds one of these tape drives. If each process now requests another
tape drive, the three processes will be in a deadlock state. Each is waiting for the event “tape
drive is released,” which can be caused only by one of the other waiting processes. This example
illustrates a deadlock involving the same resource type. Deadlocks may also involve different
resource types. For example, consider a system with one printer and one tape drive. Suppose
that process Pi is holding the tape drive and process Pi is holding the printer. If Pi requests the
printer and Pi requests the tape drive, a deadlock occurs.

A programmer who is developing multi-threaded applications must pay
particular attention to this problem—Multi-threaded programs are good
candidates for deadlock because multiple threads can compete for shared
resources.

4.6.2 Deadlock Characterization

In a deadlock, processes never finish executing and system resources are tied up, preventing
other jobs from starting. Before we discuss the various methods for dealing with the deadlock
problem, we shall describe features that characterize deadlocks.

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 nonsharable 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 {Po, PI, ..., P,) of waiting processes must exist such that Po is waiting
for a resource that is held by PI, PI is waiting for a resource that is held by P2, ..., PnPl
is waiting for a resource that is held by P,, and P, is waiting for a resource that is held
by Po. We emphasize that all four conditions must hold for a deadlock to occur. The
circular-wait condition implies the hold-and-wait condition, so the four conditions are
not completely independent.
4.6.3 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 = {PI, 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 requested an instance of resource
type Ri and is currently waiting for that resource. A directed edge from resource type Ri
to process Pi is denoted by Rj -+ Pi; it signifies that an instance of resource type Ri has
been allocated to process Pi. A directed edge Pi -+ Rj is called a request edge; a directed

LOVELY PROFESSIONAL UNIVERSITY 127