Problem Set Solutions/Memory Consistency/Problem03

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.

Write some short code for two threads that can distinguish between sequential and weak consistency? Note that the code need not always have a different observable result when run under different consistency models – it is enough that it is possible to get some outcome under one model that is not possible under the other.


There are many possibilities, but the easiest one is the one we used in class (assumes that D and L start out with zero values):

Thread 0:               Thread 1:
D=1;                printf(“L:%d ”, L);
L=1;                printf(“D: %d\n”,D);

Under sequential consistency, the possible printouts are “L:0 D:0” (if Thread 0 does both of its accesses after Thread 1 prints both variables), “L:1 D:1” (if Thread 0 does both accesses before Thread 1 prints them), or “L:0 D:1” (if Thread 1 prints L, then Thread 1 modifies D, and then thread 1 prints D). The outcome of “L:1 D:0” cannot happen because the printout of “L:1” means that Thread 0 did its “L=1” access, and sequential consistency ensues that by that time “D=1” is also complete so “D:0” cannot be printed after printing “L:1”.

In contrast, weak consistency allows the two accesses in Thread 0 to be reordered, in which case it is possible to print out “L:1 D:0” (print both L and D in Thread 1 after L=1 has executed but before D=1 is executed in thread 0)