Let us say we have an atomic variable named DATA which is AtomicI32 type, and its values have been updated multiple times using the Relaxed ordering. Here is the timeline/history of its values 0, 23, 76, 90, 34. The 34 is the last value.
Some other threads used Relaxed ordering for all the updates to the DATA, now another thread tries to update the DATA using the compare_exchange() method with Relaxed.
Now I want to update the DATA by using the compare_exchange() method using the Relaxed ordering for both success and failure cases. Then the method looks like this: DATA.compare_exchange(34, 65, Relaxed, Relaxed).
Using the Relaxed for the success case forces the Relaxed order to be used for the loading part inside of the compare_exchange().
I think the DATA is not obliged to give 34 to the loading part of the compare_exchange() with Relaxed ordering so it might fail. Because Relaxed does not ensure immediate observability of the changes(that made to DATA) across the threads hence no synchronization and happens-before relationship. As a result, the code is incorrect.
Nothing ensures immediate observability of changes across threads. Even SeqCst ordering does not guarantee timely observability of changes; it just guarantees that across all threads and all SeqCst accesses, the ordering of changes is the same.
So yes, compare_exchange can fail in this case, and that's true regardless of ordering. If you're only considering a single atomic, and not other data, Relaxed, Acquire, Release, and AcqRel are all the same (they differ only in what observing a given value in the atomic can tell you about other changes made by other threads), while SeqCst adds the guarantee that across all SeqCst accesses, all threads will agree on what order the SeqCst accesses took place in (but not necessarily when the accesses happened).
The ordering of atomic operations refers to non-atomic valuesonly.
The atomic variable itself is, as the name suggests, atomic. So, all threads will see the 34, provided their read happens after the 34 was written to the atomic variable.
You can think of the atomic variable as similar to a variable inside a mutex. To read or write to the variable, it must be "locked" for a very short time. For atomic variables, this locking is handled by the CPU through the cache coherence protocol.
If a compare_exchange(34, 65) is successful, then the history must contain a 34, 65 somewhere with nothing in between. Furthermore, every update in the history must correspond to exactly one atomic operation, so if two threads call compare_exchange(34, 65) in parallel, then only one of them will successfully change the value from 34 to 65. The other thread will fail saying "the old value is not 34 but 65".
But when compare_exchange fails, it could read an old value.
Does this mean that in an history with 34, 51 when a compare_exchange(34, 65) fails it could read the old value of 34 (thus leading to the seemingly non-sensical "the old value is not 34 but 34")?
No, because it’s an atomic variable. The key point is that the memory Orderings only relates to non-atomic data.
If the atomic variable doesn’t contain 34, then it contains 51. The compare_exchange(34, 65) will fail with the value 51, as that’s what was read when the comparison failed.
It’s as simple as this: Atomic variables function like mutex-protected variables, but the "mutex" is implemented in hardware by the CPU.
Starting with an atomic value of 1 and using 3 parallel compare-and-exchange operations:
a.) compare_exchange(1, 2)
b.) compare_exchange(2, 3)
c.) compare_exchange(1, 4)
These are the possible outcomes:
1.) a succeeds, b fails with the old value 1, c fails with the old value 2
2.) a and b succeed, c fails with the old value 2
3.) a and b succeed, c fails with the old value 3
4.) c succeeds, both a and b fail with the old value 4
It may seem like, in case 2, c fails with an outdated value. But that’s only because the compare_exchange in b, which changes the value from 2 to 3, happens after c.
From c's perspective, the old value 2 is not actually outdated. It is the value at that exact instant. Shortly after, perhaps just a fraction of a nanosecond later, b changes the value from 2 to 3.
No that can't happen. When compare_exchange fails, it can read any value in the history that a load could have read, except for those where the value is equal to the first parameter.
You may find it interesting to compare with compare_exchange_weak which is allowed to fail even though the old value matches. In this case, what you described can happen. On some architectures, compare_exchange is implemented by calling compare_exchange_weak in a loop, retrying every time it fails with a matching old value.
Note that if a compare_exchange_weak(34, 65) fails with an old value of 34, then this is not necessarily non-sensical. When it fails, the history might say 34, 12 and not 34, 65.
Your list of possible outcomes is correct. But this way of thinking works because we're only working with a single atomic variable. It breaks down once more than one atomic variable is involved.
Atomics can behave in ways that would be impossible if you could write down a list of all atomic operations happening in order, where the operations always see the latest value. You must allow atomic operations to see old values to cover all possible behaviors of atomics.