The Ticket Lock
A plain spinlock has a fairness problem. When the lock is released, any waiting thread can grab it, and an unlucky thread may be repeatedly beaten to it and starve. The ticket lock solves this with the deli counter trick.
The lock holds two numbers, a next ticket value and a now serving value. To acquire, a thread atomically takes a ticket by fetching and incrementing next ticket. It then spins until now serving equals its ticket. To release, the holder simply increments now serving, which hands the lock to the thread holding the very next number.
- Fair Threads are served strictly in arrival order, so no one starves.
- First in first out The two counters encode a queue without any list structure.
- Still spinning Waiters busy wait, so this is a fairness improvement, not a sleeping lock.
The cost is that every waiter spins on the same now serving variable, so a release invalidates that cache line on every core. More advanced queue locks spread waiters onto separate locations to cut this traffic, but the ticket lock remains a clean illustration of guaranteed fairness.
Key idea
A ticket lock assigns each waiter an increasing number and serves them in order, guaranteeing fairness so no thread starves.