Shared State & Races
The core of the domain. Shared mutable state, invariants, finding the minimal critical section, enumerating interleavings to locate a failing schedule, and the distinction between a race condition and a data race that most engineers conflate.
The whole difficulty of concurrency compresses into one sentence: two tasks reach the same state, and at least one of them changes it. Remove either half — the reaching or the changing — and every lesson after this one becomes unnecessary.
Q · Two tasks can both reach the same state — when does that create a coordination requirement, and when does it create none at all?
x = x + 1 is not one operation. It is read, modify, write, and the runtime may put another task between any two of them. Learning to enumerate those orderings — and to recognise the one that loses an update — is the single skill this domain is built on.
Q · If two tasks each run three indivisible steps, what are the possible orderings, and which of them produce a wrong answer?
Synchronization exists to preserve invariants, and nothing else. "Add a mutex" is not a design decision until you can finish the sentence "so that ___ is never observed to be false". This lesson is about writing that sentence first, because it determines the primitive, the region and the test.
Q · What must remain true under every possible interleaving — and how does naming it decide which primitive you need?
Operating Systems defines what a critical section is. The engineering skill is finding the *minimal* one: the smallest region that must be indivisible for the invariant to hold. Too wide and you serialise work that did not need serialising; too narrow and the invariant breaks while every access is dutifully locked.
Q · What is the smallest region of this function that must be protected, and how do I know I have not made it one statement too small?
A race condition is correctness that depends on timing. Finding one is not a matter of staring harder — it is a repeatable procedure: list the shared accesses, put a task switch after each, and ask what the other task could do in that gap. This lesson turns the check-then-act shape into a drill you can run on any diff.
Q · Given a function I did not write, how do I systematically find the schedule that breaks it?
Two different words for two different things, used interchangeably by almost everyone. A race condition is a logical bug: correctness depends on timing. A data race is a *memory model* violation: unsynchronized conflicting access to one location, at least one of which writes. You can have either without the other, and in C++ the second one is undefined behaviour rather than a wrong answer.
Q · What exactly is the difference between a race condition and a data race, and why does the distinction change what I am allowed to assume?
Some operations look indivisible in source and are not. counter++, list.append(x), dict[k] = dict[k] + 1, if not present then insert — each is one expression and several steps. This lesson is about learning what your language actually promises, which is almost always less than the syntax suggests and occasionally more.
Q · Which operations does my language actually promise are indivisible, and which merely look that way?
Run the same concurrent program twice on the same input and you may get two different answers. Sometimes that is correct and even desirable; sometimes it is the bug. This lesson is about telling those apart, and about what nondeterminism does to the value of a passing test.
Q · When is "the output differs between runs" acceptable, and when is it the symptom I am chasing?