2023-02-14

Transitivity of release-acquire

Just when I thought I got some grip around atomics, I see another article. This is an excerpt from GCC wiki, under Overall Summary:

 -Thread 1-       -Thread 2-                   -Thread 3-
 y.store (20);    if (x.load() == 10) {        if (y.load() == 10)
 x.store (10);      assert (y.load() == 20)      assert (x.load() == 10)
                    y.store (10)
                  }

Release/acquire mode only requires the two threads involved to be synchronized. This means that synchronized values are not commutative to other threads. The assert in thread 2 must still be true since thread 1 and 2 synchronize with x.load(). Thread 3 is not involved in this synchronization, so when thread 2 and 3 synchronize with y.load(), thread 3's assert can fail. There has been no synchronization between threads 1 and 3, so no value can be assumed for 'x' there.

The article is saying that the assert in thread 2 won't fail, but that in 3 might.

I find that surprising. Here's my chain of reasoning that the thread 3 assert won't fail—perhaps someone can tell me where I'm wrong.

  1. Thread 3 observes y == 10 only if thread 2 wrote 10.
  2. Thread 2 writes 10 only if it saw x == 10.
  3. Thread 2 (or any thread) sees x == 10 only if thread 1 wrote 10. There are no further updates to x from any thread.
  4. Since thread 2 observed x == 10, and thread 3, too, having synchronized with thread 2, should observe x == 10.

Release/acquire mode only requires the two threads involved to be synchronized.

Can someone point to a source for this 2-party-only requirement, please? My understanding (granted, perhaps wrong) is that the producer has no knowledge of with whom it's synchronizing. I.e., thread 1 can't say, "my updates are only for thread 2". Likewise, thread 2 can't say, "give me the updates from thread 1". Instead, a release of x = 10 by thread 1 is for anyone to observe, if they so chose.

Thus, x = 10 being the last update (by thread 1), any acquire from anywhere in the system happened-after (ensured by transitive synchronization) is guaranteed to observe that write, isn't it?

This means that synchronized values are not commutative to other threads.

Regardless of whether it's true, the author perhaps meant transitive, not commutative, right?

Lastly, if I'm wrong above, I'm curious to know what synchronization operation(s) would guarantee that thread 3's assert won't fail.



No comments:

Post a Comment