This is the central lesson of the module. We have spent three lessons leaving asterisks behind: a counter++ that loses increments, an n_latest++ in /dev/shm/meteora-cache that does the same between processes, a 24-byte struct Reading that can be read half-written. We know what a critical section is and what three requirements a solution must meet. We know how to set up the channel between processes. What we still do not have is the protocol that prevents two flows from entering at once.

Here we build it from the bottom up, because it is the only way to understand why the primitives are the way they are. We will start by trying to solve it with ordinary variables alone — failing in three different ways, each instructive; we will see why the problem is unsolvable without help from the hardware; we will meet the atomic instructions the CPU offers for this; and on top of them we will build spinlocks, mutexes, semaphores, condition variables, read/write locks and barriers. We will finish by looking at how Linux implements it with futex, why volatile is no use for any of this, and how much contention really costs in measured microseconds.

1. The critical section problem, formalized
2. Naive attempts that fail
3. Peterson's solution and its real limits
4. Hardware support: test-and-set and compare-and-swap
5. An atomic counter for meteo-api
6. Busy waiting and spinlocks
7. Blocking with suspension and the scheduler's role
8. POSIX mutexes: Meteora's counter fixed
9. Counting and binary semaphores
10. Condition variables and monitors
11. Read/write locks and barriers
12. How Linux implements it: futex
13. Memory barriers and why volatile is no use
14. Lock granularity and the cost of contention

Let us restate the setup precisely. We have n flows repeating the cycle enter(); critical_section(); leave(); remainder();, and we have to design enter() and leave() so that the three requirements from Concurrency Concepts are met:

1. Mutual exclusion: never two flows inside the critical section at once.
2. Progress: if it is free and somebody wants to enter, the decision is not postponed indefinitely, and those in remainder() do not take part in it.
3. Bounded waiting: there is a limit to the number of times others get in before your turn comes.

And two assumptions that cannot be violated: nothing can be assumed about the relative speed of the flows (one can be a thousand times faster, or sit still for a whole second because the scheduler preempted it) nor about the number of cores. We are going to try to solve it with what we have — ordinary shared variables — failing three times; each failure teaches something we will need later.

The most natural idea: a variable busy that I set to 1 while I am inside.

It fails mutual exclusion, the most important requirement. The trace: at t1 thread A reads busy → 0 and leaves the while; at t2 the scheduler preempts it before it writes, and B reads busy → 0 and also leaves; at t3 B writes busy = 1 and enters; at t4 A writes busy = 1 and enters too.

Both inside. The reason is the one we already know: checking and acting are two separate operations, with a window between them. It is 03-01's check-then-act applied to the lock itself, and the irony is notable: the mechanism meant to protect a critical section itself contains an unprotected critical section. That is the underlying reason the problem is unsolvable with ordinary reads and writes: we need to check and modify in a single indivisible step, and no C variable gives us that.

Let us alternate rigorously, with a variable that says whose turn it is:

Now there is mutual exclusion: turn has a single value, so only one gets past the while, and since writing an aligned int is atomic there is no window at all. But it fails progress, and seriously. If thread A leaves its critical section setting turn = 1, and thread B decides never to enter again because it is busy in remainder(), then B will never set turn = 0 and A waits forever with the critical section free. This directly violates the clause saying that a flow in remainder() must not take part in the decision. And in practice it is a performance disaster: if A enters a thousand times per second and B once a minute, A is limited to one entry per minute. Strict alternation imposes the pace of the slowest on everybody.

Let us separate "I want to enter" from "I am inside", with one flag per thread:

