8

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.

Rick
  • 7,007
  • 2
  • 49
  • 79
  • I read the last sentence as: If one thread called `notify_one()`, then the thread which is woken up started it's waiting before `notify_one()` was called. (It's impossible that a thread is considered which started waiting after.) At this point, there is granted a certain determinism, that normally isn't between threads (without any kind of locking/synchronization). – Scheff's Cat Nov 13 '18 at 17:13
  • 2
    Why is this duplicate ..? I took a glance at those two questions and did not find an direct answer. – Rick Nov 13 '18 at 17:18

1 Answers1

3

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.

Caleth
  • 52,200
  • 2
  • 44
  • 75
  • Thank you very much for this explanation. I would however be keen on reading more about this topic. Do you have any reference to share? – VincentTellier Mar 15 '22 at 14:12