How Atomic Operations Implement Fair Locks: From Spin Locks to Ticket Locks

From spin locks to ticket locks: how atomic operations achieve fairness while balancing performance and policy complexity.
Using a deli ticket system as an analogy, the article explains fairness issues in concurrent locks. Spin locks rely on compare-and-swap and are simple but unfair, potentially causing starvation. With atomic addition, ticket locks use "next ticket" and "now serving" counters to guarantee first-come, first-served and eliminate starvation. Yet fairness has costs: timeout handling is complex, and mixed long/short tasks can cause priority inversion. High-performance scenarios can use fast-path checks and double-checked locking to reduce overhead, but memory visibility must be handled carefully. Spin locks continuously consume CPU and suit very short critical sections, while long waits should use blocking locks. The core conclusion is that atomic operations are the cornerstone of concurrency primitives, and trade-offs among fairness, performance, and policy complexity always exist.
In concurrent programming, mutexes are a fundamental tool for ensuring data safety, but not all locks are fair. A Computerphile video uses the analogy of a deli ticket system to explain in accessible terms how atomic operations can build fairer locking mechanisms, and explores the trade-off between performance and fairness.
The Fairness Dilemma of Spin Locks
The mutex implementation introduced in the previous episode is the spin lock. It works simply: a thread keeps trying to acquire the lock until it succeeds. The problem with this kind of lock is that it is unfair. The video uses a vivid analogy: 20 people simultaneously try to open a restroom door, each constantly jiggling the handle. If one of them is slightly slower or simply unlucky, he may never beat those who "count to 9" before trying, ultimately leading to starvation.
The spin lock implementation relies on an atomic operation provided by the hardware: compare-and-swap. A thread can atomically write a value (say 1) into a memory cell and retrieve the old value (say 0), with no other thread able to interleave during the process. This is enough to build a basic spin lock, but it cannot guarantee the order of waiting.

Starvation refers to a state in which a thread cannot make progress because it is unable to obtain the required resource for a long time. Unlike deadlock, the system as a whole is still running; only individual threads are indefinitely postponed. In an unfair lock, newly arriving threads may continually "cut in line," causing earlier waiting threads to never acquire the lock. Besides starvation, unfair locks can also cause the convoy effect: after one thread releases the lock, a large number of threads contend simultaneously, causing a surge in context-switching and cache-invalidation overhead. Fair locks alleviate these problems by enforcing queuing, but they also reduce throughput, because thread switching and wake-ups incur additional overhead, and newly arriving threads cannot exploit the window when "the lock happens to be free" to acquire it directly.
Ticket Locks: Achieving Fairness with Atomic Increment
To achieve fairness, we need a little more capability from the hardware: atomic addition. The video explains that instead of merely replacing a value in memory, we perform a simple arithmetic operation on the memory cell, such as adding one. This way, a thread can atomically increment a memory location and know the value before the increment.
This small extension gives rise to the ticket lock. Its core idea borrows from the deli ticket system: customers take a number from the dispenser and then wait for their number to be called. In a computer, there are two counters:
- Next ticket: a newly arriving thread atomically increments this counter and obtains its own ticket number.
- Now serving: when the thread currently holding the lock finishes its work, it increments this counter to notify the thread with the next ticket number that it may enter.
The video demonstrates the specific process: initially both counters are 0. The first thread performs an atomic add-one, obtaining the old value 0, so its ticket number is 0, and the next ticket becomes 1. It checks whether now serving is 0; if so, it acquires the lock. When releasing the lock, it increments now serving to 1, so the thread with ticket number 1 can proceed.

This mechanism guarantees first-come, first-served: each thread has a unique ticket number and acquires the lock strictly in ticket order, so starvation cannot occur. The video emphasizes that this achieves fairness merely by adding an atomic addition operation.
Atomic addition (also called fetch-and-add) is a hardware primitive that completes the three steps of "read the old value, add the increment, write back the new value" within a single instruction, without interruption by other threads. Unlike compare-and-swap, atomic addition is naturally suited to implementing queuing: each thread calls it once and obtains a globally unique increasing sequence number, with the call order matching the sequence order. On x86 architectures this is typically implemented by the LOCK XADD instruction; on ARM it is done through LDXR/STXR loops or atomic instructions such as LDADD. It is precisely this "take a number, join the queue" semantics that enables ticket locks to guarantee first-come, first-served without any additional synchronization.
The Cost of Fairness: Timeouts and Complex Policies
Ticket locks are not perfect. The video points out that if a thread takes a number but fails to check the "now serving" counter in time (for example, it goes "shopping"), the entire queue is blocked. In reality, a deli would skip an absent customer, but handling timeouts in a computer is very complex: if a thread that has waited too long is allowed to forcibly acquire the lock, then the skipped thread may cause conflicts when it returns, requiring complex coordination mechanisms.
In addition, ticket locks assume that all tasks take similar amounts of time. The video mentions that if long and short tasks are mixed, a priority inversion problem may arise: a low-priority long task holds the lock while a high-priority task can only wait. This is a policy-level issue, not a safety issue of the atomic operation primitives themselves.

