Synchronization-with (SW) order vs synchronization order (SO)

Question

Here: http://cs.oswego.edu/pipermail/concurrency-interest/2013-November/011954.html one of the interlocutors says:

In your reasoning, you do not distinguish between synchronization order (so) and synchronizes-with order (sw)

I do not see a difference between so and sw as well. Can someone explain it?

---

EDITED_1:

   read(a, !null) (1)
      \--po--> vread(a.f, 0)
                    \---so---> vstore(a.f, 42)
                                    \---po---> store(a) (4)

Particullary, I don't undertand the above diagram: read(a, !null)(1) means that action read a and it is not-null whileas an action (4) store(a) stored to the a variable after (1).

So, if we have:

read(a) --> store_to_a How read(a) can return not null?

---

EDITED_2 I don't understand:

   vstore(A.f, null) --so--> vread(A.f, null) --so--> vstore(A.f, 42)

What does it mean vstore(A.f, null). I mean A.f is an int. So, why the author stores null to int? The same with vread(A.f, null)

Answer 1

Synchronization order is a property of each individual execution, and it's the order of all synchronization actions on that execution.

Synchronizes-with is a relation partially based on synchronization order (See JLS 17.4.4).

In particular, the post this is responding to assumes there is a sw relation between volatile-read(a.f) and volatile-write(a.f): there is no such relation, that execution just happens to have those two actions following each other in synchronization order, but since there is no sw relation, there is no requirement to introduce appropriate fences (and in fact, on some systems you may have a read-acquire followed by a store-release, which don't synchronize in that order), or, from another point of view, there is no happens-before, so there is a data race, the actual behavior is anyone's guess, and it's actually possible for volatile-read(a.f) to read 0 without violating anything in JLS 17.

Answer to Edit 1

   read(a, !null) (1)
      \--po--> vread(a.f, 0)
                    \---so---> vstore(a.f, 42)
                                    \---po---> store(a) (4)

Particullary, I don't undertand the above diagram: read(a, !null)(1) means that action read a and it is not-null whileas an action (4) store(a) stored to the a variable after (1).

Action 4 happens in a different thread than action 1. Since f is not a final field, and store(a) is not a volatile write, protected by a monitor, ... there is nothing forcing the subscribing thread to see vstore(a.f, 42) and store(a) in that order. e.g. store(a) can be forwarded to another CPU before vstore(a.f, 42).

Put another way, the diagram is misleading, and should better be decomposed into:

Synchronization Order:
    vread(a.f, 0) ---so---> vstore(a.f, 42)
Program Order in publishing thread:
    vstore(a.f, 42) ---po---> store(a)
Program Order in subscribing thread:
    read(a, !null) ---po---> vread(a.f, 0)

It would make sense to use a single diagram only if the program was race-free, which would imply that all executions would need to appear to be sequentially-consistent, which looks like a simple interleaving of threads. In the absence of DRF-SC (data race freedom - sequentially consistent) behaviour, things are not so simple. Even then, I would recommend a diagram with separate threads, as below:

Publishing thread       Subscribing thread

                             read(a, !null)
                                  |
                                  po
                                  |
                                  v
                            vread(a.f, 0)
                          /     
                         so     
                        /       
                       v       
    vstore(a.f, 42)
       |
       po
       |
       v
    store(a) 

The happens-before order is composed solely of the intra-thread program-order of the two threads, and no inter-thread synchronizes-with ordering at all. In particular, there is no happens-before relation between vread(a.f, 0) and vstore(a.f, 42), so there is a data race, and not all executions of the program need to appear to be sequentially-consistent.

Answer to Edit 2

What does it mean vstore(A.f, null). I mean A.f is an int. So, why the author stores null to int? The same with vread(A.f, null)

In this case, the author used null to represent the default value of the field. It's just notation, don't read too much into it.