synchronizes-with, happens-before relation and acquire-release semantics

Question

I need help in understanding synchronizes-with relation. The more I'm reading it an trying to understand example, the more I feel that I understand nothing. Sometimes I feel that here is it, I've got it, but after looking at another example I get confused again. Please help me to get it right.

It's said that an operation A synchronizes-with an operation B if A is a store to some atomic variable m, with release semantics, B is a load from the same variable m, with acquire semantics, and B reads the value stored by A. It's also said that an operation A happens-before an operation B if

• A is performed on the same thread as B, and A is before B in program order, or
• A synchronizes-with B, or
• A happens-before some other operation C, and C happens-before B

OK. If we look at this example

thread0 performs | thread1 performs

---

store x (release) | load x (acquire)

does store to x here synchronize-with load from x? If we do have synchronizes-with relationship here, then store to x happens before load from x, so everything what is sequenced before store to x in thread 0 happens-before load from x in thread 1. It means there is enforced ordering here. Is it right? But in this case I don't understand what does the "and B reads the value stored by A" part of definition mean? If thread 1 is faster then thread 0 it may read the old value. So what is the relationship here and is there any relationship at all? If there is no, how can I provide that relationship?

Thanks in advance.

Answer 1

I cannot say that I am well familiar with the terminology, but this is how I think it goes. I will use the .NET definitions for terms: "An operation has acquire semantics if other processors will always see its effect before any subsequent operation's effect. An operation has release semantics if other processors will see every preceding operation's effect before the effect of the operation itself."

There is no enforced ordering between the store and load in the example. Either one may be executed first. A synchronizes-with B when the store operation happens to be executed before load. When this happens, all operations before the store (release) are guaranteed to be executed before the operations after the load (acquire) are executed.

However, the load operation may be executed before the store. In that case A does not synchronize-with B (as the condition "and B reads the value stored by A" is not true) and so the operations after load may be executed before the operations that precede the store. The order is vague.

The release semantics guarantees that for certain value of x we will know that the operations preceding the store will be executed before we are able to load the same stored value in the second thread (and before we are able to execute the operations following the load).

Let's assume that count and flag are initialized to zero and both threads are run in parallel:

thread0:
st          count, 1   (A)
st.release  flag, 1    (B)

thread1:
ld.acquire  flag       (C)
ld          count      (D)

We know that A happens-before B and C happens-before D, because their order is forced by the release and acquire semantics. The order of B and C is undefined. It only becomes defined when B synchronizes-with C and then we know that A happens-before D (as A happens-before B happens-before C happens-before D).

In thread1 the count is always 1 if flag is 1. If flag is 0 the count may be either 0 or 1. We could test the flag to determine if the other thread has set the value to the count.

Without acquire and release semantics the loads and stores could be reordered and both the flag and count could be either 0 or 1 with no dependency to each other.

If we want to ensure that B happens-before C, we can use semaphores or some other wait-and-signal mechanism. In previous example we could enforce the order by busy-waiting the flag to be set.

thread1:
ld.acquire  flag       (C)
repeat C while flag == 0
ld          count      (D)