Priority inversion refers to a high-priority task being blocked because it waits for a lock held by a low-priority task, while the low-priority task may in turn be preempted by a medium-priority task, causing the high-priority task's actual waiting time to far exceed expectations. The classic case is the 1997 Mars Pathfinder mission, in which a high-priority information bus task was blocked by a low-priority communications task, which was in turn preempted by a medium-priority weather task, ultimately triggering a system reset. Common mitigation methods include priority inheritance (the low-priority task holding the lock is temporarily boosted to high priority) and priority ceiling (the lock is boosted to the highest priority of any task that may access it when acquired). These mechanisms belong to the scheduling policy level and are orthogonal to lock fairness, but under mixed task loads they must be considered together with fair mechanisms such as ticket locks.
Performance Optimization: Fast Paths and Optimistic Checks
The video finally discusses optimization techniques in high-performance scenarios. A common pattern is the fast-path check: before actually acquiring the lock, first check whether the condition is already satisfied. For example, when initializing a database connection, if the connection has already been established, a thread can use it directly without acquiring the lock; only when the connection does not exist does it take the slow path of locking.
This optimization requires careful handling of double-checked locking: a thread checks without the lock and finds the connection absent, and after acquiring the lock it must check again, because another thread may have established the connection in the meantime. The video warns that this pattern is error-prone, but sometimes it must be adopted for performance.

Another noteworthy point is the CPU overhead of spin locks. A thread spinning continuously occupies the CPU performing meaningless checks; the video describes this as constantly knocking on the door and asking "Are you done yet?", which is both annoying and resource-consuming. Therefore, spin locks are suitable for scenarios with extremely short critical sections, while longer waits should use blocking locks.
Double-checked locking became well known in languages such as Java due to memory visibility issues: the object reference read by a thread without the lock may be non-null, but the object has not yet completed initialization, so a partially constructed object is used. The fix is usually to declare the shared variable as volatile (or use a type with acquire/release semantics such as std::atomic), ensuring that the initialization write happens before the reference is published. The database connection scenario mentioned in the video is a typical application of this pattern: the first check avoids locking overhead, the second check after locking prevents duplicate initialization, and correct memory ordering is the prerequisite for the pattern's safety.
Conclusion
Atomic operations are the cornerstone of building concurrency primitives. From simple compare-and-swap to atomic addition, a small hardware enhancement enables the leap from unfair spin locks to fair ticket locks. However, the trade-offs among fairness, performance, and policy complexity always exist, and understanding these low-level mechanisms helps make more reasonable choices in practical development.
Related articles

Gemini 4 Hydrogen Hands-On: Google's Fastest and Cheapest AI Model
Hands-on with Gemini 4 Hydrogen: the fastest, cheapest model in the Gemini 4 family. We break down the Carbon/Argon/Hydrogen split, API pricing traps, free-tier limits, and the cost trade-offs of four thinking levels—with a real bug-debugging demo.

Gemini 4 Hydrogen vs Sonnet Comparison Test: Uses Only 1% of Weekly Quota, Performance on Par
Hands-on test: Gemini 4 Hydrogen vs Sonnet on the same CRUD task—Hydrogen used only 1% weekly quota with comparable performance and better UI details, while Anthropic's model used 7%. Developer says daily tasks don't require expensive models.

Gemini 4 Neon Released: Beats Opus 5.5 on Multiple Benchmarks, Google Returns to the Top Tier
Google DeepMind releases Gemini 4 Neon: 61 on the Artificial Analysis intelligence index (3rd) and 1st on the coding index, beating Opus 5.5 on multiple benchmarks. $3/$15 per million tokens; available in the Gemini API and AI Studio.