18. Deadlock — Avoidance, Prevention, Detection

Four Coffman conditions (all must hold for deadlock): mutual exclusion, hold-and-wait, no preemption, circular wait. Break any one → no deadlock.

1. Prevention — design so one condition can never hold:

• Break mutual exclusion: make resources shareable (rarely possible).
• Break hold-and-wait: request all resources upfront, or release everything before requesting more.
• Break no-preemption: allow forcible resource takeaway (only works for state-saveable resources).
• Break circular wait (most practical): assign a global lock order and always acquire in increasing order.

2. Avoidance — dynamically check each request; grant only if the system stays in a safe state (a sequence exists where all threads can finish). Banker's Algorithm does this via Max/Allocation/Need matrices, but requires threads to declare max needs upfront and has high runtime overhead — real OSes rarely use it.

3. Detection and recovery — let deadlocks happen, detect periodically, recover. Single-instance resources: build a Resource Allocation Graph and check for cycles. Multi-instance: an algorithm like Banker's but using a Request matrix (actual outstanding requests) rather than a pessimistic Need matrix. Recovery: kill process(es), or preempt resources from a victim (risking starvation without an aging factor).

Livelock vs deadlock vs starvation: deadlock = waiting forever, doing nothing; livelock = actively running but making no progress (two people stepping aside for each other in a hallway, forever); starvation = never getting CPU/resource because higher-priority work keeps cutting in.

What real systems do: Linux/Windows mostly use the Ostrich Algorithm — ignore it, rely on developer lock ordering. Databases lean on detection + rollback. RTOSes enforce strict lock ordering and priority inheritance.

---