Deadlock

1.	Types of resources

a.	serially reusable resource

b.	consumable resource

2.	Deadlock

3.	Approaches to solving the problem

a.	avoidance

b.	prevention

c.	detection and recovery

4.	System model

a.	states: process blocked, deadlocked; deadlock, safe states

b.	system: resource graph, with resource and process nodes, and request, assignment edges

c.	operations: request, acquire, release

5.	Graph theory

a.	sinks, isolated nodes

b.	cycles, reach, knot

6.	Deadlock detection with serially reusable resources

a.	Graph reduction

b.	Deadlock Theorem

c.	Cycle Theorem (general)

d.	Continuous deadlock detection: when do you have to look?

e.	Expedient states and the Knot Theorem

f.	Cycle Theorem (Single Unit Resources)

g.	Single unit requests in expedient states

7.	Deadlock recovery

a.	lowest termination cost first

b.	minimum cost recovery

c.	process pre-emption

8.	Deadlock prevention

a.	necessary and sufficient conditions

b.	collective request method

c.	pre-emption

d.	ordered request method

9.	Deadlock avoidance

a.	maximum claim graphs

b.	Banker's algorithm

10.	Consumable resources

a.	general properties

b.	known producers, unknown consumers: deadlock detection

c.	order of reductions

d.	theorems

e.	recovery

f.	known producers and known consumers

g.	claim-limited state

11.	General Resource Graph

a.	Results