Deadlock

Deadlock is a standoff where a set of processes are stuck *forever*: each one holds a resource that another in the set is waiting for, arranged in a closed circle. Nobody can move, nobody will give up what they already hold, so the whole group freezes. The operating system can model the situation as a resource-allocation graph — and when resources have a single instance, a deadlock shows up as a literal cycle in that graph.

The four Coffman conditions

Deadlock is only possible when all four of these hold at the same time. They were catalogued by Edward Coffman in 1971, and removing any single one of them makes deadlock impossible.

1. 1Mutual exclusion — at least one resource is non-shareable: only one process can hold it at a time.
2. 2Hold and wait — a process keeps the resources it already has while waiting to acquire more.
3. 3No preemption — a resource can't be forcibly taken away; it's released only voluntarily by the process holding it.
4. 4Circular wait — there's a closed chain of processes, each waiting for a resource held by the next one in the chain.

Worked example — two locks, opposite order

The simplest real deadlock: two threads each grab one lock, then reach for the other — in the opposite order.

// Thread A              // Thread B
lock(R1);                lock(R2);
lock(R2);  // blocks      lock(R1);  // blocks
  ...                       ...
unlock(R2);              unlock(R1);
unlock(R1);              unlock(R2);

Thread A holds R1 and waits for R2; thread B holds R2 and waits for R1. In the resource-allocation graph that's a cycle A -> R2 -> B -> R1 -> A. All four Coffman conditions hold, so neither thread will ever proceed.