Consider this example:
std::atomic<int> v = {0};
// thread 1:
for(int i = 0; i<999999;i++)
v.load(memory_order::seq_cst); // #1
v.exchange(2,memory_order::seq_cst); // #2
//thread 2:
v.store(1,memory_order::seq_cst); // #3
Assuming the modification order of v is {0, 1} where 0 is written by the initialization of v and 1 is stored by #3 in thread 2 and both #1 and #2 does not happen before #3. According to [intro.races] p14 ~ p18:
The value of an atomic object M, as determined by evaluation B, is the value stored by some unspecified side effect A that modifies M, where B does not happen before A.
If an operation A that modifies an atomic object M happens before an operation B that modifies M, then A is earlier than B in the modification order of M.
If a value computation A of an atomic object M happens before a value computation B of M, and A takes its value from a side effect X on M, then the value computed by B is either the value stored by X or the value stored by a side effect Y on M, where Y follows X in the modification order of M.
If a value computation A of an atomic object M happens before an operation B that modifies M, then A takes its value from a side effect X on M, where X precedes B in the modification order of M.
If a side effect X on an atomic object M happens before a value computation B of M, then the evaluation B takes its value from X or from a side effect Y that follows X in the modification order of M.
the load operation at #1 is permitted to always read 0 until the end of the loop, it also can be 1. However, the load part of #2 must read 1 that is written by #3 as per [atomics.order] p10
Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.
In this case, if #1 always reads 0 in its loop, it also does not violate the single total:
#1 is sequenced before #2, which also means #1 strongly happens before #2, so, in the single total order, #1 precedes #2, since #1 reads 0 and 0 precedes 1(produced by #3) in the modification order of v, according to [atomics.order] p3
An atomic operation A on some atomic object M is coherence-ordered before another atomic operation B on M if
- A is a modification, and B reads the value stored by A, or
- […]
- A and B are not the same atomic read-modify-write operation, and there exists an atomic modification X of M such that A reads the value stored by X and X precedes B in the modification order of M, or
#1 is coherence-ordered before #3, hence, #1 precedes #3 in the single total order. Finally, since #2 reads the value written by #3, #3 is coherence-ordered before #2, hence #3 precedes #2 in the single total order. which all three requirements
#1precedes#2#1precedes#3#3precedes#2
can form a valid single total {#1, #3, #2}
Hence, with the pre-conditions, #1 can always load 0, and #2 must read the value 1. Is this a possible output?
4
I think you’re overthinking it.
Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.
This just says that RMWs are invidivisable, i.e. no writes can be inserted between the read part and the write part. (In other words, they say that the “write” part of RMW appears in the modification order right after the value that was read by the “read” part, that’s all).
This doesn’t say that RMWs are any less prone to reading stale values than non-RMW reads. (Maybe that’s what happens in practice on some platforms, but that’s above my paygrade and isn’t the point.)
This presumed difference doesn’t affect how you analyze the programs anyway. If all #1s returned 0, and #2 suddenly returned 1, is it because, #1 was reading a “stale” value, or because #3 happened to happen exactly between the last #1 and #2? You can’t tell, and it doesn’t matter.
Also operations on v have to be consistent with the global seq-cst order, but that doesn’t tell you much. (If all #1s returned 0 and #2 returned 1, then #3 lands between the latest #1 and #2. If some #1 returns 1, then #3 is right before that, etc.)
[assume that] both #1 and #2 does not happen before #3
They can’t happen-before #3 in the first place, I believe (for A to happen-before B in a different thread, there has to be a synchronizes-with relationship, so either B must be a read, or must have a preceding read in the same thread). At best you can say they’re coherence-ordered-before, or that #2 precedes #3 in the modification order of v.
In general, I’d start my assumptions with what value each load returns, and deduce the various “…-before” orderings from there, not the other way around.
26
The text of your question doesn’t match its title. The title mentions “read-modify-write operations,” but in your question itself, you only use the following operations:
v.load()(read but not write)v.store(1)(write but not read)v.exchange(2)(read, then write)
A “read-modify-write operation” would be like compare_exchange_strong, or fetch_add (i.e. +=) — something that reads the atomic’s old value, computes a new value based on (“modifying”) that old value, and then writes the new value.
All atomic operations, including compare_exchange_strong and fetch_add, happen atomically, which means there’s no way for any other thread to sneak a modification in between the read and the write. In other words, atomic operations are atomic. This is not the case for operations that are “non-atomic” — i.e., composed of smaller operations. For example:
int i = v.exchange(2);
// A: Set v to 2 and load its
// immediately previous value into i.
// This is one atomic operation.
int i = v.load();
v.store(2);
// B: Load v's value into i,
// *then* set v to 2.
// This is two atomic operations.
Suppose v is initially zero, and some other thread is doing int j = v.exchange(3) at the same time that we’re executing one of the snippets above. Then it’s possible for the second snippet to observe i=0 and j=0; whereas the first snippet can only ever observe either i=0 and j=2, or i=3 and j=0.
Does that help?
2