The four Coffman conditions

Aisha's build finishes. The editor wants to open matrix to check the output, so it locks build.log first to record what it did.

At the same moment the compile job wants to append one last line to build.log. It already holds matrix, because it just wrote it.

The editor waits for matrix. The compile job waits for build.log.

Neither is broken. Neither is using any CPU. Aisha's fan goes quiet, her laptop looks completely idle, and nothing will ever happen again.

Why & what

The definition. A deadlock is a set of processes where every one of them is waiting for something that only another process in the same set can release.

Contrast it with starvation from Topic 3.4, because interviews test this constantly:

• Starvation: the process could run, but is never picked. Change the conditions and it runs.
• Deadlock: the process cannot run, ever. Nothing will change on its own.

The four conditions. A deadlock needs all four of these to be true at the same time. They are named after Edward Coffman, and you should be able to list them.

• Mutual exclusion — the resource can be held by only one process at a time. If build.log could be shared freely, nobody would wait.
• Hold and wait — a process keeps what it already holds while asking for more. The editor does not release build.log while it waits for matrix.
• No preemption — the resource cannot be taken away. Only the holder can release it, voluntarily.
• Circular wait — there is a closed loop of processes, each waiting for the next. Here it is a loop of two, but it can be any length.

Why "all four" matters so much. This is not a checklist for describing a deadlock. It is the design of every solution in Topic 5.3.

If a deadlock needs all four to be true, then making any single one of them impossible makes deadlock impossible. Break one condition, and you are done.

How it works

Tracing our two processes:

1. The compile job finishes writing matrix and still holds it.
2. The editor locks build.log to record the build result.
3. The editor requests matrix. It is held, so the editor goes to Waiting — still holding build.log. That is hold and wait.
4. The compile job requests build.log. It is held, so it also goes to Waiting — still holding matrix. The loop is now closed.
5. Nothing else can change either fact. No timer will fire, no interrupt will help. Both sit in Waiting forever.

Common confusion

"A deadlocked process is stuck in a loop burning CPU." The opposite. Both processes are in the Waiting state from Topic 2.2, so they use no CPU at all. A deadlocked system can look perfectly healthy in a task manager — quiet, cool, nothing pinned at 100%. That is exactly what makes deadlocks hard to notice.

"Deadlock needs at least two resources." It needs at least two resources and at least two processes. One process cannot deadlock against itself, unless it tries to lock the same non-reentrant lock twice, which is a related bug with its own name.

"All four conditions cause a deadlock." They are necessary, not sufficient. All four can be true right now on the Nova-14 without any deadlock existing. They describe the conditions under which one becomes possible.

Interview angle

"What are the four necessary conditions for deadlock?" List them, one line each. This is close to pure recall and it comes up constantly. A memory hook that works: M-H-N-C — Mutual exclusion, Hold and wait, No preemption, Circular wait.

"Difference between deadlock and starvation?" Answer with what would fix it. A starved process runs as soon as conditions change; a deadlocked process never runs no matter what happens.