Threads and race conditions

Start with the smallest possible parallel program: two threads, each doing x = x + 1 once on a shared integer that starts at zero. When both finish, x should be 2. Run it a few times and it usually is. But not always. Occasionally you get 1 — an increment simply vanished, even though no thread did anything you could call wrong.

The reason is that x = x + 1 is not one action. It is three: load x into a register, add one, store the register back. The two threads' loads and stores can interleave in orders you did not intend, and one ordering loses an update. This is the central lesson of concurrent programming: a correct-looking program can be wrong because of its schedule.

Step the two threads below in different orders. The same six operations give a different final value depending on when each thread reads.

The interleaving is the program #

If thread A has operations $a_1 \dots a_m$ and thread B has $b_1 \dots b_n$, any order that preserves each thread's internal sequence is a legal execution. The count of such interleavings is the binomial coefficient

$$\binom{m+n}{n} = \frac{(m+n)!}{m!\,n!}$$

For the counter, $m = n = 3$ gives $\binom{6}{3} = 20$ schedules — and all but a few of them are correct. That is the cruel part: the buggy schedules are a minority, so the program passes the demo and fails in production. It gets worse fast. Two threads of ten operations have $\binom{20}{10} = 184{,}756$ interleavings; you cannot test your way through the state space.

RAII-thinking says "it worked when I ran it", and the scheduler says "not today". Bugs that depend on timing are called heisenbugs for a reason: the debugger perturbs exactly the timing that triggers them.

Where the reorderings come from #

It is tempting to think the load and store are far apart and interleaving is unlikely. The truth is worse: the hardware and compiler are allowed to reorder, and do, as long as a single-threaded observer cannot tell.

• Preemption — the OS switches threads between any two instructions.
• Memory reordering — CPUs and GPUs use store buffers and out-of-order execution, so a store may become visible to one thread before another.
• Compiler reordering — the optimiser may move loads and stores across each other because it assumes one thread.
• Caching — a write may sit in one core's cache unseen by others until it is flushed.

The last three mean that even two instructions with no context switch between them are not necessarily ordered as written. That is why a data race — two threads accessing the same location, at least one writing, without synchronisation — is not merely a bad pattern. In C++ and Go it is formally undefined behaviour: the compiler is free to assume it never happens.

Happens-before #

The mental model that replaces "I hope the scheduler cooperates" is happens-before. Instead of reasoning about an actual timeline, you establish edges that guarantee ordering: an unlock happens-before a later lock of the same mutex, a thread start happens-before the new thread's first action, a join happens-before the joiner continues. If two accesses are not connected by a chain of such edges, they are concurrent, and concurrent access to shared mutable state is exactly what you must forbid.

This is the useful mental shift: stop asking "what order will this run in?" and start asking "which edges do I have, and is every shared access on one side of an edge?"

Check yourself

Eduspheria wiki · Systems for AI, Concurrent programming

0 / 5 answered

1. 1Thread A has 3 operations and thread B has 3. How many distinct interleavings preserve each thread's order?

   Check Hint Show answerNumeric answer
2. 2Which of these is a data race?

   A.One thread reading a variable another thread is readingB.Two threads accessing the same variable, at least one writing, with no synchronisationC.Two threads only reading the same variableD.Two threads writing different variables with no sharing

   Check Hint Show answerMultiple choice
3. 3A program with a data race is well-defined but may produce an unexpected result.

   TrueFalse

   Check Show answerTrue / false
4. 4What ordering relation, built from lock/unlock and thread start/join edges, is used to reason about concurrent accesses?

   Check Show answerShort answer
5. 5Why is adding a sleep(10) before the write a bad fix for a race?

   A.It is too slowB.It uses too much memoryC.Sleep is not available in all languagesD.It changes timing without guaranteeing an ordering edge

   Check Hint Show answerMultiple choice

From the exam paper

Modeled on NITJ AI-619, End-Sem June 2025

0 / 5 answered

1. 1Thread A has 4 operations and thread B has 4. How many distinct interleavings preserve each thread's internal order?

   Check Hint Show answerNumeric answer
2. 2Which type of parallelism applies the same operation to many independent data elements at once?

   A.Task parallelismB.Memory-level parallelismC.Data parallelismD.Instruction-level parallelism

   Check Show answerMultiple choice
3. 3Concurrency means several tasks are in flight during the same period, while parallelism means they literally execute at the same instant.

   TrueFalse

   Check Show answerTrue / false
4. 4In the GPU thread hierarchy, the threads of a block are issued together in groups of 32 called…

   A.WarpsB.GridsC.KernelsD.Streams

   Check Show answerMultiple choice
5. 5What name is given to a timing-dependent bug that tends to disappear when a debugger is attached?

   Check Show answerShort answer

Where next: the primitives — mutexes, semaphores and atomics — that create the ordering edges.