1. a resource - anything required by a process

   1. anything - os as resource manager

   2. process - owns the resource

   3. required - no resource, no progress; adaptive processes

   4. resources - sharable, serially reusable, and consumable

2. resource management - protection, economy, and convenience

   1. fairness, policy and mechanism

   2. the deadlock problem

3. deadlock background

   1. a very old problem - train track management; gridlock

   2. os can suffer from deadlock too

   3. finite, non sharable resources lead to deadlock

   4. a global condition, which makes it difficult to find and deal with

4. deadlock handling techniques - reboot, prevention, avoidance, detect and recover

5. reboot - the traditional technique

6. prevention

   1. the four deadlock conditions

      1. exclusive access to resources - no sharing

      2. incremental allocation - many points at which a process can block

      3. circular waiting - no progress

      4. no take-backs - only the process can release resources

   2. these are necessary conditions - if any is missing, deadlock can't occur

      1. sharing - no waiting; good - simple, improves utility; bad - can be expensive

      2. bulk allocation - ask for everything up front; good - simple and cheap management; bad - difficult to do, inefficient

      3. ordered resources - no backwards waiting; good - incremental, efficient; bad - difficult to find orders, still inefficient

      4. pre-emption - retreived locked resources; good - selective recovery; bad - hard to do well, hard to deal with

7. avoidance

   1. always monitoring all processes for everything is expensive and restrictive

   2. safe, unsafe, and deadlock states - unsafe states could go either way

   3. monitor processes in the unsafe state to keep them from deadlock

   4. the banker's algorithm

      1. given a set of maximum claims, how much is needed to cover - the maximum maximum

      2. assumptions - a maximum claim, non-maximum requests, no pre-emption, requests satisfied in any order

      3. objective - if no process is maxed, make sure there's always enough on hand to satisfy some maximum;

      4. procedure - deny any non-maximum request that violates the objective

8. detection and recovery

   1. model the system and determine if the model indicates deadlock - a reactive approach

   2. system state model - a directed graph

      1. each state represents some allocation of available resources

      2. each edge represents a process's request, allocation, or release

      3. a state with no outward edges is a deadlock state

      4. this is a large, expensive representation - exponential in resources

      5. with one resource this turns into state-based protocol analysis

   3. resource graphs - a directed, bipartite graph

      1. each node is either a process or a resource

      2. edges indicate requests (from p to r) or allocations (from r to p)

      3. a cycle in the resource graph indicates a deadlock

      4. extendable to multiple resources, but with difficulty - knots instead of cycles

   4. recovery

      1. reboot, selective pre-emption, delete processes, check-point and roll back

This page last modified on 22 October 2001.