Race conditions

Your approach to each question

1. Split every line into its two steps: a read into the thread’s own t, then a write made from t. The race lives in the gap between them — another thread can run any number of steps there.
2. Find the top first: the value if the threads ran one after the other. With only additions that is the start plus every increment; with an add and a multiply there are two orders, so two tops.
3. Find the bottom next: the schedule that throws away the most work. A thread that reads early and writes late wipes out everything written in between.
4. Then fill the middle. Each lost update loses one thread’s step, so with additions of 1 every value from the bottom to the top is possible. With one add of c each, the finals go up in steps of c: start + c and start + 2c, nothing between.

Techniques and tricks

• Read, gap, write

  Treat “t = x; x = t + 1” as two moments. Whatever other threads write between this thread’s read and its write is overwritten when it writes. That is the lost update, and every answer here is built from it.

• The sequential answer is only the top

  Running the threads one after the other gives the largest value, not the only one. With one increment each from 0, both can read 0, both write 1, and x ends at 1 as well as 2.

• The stale-read sandwich gives 2

  With two or more increments in every thread, the minimum is 2, however many rounds or threads. One thread reads 0 and waits; the others do all but one of their rounds; it writes 1; another thread reads that 1 and waits; the first finishes; the waiting one writes 2 last.

  e.g. A and B each add 1 three times from 0: the finals are {2, 3, 4, 5, 6}

• One single increment gives 1

  If any thread increments only once, the minimum drops to 1 from a start of 0. That thread reads 0, sleeps through all the other work, and writes 1 last.

  e.g. A adds 1 twice, B once: {1, 2, 3}

• Add against multiply: four cases

  With one add and one multiply, list four finals: both orders run in full, and each thread’s write lost. Add then multiply, multiply then add, the add alone (the multiply was lost), the multiply alone (the add was lost).

  e.g. x = 4, A adds 3, B doubles: (4 + 3) × 2 = 14, 4 × 2 + 3 = 11, 4 + 3 = 7, 4 × 2 = 8 → {7, 8, 11, 14}

• A lock is only a lock if everyone takes it

  A lock makes a thread wait only for another thread that also asks for it. If both threads lock around their increment, each read-and-write is whole, and only the sequential answer is left. If only one does, nothing changes: the set is the same as with no lock.

• Cross copies: never both doubled

  With x = y + c and y = x + c from zero, whichever thread writes first, the other has either read already (and copies 0) or reads that write. So x = c, y = c is possible, and so is one of them at 2c, but never both.

How to practise

• Use “Kinds of question” to drill one kind until its rule is automatic — “Add against multiply” for the four cases, “With a lock” for the one-sided lock.
• Keep “Answer by” on “Ticking every right one” to learn the sets. It makes you decide each value on its own; “Choosing an option” lets you compare whole sets, which is faster but teaches less.
• For “Three threads: the minimum”, switch “Answer by” to “Typing the answer” and give the smallest value with no options to lean on.
• Read the schedule in the working after a miss. It is one real order of steps that reaches the smallest value; follow it read by write and the trick becomes something you can see.