Now there is mutual exclusion (if both were inside, each would have had to see the other's flag at 0 after setting its own to 1, which is impossible) and there is progress against an idle thread. But it fails in a new and worse way: if A sets wants[0] = 1 and, before reaching its while, B sets wants[1] = 1, then both enter their waiting loop and neither ever leaves it. Each waits for the other to give up, and neither gives up because it is blocked waiting. It is a deadlock, the subject of Deadlocks, manufactured here in five lines.

A tempting variant is "if I see the other one also wants in, I withdraw my flag for a moment and retry". That avoids the deadlock but introduces a livelock: the two can withdraw and restore their flags in lockstep forever, each politely giving way to the other without either making progress. It is the computing version of two people meeting in a corridor and stepping aside to the same side over and over. Summary of the three attempts:

Gary Peterson published in 1981 the most elegant solution to the problem for two flows, combining the two previous ideas: the flags say who wants to enter, and the turn breaks the tie.

Line (2) is the brilliant one, and it is counterintuitive: I hand the turn to the other precisely when I want to enter. Why it works, requirement by requirement:

Mutual exclusion. For both to be inside, both would have left the while. A leaves if wants[B] == 0 or if turn == A; B leaves if wants[A] == 0 or if turn == B. If both are inside, both set their flag to 1, so the first two conditions are false and we would need turn == A and turn == B at the same time: impossible, because turn is a single variable. Contradiction. Progress. If B does not want to enter, its flag is 0 and A goes straight through; if both want to, turn has a single value and one of the two gets through. Bounded waiting. When A leaves and wants to come back in, it sets turn = B, so if B was waiting, it now gets through: A can overtake B at most once, the best possible bound.

If you swapped lines (1) and (2) the solution would stop being correct. And if both execute (2) almost at the same time, the second one to write wins the tiebreak — its write to turn is the one that stands — and the first one gets through: a tiebreak that resolves itself, with no compound atomic operation at all.

Peterson is a beautiful theoretical result that in practice is never used, for three reasons that explain everything that follows. It only works for two threads: there is a generalization to n — the filter algorithm, or Lamport's bakery algorithm — but it requires n waiting steps and arrays of size n, so it does not scale. It is pure busy waiting: that while (...) ; burns a whole core, which is catastrophic with more threads than cores, because the waiter consumes its quantum without progressing while the holder of the lock cannot run.

And the third, the decisive reason: memory reordering. Peterson is correct over a sequentially consistent memory model, in which every core sees the writes in the same order. No modern processor satisfies that. On x86-64 a write goes first through the core's store buffer before becoming visible to the rest, and the processor can move a later read ahead of an earlier write to a different address. In the code above, the processor can execute the read of wants[other] before the write of wants[me] has left the store buffer and become visible to the other thread. If both do the same symmetrically, both read the other's flag as 0 and both enter. Mutual exclusion breaks, not because the algorithm is faulty, but because the hardware does not execute what the code says, but something equivalent for a single thread.

For Peterson to work on real hardware you have to insert an explicit barrier, __atomic_thread_fence(__ATOMIC_SEQ_CST);, between the write of turn and the waiting loop. And that line is the doorway to everything that follows: correct synchronization needs hardware support, writing clever code is not enough. We will come back to memory barriers in section 13.

The underlying problem in all the attempts was the same: checking and modifying are two operations and there is a window between them. The solution is for the processor to offer an instruction that does both indivisibly, and every modern architecture has one, in two variants.

CAS is strictly more powerful than test-and-set and it is the primitive practically everything is built on. On x86-64 it is implemented with lock cmpxchg; the lock prefix is what works the magic: for the duration of that instruction, the core holds the cache line in the exclusive state and no other core can modify it.

In C11 there is no need to write assembly: GCC and Clang offer the __atomic_* functions and the standard defines <stdatomic.h>:

This does satisfy mutual exclusion, with no tricks or manual barriers, and for any number of threads: the loop retries while somebody else holds the lock, and as soon as it is released a CAS succeeds and only one wins, because the comparison and the write are indivisible.

Two details of C11's CAS that confuse people the first time. atomic_compare_exchange_weak modifies expected when it fails, leaving in it the actual value it found, and that is why it has to be reset to 0 inside the loop; the _strong version cannot fail spuriously but is slightly slower on some architectures, so in a retry loop always use _weak. And there is atomic_flag_test_and_set, the test-and-set primitive, guaranteed to be lock-free on every platform.

Comparing the two: both work for locks and both cost the same (~20 ns with no contention, ~500 ns with 8 cores fighting over it), but only CAS works for lock-free counters, stacks and queues, because it can make the write conditional on the previous value. In exchange, CAS drags along the well-known ABA problem in structures with pointers. Those 20 nanoseconds against the ~1 ns of a normal write are the price of atomicity: the instruction negotiates exclusive ownership of the cache line with the other cores through the coherence protocol. 20 times more expensive than a normal write, and that number is the reason for the whole of section 14 on granularity.

With this we can now fix the module's first asterisk: total_requests++ in /dev/shm/meteora-cache.

Three things to learn from this example.

atomic_fetch_add is the operation we needed: read-add-write indivisibly, in a single instruction (lock xadd on x86-64). There is no longer a window between the read and the write, and therefore no lost increments. Ever.

memory_order_relaxed is a deliberate optimization and it is correct here. By default, C11's atomic operations use memory_order_seq_cst, which as well as being atomic imposes a global order among all the operations of all the threads, forcing expensive barriers. For a statistics counter we need no ordering at all: only that the sum be correct, not that its value coordinate anything else. relaxed gives atomicity without ordering and is noticeably faster:

Careful: relaxed is only correct when the value is not used to deduce anything about other variables; if the counter were a flag of the "the data is ready now" kind, it would be a serious mistake, and when in doubt the default mode is slower but never incorrect. Note as well that an atomic counter is much cheaper than a mutex: 0.192 s against 0.687 s, 3.6 times faster. General rule: if the critical section is a single operation on a single variable, use an atomic, not a lock. And for Meteora, with processes rather than threads, atomic types work the same between processes when the variable is in shared memory, provided atomic_is_lock_free() is true — if it were not, the implementation would use an internal library lock, private to each process and therefore useless. For types of 8 bytes or less on x86-64, it always is.

The lock we built with CAS has a characteristic that has to be examined: busy waiting (or spinning). The thread that fails to get the lock goes round and round in a loop, consuming CPU without progressing, and that kind of lock is called a spinlock.

That pause instruction tells the processor "I am in a waiting loop": it reduces power consumption, avoids the misspeculation penalty on leaving the loop and, with hyperthreading, yields execution resources to the sibling thread. A spinlock without pause can be 2 or 3 times slower than one with it. It is a line people forget constantly.

When does it make sense to burn CPU waiting? The decision comes down to comparing two numbers: going to sleep and waking up costs ~2-5 µs (two context switches plus managing the wait queue), and spinning costs whatever the critical section lasts. If the critical section is shorter than the cost of going to sleep, spinning comes out cheaper; if it is longer, sleeping wins.

The last row describes the classic disaster: with a single core, thread A holding the lock and thread B spinning, B consumes its entire quantum — milliseconds — without progressing, because A cannot run to release it. The spinlock has turned a 50-nanosecond wait into one of several milliseconds: a factor of 100,000. There is also priority inversion: a low-priority thread holds the lock, a high-priority one spins waiting for it, and the scheduler never runs the low-priority one because the high-priority one is runnable, so the system hangs. It was the cause of the famous Mars Pathfinder failure in 1997, which kept resetting on Mars, and the solution is priority inheritance — the holder temporarily inherits the priority of the waiter — which in POSIX is enabled with pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT).

