Problem Set Solutions/Memory Consistency/Problem02

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 the following code distinguish between some or all of the above consistency models? Assume that initially a==0:

Thread 0:                   Thread 1:

mutex_lock(l);              mutex_lock(l);
a=a+1;                  a=a-1;
mutex_unlock(l);                mutex_unlock(l);
printf(“0: %d\n”,a);            printf(“1: %d\n”,a);

To distinguish between two consistency models, the code must exhibit observable behavior (e.g. what is printed) under one model that is not possible under the other model. Note that instruction ordering is not observable behavior unless it results in different printouts.


No, the possible outputs produced by this code are the same in all three consistency models. Under weak consistency, the independent accesses within a critical section can be reordered by a processor, but in this code each critical section has only two accesses which have data dependences, a flow dependence through registers (write uses results of increment/decrement, which uses the result of the load) and a anti-dependence through memory (store overwrites the value read by the load). Either of these dependences is enough to prevent the processor from reordering these two instructions, regardless of the consistency model. Overall, under weak consistency the order in which load/store instructions are executed is exactly the same as under sequential consistency, so the possible outcomes are also exactly the same. For release consistency, the load of “a” must be executed after the lock (acqure) because the consistency model requires that. The load must precede the store (because of data dependences), and the store must be executed before the unlock (release) operation. As a result, the order of instructions execution (and the possible outcomes) is exactly the same a s in sequential consistency.