Deadlock I

Tom Kelliher, CS42

Oct. 18, 1996

System Model

  1. Processes competing for resources. Process model:
    while (1)
       request some resources;
       release some resources;

  2. Resource: anything a process may block on. Examples:

    Two types of resources:

    1. Serially reusable resources: printer, tape drive, CPU, etc.

    2. Consumable resources: semaphores, messages, etc.

Deadlock Examples


semaphore A(0), B(0);



Process 1 is waiting for process 2 is waiting for process 1...

Tape Drives

System has five tape drives.

Resource allocation graph.

Necessary Conditions for a Deadlock

  1. Mutual exclusion --- A resource is not sharable.

  2. Hold and wait --- A process is allowed to hold a resource while it's waiting for other resources.

  3. No preemption --- A process cannot be forced to give up a resource.

  4. Circular wait --- P1 is blocked because of P2; P2 is blocked because of P3; ...; Pn is blocked because of P1.

Why aren't these sufficient conditions?

How does deadlock differ from starvation?

Resource Allocation Graphs

Pretty simple:

  1. Vertices:

  2. Edges:

Dealing with Deadlocks

  1. Ignorance. More common than you'd think.

  2. Detection and recovery.

  3. Prevention --- Prevent one of the four necessary conditions.

  4. Avoidance --- Manage resources so that a deadlock never occurs:

Deadlock Prevention

Removal of one of the four necessary conditions.

Mutual Exclusion

  1. Share the resource.

  2. Example?

  3. Limitations?

Hold and Wait

  1. A process must release all resources before requesting more.

  2. Example?

  3. Limitations? (Request everything at once or wait a lot.)

No Preemption

  1. Kernel forcibly reclaims resources.

  2. Example?

  3. Limitations?

Circular Waiting

  1. Impose a total order on all resources.

  2. Resource i may only be requested if process holds no resource j with j > i.

  3. Example?

  4. Limitations:

Usefulness of Prevention

Thomas P. Kelliher
Wed Oct 16 23:15:41 EDT 1996
Tom Kelliher