THE FOLD / BOSS / THE WALL / THE BANKER DEADLOCK
THE BANKER DEADLOCK
he can afford it and he refuses anyway
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Dijkstra’s banker will not lend you money he has, if lending it means he might later be unable to pay anyone in full. The resources are available. The request is legal. He refuses anyway.
LIT verified live. the classic five-process, three-resource state is safe, with the completion order P1, P3, P4, P0, P2 found by the algorithm. Enumerating every single request a process could legally make within its declared need gives 65 requests, and all 65 have enough free resources to be granted on the spot. Only 56 are safe. The remaining 9 — 13.8% — are requests the banker can afford and must still refuse, because granting them leaves a state from which some completion order no longer exists.
LIT verified live. the classic five-process, three-resource state is safe, with the completion order P1, P3, P4, P0, P2 found by the algorithm. Enumerating every single request a process could legally make within its declared need gives 65 requests, and all 65 have enough free resources to be granted on the spot. Only 56 are safe. The remaining 9 — 13.8% — are requests the banker can afford and must still refuse, because granting them leaves a state from which some completion order no longer exists.
2 HOW IT WAS WEAVED · AI + HUMAN
The banker’s algorithm is Dijkstra’s (1965), and the five-process instance is the one from Silberschatz.
AVAN (AI) enumerated the request space rather than showing the single textbook example, because one example makes the gap look like a curiosity. 65 requests are affordable and 9 of them are traps — availability and safety are genuinely different predicates, and the difference is not rare. The algorithm’s real cost is stated on the page rather than buried: every process must declare its maximum future need before it starts, which is information almost no real program has.
AVAN (AI) enumerated the request space rather than showing the single textbook example, because one example makes the gap look like a curiosity. 65 requests are affordable and 9 of them are traps — availability and safety are genuinely different predicates, and the difference is not rare. The algorithm’s real cost is stated on the page rather than buried: every process must declare its maximum future need before it starts, which is information almost no real program has.
3 ONE DIMENSION
65 affordable requests. Nine of them are traps.
4 TWO DIMENSIONS · INTERACTIVE
Try a request the banker can afford and watch him refuse.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that the banker prevents deadlock. The inverse is that he can only do it by demanding a promise nobody can keep. Safety here is computed from declared maxima, so the guarantee is exactly as good as the declarations — and a process that must state its worst-case need in advance will either overstate it, wasting the resources it reserved against a case that never comes, or understate it and void the proof. Read backwards, deadlock avoidance is not an algorithm problem, it is an information problem, and the algorithm is what you get once you assume the information away.
LIT the classic five-process three-resource state is safe, with the completion order P1, P3, P4, P0, P2 found by the algorithm; enumerating every request a process could legally make within its declared need gives 65 requests and ALL 65 have enough free resources to be granted on the spot, but only 56 are safe - the remaining 9, or 13.8%, are requests the banker can afford and must still refuse because granting them leaves a state from which some completion order no longer exists
FIG The banker's algorithm is Dijkstra's (1965) and the five-process instance is Silberschatz's. AVAN enumerated the request space rather than showing the single textbook example, because one example makes the gap look like a curiosity: 65 requests are affordable and 9 are traps, so availability and safety are genuinely different predicates and the difference is not rare. The real cost is stated on the page rather than buried - every process must declare its MAXIMUM future need before it starts, which is information almost no real program has.
FIG The banker's algorithm is Dijkstra's (1965) and the five-process instance is Silberschatz's. AVAN enumerated the request space rather than showing the single textbook example, because one example makes the gap look like a curiosity: 65 requests are affordable and 9 are traps, so availability and safety are genuinely different predicates and the difference is not rare. The real cost is stated on the page rather than buried - every process must declare its MAXIMUM future need before it starts, which is information almost no real program has.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN