c++ - Does this result depend on out-of-thin-air value? - Stack Overflow

admin管理员组

文章数量:1122832

Given this example, x is initially 0, and y is initially 2.

std::atomic<int> x = 0, y = 2;
// thread 1:
if(y.load(relaxed) == 1){ // #1
   x.store(1,relaxed); // #2
}
//thread 2:
int pre = x.load(relaxed); // #3
while(pre != 0){
   if(xpare_exchange_strong(pre, pre+1, acquire, relaxed)){  // #4
       break;
   }
}
y.store(1,relaxed); // #5

If both #1 and #4 are true, does this result depend on out-of-thin-air value? [atomics.order] p8 says:

Implementations should ensure that no “out-of-thin-air” values are computed that circularly depend on their own computation.

In this example, #1 returns true depending on whether it reads #5. #5 is executed whatever pre is zero or non-zero. The tricky part is that #4 might be a successful RMW operation only if pre !=0, otherwise #4 is never executed. In this example, x is initially 0, so #4 returns true only if #3 reads #2 and #4 reads #2. After this analysis, I'm not sure whether the above example can be simplified to the following:

// thread 1:
if(y.load(relaxed) == 1){ // #1
   x.store(1,relaxed); // #2
}
// thread 2:
int pre = 1;
while(!xpare_exchange_strong(pre,pre+1, acquire, relaxed)){} // #4
y.store(1,relaxed); // #5

Now, #1 depends on #5, and #5 depends on #4 reads #2, #2 depends on #1. So, if both #1 and #4 returns true, this result depends on OOTA?

Given this example, x is initially 0, and y is initially 2.

std::atomic<int> x = 0, y = 2;
// thread 1:
if(y.load(relaxed) == 1){ // #1
   x.store(1,relaxed); // #2
}
//thread 2:
int pre = x.load(relaxed); // #3
while(pre != 0){
   if(x.compare_exchange_strong(pre, pre+1, acquire, relaxed)){  // #4
       break;
   }
}
y.store(1,relaxed); // #5

If both #1 and #4 are true, does this result depend on out-of-thin-air value? [atomics.order] p8 says:

Implementations should ensure that no “out-of-thin-air” values are computed that circularly depend on their own computation.

In this example, #1 returns true depending on whether it reads #5. #5 is executed whatever pre is zero or non-zero. The tricky part is that #4 might be a successful RMW operation only if pre !=0, otherwise #4 is never executed. In this example, x is initially 0, so #4 returns true only if #3 reads #2 and #4 reads #2. After this analysis, I'm not sure whether the above example can be simplified to the following:

// thread 1:
if(y.load(relaxed) == 1){ // #1
   x.store(1,relaxed); // #2
}
// thread 2:
int pre = 1;
while(!x.compare_exchange_strong(pre,pre+1, acquire, relaxed)){} // #4
y.store(1,relaxed); // #5

Now, #1 depends on #5, and #5 depends on #4 reads #2, #2 depends on #1. So, if both #1 and #4 returns true, this result depends on OOTA?

• c++
• language-lawyer
• atomic

Share Improve this question Follow edited Nov 27, 2024 at 6:44 xmh0511 asked Nov 22, 2024 at 2:52 xmh0511xmh0511 7,35911 gold badge1111 silver badges4141 bronze badges 4

• 1 If it's possible at all, it's via out-of-thin-air values. There's no plausible compile-time reordering (due to branches) or seq_cst interleaving that does it. If the CAS_strong is reached at all (from t2's x.load having read non-zero) and succeeds, its load of x happens-before y.store, and x.load(relaxed) happens even before that (same object same thread). But x=1 happening at all depends on y=1 happening. The pre!=0 loop condition is what prevents there from being a seq_cst execution order where all of thread 2 runs before all of thread 1 to satisfy your condition. – Peter Cordes Commented Nov 22, 2024 at 3:25
• You can simplify it to if(pre !=0) CAS(pre, pre+1, order); - if we reach it at all, x is already 1 and won't change again so CAS succeeds. – Peter Cordes Commented Nov 22, 2024 at 3:27
• @PeterCordes Do you mean with the constraint that #1 and #4 must both return true, the code is functionally equivalent to //t1: if(y.load(relaxed) == 1){x.store(1,relaxed);} // t2: if(x.load(Relaxed)==1){CAS(1, 2, order);} y.store(1,relaxed);. The CAS can be reached and succeed only if x.load(Relaxed)==1. However, the tricky part is that #5 is free-executed, it is not constrained by whether x.load()==1, if y.load were within the block of the if, it would be a classic OOTA. – xmh0511 Commented Nov 22, 2024 at 5:17
• @PeterCordes It appears to me the example is much more like: //t1: if(y.load(relaxed) == 1){x.store(1,relaxed);} //t2: auto r = x.load(Relaxed)==1; y.store(1,relaxed);. The store to y does not depend on r, because the written value of the CAS does not contribute to the load in t1, and what r is does not affect #5 is executed, it seems not to form the dependency chain? – xmh0511 Commented Nov 22, 2024 at 5:27

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

