Deadlocks, jigsaws, and philosophers

A deadlock happens when at least two process try to access the same resource, but can't, until the other one frees up their resource.

Imagine each of them holding a jigsaw piece, but none of them can finish, until the other one voluntary put their own peace down.

Another metaphor for this would be the philosopher's problem. Imagine a philosopher which only knows three states of being which are thinking, eating and sleeping. If the philosopher wants to eat, but can't because he is missing a fork, he immediately falls asleep. A philosopher can only be woken up by another philosopher.

And now imagine a scenario in which these steps (thinking, eating, and sleeping) happen in such an order that all philosophers are asleep; nobody can wake the other ones up and they sleep forever. We got a deadlock.

Coffman's four deadlock conditions

1. Mutual Exclusion: At least one resource has to be held in a non-shareable state.
2. Hold on wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.
3. No preemption: Resources can not be taken by force; they must be released voluntarily.
4. Circular wait: A circular chain of processes exists, where each process is waiting for a resource held by the next process in the chain.

Recognizing a deadlock

We can use a Resource Allocation Graph to recognize such circular wait conditions.