CODEWITHSUNDEEP
javajava-memory-model
user341
user341

Reputation: 133

Why is synchronization order defined as total order over all of the synchronization actions?

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?

Upvotes: 2

Views: 413

Answers (2)

user16792827
user16792827

Reputation: 21

To add to the answer above: total order of synchronization actions is also required for SC-DRF.

Sequential consistency for data-race-free programs (SC-DRF) is one of the key features of Java Memory Model.
From JLS 17.4.5:

If a program is correctly synchronized, then all executions of the program will appear to be sequentially consistent (§17.4.3).

This is an extremely strong guarantee for programmers. Programmers do not need to reason about reorderings ...

Sequential consistency (see JLS 17.4.3) means that there is a single total order over all program actions, the same for every thread.

But if synchronization actions weren't in totally ordered, then SC-DRF would be violated in some cases. One of these cases would be famous IRIW:

    volatile int x, y; // initially zero

    Thread 1 | Thread 2 | Thread 3       | Thread 4
    x = 1;   | y = 1;   | while(x != 1); | while(y != 1);
             |          | int r1 = y;    | int r2 = x;

When x and y are volatile, then result (r1=0, r2=0) is impossible.

Let's replace volatile with setRelease+getAcquire — we only lose total order over synchronization actions.
From VarHandle:

In addition to obeying Acquire and Release properties, all Volatile operations are totally ordered with respect to each other.

    int x, y; // initially zero, with VarHandles X and Y

    Thread 1               | Thread 2               | Thread 3                        | Thread 4
    X.setRelease(this, 1); | Y.setRelease(this, 1); | while(X.getAcquire(this) != 1); | while(Y.getAcquire(this) != 1);
                           |                        | int r1 = Y.getAcquire(this);    | int r2 = X.getAcquire(this);

Now result (r1=0, r2=0) is possible
=> Threads 3 and Threads 4 see writes to x and y in different order
=> violation of SC, which requires a single total order over all program actions, the same for every thread

So, SC-DRF requires total order of synchronization actions.

There is a similar example in C++ docs for memory_order.

Upvotes: 2

pveentjer
pveentjer

Reputation: 11392

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.

Note 1: 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.

Note 2: 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.

Upvotes: 6

Related Questions