operating system

CMET 331 Operating Systems

7. Deadlocks

Outline • The Deadlock Problem • System Model • Deadlock Characterization • Methods for Handling Deadlocks • Deadlock Prevention

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 deadlocks in a computer system.

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)

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.

Illustration of Deadlock

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

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, …, 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, and Pn is waiting for a resource that is held by P0.

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 Pi  Rj • assignment edge – directed edge Rj  Pi

Resource-Allocation Graph (Cont.)

Pi

Pi Rj

Rj

• Process

• Resource Type with 4 instances

• Pi requests instance of Rj

• Pi is holding an instance of Rj

Example of a Resource Allocation Graph

Resource Allocation Graph With A Deadlock

Graph With A Cycle But No Deadlock

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.

Deadlock Handling Strategies • Ignore the problem altogether • Detection and recovery • Avoidance by careful resource allocation • Prevention by negating one of the four

necessary conditions

Deadlock with Multiple Processes • Deadlock between three processes

— A & C need R, indirect dependence through B

6. C requests R (deadlock)

1. A gets R

4. A requests S

2. B gets S

5. B requests T

3. C gets T

Process A Process B Process C

• Requests R • Requests S • Release R • Release S

• Requests S • Requests T • Release S • Release T

• Requests T • Requests R • Release T • Release R

A B C

R S T

Preventing Deadlock • OS scheduling eliminates circular wait

— Delaying B eliminates dependence on T

2. C gets T

1. A gets R

3. A gets S

4. C requests R

5. A releases R and S

6. C gets R

7. B gets S

8. B requests T

Process A Process B Process C

• Requests R • Requests S • Release R • Release S

• Requests S • Requests T • Release S • Release T

• Requests T • Requests R • Release T • Release R

A B C

R S T

Dealing with Deadlock within the OS • Do nothing

— Hope that is never happens • Deadlock Prevention

— Do not allow one of the 4 deadlock conditions • Deadlock Avoidance

— Never allow a state where deadlock can occur • Deadlock Detection and Recovery

— Periodically check for deadlock and then fix it

No Explicit Deadlock Scheme • Eliminating deadlock is expensive

— Schemes require extra OS intervention • Assume that deadlock is infrequent

— Treat it as an error condition • Use brute force techniques

— Allow more resources than needed • Use design techniques to eliminate some

sources of deadlock — i.e. deadlock prevention — Time tested practices (i.e. process model)

Deadlock Prevention • Eliminating mutual exclusion

— In general not possible — May be possible by changing design of certain devices (i.e.

print spooling) • Eliminating hold and wait

— Processes request all resources before starting — Release resources when requesting more

• Eliminating the no preemption condition — Processes give up resources when blocking — Only possible with preemptable resources

Eliminating Circular Wait • Only allow processes to own a single resource

at a time (not feasible) • Allocate resources in order

— Resource dependencies cannot circle back

A

R

B

S

C

T

• Requests R • Requests S • Release R • Release S

• Requests S • Requests T • Release S • Release T

• Requests R • Requests T • Release R • Release T

Process A Process B Process C

1. A gets R

2. B gets S

4. A requests S

5. B requests T

3. C requests R

6. C is blocked waiting on R

End of Chapter 7