On Linux, spin_lock() is the standard kernel primitive, precisely because in interrupt context there is no alternative: you cannot sleep. In user space pthread_spinlock_t exists, but its correct use is rare.

The alternative to spinning is sleeping: if the lock is taken, the flow asks the kernel to suspend it and wake it when the lock is free. The complete mechanism, connecting with module 2: the thread tries to acquire the lock with an atomic operation and fails; it calls the kernel, which puts it in state S (interruptible sleep) and queues it in the wait queue associated with the lock; the scheduler takes it out of the ready queue and picks another, with zero CPU consumed; when the holder releases, the kernel takes a thread out of that queue and puts it in R; and the scheduler will run it when its turn comes according to its vruntime.

Compared, spinning consumes 100 % of a core while waiting and sleeping 0 %; spinning is disastrous with more threads than cores and sleeping is impossible in interrupt context; spinning wakes instantly and sleeping depends on the scheduler. But the decisive observation is another one: when there is no contention, the two cost the same (~20 ns), because both come down to an atomic operation that succeeds on the first attempt. That is the observation that gives rise to the design of futex and the one that explains why a POSIX mutex is almost free in the common case.

A mutex (from mutual exclusion) is the standard mutual exclusion primitive in user space. Its two defining properties are that it is binary (free or taken, with no intermediate states) and that it has an owner: only the thread that locked it can unlock it.

