We closed module 2 acknowledging a debt. Every time two processes shared a page with MAP_SHARED, every time a softirq and a process touched the same packet queue, every time two meteo-api workers wrote to /dev/shm/meteora-cache, we said "this requires synchronization" and moved on. This lesson starts paying that debt.

And it starts with the most important part: understanding the problem before learning the tools. It is a very common mistake to rush into memorizing mutexes, semaphores and condition variables without having grasped precisely what exactly goes wrong when they are not used. Someone who does not understand the failure uses the tools out of superstition: they put a lock "just in case" where none is needed and forget it where one is. Here we are going to break a counter++ down to its machine instructions and see, step by step, how an increment gets lost.

By the end you will be able to tell concurrency from parallelism rigorously, recognize a race condition by reading code, state precisely the three requirements any solution to the critical section problem must meet, and use Amdahl's law to work out how much the aggregator can really be sped up by adding cores.

1. Concurrency and parallelism are not the same thing
2. Why concurrency is unavoidable
3. Instruction interleaving as a mental model
4. The race condition, taken apart
5. The real case: the meteo-api request counter
6. The critical section and the three requirements
7. Atomicity: what really is atomic and what is not
8. Non-determinism, heisenbugs and why they do not reproduce
9. Concurrency models compared
10. Scalability and Amdahl's law applied to the aggregator

They are two words used as synonyms, and they are not. The distinction underpins the whole module, so let us be precise about the definitions.

Concurrency is a property of the program's structure: several tasks are in progress during the same interval of time, and their advance is interleaved. It does not demand that they run simultaneously; it demands that none has to finish before another can start.

Parallelism is a property of the execution: several tasks execute instructions at the same physical instant, on different compute units. It requires hardware with more than one core (or more than one CPU, or a GPU, or a cluster).

The line that sums it up best, attributed to Rob Pike: concurrency is a way of structuring a program; parallelism is a way of running it.

The point almost everyone overlooks and which is worth burning in: concurrency on a single core already produces every problem in this module. Real parallelism is not required. If meteo-01 had a single core and ran two meteo-api workers, the scheduler would still alternate between them every few milliseconds — or sooner, if one blocks on I/O — and that switch can land in the middle of a counter++. The wrong result is exactly the same.

Real parallelism adds an aggravating factor, not a new problem: on a single core the interleaving only happens at the points where the scheduler preempts a thread; with several cores it happens continuously, and on top of that each core's caches come into play and can make two threads see different values of the same variable for an instant. We will deal with that second effect in Synchronization and Mutual Exclusion, when we talk about memory barriers.

At the top, one core alternates: both tasks are in progress for the whole 8 seconds, but they never run at the same time. At the bottom, two cores: both finish in 4 seconds because they really do run simultaneously. There is concurrency in both cases; there is parallelism only in the second.

You might wonder whether it would not be simpler to ban it. The answer is that a modern operating system could not avoid it even if it wanted to, for four cumulative reasons.

1. Hardware stopped getting faster in frequency around 2005. For three decades, a sequential program ran faster every year without touching a line of code: the clock frequency kept rising. That curve broke on thermal dissipation: power grows roughly with the cube of the frequency. The industry pivoted to adding cores. A typical server such as meteo-01 has 8 or 16 cores; a strictly sequential program uses one and wastes 87 % or 94 % of the machine.

2. I/O is between a thousand and a million times slower than the CPU. Recalling the figures from module 2:

If the ingestor served one station at a time and waited for its reply sequentially, it would spend 99.99 % of the time doing nothing. Concurrency is what lets those waits overlap: while one flow waits for data from station 41, another processes the data from station 12.

3. The real world is concurrent. Meteora has 800 stations that send whenever they please, hundreds of HTTP clients querying the API and an aggregator that has to compute averages every hour. There is no natural sequential order among those events. Modeling them as a sequence would be forcing a lie.

4. The kernel itself is concurrent by construction. Even if you wrote a single-threaded program, underneath it there are interrupts preempting it without warning (module 2), kernel threads such as kswapd or the ksoftirqds, and other processes competing for the same resources. Concurrency is not an option you switch on: it is the medium your code lives in.