To start:

• For Thread 1 to execute its store (x.store(1, relaxed)), the condition in #1 must be evaluated as true, which depends on y.load(relaxed) == 1.

• Given that Thread 2 stores 1 to y in #5, Thread 1's check in #1 will only succeed if it sees y == 1. However, there's no guarantee that the y.store(1, relaxed) from Thread 2 will be visible to Thread 1 at the time of the load because relaxed ordering does not enforce synchronization.

• Thread 2 will not attempt the CAS operation unless pre != 0 is true (because it initializes pre with x.load(relaxed) and the loop continues until pre is 0).

What Happens When Both #1 and #4 Are True?

• For #1 to return true, Thread 1 must see y == 1. For #4 to execute successfully, Thread 2 must see that x != 0 (because it must read pre != 0), and then x must change from its initial value (0) to pre+1 atomically.

• This creates a dependency where Thread 2 depends on x != 0 to even attempt #4, but Thread 1 could potentially set x = 1 if #1 succeeds and y == 1 is true. In this case, Thread 2 would succeed in the CAS in #4, and Thread 1 would have already set x = 1.

• The tricky part is that Thread 1 and Thread 2 could both be running concurrently. Due to the relaxed memory ordering, Thread 2 might not see the x = 1 store from Thread 1 immediately, leading to a potential out-of-thin-air value.

• Specifically, if Thread 2 sees the initial value of x == 0, but later Thread 1 sets x = 1, and this store is not visible to Thread 2 at the correct point, then Thread 2 might see x as still 0 even though Thread 1 has set it to 1.

TL;DR

So, to answer, yes, if both #1 and #4 are true, the result can depend on "out-of-thin-air" values because the relaxed memory orderings may not guarantee that the stores in Thread 1 (e.g., x.store(1, relaxed)) will be visible to Thread 2 at the right time.

I hope this helps. If you have any questions or want some references, just comment, and I'll edit this question.

Edit:

Does #5 Indirectly Depend on x.load()?
Against OOTA

1. Thread 2's y.store(1, relaxed) (#5):

• The value being stored (1) does not depend on the value of x.
• The execution of y.store is not conditional on the value of x. It is executed unconditionally, regardless of whether the loop involving compare_exchange_strong (#4) succeeds or fails.

2. Circular Dependency Analysis:

• For Thread 1, y.load() (#1) must see y == 1 for it to proceed with the store to x (#2).
• For Thread 2, the CAS in #4 depends on x != 0. However, the unconditional store to y in #5 does not rely on the success or failure of the CAS in #4.
• Because the execution of #5 does not depend on any condition involving x, there is no direct or indirect feedback loop between the operations on x and the store to y.

3. Relaxed Memory Ordering:

• The relaxed memory ordering allows reordering and lack of visibility guarantees but does not create circular dependencies unless there is an explicit dependency in the code. Here, the relaxed ordering alone does not establish the conditions for OOTA.

Argument for OOTA

The "arguable part" that you mentioned has this edge case:

• If #5's execution can be argued to depend on the loop in Thread 2 (and indirectly on x.load()), then we might consider it a dependency chain. For example:
  • The loop in Thread 2 exits only when compare_exchange_strong (#4) succeeds, which depends on x.load() reading a specific value (e.g., x = 1).
  • If Thread 2's progress (including the execution of #5) hinges on the state of x, this could introduce a subtle indirect dependency.

However, this indirect dependency does not qualify as OOTA because:

1. The store to y (#5) is not affected by the value of x. It is executed independently once the loop exits.
2. While the execution of #5 might be delayed until the loop exits, it does not form a dependency cycle that could lead to an "out-of-thin-air" result.

Conclusion

This does not qualify as OOTA:

• The store to y in #5 does not depend on the value of x, either directly or indirectly.
• While #5 may execute after the loop exits, its execution timing is not contingent on the result of any operation involving x.load().

For OOTA to occur, there must be a true circular dependency involving a feedback loop, which isn't here.

本文标签： cDoes this result depend on outofthinair valueStack Overflow