The output is Expected: 2000000 Got: 2000000 Time: 0.412 s. Now the complete problem really is solved: not just the counter, but the write of the 24-byte struct Reading, which no atomic type can make indivisible on its own. A mutex protects an arbitrarily complex region of code, and that is its advantage over atomics.

Two design decisions in the example worth copying. The lock lives inside the structure it protects, the convention that makes code maintainable: anyone who sees struct meteora_cache immediately knows which lock protects which data, whereas a loose global mutex in another file is an inexhaustible source of omissions. And the critical section is as short as possible: everything that does not need protection (computing r, preparing the HTTP response, writing to the log) goes outside, because the longer the lock is held, the longer everyone else waits and the worse it scales.

For separate processes, such as the meteo-api workers sharing /dev/shm/meteora-cache, it has to be declared shared between processes explicitly, or it will not work:

PTHREAD_MUTEX_ROBUST solves a problem specific to processes: if a worker dies holding the lock, without robust the lock stays locked forever and everybody else hangs; with robust, the next one to try gets EOWNERDEAD, can repair the inconsistent state and call pthread_mutex_consistent() to reactivate it. It is the difference between a service that recovers from the death of a worker and one that hangs until somebody restarts it by hand.

The previous numbers deserve to be looked at together. With 4 threads incrementing the same counter 500,000 times each:

Two quantitative lessons: a mutex costs about 200 ns per operation with moderate contention, some 30 times more than the unprotected operation; and, more importantly, the cost per operation grows with the number of threads — from 4 to 16 threads, the unit cost multiplies by 2.6. It does not merely fail to scale: it gets worse. It is the negative scalability we anticipated in 03-01 when talking about Amdahl's law, and the reason section 14 is about granularity.

A semaphore, invented by Dijkstra in 1965, is a non-negative integer counter with two atomic operations: wait() (historically P, from proberen) decrements the counter and, if it would go negative, blocks the flow; post() (historically V, from verhogen) increments it and, if somebody was blocked, wakes one of them. The intuitive reading is direct: the counter represents how many units of the resource are still available.

Running it, you can see the effect: requests 0, 1 and 2 start immediately; number 3 does not start until one of the three finishes, some 200 ms later. Ten requests take 800 ms (four rounds of 200 ms) instead of the 200 ms they would take all at once. The semaphore has imposed a concurrency limit of 3, which is exactly what we wanted. A semaphore initialized to 1 is called a binary semaphore and looks equivalent to a mutex. It is not, and the difference matters:

Ownership separates the two uses, and from it comes the practical rule: to protect shared data, a mutex — ownership turns unlocking by another thread into a detectable error, allows priority inheritance and expresses the intent better; to signal that something has happened or to count resources, a semaphore — a producer does sem_post and a consumer sem_wait: they are different flows by design, and a mutex there would be incorrect. The last row of the table adds a useful detail: sem_post() is one of the very few functions that are safe inside a signal handler (we saw it in the IPC lesson), which makes it the canonical way for a handler to wake the main loop.

POSIX semaphores come unnamed (sem_init, for threads, or for processes if it lives in shared memory and the second argument is 1) and named (sem_open("/meteora-slots", ...), which creates /dev/shm/sem.meteora-slots and works for unrelated processes).

Mutexes solve "only one at a time" and semaphores "at most N at a time". A third, very different problem is missing: waiting for a condition on the data to become true. The typical case: a meteo-api worker wants to respond with fresh data, but the aggregator has not updated the cache yet, so it needs to wait until n_latest > 0. With no tools, the only option would be to spin checking, and spinning while holding a mutex is a guaranteed deadlock.

A condition variable is a wait queue associated with a logical condition, with three operations: wait(cond, mutex) releases the mutex atomically, sleeps, and on waking takes it again; signal(cond) wakes one of the waiters; broadcast(cond) wakes them all.

That word "atomically" is the key to the whole mechanism: if releasing the mutex and going to sleep were two steps, another thread could slip in between them, change the condition and signal before we went to sleep, so the signal would be lost and we would sleep forever. That is the lost wakeup problem, and the atomicity of wait is what prevents it.

