While studying Java Memory Model, I was confused by the definition of synchronization order (SO). It is said that SO is a total order over all of the synchronization actions (SA) of an execution. But what is the point of talking about all SA of an execution? I can’t figure out how this might be useful to me. How can I think about all SA? I understand the meaning of the following statement:
For each thread t, the synchronization order of the synchronization
actions in t is consistent with the program order of t.
The usefulness of the statement is obvious, and I can easily use it. But definition of SO isn’t clear for me. Therefore, I cannot figure out how to use it when it comes to SO over several threads. That worries me. How do you understand SO and how do you use it when writing programs?
SO is not something you deal with on a day to day basis. It is just a basis to construct the happens-before relation.
There are a few orders involved in the happens-before relation.
There is the program order (PO): so the order in which loads/stores get executed by a single thread as specified by the Java source code before any optimizations have been applied. The program order creates a total order for all loads/stores of a single thread. But it is a partial order because it doesn’t order loads/stores of different threads.
Then there is the synchronization order (SO): which is a total order over all synchronization actions (lock acquire/release, volatile load/store etc). Because each synchronization action is atomic, they automatically form a total order. So it will even order a release of a lock A and an acquire of a lock B. The SO is consistent with the PO.
Then we have the synchronize-with (SW) order: the SW is a sub-order of SO so that it only captures the synchronizes-with relation. E.g. if a volatile write of X is before a volatile read of X in the SO, then the synchronizes-with relation will order these 2. It will actually order the the write of X with all subsequent reads of X. But unlike SO, it will not order e.g. a volatile write of X and a volatile read of Y. SW will also be consistent with PO.
The happens-before order is defined as the transitive closure of the union of the PO and SW.
The reason that SW and SO need to be consistent with PO is that we do not want that either SW/SO say a->b and the PO says b->a. Because this would lead to a cycle in the happens-before relation and would render it invalid because of a causal loop.
Why do synchronization instructions create a total order? Well; they don’t. But we can pretend a total order exist. If CPU1 is executing volatile store A and and CPU2 is executing a volatile store B (different variables), then it is impossible for A,B to be causally related, therefor A-/->B and B-/->A (doesn’t happen-before). So we now have 2 actions which are not ordered with respect to each other. The cool thing is that we can just pick any order because nobody can prove otherwise. A more technical argument is that the SO is DAG and every DAG always has at least 1 topological sort which is a total order.