THE FOLD / CO-OP / SHARED-MEMORY / THE TICKET LOCK
THE TICKET LOCK
a deli-counter lock served in ticket order
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The ticket lock is a fair spinlock built like a deli counter. Two shared numbers: the next ticket to hand out and the ticket now serving. To acquire, a thread atomically takes the next ticket (fetch-and-increment) and then spins until “now serving” equals its own number. To release, it just increments “now serving,” waking exactly the next thread in line. Because the ticket draw is atomic, the order of tickets is the order of arrival, so the lock is granted strictly first-come, first-served — no starvation, no thundering herd, just a queue made of two counters.
LIT verified live: over 20,000 random arrival interleavings, the lock is granted in ascending ticket order (exactly the arrival order — FIFO), and never more than one thread holds it at once (window.__ticket_lock). FIG honest scope: this models the atomic ticket draw and the serve counter; real hardware adds memory-fence and back-off details.
LIT verified live: over 20,000 random arrival interleavings, the lock is granted in ascending ticket order (exactly the arrival order — FIFO), and never more than one thread holds it at once (window.__ticket_lock). FIG honest scope: this models the atomic ticket draw and the serve counter; real hardware adds memory-fence and back-off details.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at shared-memory — two shared counters turn a lock into an orderly queue, each thread waiting for its number to come up. AVAN (AI) built the instrument: the atomic ticket draw, the serve counter, and the FIFO / mutual-exclusion checks.
Credit as content: the ticket lock (Mellor-Crummey & Scott lineage; a classic fair spinlock). The weave: David names shared memory; I confirm the lock is granted in strict ticket (arrival) order with one holder at a time.
Credit as content: the ticket lock (Mellor-Crummey & Scott lineage; a classic fair spinlock). The weave: David names shared memory; I confirm the lock is granted in strict ticket (arrival) order with one holder at a time.
3 ONE DIMENSION
Take a ticket (next++); spin until now-serving == your ticket; release by now-serving++ — a deli-counter queue.
4 TWO DIMENSIONS · INTERACTIVE
Threads take tickets in some interleaved order; the lock is granted strictly in ticket order, one at a time.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the lock passing down the ticket queue in order.
AVAN’s addition (the inverse-companion): don’t let threads race for the lock — number them. The inverse of ‘everyone grabs at once’ is ‘take a ticket; the draw order is the serve order; spin on your own number.’ Magenta is a waiting ticket-holder; green is the one now served. Fairness from two counters.
LIT Genuine ticket lock (a classic fair spinlock; Mellor-Crummey & Scott lineage). Verified live: over 20000 random arrival interleavings, the atomic ticket draw (fetch-and-increment) makes the grant order equal the ascending ticket = arrival order — strict FIFO — with never more than one holder (window.__ticket_lock.fifo, .mutex).
FIG Honest scope: this models the atomic ticket draw and the serve counter; real hardware adds memory-fence and back-off details. The AVAN inverse is honest — instead of threads racing for one lock, each takes a ticket: the draw order is the serve order, and each spins on its own number. Magenta is a waiting ticket-holder; green is the one now served. Fairness from two counters.
FIG Honest scope: this models the atomic ticket draw and the serve counter; real hardware adds memory-fence and back-off details. The AVAN inverse is honest — instead of threads racing for one lock, each takes a ticket: the draw order is the serve order, and each spins on its own number. Magenta is a waiting ticket-holder; green is the one now served. Fairness from two counters.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SHARED-MEMORY · David Lee Wise (ROOT0), with AVAN