Deadlock I

Tom Kelliher, CS42

Oct. 18, 1996

System Model

1. Processes competing for resources. Process model:

   while (1)
   {
      request some resources;
      compute;
      release some resources;
   }
   

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

   • Device (disk read/write, printer, etc.)

   • Memory.

   • CPU.

   • File.

   Two types of resources:

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

   2. Consumable resources: semaphores, messages, etc.

Deadlock Examples

Semaphores

semaphore A(0), B(0);

process1()
{
   A.wait();
   B.signal();
}

process2()
{
   B.wait();
   A.signal();
}

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.

How does deadlock differ from starvation?

Resource Allocation Graphs

Pretty simple:

1. Vertices:
   • Processes.

   • Collections of resources of same type.

2. Edges:
   • Allocation.

   • Request.

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:
   • Determining the order.

   • How does an ``out of order'' process proceed?

Usefulness of Prevention

• Works for specific resources.

• No one mechanism is generally applicable.