THE FOLD / BOSS / THE-CHOKE-POINT / THE MCS LOCK
THE MCS LOCK
a lock that grants in arrival order
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The MCS lock is a fair, scalable spinlock built as a queue. A naive spinlock has every waiting thread hammering the same memory location, flooding the interconnect and granting the lock unpredictably. The MCS lock instead gives each thread its own little node: to acquire, a thread atomically swaps itself onto the tail of a queue and then spins only on its own flag; the thread ahead flips that flag on release. Because the tail swap is atomic, the queue order is exactly the arrival order, so the lock is granted first-come, first-served — no starvation — and each thread spins on a private, cache-local variable.
LIT verified live: over 20,000 random arrival interleavings, the grant order equals the atomic-swap (arrival) order — strict FIFO — and at most one thread ever holds the lock (window.__mcs_lock). FIG honest scope: this models the atomic tail-swap and the grant chain; real hardware adds memory-fence details.
LIT verified live: over 20,000 random arrival interleavings, the grant order equals the atomic-swap (arrival) order — strict FIFO — and at most one thread ever holds the lock (window.__mcs_lock). FIG honest scope: this models the atomic tail-swap and the grant chain; real hardware adds memory-fence details.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-choke-point — the single lock every thread must pass, but as an orderly queue where each waits on its own flag. AVAN (AI) built the instrument: the atomic tail-swap queue, the per-node spin flag, the release-to-successor chain, and the FIFO / mutual-exclusion checks.
Credit as content: John Mellor-Crummey & Michael Scott (1991). The weave: David names the choke point; I confirm the queue grants the lock in strict arrival order with never more than one holder.
Credit as content: John Mellor-Crummey & Michael Scott (1991). The weave: David names the choke point; I confirm the queue grants the lock in strict arrival order with never more than one holder.
3 ONE DIMENSION
Each thread swaps onto the tail and spins on its own flag; the predecessor flips it on release — a FIFO queue.
4 TWO DIMENSIONS · INTERACTIVE
Threads arrive in some interleaved order; the lock is granted strictly first-come, first-served, one at a time.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the lock passing down the queue in order.
AVAN’s addition (the inverse-companion): don’t spin on the shared lock — queue and spin on your own flag. The inverse of ‘everyone polls one location’ is ‘swap onto the tail; the arrival order IS the grant order, and each waits on a private flag.’ Magenta is a waiting thread; green is the current holder. Fairness from a queue.
LIT Genuine MCS queue lock (John Mellor-Crummey & Michael Scott, 1991). Verified live: over 20000 random arrival interleavings, the atomic-tail-swap queue grants the lock in exactly the arrival (swap) order — strict FIFO — with never more than one holder at a time (window.__mcs_lock.fifo, .mutex).
FIG Honest scope: this models the atomic tail-swap and the grant chain; real hardware adds memory-fence details. The AVAN inverse is honest — instead of every thread polling one shared lock, each swaps onto the tail and spins on its own private flag; the arrival order IS the grant order. Magenta is a waiting thread; green is the current holder. Fairness from a queue.
FIG Honest scope: this models the atomic tail-swap and the grant chain; real hardware adds memory-fence details. The AVAN inverse is honest — instead of every thread polling one shared lock, each swaps onto the tail and spins on its own private flag; the arrival order IS the grant order. Magenta is a waiting thread; green is the current holder. Fairness from a queue.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-CHOKE-POINT · David Lee Wise (ROOT0), with AVAN