Is there a `notify_one()` queue for `std::condition_variable`s?

Question

Consider the first thread function and global variables:

    std::mutex mut;
    std::condition_variable officer;
    bool firstPlayerIsReady = false;
    bool secondPlayerIsReady = false;

---

void firstPlayer(){
    constexpr auto doIt = true;
    while(doIt)
    {
        std::unique_lock lock{mut};
        auto toContinue = ring();
        secondPlayerIsReady = true;
        firstPlayerIsReady = false;
        officer.notify_one();   //#1
        if(!toContinue) return;
        officer.wait(lock,[=](){ return firstPlayerIsReady;});
    }
}

It calls some ring and ring() returns a continuation condition; It then updates readiness values for each thread in the next loop;

Consider the next thread:

void secondPlayer(){
    constexpr auto doIt = true;
    while(doIt)
    {
        auto period = std::chrono::seconds(5);
        std::this_thread::sleep_for(period);

        std::unique_lock lock{mut};   //#2
        officer.wait(lock,[this](){ return secondPlayerIsReady;});
        auto toContinue = ring();
        firstPlayerIsReady = true;
        secondPlayerIsReady = false;
        officer.notify_one();
        if(!toContinue) return;
    }
}

This thread wait for 5 seconds and after are locked with wait( ) until the first thread calls the notify_one( ); Further, similar to the first thread.

A priori, the line with #1 tag was executed earlier than the line with #2 tag, therefore the notification was sent earlier than the second thread was locked. The question is - Is there a notify_one ( ) queue? Otherwise, the notification wasn't sent, obviously.

Humbert

Any reason for constexpr volatile auto doIt? while that expression is valid, the volatile qualifier is useless in the context of your code. secondly you are not actually protecting concurrent accesses to firstPlayerIsReady, likewise the other – Pyromania

@WhiZTiM, thank you, I've fixed it. – Humbert

See also: what if notify() is called before wait()? – Camilla

Answer 1

There is no queue. If one thread calls notify_one and there are no other threads waiting it will not do anything.

That's why you have the predicate, in your example

officer.wait(lock,[this](){ return secondPlayerIsReady;});

So when a thread calls this, if secondPlayerIsReady is true, then the thread will not wait at all, but just skip past this line.

So calling notify_one too "early" is not a problem as long as the flag is set properly. Just remember that the flag needs to be protected by the mutex when modified.

Peatroy

Your answer implies that the boolean predicate lambda is tested before wait() puts the thread to sleep. I always thought it was the other way around: that the wait() method put the thread to sleep and then only tested the predicate each time after waking up. If the predicate is true, then it returns from the wait function. So, which is it? Is the predicate tested for true before sleeping, after sleeping, or both? – Camilla

If the mutex can be aquired, it can check the condition before going to sleep. I'm not sure if it's required to or if that's an implementation detail, but it's clearly stated here. – Peatroy

I finally got it! Yaay. :) I wrote this to put it in my own words. – Camilla

Answer 2

@super is exactly right, but I was having a really hard time understanding this concept, so I wanted to put it into my own words and add my own answer as well. Here goes:

No, std::condition_variables do not have an underlying notification queue...

...but that doesn't really matter at all! So long as you use a boolean predicate, an early notification (by a producer) which is sent before the consumer hits the wait() function will not be missed by the consumer!

That is because this call with the lambda function boolean predicate as the 2nd parameter:

cv.wait(lock, []() { 
    return sharedData.isNewData; 
});

...is exactly identical to this while loop:

while (sharedData.isNewData == false) // OR: `while (!sharedData.isNewData)`
{
    cv.wait(lock);
}

...and the while loop's cv.wait(lock); line is only called if the predicate is false in the first place!

In detail:

There is NOT an underlying notification queue, nor counter, nor boolean flag. Rather, the boolean predicate we check is the flag! And, it is checked both at the start of the wait() function, before sleeping, as well as at the end of the wait() function, after sleeping and each time the thread wakes up. The wait() function only sleeps the thread if the predicate starts out false, and it only exits the wait() function by returning from it when the predicate is true. Look at that while loop version just above and this will become perfectly clear.

So, if the producer thread sets a shared predicate to true, and then sends a my_condition_variable.notify_one() call, if the consumer thread is not already waiting, it does not receive that notification. BUT, it doesn't really matter! So long as the consumer thread is either using the 2-parameter wait() call (with the 2nd parameter being a boolean predicate), OR using the while loop predicate-checking technique, then once the consumer thread hits the wait() call (or while loop), the predicate will be seen as being true, and the whole while block and waiting sleep will be skipped entirely, and the consumer will go ahead and run instantly as though it had received the notify_one() notification while waiting! When the predicate is used, the end result is the same as though the condition variable did have an underlying notification queue (or flag) of length one.

See:

1. https://en.cppreference.com/w/cpp/thread/condition_variable/wait - it states that this templated function:

   template< class Predicate >
   void wait( std::unique_lock<std::mutex>& lock, Predicate stop_waiting );
   

   is:

   Equivalent to

   while (!stop_waiting()) {
       wait(lock);
   }
   

2. Answer by @super, who set me on the right track to finally understand this myself

See also

1. I documented the above information, with detailed full examples of std::condition_variable and how to use it in a producer-consumer thread-safe queue in my eRCaGuy_hello_world repo here: std_mutex_vs_std_lock_guard_vs_std_unique_lock_vs_std_scoped_lock_README.md, and on my personal website here: https://gabrielstaples.com/cpp-mutexes-and-locks/.

Camilla