All reasoning about concurrency rests on a single mental model. It is worth stating clearly, because the rest of the lesson uses it constantly.

When several flows of execution (threads or processes) advance concurrently, the real execution is one of the possible interleavings of their instructions, and you do not control which one. A concurrent program is correct only if it is correct for every possible interleaving.

Two important consequences:

• The number of interleavings grows explosively. With two threads of m and n instructions respectively, there are C(m+n, m) interleavings. For two threads of just 10 instructions each: 184,756 possible orders. For three threads of 10, more than 5.5 billion. Testing "to see whether it fails" does not cover even a fraction of the space.
• The points where the flow can switch are not the ones that look likely in the source code. The unit of interleaving is neither the C line nor the Python statement: it is the machine instruction, and one innocent-looking line can be several.

That last point is exactly what makes counter++ dangerous.

A race condition is a situation in which the program's result depends on the relative order in which the operations of several flows of execution are interleaved, when that order is not controlled.

Here is the canonical example. This C code increments a shared variable:

Two threads, one million increments each. The expected result is 2,000,000. What actually happens:

Between 400,000 and 900,000 increments are lost, and the figure changes on every run. It never comes out too high; always too low. To understand why, you have to look at what counter++ really compiles to:

There is the whole problem. counter++ is not one operation, it is three: read from memory into a register, add in the register, write the register back to memory. It is the read-modify-write pattern, and it is the origin of the vast majority of the race conditions you will meet in your professional life.

The %rax register is private to each thread: it is part of its context and gets saved and restored on every context switch (module 2). The counter variable in memory is shared. Between step (1) and step (3) of one thread, the value in memory may have changed without that thread noticing.

A trace of an interleaving that loses an increment, starting from counter = 41:

Result: two increments executed, counter holds 42 instead of 43. One has been lost. Not because the hardware or the compiler failed: because thread A read 41 at t1 and wrote its result at t6, unaware that B had written 42 in between. A's write stomps on B's. In the literature this is called a lost update.

The danger window is the interval between (1) and (3): barely 3 or 4 cycles, around 1 nanosecond. It seems impossible for two threads to coincide in such a narrow window. But with two million iterations and a core each, that window opens two million times per second in each thread. The improbable, repeated often enough, becomes inevitable. That is the second point to internalize: a race condition with a vanishing probability per operation becomes a daily failure once the operation happens millions of times.

And compiling with optimizations fixes nothing; sometimes it masks the problem and makes it more treacherous:

With -O2, GCC hoists counter out of the loop, accumulates in a register and writes just once at the end. Both threads write 1,000,000 and the last one wins. The result is just as incorrect, but now it is stable, which is worse: it looks like a deterministic logic bug rather than a race.

Let us bring this to Meteora. meteo-api has four workers serving HTTP queries and sharing a block of statistics in /dev/shm/meteora-cache, the shared memory that appeared in module 2:

Each worker, on finishing a query, does:

With 1,200 requests per second spread across 4 workers, the accounting after a day shows this:

67,116 requests are missing, 0.065 %. It is a small deviation, and that is where the real danger lies: it breaks nothing visibly. Nobody looks at a dashboard and thinks "this is wrong". Usage-based billing simply comes out 0.065 % low, threshold alerts fire a little late, and the monthly report lies about a figure nobody cross-checks.

An important nuance: here the competing flows are different processes, not threads. They share the variable because they share the physical page through MAP_SHARED, not because they share an address space. The race condition is exactly the same. What makes a piece of data dangerous is not where it lives, but that two flows write it without coordination.

That same block has a second problem, more serious than losing counts. When the aggregator updates latest[] with new hourly averages while a meteo-api worker is reading it, the reader can see a half-updated structure: the new timestamp with the old temperature. No data is lost; a datum that never existed is invented. That is no longer a statistical deviation, it is an incorrect HTTP response. We will build the solution to the general case in Synchronization and Mutual Exclusion; this specific readers-and-writers pattern we will deal with in Classic Concurrency Problems.

We can now name the problem precisely.

A critical section is the fragment of code in a flow of execution that accesses a shared resource in a way that can conflict with the accesses of other flows.