The most important rule in this lesson: pthread_cond_wait ALWAYS goes inside a while loop, never an if. There are three independent reasons and any one of them is enough to justify it. Spurious wakeups: POSIX explicitly allows pthread_cond_wait to return without anyone having called signal — it is not an implementation flaw, allowing it makes the primitive simpler and faster, and on Linux it really does happen when a signal interrupts the wait. Another thread may have got in first: with broadcast, three consumers wake up but there is only one reading available; the first to reacquire the mutex consumes it and the other two find the condition false again. And the condition may have changed by another route, because in real code more than one place modifies the state.

With while, any of those cases simply goes back to sleep; with if, it produces silent corruption. This mistake is probably the most common in all of concurrent programming, and the most expensive because it fails only rarely. Between signal and broadcast, the choice is: signal wakes one and is cheaper, but used wrongly it can wake the wrong thread and leave everybody asleep; broadcast wakes them all, is more expensive (a thundering herd of wakeups) and cannot go wrong. Use broadcast if you have any doubt; signal only when every waiter checks the same condition and there is a single unit available.

A monitor packages the data, the mutex and the condition variables into a unit where mutual exclusion is automatic. Java has it with synchronized; Python offers it with threading.Condition, which incorporates its own lock:

The correspondence is exact: with self._cond is the lock/unlock pair, wait() releases the lock atomically and recovers it on waking, notify()/notify_all() are signal/broadcast, and the while rule stays identical because Python also allows spurious wakeups. What the monitor gains is that the with guarantees the lock is released even if an exception occurs, eliminating the forgotten unlock at the root.

A mutex treats readers and writers alike: only one at a time. But several simultaneous readers do not get in each other's way — if nobody modifies the data, reading it from ten threads at once is safe — and a mutex wastes that opportunity. A read/write lock (pthread_rwlock_t) distinguishes shared reading (many readers at once) from exclusive writing (one writer alone, with no readers):

The question is when it pays off, because an rwlock is not free: its internal structure is more complex than a mutex's and acquiring it costs more. With short critical sections (~100 ns) the mutex wins or draws up to ratios of 99/1, and only from 99.9/0.1 onwards is it worth considering something better — RCU or a double buffer. With long sections (~10 µs), by contrast, the rwlock already wins from 90/10 and wins by a lot from 99/1.

The rule in short: an rwlock pays off when reads clearly dominate and the critical section is long enough for the parallelism between readers to outweigh its higher acquisition cost; with sections of nanoseconds, the overhead eats the advantage. Meteora's case fits easily: meteo-api reads 1,200 times per second and the aggregator writes once an hour, a ratio of 4,320,000 to 1. That said, the rwlock has a problem you need to know about: writer starvation. If readers keep arriving, there may never be an instant with no readers and the writer waits indefinitely. Linux offers pthread_rwlockattr_setkind_np(&attr, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP) to give them preference. That trade-off between favoring one side or the other is precisely the readers-writers problem, which we will develop in Classic Concurrency Problems.

A barrier synchronizes a group of threads at a point: none gets past until all have arrived.

It is the natural primitive for phased computations, when phase N+1 needs the complete results of phase N: in the aggregator, with 4 threads computing partial averages by range of stations, it guarantees that nobody merges before every partial exists. Its cost is that of the slowest thread — a barrier makes everyone go at the pace of the worst — so balancing the distribution of work matters far more in code with barriers than in code without them.

We can now answer the question left open in section 7: if spinning is bad under contention and sleeping always costs 2-5 µs, how does a pthread_mutex_lock manage to be cheap? The answer is futex (fast userspace mutex), the system call Linux introduced in 2002 and on which all of glibc's mutexes, semaphores and condition variables are built. Its idea is as simple as it is brilliant:

The common case — no contention — is resolved entirely in user space with an atomic operation, without calling the kernel. Only when there is real contention do you pay the price of a system call.

A mutex is, in essence, an int in shared memory. The simplified logic:

The integer's three values encode the whole state: 0 free, 1 taken with nobody waiting, 2 taken with at least one waiter. That third value is what lets unlock know whether it needs to wake somebody or can return without calling the kernel. The numbers say it all: an uncontended lock costs ~20 ns with no system call at all and an unlock with nobody waiting ~15 ns, also with no syscall; only when there is contention do FUTEX_WAIT (~2-5 µs) and FUTEX_WAKE (~1-2 µs) show up.

