Transcript No Slide Title

Chapter 7: Deadlocks
Operating System Concepts – 8th Edition
Silberschatz, Galvin and Gagne ©2009
Chapter 7: Deadlocks
n
The Deadlock Problem
n
System Model
n
Deadlock Characterization
n
Methods for Handling Deadlocks
Operating System Concepts – 8th Edition
7.2
Silberschatz, Galvin and Gagne ©2009
Chapter Objectives
n
To develop a description of deadlocks, which prevent sets of
concurrent processes from completing their tasks
n
To present methods for Handling Deadlocks
Operating System Concepts – 8th Edition
7.3
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.4
Silberschatz, Galvin and Gagne ©2009
Introduction
n
In a multiprogramming environment, several processes may compete for a
finite number of resources.
n
A process requests resources; if the resources are not available at that
time, the process enters a waiting state.
n
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.
Operating System Concepts – 8th Edition
7.5
Silberschatz, Galvin and Gagne ©2009
The Deadlock Problem
n
What is a deadlock problem??
l
n
n
A set of blocked processes each holding a resource and waiting to
acquire a resource held by another process in the set
Example
l
System has 2 disk drives
l
P1 and P2 each hold one disk drive and each needs another one
Note :–
l
Most OSs do not prevent or deal with deadlocks
Operating System Concepts – 8th Edition
7.6
Silberschatz, Galvin and Gagne ©2009
Bridge Crossing Example
n
Traffic only in one direction
n
Each section of a bridge can be viewed as a resource
n
If a deadlock occurs, it can be resolved if one car backs up
(preempt resources and rollback)
n
Several cars may have to be backed up if a deadlock occurs
n
Starvation is possible
Operating System Concepts – 8th Edition
7.7
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.8
Silberschatz, Galvin and Gagne ©2009
System Model
n
The resources are partitioned into several types (R1, R2, . . ., Rm )
l
n
Instances are
identical
Each resource type Ri has Wi instances.
l
n
E.g.: CPU cycles, memory space, I/O devices
Examples:

If a system has (2) CPUs, then the resource type CPU has (2)
instances.

The resource type printer may have (5) instances.
Each process utilizes a resource as follows:
l
Request >> If the request cannot be granted immediately ,then the
requesting process must wait until it can acquire the resource.
l
Use
l
Release
Operating System Concepts – 8th Edition
7.9
Silberschatz, Galvin and Gagne ©2009
System Model (cont.)
n
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.
n
Resource forms:
l
Physical resources

l
Logical resources

n
e.g. printers, DVD drives, memory space, and CPU cycles
e.g. files
Example:
l
consider a system with one printer and one DVD drive.
l
Suppose that process Pi is holding the DVD and process Pj is holding the
printer.
l
If Pi requests the printer and Pj requests the DVD drive, a deadlock
occurs.
Operating System Concepts – 8th Edition
7.10
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.11
Silberschatz, Galvin and Gagne ©2009
Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously:
n
Mutual exclusion: only one process at a time can use a resource…(i.e.
No recourse sharing)
n
Hold and wait: a process holding at least one resource is waiting to
acquire additional resources held by other processes
n
No preemption: a resource can be released only voluntarily by the
process holding it, after that process has completed its task
n
Circular wait:
l
There exists a set {P0, P1, …, Pn} of waiting processes such that :

P0 is waiting for a resource that is held by P1,

P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting
for a resource that is held by Pn,

Pn is waiting for a resource that is held by P0.
Operating System Concepts – 8th Edition
7.12
Silberschatz, Galvin and Gagne ©2009
Resource-Allocation Graph
n Deadlocks can be described in terms of a directed graph called a
system resource-allocation graph.
n This graph consists of a set of vertices V and a set of edges E.
n V is partitioned into two types:
l
P = {P1, P2, …, Pn}, the set consisting of all the processes in
the system
l
R = {R1, R2, …, Rm}, the set consisting of all resource types in
the system
n E is partitioned into two types:
Pi  Rj
l
Request edge – directed edge
l
Assignment edge – directed edge
Operating System Concepts – 8th Edition
7.13
Rj  Pi
Silberschatz, Galvin and Gagne ©2009
Resource-Allocation Graph (Cont.)
n
Process
n
Resource Type with 4 instances
n
Pi requests instance of Rj
Pi
n
Rj
Pi is holding an instance of Rj
Pi
Rj
Operating System Concepts – 8th Edition
7.14
Silberschatz, Galvin and Gagne ©2009
Example of a Resource Allocation Graph
The sets P, R, and E:

P = {P1, P2, P3}

R = {R1, R2, R3, R4}

E = {P1 → R1, P2 → R3, R1 → P2, R2 →
P2, R2 → P1, R3 → P3}
Resource instances:

(1) instance of resource type R1

(2) instances of resource type R2

(1) instance of resource type R3

(3) 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.
Operating System Concepts – 8th Edition
7.15
Silberschatz, Galvin and Gagne ©2009
Basic Facts
How we recognize deadlock by using a Resource
Allocation Graph??
If graph contains no cycles  no deadlock
If graph contains a cycle 
 If
only one instance per resource type, then there is a
deadlock
 If
several instances per resource type, possibility of
deadlock .
Operating System Concepts – 8th Edition
7.16
Silberschatz, Galvin and Gagne ©2009
Resource Allocation Graph With NO Deadlock
Example (1):
The graph contains NO cycles  NO deadlock is occurred.
Operating System Concepts – 8th Edition
7.17
Silberschatz, Galvin and Gagne ©2009
Resource Allocation Graph With a Deadlock
Example (2):
The graph contains (2)cycles  may be a deadlock is
occurred.

Cycle (1) :
P1 → R1 → P2 → R3 → P3 → R2 → P1

Cycle (2) :P2 → R3 → P3 → R2 → P2
It ‘s a dead lock situation >>> Processes P1, P2, and
P3 are deadlocked…….why??

There is no chance to break the cycle.
Operating System Concepts – 8th Edition
7.18
Silberschatz, Galvin and Gagne ©2009
Graph With A Cycle But No Deadlock
Example (3):
The graph contains (1)cycle  may be a deadlock

Cycle :
P1 → R1 → P3 → R2 → P1
NO dead lock situation .....WHY????

process P4 may release its instance of resource type R2……
That resource can then be allocated to P3, breaking the
cycle.
Operating System Concepts – 8th Edition
7.19
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.20
Silberschatz, Galvin and Gagne ©2009
Methods for Handling Deadlocks
OS can deal with the deadlock problem in one of
three ways:
Use a protocol to prevent or avoid deadlocks, ensuring that
the system will never enter a deadlocked state.
Allow the system to enter a deadlocked state, detect it, and
recover.
Ignore the problem altogether and pretend that deadlocks
never occur in the system.

Used by most operating systems, including Unix & windows

This method is cheaper than the prevention, avoidance, or detection
and recovery methods.

Solution: The system must be restarted manually.
Operating System Concepts – 8th Edition
7.21
Silberschatz, Galvin and Gagne ©2009
End of Chapter 7
Operating System Concepts – 8th Edition
Silberschatz, Galvin and Gagne ©2009