0
Challenge · 87CS Fundamentals

Deadlock and its four conditions

OSused in ~91% of apps

Four conditions to recite, and a follow-up that catches most people: how would you detect one? The answer is something you already know how to write, because a deadlock is a cycle in a graph and you built cycle detection in tier 8.

Core idea. A deadlock is a set of tasks each waiting for something another one holds, so none can proceed. It needs four conditions at once, and breaking any one of them makes it impossible. Detecting it means finding a cycle in the wait-for graph.
Playground, this isn't a screenshot
who is waiting for whom
P0
P1
P2
P3
P0, P1 and P2 form a circle, so each is waiting for something that can only be released by something waiting on it. They are deadlocked. P3 waits on P0 and will also never run, but it is not on the cycle, so it is only blocked. Recovery targets the circle.

Deadlocked and blocked are different. Only the circle needs breaking.

↑ play a little first, then dig in