Please see the following code brought from http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4507.pdf, page 12:
using namespace std::experimental::parallel;
std::atomic<int> x = 0;
int a[] = {1,2};
for_each(par, std::begin(a), std::end(a), [&](int n) {
x.fetch_add(1, std::memory_order_relaxed);
// spin wait for another iteration to change the value of x
while (x.load(std::memory_order_relaxed) == 1) { }
});
There is a comment attached in this example:
The above example depends on the order of execution of the iterations, and is therefore undefined (may deadlock).
But I can't see why it may lead to a deadlock. As I understood, although the memory order is specified as std::memory_order_relaxed, this is only about the timing a thread sees some changes made by another thread, so eventually (after a possibly unbounded amount of time) that changes should be anyway noticed by the reading thread.
Can someone explain? Thank you!
The reason the example code can deadlock has nothing to do with the use of memory_order_relaxed.
A change to an atomic variable will become visible to another core and if it does not (according to the standard it should become visible), it is not related to memory orderering which is only used to specify how other memory operations are ordered with respect to the atomic operation.
The example given in the document the link refers to can deadlock because apparently it is not guaranteed that the execution is truly concurrent. In a later draft (N4640), the text has been revised:
... depends on the order of execution of the iterations, and will not terminate if both iterations are executed sequentially on the same thread of execution.
And that is what this is all about; If both iterations are executed sequentially, the first keeps spinning on a value that will never change.