Step 2 of 6

Data races

What if both threads add to the same counter? This looks harmless:

#include <iostream>
#include <thread>

int main() {
    long long counter = 0;
    auto work = [&] {
        for (int i = 0; i < 1000000; i++) counter++;   // DATA RACE
    };
    std::thread a(work), b(work);
    a.join();
    b.join();
    std::cout << counter << "\n";
}

Two threads, a million increments each, so it should print 2000000. Built without optimization (-O0) on a 4-core Linux machine, four runs printed 1367998, 1257188, 1162747 and 1363165: a different wrong answer every time. Built with -O2, it printed 2000000 all four times, because the optimizer turned each loop into a single addition, which made the problem much rarer. Either way the program is broken, and ThreadSanitizer (-fsanitize=thread) reports it on the first run: WARNING: ThreadSanitizer: data race.

Why updates get lost

counter++ looks like one action, but the processor does it in three steps: load the value from memory into a register, add 1, store the result back. Two threads can interleave those steps:

Two increments ran, but the counter only went up by one. B's store overwrote A's work: a lost update. Which interleaving happens depends on timing, so the result changes from run to run.

The rule

A data race is two threads accessing the same memory location at the same time, where at least one of them writes and nothing synchronizes them. In C++ a data race is undefined behavior, not just "a slightly wrong number". The compiler optimizes assuming races never happen (that's what the -O2 build did), so a racy program can misbehave in ways the source code doesn't suggest.

Reading shared data from several threads is fine if nobody writes it. The moment one thread writes, every access needs synchronization: a mutex (next step), an atomic, or not sharing at all.

Simulating the interleaving

Timing makes real races hard to study, so this program plays one out deterministically. Each "thread" does counter++ as three separate steps, and the schedule string says whose turn it is:

#include <iostream>
#include <string>

struct Thread {
    int reg = 0;     // its private copy of the value (a CPU register)
    int stage = 0;   // 0 = load next, 1 = add next, 2 = store next
};

int main() {
    int counter = 0;
    Thread a, b;
    std::string schedule = "ABABAB";
    for (char who : schedule) {
        Thread& t = (who == 'A') ? a : b;
        if (t.stage == 0) t.reg = counter;       // load
        else if (t.stage == 1) t.reg += 1;       // add
        else counter = t.reg;                    // store
        t.stage = (t.stage + 1) % 3;
    }
    std::cout << "counter = " << counter << "\n";
}

counter = 1

With the schedule "AAABBB" (A finishes before B starts) it prints 2. With "ABABAB" it's exactly the table above, and one update is lost.

Your turn: write simulate(schedule), which returns the final counter when threads 'A' and 'B' repeat counter++ as load, add, store and the schedule says whose step comes next (a thread keeps incrementing as long as it gets turns; an increment that never reaches its store has no effect). Then write lost_updates(schedule): how many completed increments (stores) didn't show up in the final counter.

Previous: Threads and splitting work Next: Mutexes and lock_guard