What does "a single total order" mean in std::notify_one()?

Question

I have read Concurrency: Atomic and volatile in C++11 memory model and How std::memory_order_seq_cst works, it doesn't help much and answer my question directly.

---

From https://en.cppreference.com/w/cpp/thread/condition_variable/notify_one:

The effects of notify_one()/notify_all() and each of the three atomic parts of wait()/wait_for()/wait_until() (unlock+wait, wakeup, and lock) take place in a single total order that can be viewed as modification order of an atomic variable: the order is specific to this individual condition_variable. This makes it impossible for notify_one() to, for example, be delayed and unblock a thread that started waiting just after the call to notify_one() was made.

What does it mean by saying "take place in a single total order"? How is this related to the next sentence "This makes it impossible ..... was made."? (It seems that it's telling a cause and effect).

I read it word by word more than 10 times and don't understand what it's saying.. Definition of "total order" from Wikipedia can't help much.

Answer 1

What does it mean by saying "take place in a single total order"?

It means that every thread sees same sequence of operations. As an example, using multiple non-atomic variables, thread C can see the changes to int a caused by thread A, before it sees changes to int b caused by thread B, while thread D sees those of B before A. There are multiple incompatible timelines of which events occur before others, potentially every thread disagreeing with another. Without synchronisation mechanisms (like std::condition_variable) it can be impossible to prevent unwanted system behaviours.

A total order means that every element can be compared to every other element (contrast a partial order, where some pairs of elements are incomparable). In this case, there exists a timeline of events. It is single in that all threads agree on it.

How is this related to the next sentence "This makes it impossible for notify_one() to, for example, be delayed and unblock a thread that started waiting just after the call to notify_one() was made."?

Because all threads agree on the order that things happen, you can't anywhere observing an effect preceding it's cause.