Why It Gets Worse: Shared Data … Uncontrolled Scheduling

26.3 Why It Gets Worse: Shared Data

The A/B example showed threads running; it hid how they interact. Now the fateful program (t1.c): two workers, one global:

static volatile int counter = 0;

// mythread(): simply adds 1 to counter repeatedly, in a loop
void *mythread(void *arg) {
    printf("%s: begin\n", (char *) arg);
    int i;
    for (i = 0; i < 1e7; i++) {
        counter = counter + 1;
    }
    printf("%s: done\n", (char *) arg);
    return NULL;
}

Each worker adds 1 to counter ten million times, so the answer is 20,000,000. Sometimes it even is:

prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 20000000)

And sometimes — same binary, same machine, even a single processor:

prompt> ./main
main: done with both (counter = 19345221)
prompt> ./main
main: done with both (counter = 19221041)

Wrong, and differently wrong each run. Aren’t computers supposed to be deterministic? Have your professors been lying to you? (gasp)

Tip: Know And Use Your Tools

How do you see what a line of C really does? A disassembler: run objdump -d main (Linux) and read the instructions that make up the program. objdump, gdb, valgrind, the compiler itself — the better you are with your tools, the better systems you’ll build.

26.4 The Heart Of The Problem: Uncontrolled Scheduling

The disassembler delivers the verdict: counter = counter + 1 is not one action but three:

100 mov 0x8049a1c, %eax    ; load counter into eax
105 add $0x1, %eax         ; eax = eax + 1
108 mov %eax, 0x8049a1c    ; store eax back to counter

A timer interrupt can strike between any two — and when it does, the other thread walks into the half-finished update. The book’s exact scenario, yours to replay and to break differently:

Figure 26.7, live: two threads, one counter, three instructions each. Run the book's schedule — then find your own poison.

Thread 1

100 mov 0x8049a1c, %eax
105 add $0x1, %eax
108 mov %eax, 0x8049a1c

eax = 0 · next PC = 100

Thread 2

100 mov 0x8049a1c, %eax
105 add $0x1, %eax
108 mov %eax, 0x8049a1c

eax = 0 · next PC = 100

shared memory: counter (0x8049a1c) = 50

OS	Thread 1	Thread 2	PC	eax	counter
before critical section			100	0	50

The book's schedule: T1 loads 50 and adds (eax=51) — interrupt! — T2 runs its whole pass (counter=51) — interrupt — T1 resumes with its SAVED, stale eax=51 and stores it. Two increments ran; the counter moved once. Watch the "restore T1" row: the context switch faithfully preserved exactly the wrong thing. Then run "sequential" for the world as it should be — and then step freely: where can a switch land harmlessly?

What happened has names — nearly all coined by Edsger Dijkstra, whose Turing Award rests partly on this ground. The result depending on execution timing is a race condition (more specifically, a data race); a program containing one is indeterminate — its output varies run to run, instead of the determinism we expect of computers. The three-instruction sequence is a critical section : code that accesses a shared resource and must not be concurrently executed by more than one thread. And the property we wish we had is mutual exclusion : if one thread is executing inside the critical section, the others are prevented from doing so.

One line of C. Three instructions. Two seams. Ten million iterations rolling the dice on every one — and the dice, as your two wrong totals attest, come up snake eyes hundreds of thousands of times per run. The fix requires new machinery, and building it is the business of the chapters ahead.

Check yourself

1.Two threads each add 1 to a shared counter ten million times. The program prints 19,345,221 one run and 19,221,041 the next. Name what you're seeing — twice.

2.Why does the innocent line counter = counter + 1 even HAVE a vulnerability?

3.Trace Fig 26.7's schedule: counter starts at 50; T1 runs mov and add (eax=51), is interrupted; T2 runs all three; T1 resumes. Final counter, and why?

4.Define critical section and mutual exclusion, per Dijkstra (and this chapter).

5.In the explorer, which single placements of the context switch are actually HARMLESS to correctness?

5 questions