§ You don't know jack about data races

§ Toy example

• Consider a function void incr() { global += 1; }.
• On running this on multiple thread, the final value of incr can be too low.
• It can even be a constant! Thread 1 reads the value of global(0), gets suspended, then writes global = 0 + 1at the end of the execution!
• It can even be larger than correect. If a 128 bit number is stored as two 64 bit registers, data races could cause the high and low parts to desync, causing the final count to be off. Assume we have two decimal bits lo, hi. If we have 08 ( hi=0, lo=8) and both threads try to update, one thread wants to write 09 and the other thread which writes after this wants to write 10. An interleaving can cause 19, which is way larger than 10.

§ Rules of Racy Programs

• Sequentual consistency: A program is executed by interleaving steps from each thread. Logically the computer executes a step from one thread, then picks another thread, or possibly the same one, executes its next step, and so on.
• Real machines sometimes have non-sequentially consistent semantics, due to assignments being visible to threads out of order. (QUESTION: This is at the C level. But if we view it at the hardware level, it's still sequentially consistent?)
• All modern languages promise sequential consistency for programs without data races .
• What is a data race?
• Two memory operations conflict if they access the same location and at least one of them is a write.
• Two conflicting data operations form a data race if they are from different threads and can be executed "at the same time". But wen is tis possible? Clearly, this depends on the semantics of parallel computation, which we are trying to define in the first place!
• We break this circularity by considering only sequentially consistent executions.
• Two conflicting data operations form a data race iff (definition) one executes immediately after the other in that execution’s interleaving.
• Now we can say that a program is data-race-free if none of its sequentially consistent executions has a data race.
• We define this in terms of conflicting data operations to exclude synchronization operations on mutexes. Synchronization operations do not constitute a data race even if they appear next to each other in the interleaving.
• Thus, the programming model is:

1. Write code such that data races are impossible, assuming that the implementation follows sequential consistency rules.
2. The implementation then guarantees sequential consistency for such code.

§ Counter-intuitive implications

• Consider an example where the initial state is that x,y are false.

P1: if(x) { y = true; }
P2: if(y) { x = true; }

• There is no sequentially consistent set of executions where both assignments are executed.

§ Higher Level

• Article