Outline for May 30, 2008

Reading: Text, §8, 9

1. Greetings and felicitations!
2. Disk directory
   1. What blocks are in use, where files are, etc.
   2. Free list implementations, bit maps
   3. File maps: linked list, pairs
3. Allocation of Disk Blocks to Files
   1. Contiguous allocation
   2. Linked allocation
   3. Indexed allocation
4. Network File System (NFS)
   1. How it works
   2. Protocol
   3. Generation numbers
5. Deadlock
   1. Resource manager, request, release
   2. What is deadlock
   3. Difference between it and starvation
   4. Liberal, conservative, and serialization approaches to resource allocation
6. Resource types
   1. Reusable
   2. Consumable
7. How to Deal with Deadlock (Policies)
   1. Ignore
   2. Detection and recovery
   3. Prevention: mutual exclusion, no preemption, circular wait, hold and wait
   4. Avoidance
8. Deadlock Recovery
   1. Breaking circular wait
   2. Break no preemption (i.e., allow preemption)
9. Deadlock Prevention
   1. Single-programming environment
   2. Hierarchical ordering (ordered resource) policy
   3. Acquire all resources before running
   4. Maximum claim techniques
10. Deadlock Avoidance
    1. Banker’s Algorithm