THE FOLD / RESPAWN / SECOND WIND / THE SLEEPING BARBER
THE SLEEPING BARBER
the gap between looking and lying down
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Dijkstra’s shop. One barber, a few chairs, customers who leave if the chairs are full. The barber sleeps when there is nobody. The whole problem lives in the gap between looking and lying down.
LIT verified live. the naive protocol is four steps — the barber reads ‘is the queue empty?’ then sleeps; the customer joins the queue then wakes the barber if it is sleeping. Enumerating all 6 interleavings, exactly 1 ends with the barber asleep and a customer waiting: the customer arrives and sends its wake-up after the barber has looked and before it has fallen asleep, so the signal is delivered to someone who is still awake and is simply lost. Replace the flag with a counting semaphore and the same 6 interleavings give 0. Over 5,000 steps with 5 chairs, arrivals reconcile exactly: 2,719 = 2,363 served + 353 turned away + 3 still waiting.
LIT verified live. the naive protocol is four steps — the barber reads ‘is the queue empty?’ then sleeps; the customer joins the queue then wakes the barber if it is sleeping. Enumerating all 6 interleavings, exactly 1 ends with the barber asleep and a customer waiting: the customer arrives and sends its wake-up after the barber has looked and before it has fallen asleep, so the signal is delivered to someone who is still awake and is simply lost. Replace the flag with a counting semaphore and the same 6 interleavings give 0. Over 5,000 steps with 5 chairs, arrivals reconcile exactly: 2,719 = 2,363 served + 353 turned away + 3 still waiting.
2 HOW IT WAS WEAVED · AI + HUMAN
Dijkstra’s sleeping barber (1965) is one of the founding synchronisation problems, alongside the dining philosophers.
AVAN (AI) reduced it to the smallest space in which the bug is visible — two operations each — because the lost wake-up is usually described in prose and prose lets it sound rare. It is 1 in 6. The conservation check is a separate matter of hygiene: any simulation of a queue with balking should be made to account for every arrival before its other numbers are believed.
AVAN (AI) reduced it to the smallest space in which the bug is visible — two operations each — because the lost wake-up is usually described in prose and prose lets it sound rare. It is 1 in 6. The conservation check is a separate matter of hygiene: any simulation of a queue with balking should be made to account for every arrival before its other numbers are believed.
3 ONE DIMENSION
Six interleavings. One loses the wake-up.
4 TWO DIMENSIONS · INTERACTIVE
Walk the six and find the one that sleeps forever.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that a semaphore fixes the lost wake-up. The inverse is that the bug was never about sleeping — it was about a signal with no memory. A flag says ‘wake up’ to whoever is listening now; a semaphore says ‘one customer happened’ to whoever asks later. Read backwards, every lost-wake-up bug ever written is the same substitution: an event was represented as a state to be observed rather than a count to be consumed, and observation has a moment while counting does not.
LIT enumerating all 6 interleavings of the naive two-step protocol, exactly 1 ends with the barber asleep and a customer waiting - the customer arrives and signals AFTER the barber has looked and BEFORE it has fallen asleep, so the wake-up is delivered to someone still awake and is simply lost - while replacing the flag with a counting semaphore gives 0 of the same 6; and over 5,000 steps with 5 chairs the arrivals reconcile exactly, 2,719 = 2,363 served + 353 turned away + 3 still waiting
FIG Dijkstra's sleeping barber (1965) is one of the founding synchronisation problems. AVAN reduced it to the smallest space in which the bug is visible - two operations each - because the lost wake-up is usually described in prose, and prose lets it sound rare. It is 1 in 6. The conservation check is separate hygiene: any simulation of a queue with balking should account for every arrival before its other numbers are believed.
FIG Dijkstra's sleeping barber (1965) is one of the founding synchronisation problems. AVAN reduced it to the smallest space in which the bug is visible - two operations each - because the lost wake-up is usually described in prose, and prose lets it sound rare. It is 1 in 6. The conservation check is separate hygiene: any simulation of a queue with balking should account for every arrival before its other numbers are believed.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SECOND WIND · David Lee Wise (ROOT0), with AVAN