And in a well-designed program the vast majority of acquisitions are uncontended, so a POSIX mutex hardly ever gets to talk to the kernel. You can check it with strace, and the result is revealing:

841 calls to futex for 2,000,000 acquisitions: one for every 2,378 locks, with 99.96 % resolved entirely in user space. If every acquisition had involved a system call, the program would have taken about 4 seconds instead of 0.412. Two more details: futexes work between processes because they operate on the physical address of the page — which is why the mutexes in /dev/shm/meteora-cache work with PTHREAD_PROCESS_SHARED — and the kernel indexes the wait queues by that address in a global hash. To see contention live, perf lock contention or strace -c itself.

One piece remains, which has been cropping up since section 3 and has to be closed: memory reordering. Neither the compiler nor the processor executes your instructions in the order you wrote them; both reorder them freely, with a single guarantee: the result must be the same from the point of view of a single thread. That clause is the trap, because as soon as another thread is watching, the reordering becomes observable.

For a single thread both versions are equivalent: nobody looks at ready in between. But another thread doing while (!ready); use(data.temperature); can see ready == 1 and read a garbage temperature. There are two levels of reordering, and both have to be fought:

And here is the answer to the question in the heading:

volatile prevents the compiler's reordering, but not the processor's, and it makes no operation atomic.

It solves two of the five problems — the compiler caching the variable in a register, and the compiler reordering the accesses — and leaves untouched the three that matter: the processor reordering, the operation being read-modify-write, and another core seeing a stale value. That is why volatile long counter; counter++; still loses increments exactly as it does without volatile: it is read from memory, incremented in a register and written back, with the same old window.

The correct use of volatile is very narrow: hardware registers mapped into memory (where each read has side effects) and the volatile sig_atomic_t flag of a signal handler, correct because the handler runs in the same thread and no two cores are involved. For everything else, the answer is _Atomic / <stdatomic.h>, whose types come with the necessary barriers built in according to the memory order you ask for:

The release/acquire pattern solves the example above and deserves memorizing: the writer prepares the data and then does a release write of the flag; the reader does an acquire read and, if it sees the flag set, is guaranteed to see everything the writer did beforehand. It is the basis of safe publication of data between threads.

A final piece of good news: if you use mutexes, semaphores or condition variables, all of this is solved for you, because pthread_mutex_lock includes an acquire barrier and pthread_mutex_unlock a release one. You only need to understand barriers if you write lock-free code, and that is where most people get it wrong.

A last question, of design: how much should a lock protect? The choice determines the performance of the whole system:

An example on Meteora's cache. With a global lock for latest[1024], the 4 workers always compete, even if they touch different entries. With partitioning:

Now two workers serving stations from different shards do not compete at all: with 16 shards and stations well spread out, the probability of a collision drops to 1/16. And the padding up to 64 bytes is not decorative: without it, several mutexes would fall in the same cache line and the cores would invalidate it for each other while locking different locks. It is the false sharing from 03-01, and it can wipe out the advantage of partitioning completely.

Measurement on meteo-01 with 8 threads and 4 million operations:

Three conclusions: partitioning works (7.25× with 8 threads is close to the maximum possible), there are diminishing returns (from 16 to 64 shards barely anything is gained, because with 8 threads there are hardly any collisions left) and forgetting the padding ruins the design (2.97 s against 0.53 s: a factor of 5.6 lost for not aligning to the cache line).

The engineering rules that follow: start with coarse granularity, because a simple, correct lock is worth more than a fine, broken one; measure before refining, since if the lock is acquired without contention 99 % of the time, refining it will gain nothing; keep the critical section short, because taking a printf or a malloc out of it usually yields more than any redesign of the lock; never do I/O while holding a lock, since a write() to disk can keep the others waiting for milliseconds, four orders of magnitude more than expected; align locks to the cache line when you have several; and always take the locks in the same order, which is the rule that prevents deadlocks and to which we will devote the whole of Deadlocks.

Using if instead of while with pthread_cond_wait. The most common and most expensive mistake: spurious wakeups exist, and with broadcast several threads wake up even though there is work for only one, so with if they all carry on over a false condition. Always while.

Believing volatile is good for synchronization. It prevents the compiler's reordering, not the processor's, and it makes no operation atomic: volatile int counter; counter++; loses increments exactly as before. Use <stdatomic.h> or a mutex.

