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 tape drives.

P1 and P2 each hold one tape 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

  1. Traffic only in one direction.

  2.  Each section of a bridge can be viewed as a resource.

  3.  If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback).

  4.  Several cars may have to be backed up if a deadlock occurs.

  5.  Starvation is possible.

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:

   1. request

   2. use

   3. release