In the example, each worker's critical section is the three instructions of cache->total_requests++. In the case of latest[], it is the whole block that writes the fields of a complete Reading.

A detail often misread: the critical section is not the data, it is the code. And the same piece of data can have several critical sections scattered through the program. All of them must be protected; forgetting a single one makes protecting the rest worthless.

The critical section problem consists of designing a protocol — an "I want in" and an "I am out" — that guarantees three properties. They were formulated by Dijkstra in 1965 and they are still the criteria any solution is judged by:

1. Mutual exclusion. If one flow is executing its critical section, no other may be executing its own over the same resource. It is the safety property: it guarantees that nothing bad ever happens.

2. Progress. If no flow is in its critical section and there are flows that want to enter, only those flows take part in deciding who goes in, and that decision cannot be postponed indefinitely. It forbids the critical section being blocked by nobody, or a flow that does not even want to enter preventing others from doing so. It is what avoids deadlock, which we will see in Deadlocks.

3. Bounded waiting. There is a limit to the number of times other flows may enter their critical section after a flow has requested entry and before it is granted. It is what avoids starvation: without it, one flow can wait forever while its peers take turns indefinitely.

All three are necessary and they are independent: a solution can meet two and fail the third. A lock that is never released satisfies mutual exclusion perfectly and violates progress catastrophically. Keep this list, because in Synchronization and Mutual Exclusion we will assess every proposed solution against these exact three criteria.

To those three, practice adds two assumptions worth spelling out because they are sometimes forgotten: you may assume nothing about the relative speed of the flows (one can be a thousand times faster than another) nor about the number of cores.

An operation is atomic if, from the point of view of any other flow, it either happens completely or does not happen at all: there is no instant at which it can be observed half-done.

The word comes from the Greek átomos, "indivisible". And the practical question is: what is genuinely atomic in a real system?

Four practical conclusions from this table:

• A simple assignment of a word-sized, aligned type is atomic on today's architectures. That is why writing a shared int does not corrupt the value: you will see the old one or the new one, never a mixture of bits.
• Anything that is read-modify-write is not atomic, and that includes ++, --, +=, and any if that decides based on a shared value it then modifies.
• Nothing made of several words is atomic. Updating a 24-byte struct Reading is at least three writes; a reader can slip in halfway through.
• Atomic does not mean correct. Even if total_requests++ were atomic, if your logic is "read the counter, decide based on it, and then write it", the decision is still a race. Atomicity is at the level of the operation; correctness is at the level of the invariant.

That last idea is subtle and deserves an example. In Meteora, the aggregator decides whether to rotate the day's file:

Each line on its own is atomic. The whole is not: two workers can pass the check before either has written, and run the aggregation twice. This is the check-then-act pattern, and it is the second great family of race conditions after read-modify-write. Learn to recognize both by reading code; they will save you a lot of debugging time.

A sequential program is deterministic: given the same inputs it always produces the same output and follows the same path. That is the property that makes the usual way of debugging possible — reproduce, set a breakpoint, look.

A concurrent program is not deterministic. Given the same inputs it can produce different outputs, because the specific interleaving depends on factors that neither the program nor you control:

• The decisions of the CFS-EEVDF scheduler, which depend on the accumulated vruntime and therefore on everything that has happened on the machine beforehand (module 2).
• Interrupts, which arrive when they arrive and preempt the running thread.
• The state of the caches and the TLB: a cache miss stretches an instruction from 1 ns to 80 ns and shifts the danger window.
• Migration between cores, dynamic CPU frequency, the load from the rest of the system.

Hence the term heisenbug: a fault that changes behavior or vanishes when you try to observe it. The name plays on Heisenberg's uncertainty principle, and it describes a very real experience:

The explanation is direct: gdb and strace intercept events and add tens of microseconds per operation. That completely changes the timing distribution and means the threads almost never coincide within the 1 ns window. The fault has not been fixed; it has become improbable.

This has three very practical consequences for your work:

1. You cannot prove the absence of races by testing. That 10,000 runs pass says nothing: you have sampled 10,000 interleavings out of billions. Concurrent correctness is demonstrated by reasoning about invariants, not by running.
2. Races show up when the environment changes. Code that had been in production for two years fails when you move from 4 to 32 cores, or when traffic doubles, or when you go from a hard disk to NVMe. The code has not changed: the probability of the bad interleaving has.
3. You need detection tools, not reproduction tools. ThreadSanitizer (gcc -fsanitize=thread) instruments every memory access and detects conflicting accesses even if the failure never manifests:

It gives you the exact line and the two threads involved, on the very first run. The cost is 5 to 15 times slower and 5 to 10 times more memory, so it is used in testing, not in production. It is by far the most cost-effective tool in this module.

There is no single way to structure a concurrent program. There are four big families, and choosing well among them determines half the problems you will have later.

It is worth understanding the underlying trade-off in each one:

• Multiprocess: isolation in exchange for cost. The address spaces are independent, so a corrupt pointer in one process cannot touch the others. Chrome uses one process per tab for exactly this reason. The price: creating a process costs an order of magnitude more than a thread, and sharing data demands an explicit mechanism, which we will see in Inter-Process Communication (IPC).
• Multithreaded: performance in exchange for danger. Sharing memory is free, and that is why it is so fast... and why any variable is a potential race. It is the model that demands the most discipline. We develop it in the next lesson, Threads and Processes.
• Event-based: it eliminates races by construction, because there is only one thread and nothing runs at the same time. In exchange, any blocking operation freezes the whole server, and a long computation blocks every client. It is the model of nginx and Redis, and it explains why Redis, being single-threaded, serves hundreds of thousands of operations per second: everything it does is memory work, and very short.
• Actors: each actor has private state and communicates only through messages; since nothing is shared, there is nothing to protect. It is the model that scales best to distributed systems, because a message between actors works the same within one machine as between two. The cost is copying data and a deep change in programming style.

A real system almost always mixes them. Meteora, to look no further, uses three at once: ingestor, aggregator and meteo-api are separate processes (isolation); inside meteo-api there are several worker threads (performance); and the ingestor serves its 800 sockets with an event loop based on epoll (scalability with many slow connections). That combination is no accident, and in Threads and Processes we will see why each piece chose what it chose.

Last piece, and the most useful one for making decisions: how much can a program be sped up by adding cores?

Gene Amdahl gave the answer in 1967, and it is more pessimistic than almost anyone expects. If a fraction P of the execution time is parallelizable and the rest (1−P) is strictly sequential, the speedup with N processing units is:

And in the limit, with infinite cores:

That is: the sequential part sets an absolute ceiling, and that ceiling does not depend on the hardware you buy.

Let us apply it to Meteora's aggregator. Its daily work, measured with perf on the file 2026-08-31.dat (17 MB, about 700,000 readings):

The parallelizable fraction is P = 7.2 / 10.0 = 0.72. With that we can already compute:

Read the table slowly, because it holds three expensive lessons:

First: the ceiling is 3.57×, not 32×. Even if Meteora bought a 128-core server, the aggregator would not go below 2.8 seconds. The 2.8 s of sequential parts are not going anywhere.

Second: efficiency collapses. Going from 1 to 4 cores gains 5.4 seconds. Going from 4 to 16 gains only 1.35 seconds more, using twelve additional cores. Those twelve cores could be serving meteo-api requests; devoting them to the aggregator to gain 1.35 s is probably a bad architectural decision.

Third, and the one almost everyone forgets: the formula is optimistic. It assumes parallelizing is free, and it is not. The work has to be split up, and above all it has to be synchronized, and synchronization has a cost that grows with the number of flows. If the aggregator's 8 threads compete for a mutex on the partial result, the real time with 8 cores can be worse than predicted — and in cases of high contention, worse than with 4 cores. That is what is called negative scalability, and it is surprisingly common. We will measure that cost with concrete numbers in Synchronization and Mutual Exclusion.

The operational conclusion: before parallelizing, measure P. If your P is 0.72, the realistic target is 4 cores and 2.2×; buying 32 is throwing money away. And very often reducing the sequential part (here, 0.9 s of reading: can it be overlapped with the computation?) yields more than adding cores.