Forgetting unlock on an error path. An early return inside the critical section leaves the lock held forever and hangs everybody else. In C, a single exit point or cleanup macros; in C++, std::lock_guard; in Python, with lock:.

Using a spinlock where a mutex belonged, or putting several mutexes in the same cache line. If the critical section lasts more than a few hundred nanoseconds, or there are more threads than cores, a spinlock burns whole cores waiting: in user space, the default answer is always the mutex. And several independent locks sharing a cache line come out 5.6 times slower, as we measured above; pad to 64 bytes or use alignas(64).

Protecting with the wrong lock, or not using PTHREAD_PROCESS_SHARED in shared memory. Two critical sections over the same data with different locks do not exclude each other, and a default mutex placed in /dev/shm/meteora-cache gives no error: it simply excludes nothing. The convention of keeping the lock inside the structure it protects avoids almost every case of the first kind.

Tip: the practical order of preference is (1) do not share, (2) immutable data, (3) an atomic operation, (4) a mutex, (5) an rwlock or fine granularity if you have measured contention, (6) lock-free code only if you are a specialist. Go down one step only when the previous one is not enough, and with a measurement in hand. And document what each lock protects: a comment /* protects: total_requests, n_latest, latest[] */ next to the declaration is the first thing whoever debugs a hang at three in the morning will look for.

Implement a shared counter incremented by N threads a million times each, with four strategies: no protection, atomic_fetch_add in relaxed mode, pthread_mutex_t and pthread_spinlock_t. Measure the time with N = 1, 2, 4 and 8 threads, verify the correctness of each one and build the table. Explain why the spinlock behaves as it does when going from 4 to 8 threads on an 8-core machine with other processes active.

Write a program with a shared queue of capacity 1, three consumers waiting on a condition variable and a producer that does a broadcast after inserting one item. Implement the wait first with if and then with while. Run both versions and explain exactly what happens in the if version, including what it prints and why.

Implement Meteora's cache in two variants: protected by pthread_mutex_t and by pthread_rwlock_t. Launch 7 reader threads and 1 writer, where each read walks 100 elements of the array and each write updates 100 elements. Measure the total number of operations per second of each variant and determine, by varying the proportion of writes (1 %, 10 %, 50 %), from what point the mutex becomes better again.

Solution 1

Results on meteo-01 (8 cores):

(✓ = correct result; ✗ = lost increments.) Reading the table. The unprotected version is always the fastest and always incorrect from 2 threads onwards: synchronization has a real cost and it has to be paid. The atomic is 4-9 times faster than the mutex, because a single lock xadd instruction replaces the whole acquisition and release protocol.

Why the spinlock blows up with 8 threads. Up to 4 threads the spinlock beats the mutex (0.381 s against 0.412 s): with a critical section of nanoseconds, spinning costs less than sleeping. With 8 threads on 8 cores it shoots up to 4.72 s, 2.5 times worse, for two reasons that compound. First: there is no genuinely free core, because the system (the shell, systemd, the ksoftirqds) also wants CPU, so when the scheduler preempts the thread holding the spinlock, the other seven keep spinning for whole milliseconds without anybody being able to progress. Second: every spin is a CAS that demands exclusive ownership of the cache line, and eight cores fighting over it generate a storm of coherence traffic that slows down even the one that does hold the lock.

The mutex, by contrast, puts to sleep those who cannot get in: they stop consuming CPU and stop invalidating the cache line. Rule: in user space, mutex by default; spinlock only with critical sections of nanoseconds, fewer threads than cores and a measurement to back it up.

Solution 2

What happens with if. The broadcast wakes the three consumers, but there is only one item. All three were inside pthread_cond_wait, they reacquire the mutex one after another and all three carry on past the if, because an if checks the condition just once, before sleeping. Consumer 0 consumes the only item and leaves items = 0; consumers 1 and 2, already awake, do not check anything again and decrement all the same, leaving the counter at -2.

Here the damage is a negative number. In real code it is far worse: if items were an array index, you would have accesses with a negative index; if it were a pointer taken from an empty queue, a dereferenced NULL; if it were a descriptor, a read on garbage. And all of it intermittently, because it only happens when several consumers are waiting at once.

