Transcript Lecture #13: Deadlocks

Lecture 13
Chapter 7: Deadlocks
Modified from Silberschatz, Galvin and Gagne
Chapter 7: Deadlocks

The Deadlock Problem

System Model

Deadlock Characterization

Methods for Handling Deadlocks
 Deadlock Prevention

Deadlock Avoidance

Deadlock Detection

Recovery from Deadlock
Principles of Computer Operating Systems
2
Chapter Objectives
 To develop a description of deadlocks,

which prevent sets of concurrent processes from completing their
tasks
 To present a number of different methods for preventing or avoiding
deadlocks in a computer system
Principles of Computer Operating Systems
3
The Deadlock Problem
 A set of blocked processes each holding a resource and waiting to
acquire a resource held by another process in the set


Example

System has 2 disk drives

P1 and P2 each hold one disk drive and each needs another one
Example

semaphores A and B, initialized to 1
P0
P1
wait (A);
wait(B)
wait (B);
wait(A)
Principles of Computer Operating Systems
4
Bridge Crossing Example
 Traffic only in one direction
 Each section of a bridge can be viewed as a resource
 If a deadlock occurs, it can be resolved if one car backs up

preempt resources and rollback
 Several cars may have to be backed up if a deadlock occurs
 Starvation is possible
 Note : Most OSes do not prevent or deal with deadlocks
Principles of Computer Operating Systems
5
Deadlock Principles
 A deadlock is a permanent blocking of a set of threads

a deadlock can happen while threads/processes are competing for system
resources or communicating with each other
Illustration of a deadlock
Principles of Computer Operating Systems
6
Tanenbaum, A. S. (2001)
Modern Operating Systems (2nd Edition).
Deadlock Principles
 Illustration of a deadlock — scheduling path 1 


A required
B required
Q executes everything before P can ever get A
when P is ready, resources A and B are free and P can proceed
Process P
Process Q
...
Get A
...
Get B
...
Release A
...
Release B
...
...
Get B
...
Get A
...
Release B
...
Release A
...
Happy scheduling 1
Principles of Computer Operating Systems
7
B required
A required
Deadlock Principles
 Illustration of a deadlock — scheduling path 2 

A required
B required
Q gets B and A, then P is scheduled; P wants A but is blocked by A’s mutex; so Q
resumes and releases B and A; P can now go
Process P
Process Q
...
Get A
...
Get B
...
Release A
...
Release B
...
...
Get B
...
Get A
...
Release B
...
Release A
...
Happy scheduling 2
Principles of Computer Operating Systems
8
B required
A required
Deadlock Principles
 Illustration of a deadlock — scheduling path 3 

A required
B required
Q gets only B, then P is scheduled and gets A; now both P and Q are blocked, each
waiting for the other to release a resource
Process P
Process Q
...
Get A
...
Get B
...
Release A
...
Release B
...
...
Get B
...
Get A
...
Release B
...
Release A
...
deadlock
Bad scheduling  deadlock
Principles of Computer Operating Systems
9
B required
A required
Deadlock Principles
Stallings, W. (2004) Operating Systems:
Internals and Design Principles (5th Edition).
Joint progress diagram
Principles of Computer Operating Systems
10
Deadlock Principles

Deadlocks depend on the program and the scheduling

program design



the order of the statements in the code creates
the “landscape” of the joint progress diagram
this landscape may contain gray “swamp”
areas leading to deadlock
scheduling condition

the interleaved dynamics of multiple
executions traces a “path” in this landscape

this path may sink in the swamps
Principles of Computer Operating Systems
11
Deadlock Principles
 Changing the program changes the landscape


A required
B required
here, P releases A before getting B
deadlocks between P and Q are not possible anymore
Process P
Process Q
...
Get A
...
Release A
...
Get B
...
Release B
...
...
Get B
...
Get A
...
Release B
...
Release A
...
Competing processes
Principles of Computer Operating Systems
12
B required
A required
Deadlock Principles
Joint progress diagram

no swamp area: there exists no path
leading to deadlock
Principles of Computer Operating Systems
Stallings, W. (2004) Operating Systems:
Internals and Design Principles (5th Edition).
13
System Model
 Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
 Each resource type Ri has Wi instances.
 Each process utilizes a resource as follows:

request

use

release
Principles of Computer Operating Systems
14
Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.
 Mutual exclusion: only one process at a time can use a resource
 Hold and wait: a process holding at least one resource is waiting
to acquire additional resources held by other processes
 No preemption: a resource can be released only voluntarily by
the process holding it, after that process has completed its task
 Circular wait: there exists a set {P0, P1, …, P0} 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, and P0 is waiting for a resource that is held by P0.
Principles of Computer Operating Systems
15
Resource-Allocation Graph
A set of vertices V and a set of edges E.
 V is partitioned into two types:

P = {P1, P2, …, Pn}, the set consisting of all the processes in
the system

R = {R1, R2, …, Rm}, the set consisting of all resource types in
the system
 request edge – directed edge P1  Rj
 assignment edge – directed edge Rj  Pi
Principles of Computer Operating Systems
16
Resource-Allocation Graph (Cont.)
 Process
 Resource Type with 4 instances
 Pi requests instance of Rj
Pi
Rj
 Pi is holding an instance of Rj
Pi
Rj
Principles of Computer Operating Systems
17
Example of a Resource Allocation Graph
Principles of Computer Operating Systems
18
Resource Allocation Graph With A Deadlock
Principles of Computer Operating Systems
19
Graph With A Cycle But No Deadlock
Principles of Computer Operating Systems
20
Basic Facts
 If graph contains no cycles  no deadlock
 If graph contains a cycle 

if only one instance per resource type, then deadlock

if several instances per resource type, possibility of deadlock
Principles of Computer Operating Systems
21