Believing that if the program does not fail, there is no race. It is the most expensive mistake in the module. A race can have a probability of 10⁻⁹ per operation and not show up for two years... until traffic multiplies by ten or you migrate to a machine with twice the cores. Use -fsanitize=thread in your tests: it detects the conflicting access even if the failure never occurs.

Confusing "it is a single line" with "it is atomic". counter++, list.append(x), if (p == NULL) p = create(); are one line each and none of them is atomic. The unit of interleaving is the machine instruction, and in high-level languages, the interpreter's operation. Always ask yourself: does this read and then write? If so, it is a potential race.

Thinking concurrency only matters with several cores. False. One core with two threads already suffers every race condition in this lesson, because the scheduler preempts at any point. Confining the process to one core with taskset -c 0 reduces the frequency of the failure, it does not remove it, and it creates a false sense of security.

Adding threads and expecting a proportional improvement. Amdahl's law says no, and synchronization makes the prediction worse still. Measure the parallelizable fraction before redesigning.

Using volatile in C believing it helps with concurrency. It does not. volatile tells the compiler not to cache the variable in a register, but it does not prevent processor reordering nor does it make a ++ atomic. A volatile long counter; counter++; still loses increments. It is such a widespread mistake that we will devote a whole section to it in Synchronization and Mutual Exclusion.

Tip: identify the shared data before the critical sections. Make a list of which variables more than one flow touches and who writes them. In Meteora that list is short: total_requests, latest[], last_aggregation. Almost everything else is private to each thread and needs no protection. Protecting what does not need it costs performance; forgetting what does costs correctness.

Tip: prefer not sharing over synchronizing well. If each meteo-api worker keeps its own counter and someone adds them up once a minute, there is no critical section to protect. The technique is called counter sharding and it is usually much faster than a perfectly synchronized shared counter.

Write a C program with two threads that increment a shared variable a configurable number of times (given as an argument). Run it with 1,000, 100,000 and 10,000,000 iterations, five times each, and build a table with the average percentage of lost increments. Explain the trend. Then compile it with ThreadSanitizer and check whether it detects the race with only 1,000 iterations.

For each fragment, say whether it contains a race condition when two threads run it, what type it is (read-modify-write, check-then-act, non-atomic structure write, or none) and what exactly the critical section is.

Meteora's ingestor takes 4.0 s to process a batch of 100,000 readings: 0.5 s reading from the socket (sequential), 3.0 s validating and converting each reading (parallelizable), 0.5 s writing the file (sequential). Meteora is considering two investments that cost the same:

• Option A: parallelize the validation with 8 threads.
• Option B: keep it single-threaded but optimize the write from 0.5 s to 0.1 s and the read from 0.5 s to 0.2 s.

Compute the final time for each option and argue which you would choose. Then compute what happens if both are done and what the new theoretical ceiling is.

Solution 1

Compile with gcc -O0 -pthread measure_race.c -o measure_race (the -O0 matters: with -O2 the compiler hoists the counter out of the loop and the phenomenon changes in nature).

Typical results:

Explanation of the trend. With 1,000 iterations the loop lasts about 3 µs, less than the time the second thread takes to start (~20 µs): in practice they run one after the other and there is no overlap. With 100,000 the overlap exists but is partial, and the loss is erratic. With 10 million both threads run in parallel almost all the time, on different cores, and the cache line holding counter bounces between them constantly: each thread reads stale values nearly always and the loss approaches 50 %, which is the theoretical maximum (the two threads advance "in parallel" over the same value and only one of them counts).

This result illustrates the key lesson: with few iterations the program "works". If your unit test uses 1,000 and production uses 10 million, your test always passes and production always fails.

With ThreadSanitizer:

It detects the race with 1,000 iterations, where the result is correct. That is exactly what makes it valuable: it does not look for symptoms, it looks for the cause. TSan keeps per-thread vector clocks and detects that two accesses, one of them a write, touch the same address with no ordering relation separating them.

Solution 2