With while, consumers 1 and 2 reevaluate items == 0 on waking, find that it is true and go back to sleep. That reevaluation is what the loop contributes, and it is the reason POSIX can allow spurious wakeups without breaking any well-written program.

Solution 3

Results with 8 threads, in thousands of operations per second:

Interpretation. With reads dominating, the rwlock wins clearly: the 7 readers walk the array in parallel instead of serially, and the gain of 5.56× with 0.1 % writes comes close to the theoretical maximum of 7×. The break-even point is around 35-40 % writes; beyond that the rwlock is worse than the mutex, for two compounding reasons: its internal structure is more complex — it keeps a count of active readers, which requires extra atomic operations on every acquisition — and with many writes the readers barely overlap, so you pay the overhead without collecting the advantage.

Applied to Meteora: meteo-api reads 1,200 times per second and the aggregator writes once an hour, 0.00002 % writes, far to the left of the first row. The rwlock is the right choice, and with such an extreme ratio it is worth going one step further: a double buffer scheme in which the aggregator prepares a fresh copy and publishes its pointer with an atomic_store in release mode would mean the readers took no lock at all, not even the read one.

The critical section problem cannot be solved properly with ordinary variables, and we have seen why by failing three times: the single flag breaks mutual exclusion because checking and acting are two operations; strict alternation guarantees it but violates progress, letting an idle thread block another forever; and the two flags produce a deadlock in five lines. Peterson's solution combines them and is correct on paper, with optimal bounded waiting, but it only works for two threads, it is pure busy waiting and — the decisive point — it fails on real hardware because of memory reordering unless you add an explicit barrier.

The way out is the hardware: test-and-set and above all compare-and-swap, which compare and write indivisibly in a single instruction (lock cmpxchg). They cost about 20 ns, twenty times more than a normal write, because they negotiate exclusive ownership of the cache line. On top of CAS we have fixed the module's first asterisk: atomic_fetch_add on total_requests gives the exact result every time, is 3.6 times faster than a mutex, and works the same between processes in /dev/shm/meteora-cache as long as it is lock-free.

From there come the two families of waiting. Spinlocks spin: correct for sections of nanoseconds and mandatory in interrupt context, catastrophic with more threads than cores — we have measured it: 4.72 s against the mutex's 1.89 s with 8 threads. Blocking with suspension puts the thread to sleep, costs 2-5 µs and consumes zero CPU. POSIX mutexes protect arbitrary regions of code and not just a single variable, which makes them the answer when a 24-byte struct Reading has to be written indivisibly; between processes they require PTHREAD_PROCESS_SHARED, and PTHREAD_MUTEX_ROBUST prevents the death of one worker from hanging the whole service. Semaphores count resources and have no owner, which makes them the signaling tool between distinct flows and the only one that is safe inside a signal handler. Condition variables solve "waiting for something to become true", with the atomicity of wait protecting against the lost wakeup and the most important rule in the lesson: always while, never if. Rwlocks allow simultaneous readers — 5.56× with 0.1 % writes, but worse than a mutex beyond 40 % — and barriers synchronize computation phases at the pace of the slowest thread.

Underneath, Linux implements it all with futex: the uncontended case is resolved entirely in user space with a 20 ns CAS, and the kernel is only called to sleep or to wake. The numbers confirm it: 841 system calls for 2,000,000 acquisitions, 99.96 % without touching the kernel. We have also closed the account on volatile: it prevents the compiler's reordering but not the processor's, and it makes nothing atomic, so it is no use for synchronizing; its place is hardware registers and the flag of a signal handler. And granularity decides performance: partitioning the cache into 16 cache-line-aligned locks gives 7.25× against the global lock, whereas forgetting the 64-byte padding sinks it to 1.29× through false sharing.

You now have all the pieces, and now comes the interesting part: combining them. A mutex protects one piece of data, but how do you coordinate a producer filling a buffer with a consumer emptying it, without the producer writing into a full buffer or the consumer reading from an empty one? How do you share access between many readers and one writer without anybody going hungry? And why do five philosophers with five forks all end up blocked? These patterns have had names of their own for sixty years, they are the common vocabulary of concurrency, and every real problem you meet will be a variant of one of them. We will see them in Classic Concurrency Problems.