One of the key differences between acquire/release and volatile (sequential consistency) can be demonstrated using Dekker's algorithm.
public void lock(int t) {
int other = 1-t;
flag[t]=1
while (flag[other] == 1) {
if (turn == other) {
flag[t]=0;
while (turn == other);
flag[t]=1
}
}
}
public void unlock(int t) {
turn = 1-t;
flag[t]=0
}
So lets assume that the writing of the flag is done using a release store and the loading of the flag is done using an acquire-load, then we'll get the following ordering guarantees:
.. other loads/stores
[StoreStore][LoadStore]
flag[t]=1 // release-store
flag[other] // acquire-load
[LoadLoad][LoadStore]
.. other loads/stores
The problem is that the earlier write to flag[t] can be reordered with the later load of flag[other] and the consequence is that 2 threads could end up in the critical section.
The reason the earlier store and the later load to a different address can be reordered is 2 fold:
- the compiler could reorder it.
- modern CPU's have store buffers to hide the memory latency. Since stores are going to be made eventually anyway, there is no point on letting the CPU stall on a cache write miss.
To prevent this from happening a stronger memory model is needed. In this case we need sequential consistency since we do not want any reordering to take place. This can be realized by adding a [StoreLoad] between the store and the load.
.. other loads/stores
[StoreStore][LoadStore]
flag[t]=1 // release-store
[StoreLoad]
flag[other] // acquire-load
[LoadLoad][LoadStore]
.. other loads/stores
It depends on the ISA on which side this is done; e.g. on the X86 this is typically done on the writing side. E.g. using an MFENCE (there are other like XCHG that has an implicit lock or using a LOCK ADDL 0 to the stack pointer like the JVM typically does).
On the ARM this is done on the reading side. Instead of using a weaker load like an LDAPR, a LDAR is needed which will lead the LDAR to wait till the STLR's have been drained from the store buffer.
For a good read, check the following link:
https://shipilev.net/blog/2014/on-the-fence-with-dependencies/