Case (e) deserves an extra comment because it teaches something important: correct and fast are different things. There is no race, the result is always correct, but if the threads write to contiguous positions in the array, the cores invalidate each other's cache line and performance can drop by a factor of 5 or 10. The fix is to align each element to 64 bytes. It is a performance problem caused by concurrency, not a correctness one.

Solution 3

The structure of the original time: sequential = 0.5 + 0.5 = 1.0 s; parallelizable = 3.0 s; total 4.0 s. Therefore P = 3.0/4.0 = 0.75.

Option A (8 threads in the validation):

Direct check: 0.5 + 3.0/8 + 0.5 = 0.5 + 0.375 + 0.5 = 1.375 s.

Option B (optimizing the sequential parts):

Which to choose. Option A is clearly better in raw time (1.375 s against 3.3 s, 2.4 times faster). But the engineering decision has more facets:

• A consumes 8 cores for 0.375 s; B consumes 1 for 3.3 s. If meteo-01 has 8 cores and meteo-api needs them to serve clients, A degrades the API's latency during that spell.
• A introduces concurrency over the data: the batch has to be split, and the threads will write results that are merged afterwards. That opens the door to every race in this lesson. B does not touch the structure of the program and cannot introduce any concurrency bug.
• B reduces the sequential part, which raises the ceiling for future parallelization.

If the goal is batch latency and there are free cores, A. If the system is already saturated or the team has little experience with concurrency, B is a safe and cheap improvement.

Doing both:

New theoretical ceiling with infinite cores, once the sequential parts are optimized:

Notice what has happened: the original ceiling was 4.0/1.0 = 4×. Reducing the sequential part from 1.0 s to 0.3 s has raised it to 13.3×. Optimizing the sequential part does not just improve the current time: it improves the return on all future parallelism. It is the least intuitive lesson of Amdahl's law and the most useful one in practice.

Concurrency is a property of a program's structure — tasks in progress during the same interval; parallelism is a property of its execution — instructions in the same physical instant. The distinction matters because a single core with two threads already produces every problem in this module: all it takes is for the scheduler to preempt at the wrong point. And concurrency is not optional: hardware stopped getting faster in frequency, I/O is between a thousand and a million times slower than the CPU, the world we model is concurrent, and the kernel itself is concurrent by construction.

The mental model that governs everything is interleaving: the real execution is one of the many possible orders of each flow's instructions, you do not choose which, and your program is only correct if it is correct for all of them. With two threads of ten instructions there are 184,756 interleavings; testing covers nothing. From that comes the race condition, which we have taken apart down to the assembly: counter++ is three instructions — read, modify, write — and the 1 ns window between the first and the third is enough to lose half a million increments per run. At Meteora that translates into 67,116 unaccounted requests a day: 0.065 % that breaks nothing visible, and that is exactly why it is dangerous.

The zone to protect is the critical section, which is code and not data, and any solution must meet three independent requirements: mutual exclusion (never two inside), progress (if it is free, someone gets in) and bounded waiting (nobody waits forever). They are the criteria by which we will judge every primitive in the module. We have also seen what is really atomic — an aligned, word-sized write is; ++, +=, an if that then writes, or any multi-word structure, is not — and the two families of races you will recognize in 90 % of real code: read-modify-write and check-then-act.

These failures are non-deterministic, they depend on the scheduler, on interrupts and on the caches, and that is why they vanish under gdb or strace: they are heisenbugs. The practical consequence is that they are not debugged by reproducing them, but with detectors such as ThreadSanitizer, which finds the race even when the result comes out correct. The four concurrency models — multiprocess, multithreaded, events and actors — distribute the same trade-off between isolation, cost and race risk differently, and Meteora uses three at once. And Amdahl's law sets the limit: with P = 0.72, the aggregator will never go below 2.8 s even with 128 cores, and going from 4 to 16 cores gains barely 1.35 s.

You now know what goes wrong and why. It is time to meet the protagonists up close. We have talked about "flows of execution" without committing: processes that share a page, threads that share everything. What exactly is a thread? What does it share with its siblings and what does it keep private? Why does creating a thread cost 20 µs and creating a process 200? And why, on Linux, are a thread and a process the same thing under the hood, just called differently?

We will see that in Threads and Processes.