11.1 How Locks Work
High-level interfaces hide two important mechanisms: locks reduce concurrency protocols to atomic operations and wait strategies, while dynamic allocators manage memory regions that are repeatedly split and merged. Their boundaries determine the real cost of synchronization and allocation.
Two threads incrementing an ordinary C counter without synchronization cause a data race; lost updates are only one possible symptom. Chapter 9 already provided the application-layer answer: shared mutable state requires synchronization. This chapter goes one level deeper, examining how locks use atomic operations, cache coherence, and kernel wait queues to transform "simultaneous entry" into "sequential passage."
This discussion focuses on the underlying implementation principles, not on encouraging developers to build their own locks in business logic. Production code should prefer pthread_mutex_t, Java Lock, or synchronization primitives provided by the language runtime. Mature implementations must also handle edge cases such as cancellation, process sharing, robustness, and priority inheritance.
1. Why Simple Read-Write Is Insufficient
The following code appears to check first, then acquire, but it actually has two critical flaws:
int locked = 0;
void lock(void) {
while (locked) {
}
locked = 1;
}First, "read 0" and "write 1" are two separate steps, meaning two threads could pass the check simultaneously. Second, in C, uncoordinated read and write operations on the same object by multiple threads result in data races, whose behavior is undefined. volatile can only constrain certain compiler optimizations and cannot merge the two steps into a single atomic operation, nor can it establish a proper memory ordering between threads.
A lock must accomplish at least two things:
- Perform an indivisible modification of the lock state to determine a single winner;
- Establish a correct causal ordering between the winner's operations in the critical section and the subsequent thread that acquires the lock.
The implementation below selects a winner with an atomic read-modify-write and establishes synchronization with acquire/release. This is its chosen protocol; not every mutual-exclusion algorithm requires CAS.
2. A Working C11 Spinlock
Save this GCC/Clang + POSIX example as spinlock.c. It reads the state first and attempts CAS when the lock appears available. It effectively illustrates the underlying principle, but lacks fairness, blocking wait mechanisms, and priority handling, making it unsuitable for direct replacement of pthread_mutex_t.
#include <pthread.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct {
_Atomic bool locked;
} spinlock_t;
#define SPINLOCK_INIT { false }
static inline void cpu_relax(void) {
#if defined(__x86_64__) || defined(__i386__)
__builtin_ia32_pause();
#elif defined(__aarch64__) || (defined(__arm__) && __ARM_ARCH >= 7)
__asm__ volatile("yield");
#else
atomic_signal_fence(memory_order_seq_cst);
#endif
}
static void spin_lock(spinlock_t *lock) {
for (;;) {
while (atomic_load_explicit(&lock->locked,
memory_order_relaxed)) {
cpu_relax();
}
bool expected = false;
if (atomic_compare_exchange_weak_explicit(
&lock->locked, &expected, true,
memory_order_acquire, memory_order_relaxed)) {
return;
}
}
}
static void spin_unlock(spinlock_t *lock) {
atomic_store_explicit(&lock->locked, false,
memory_order_release);
}
enum { THREADS = 4, INCREMENTS = 50000 };
static spinlock_t lock = SPINLOCK_INIT;
static long counter = 0;
static void *worker(void *unused) {
(void)unused;
for (int i = 0; i < INCREMENTS; ++i) {
spin_lock(&lock);
++counter;
spin_unlock(&lock);
}
return NULL;
}
int main(void) {
if (!atomic_is_lock_free(&lock.locked)) {
fputs("this demo requires lock-free atomic bool\n", stderr);
return EXIT_FAILURE;
}
pthread_t threads[THREADS];
for (int i = 0; i < THREADS; ++i) {
if (pthread_create(&threads[i], NULL, worker, NULL) != 0) {
return EXIT_FAILURE;
}
}
for (int i = 0; i < THREADS; ++i) {
if (pthread_join(threads[i], NULL) != 0) {
return EXIT_FAILURE;
}
}
printf("%ld\n", counter);
return counter == (long)THREADS * INCREMENTS
? EXIT_SUCCESS : EXIT_FAILURE;
}Compile and run:
cc -std=c17 -O2 -Wall -Wextra -Werror -pthread spinlock.c
./a.out
# 200000A successful CAS relies on memory_order_acquire: after acquiring the lock, the thread observes the writes completed by the previous holder before they released the lock. Unlocking is performed via memory_order_release, which pairs with the next successful acquire. Failed attempts do not require reading critical section data, so relaxed memory ordering is sufficient.
This relationship is more precise than simply "adding a memory barrier":
Thread A: modifies shared data
releases lock
│ synchronizes-with
▼
Thread B: acquires lock successfully
reads shared data3. TAS, TTAS, and Cache Coherence
A straightforward spinlock repeatedly performs test-and-set: each attempt is an atomic read-and-update. When the lock is held, many cores still continuously contend for the same cache line, generating substantial coherence traffic.
The implementation above follows the test-and-test-and-set (TTAS) approach:
- First, perform a regular atomic read to observe the current state;
- Only if the state indicates availability do threads attempt a CAS (compare-and-swap) to acquire the lock.
Polling loads can hit a local cache without repeatedly requesting exclusive ownership; the unlock write invalidates shared copies held by other cores. Thus, TTAS reduces hotspots but does not eliminate them. When many threads are competing, they may all wake up simultaneously at the moment of release, resulting in a "thundering herd" scenario.
Whether _Atomic bool is lock-free depends on the implementation; the example checks first. If an atomic operation uses an internal lock, it is not a model of pure spinning costs.
cpu_relax is not a synchronization primitive. Platform-specific pause or yield instructions merely signal to the processor that this is a waiting loop, which may improve power consumption or pipeline behavior; correctness still relies on atomic operations and memory ordering. ARM yield here is a processor hint, not a request to yield the CPU to the OS scheduler. The atomic_signal_fence fallback does not emit a hardware waiting instruction.
4. When Is Spinning Worth It?
The bet behind spinning is that the lock will be released quickly and the holder is already running on another processor. However, several scenarios can make this bet risky:
- The critical section includes I/O operations, page faults, or other potentially blocking actions;
- The number of runnable threads exceeds the number of processors, meaning the thread holding the lock may have been descheduled;
- Lock contention continues to rise;
- The CPU time allocated to the virtual machine or container is unstable;
- Real-time tasks are blocked by lower-priority threads holding the lock.
The claim that "the critical section is only a few lines" does not prove that spinning is appropriate. A single cache miss or page fault can dramatically change the outcome. Whether to use spinning should be determined by actual performance metrics on the target machine, specifically, contention rates, wait times, and CPU consumption.
Operating system kernels can use spinlocks under controlled conditions such as disabled preemption. General-purpose applications lack these guarantees, making mutexes generally more reliable. Many mutex implementations include adaptive, brief spinning as part of their internal strategy, but this is an implementation detail, not a promise of the API.
5. The Fast and Slow Paths of a Mutex
A common mutex structure can be summarized as two paths:
Atomic operation detects unlocked state ── success ──> Enter critical section
│
failure
▼
Record contention state → Join waiting queue → Suspended by kernel
│
Unlocker wakes one or more waiters <──┘When there's no contention, lock acquisition and release may involve only user-space atomic operations. A contended slow path may enter a kernel waiting queue, possibly after brief spinning. Specific state bits, queue structures, spin count, and wake-up strategies are determined jointly by libc, the JVM, and the operating system, these should not be relied upon by application code.
What Linux futex Solves
The traditional Linux futex interface connects a 32-bit user-space integer, aligned to four bytes, with kernel waiting. The _Atomic bool address above is not a suitable futex word. Two key operations are:
FUTEX_WAIT: Only sleeps if the integer still matches the expected value provided by the caller;FUTEX_WAKE: Wakes up threads waiting at that address.
The atomic compare-and-block protocol closes a critical race: after a waiter decides to sleep, before actually enqueuing, the lock might have already been released. If the integer has changed, FUTEX_WAIT will not continue sleeping.
Conceptually, the waiting loop looks like this:
while (unable to atomically acquire lock):
Update state to "contention detected"
futex_wait(state_address, expected_contention_value)
# After being woken, signaled, or experiencing spurious wake-up, recheck conditionsWaking does not immediately hand the lock to a thread. The awakened thread must recontest the lock, so waiting must occur within a condition-based loop. An ordinary load followed by sleep does not provide the atomic comparison and enqueueing supplied by futex. A custom mutex can easily miss wakeups, state transitions, or lifetime rules; production code should use a mature implementation.
Java's AbstractQueuedSynchronizer also ties atomic state with a waiting queue, with LockSupport.park/unpark responsible for blocking and waking. However, it is part of the JVM-level synchronization framework, not a simple alias for futex. Whether the underlying implementation uses futex depends on the platform and JVM implementation.
6. Fairness Is Not Free
The TTAS spinlock allows newly arrived threads to preempt longer-waiting ones, potentially leading to starvation. For more stable ordering, alternative structures can be considered:
| Structure | Waiting Mechanism | Primary Cost |
|---|---|---|
| Ticket lock | Each thread takes a number and waits for its own turn | All waiting threads continuously poll the same ticket value |
| MCS lock | Each thread waits on its own queue node | Requires managing queue nodes, resulting in a more complex path |
| Queue mutex | Competitors enter a waiting queue | May involve kernel context switches and wakeups |
| Unfair mutex | After release, any thread may re-try | Throughput can be higher, but tail latency remains unstable |
Fairness helps prevent front-running but may reduce throughput. For instance, when a lock is released, allowing the thread currently running on CPU to acquire it may be cheaper than waking up the head of the waiting queue. Whether to prioritize average throughput, tail latency, or strict ordering is a design choice in synchronization primitives.
A more serious issue is priority inversion: a high-priority thread waits for a low-priority thread holding the lock, while medium-priority threads continuously occupy the CPU. Real-time systems may require mutexes with priority inheritance; standard spinlocks cannot provide this capability.
7. Read-Write Locks and the Boundary of Lock-Free Reads
Read-write locks allow multiple readers to access data concurrently, but they are not inherently faster. The reader counter itself introduces a shared write hotspot, and writers may remain indefinitely waiting for their turn. When reads are very short, the system has many concurrent readers, or writes are frequent, a simple mutex can actually perform better.
Version-based seqlocks are suitable for specific scenarios where readers can retry and writes are rare. Correct usage requires copying data into a private snapshot and verifying the sequence number before and after the copy. Returning a mutable pointer to the original shared object after verification is unsafe, because writers may still modify it afterward. If copying conflicts with a non-atomic writer, ordinary C accesses already cause a data race. Discovering a changed version afterward and retrying cannot undo undefined behavior. Solve object lifetime, language-valid access, and memory reclamation first.
Thus, "optimism" is not about omitting synchronization; it's about transforming synchronization into verification, retry logic, and safe cleanup.
8. Selection and Debugging
When dealing with shared hotspots, consider these questions in sequence:
- Can shared state be eliminated, such as thread-local state, sharded counters, or message passing?
- Can the critical section be shortened, and can I/O operations be moved outside the lock?
- Is there actually a benefit from parallel reads that justifies the use of a read-write lock?
- When contention occurs, should threads spin on the CPU or yield and sleep?
- Are fairness, cancellation, timeouts, and priority requirements part of the actual specification?
- Is the performance bottleneck due to the lock itself, or is it caused by cache line contention on the data protected by the lock?
During measurement, observe at least throughput, wait time distribution, CPU utilization, and context switches. Reporting only "how many nanoseconds per lock acquisition" often masks the true nature of contention in real workloads.
9. Summary
This TTAS implementation depends on several layers:
- Atomic read-modify-write operations identify the sole holder;
- acquire/release operations ensure that data within a critical section becomes visible as expected;
- TTAS reduces cache contention caused by continuous atomic writes, but cannot eliminate competition;
- futex allows contention-free paths to remain in user space, enabling competing threads to sleep in the kernel;
- achieving fairness, low latency, low CPU usage, and high throughput simultaneously is extremely difficult.
The lock object itself requires memory. The next section turns to dynamic memory allocators: how they partition free blocks, manage fragmentation, and prevent all threads from competing for a single heap lock. A more complete treatment of C atomic semantics will be explored in Chapter 16: C and Memory Models.