Problem Set Solutions/Memory Consistency/Problem04

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.

Can you write some short code for two threads that can distinguish between weak and release consistency? Again, 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.

Solution:

Weak consistency and release consistency both allow the same kinds of reordering for data accesses alone and for synchronization accesses alone. They differ only in that release consistency allows some reordering of data and synchronization accesses whereas weak consistency allows none. An easy way would be to use the modified code from the lecture slides:

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

In weak consistency, D=1 and L=1 execute in program order because there is a synchronization access between them and weak consistency prevents data accesses from being reordered with synchronization accesses. As a result, the possible printouts in Thread 1 are the same as for sequential consistency, and “L:1 D:0” cannot be printed. In release consistency, acquire synchronization accesses can be reordered with data writes, so “D=1” can be moved to execute after mutex_lock, and then after “L=1”. As a result, in release consistency the two data accesses can be reordered and a printout of “L:1 D:0” can happen. Therefore, this code can distinguish between weak and release consistency.