Memory Models and Data Races

Software
, ,
1

Back in 2021, Russ Cox wrote a series of blog posts talking about memory model implementations in hardware and various programming languages. I’ll link these posts below.

Here are a few of my key takeaways:

  • Data synchronization is a very hard problem in nearly all contexts
  • Decades after the first Java memory model, and after many person-centuries of research effort, we may be starting to be able to formalize entire memory models. Perhaps, one day, we will also fully understand them.
  • DRF-SC (data-race-free, sequential consistency) is the idea that a data-race-free program will be indistinguishable from one executed with sequential consistency (i.e. serially on a single processor). Almost every programming language provides a mechanism for programmers to write data-race-free programs and thus rely on the sequential consistency guarantee.
  • By default, hardware and compilers re-order operations however they want; if you want synchronization between processors / threads / goroutines, you must explicitly synchronize data accesses to avoid data races. Different hardware and different programming languages make different guarantees to developers, but they all provide mechanisms for writing programs that exhibit sequential consistency using atomic operations.
  • Again, programs that modify data being simultaneously accessed by multiple threads / goroutines must serialize such access. In Go, that means you must protect the data with channel operations or other synchronization primitives such as those in the sync and sync/atomic packages.
  • If you write a program with a data race, your program can do very strange things…
  • In C / C++, a program with a single data race is deemed completely incorrect and can have undefined behavior (i.e. execute arbitrary code hours or days after the data race occurred)!!! This is known as DRF-SC or catch fire
  • Rust still does not have a formal memory model. It is an area of active research.
  • Quoting The Go Memory Model:

While programmers should write Go programs without data races, there are limitations to what a Go implementation can do in response to a data race. An implementation may always react to a data race by reporting the race and terminating the program. Otherwise, each read of a single-word-sized or sub-word-sized memory location must observe a value actually written to that location (perhaps by a concurrent executing goroutine) and not yet overwritten. These implementation constraints make Go more like Java or JavaScript, in that most races have a limited number of outcomes, and less like C and C++, where the meaning of any program with a race is entirely undefined, and the compiler may do anything at all. Go’s approach aims to make errant programs more reliable and easier to debug, while still insisting that races are errors and that tools can diagnose and report them.

Interesting Examples:

unsigned i = x;

if (i < 2) {
    foo: ...
    switch (i) {
    case 0:
        ...;
        break;
    case 1:
        ...;
        break;
    }
}

Unlike C/C++, re-reading a shared global variable like this is not allowed in Go programs. Go compilers may push i to the stack, for example.

  • Here’s a Go program that also has a data race:
var a string
var done bool

func setup() {
	a = "hello, world"
	done = true
}

func main() {
	go setup()
	for !done {
	}
	print(a)
}

In the above program, it is clear that a data race could cause an empty string to be printed (instead of “hello, world”). But, more subtly, even in Go, it is possible that the for loop in main() may never terminate. This is because the value for done may be cached in a register and never re-read because it is not aware that setup() changed the value of done. Subtleties like this highlight the critical importance of avoiding data races.

1 Like