Problem Set Solutions/Memory Consistency/Problem01

Sequential consistency ensures that all memory accesses execute as if we process them one at a time, each time selecting a core and letting it complete its next access in program order. Note that this does not require round-robin selection of cores – it even allows one core to be selected several times in a row. This allows for many possible interleavings of accesses from different cores, but it prevents accesses from one core from being reordered.

Weak consistency distinguishes between synchronization and non-synchronization accesses. Synchronization accesses (such as those used to acquire or release a lock) are never reordered amongst themselves or with other accesses. This means that synchronization accesses are done in a sequentially-consistent way, but non-synchronization accesses that a core makes between synchronization accesses can be reordered freely (note that this reordering is still limited by coherence and dependences in program order).

Release consistency further distinguishes between acquire (e.g. lock acquire) and release (e.g. lock release) synchronization accesses. They are still not reordered amongst themselves, but non-synchronization accesses can be reordered freely, except that non-synchronization writes must complete before the next release synchronization event and reads cannot execute before the preceding acquire event.

Note that weak consistency can be achieved using release consistency by treating every every synchronization event as both an acquire and a release. Also note that sequential consistency can be achieved using weak consistency by treating every access as a synchronization access.

If we have multiple threads that do not share any data except for variables that are only accessed within critical sections protected by appropriate locks, e.g.


where lock_var is the lock that protects accesses to data_var, describe which orderings of accesses in this code the processor can use in each of the three consistency models outlined above.


In sequential consistency, mutex_lock() must execute first, then data_var is read, incremented, and written, and then mutex_unlock() executes. This order is required because sequential consistency requires each processor to follow program order.

In weak consistency, the same order of accesses is the only one that can happen. Because synchronization accesses cannot be reordered with any other access, mutex_lock() has to execute first and mutex_unlock() has to be last. Reordering of reads and writes between synchronization accesses is allowed by weak consistency, but there are two reasons why the read of “data_var” still comes before the write to “data_var”: 1) coherence still requires accesses to the same variable to occur in program order, and 2) the value to be written has a true data dependence on the value that is read (read feeds a value to the increment, which feeds a value to the write), and the processor is not going to reorder instructions that have true data dependences.

In release consistency, the read is still required to occur after the lock acquire (a read cannot execute prior to an acquire event that precedes it in program order), the write must execute after the read (same reasons as for weak consistency) and the write is still required to execute before the lock release. Overall, all three consistency models require this code to execute in program order.