Search code examples
catomic

What does it mean that the modification order is not a total order?


Each atomic object has its own associated modification order, which is a total order of modifications made to that object. If, from some thread's point of view, modification A of some atomic M happens-before modification B of the same atomic M, then in the modification order of M, A occurs before B.

Note that although each atomic object has its own modification order, it is not a total order; different threads may observe modifications to different atomic objects in different orders.

Aren't the two bold statements contradictory? I found them on https://en.cppreference.com/w/c/language/atomic and was wondering what exactly is going on now - is it a total order or not? And what exactly is guaranteed now and what isn't?


Solution

  • This is indeed a bad choice of words by cppreference. The important sentence is in fact the last sentence: different threads may observe modifications to different atomic objects in different orders

    So if atomic object 1 has the totally ordered sequence of modifications A B C, and atomic object 2 has the totally ordered sequence D E F, then all threads will see A before C and D before F, but threads may disagree whether A comes before D. Therefore, the set of all modifications {A B D C E F} has no total order.

    But all threads that agree that B comes before E will also agree that A comes before F. Partial orders still give some guarantees.