Outline for January 16, 2001

1. Greetings and felicitations!
   1. All projects turned in are on the web page; you should have received approval or disapproval by now
2. Higher-level language constructs
   1. Monitors
   2. Crowd monitors
   3. Invariant expressions
   4. CSP
   5. RPC
   6. ADA?
3. Deadlock
   1. Serially reusable resources vs. consumable resources
   2. What is deadlock?
   3. Approaches to solving it: ignore, detect and recover, prevent, avoid
4. System model
   1. Process maps one state into a set of states (each a potential ending state)
   2. Define blocked, deadlocked process; deadlocked, safe states
   3. Resource graphs; request, assignment edges; operations are requesting, acquiring, releasing
   4. Review terms: bipartite, sink, isolated nodes, path, cycle, reachable set, knot
5. Deadlock Detection
   1. Graph analysis of system: assume serially reusable resources (SRR)
   2. Reduction of SRR graphs
   3. Lemma: All reduction sequences of a given SRR graph lead to the same irreducible graph
   4. Deadlock Theorem: S is a deadlock state if and only if the reusable resource graph of S is not completely reducible.
   5. Cycle Theorem: A cycle in a reusable resource graph is a necessary condition for deadlock.
   6. Continuous deadlock detection
   7. Expediency and deadlocks
   8. Single-unit resources and deadlocks
6. Deadlock Recovery
   1. Process termination: kill one with lowest cost first
   2. Termination in expedient states, single unit requests: terminate one process per knot, minimum cost to restart
   3. Process pre-emption
7. Deadlock Prevention
   1. Requirements for deadlock: mutual exclusion, hold and wait, no pre-emption, circular wait
   2. Collective request policy
   3. Pre-emption
   4. Ordered request policy
8. Deadlock Avoidance
   1. Prevent system from ever entering an unsafe state
   2. Maximum claim graph
   3. Example: Banker's algorithm

Matt Bishop Office: 3059 Engineering Unit II Phone: +1 (530) 752-8060 Fax: +1 (530) 752-4767 Email: bishop@cs.ucdavis.edu

Copyright Matt Bishop, 2001. All federal and state copyrights reserved for all original material presented in this course through any medium, including lecture or print.