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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
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