Memory Consistency Models: A Tutorial

Summary

17 February 2016 Memory Consistency Models: A Tutorial There are, of course, only two hard things in computer science: cache invalidation, naming things, and off-by-one errors. But there is another hard problem lurking amongst the tall weeds of computer science: seeing things in order. Whether it be sorting, un-sorting, or tweeting, seeing things in order is a challenge for the ages. One common ordering challenge is memory consistency, which is the problem of defining how parallel threads can observe their shared memory state. There are many resources on memory consistency, but most are either slides (like mine!) or dense tomes. My goal is to produce a primer, and motivate why memory consistency is an issue for multicore systems. For the details, you should certainly consult these other excellent sources. Making threads agree Consistency models deal with how multiple threads (or workers, or nodes, or replicas, etc.) see the world. Consider this simple program, running two threads, and where A and B are initially both 0: To understand what this program can output, we should think about the order in which its events can happen. Intuitively, there are two obvious orders in which this program could run: (1) → (2) → (3) → (4): The first thread runs both its events before the second thread, and so the program prints 01. (3) → (4) → (1) → (2): The second thread runs both its events before the first thread. The program still prints 01. There are also some less obvious orders, where the instructions are interleaved with each other: (1) → (3) → (2) → (4): The first instruction in each thread runs before the second instruction in either thread, printing 11. (1) → (3) → (4) → (2): The first instruction from the first thread runs, then both instructions from the second thread, then the second instruction from the first thread. The program still prints 11. and a few others that have the same effect. Things that shouldn’t happen Intuitively, it shouldn’t be possible for this progr...