Lecture Notes for Operating Systems

Deadlock, 11 October 1999

1. deadlocks

2. resources

   1. pre-emptable, nonpre-emptable resource - storage, cpu; printer, keyboard

   2. resource allocation and failure

3. deadlock

   1. every process waiting on some other waiting process

   2. conditions - necessary and sufficient

      1. resource mutual exclusion - why they're waiting

      2. resources held while waiting - tie up resources for others

      3. no resource pre-emption - can't recover allocated resources

      4. a cycle of resource grants and requests

   3. resource grant-request graphs

      1. resource and process nodes

      2. request and grant arcs

      3. deadlocks are cycles in the resource graph

4. deadlock avoidance techniques

   1. ignore the problem - recover on system restarts;

      1. sometimes necessary - rare occurrences, expensive solutions

      2. good special purpose solution, bad general purpose solution

   2. detection and recovery

      1. break cycles by pre-emption (killing the holder)

      2. good - effective and general purpose

      3. bad - may be difficult to detect, roll-back may be difficult

   3. prevention - remove any of the for deadlock conditions

      1. mutual exclusion - virtual devices, multiplexing, spooling

      2. pre-allocation before execution - eliminate the wait during hold

         1. good - effective

         2. bad - inefficient, difficult to comply with

      3. allow resource pre-emption - difficult to implement without extra help

      4. eliminate request-grant cycles - order resources; difficult to find orderings that satisfy everyone

   4. deadlock avoidance - examine requests

      1. the banker's algorithm - dikjstra

         1. always have enough in reserve to satisfy someone completely

         2. delay request until safe.

      2. resource trajectories - graphical, multi-resource analysis

      3. multi-resource banker's algorithm

      4. general problems - pre-allocation difficult, requesters pop in and out of existence, resources pop in and out of existence

5. special-purpose algorithms - databases

This page last modified on 11 October 1999.