How exactly does the wait function work (in regards to condition variables)

Question

I am a little bit confused on my understanding of how condition variables work (in regards to shared data concurrent access)

The following is pseudo C code to illustrate my current problem

// Thread 1: Producer
void cakeMaker()
{
    lock(some_lock);
    while(number_of_cakes == MAX_CAKES)
        wait(rack_has_space);

    number_of_cakes++;

    signal(rack_has_cakes);
    unlock(some_lock);
}

// Thread 2: Consumer
void cakeEater()
{
    lock(some_lock);
    while(number_of_cakes == 0)
        wait(rack_has_cakes);

    number_of_cakes--;

    signal(rack_has_space);
    unlock(some_lock);
}

Lets say we currently have number_of_cakes = 0, so Thread 2 is currently stuck on wait(rack_has_cakes). Thread 1 runs and increments number_of_cakes by 1. Then it calls signal(rack_has_cakes) - this wakes up Thread 2, unfortunately Thread 2 wakes up before Thread 1 calls unlock(some_lock), so it goes back to sleep again and the signal has been missed.

I am very confused about the inner workings of wait and signal? What exactly happens with them? Are they like some boolean flag that gets automatically set to 1 when we call signal and set to 0 again when wait succeeds? What is going on?

Can someone run me through step by step 1 iteration of the above code, heavy emphasis on what happens during signal and wait?

Answer 1

thread 2 wakes up before Thread 1 calls unlock(some_lock), so it goes back to sleep again and the signal has been missed.

No, that's not how it works. I will use C++ std::condition_variable for my cite, but POSIX threads, and most run-of-the-mill implementation of mutexes and condition variables work the same way. The underlying concepts are the same.

Thread 2 has the mutex locked, when it starts waiting on a condition variable. The wait() operation unlocks the mutex and waits on the condition variable atomically:

Atomically releases lock, blocks the current executing thread, and adds it to the list of threads waiting on *this.

This operation is considered "atomic"; in other words, indivisible.

Then, when the condition variable is signaled, the thread re-locks the mutex:

When unblocked, regardless of the reason, lock is reacquired and wait exits.

The thread does not "go back to sleep" before the other thread "calls unlock". If the mutex has not yet been unlocked: when the thread wakes up upon being signaled by a condition variable, the thread will always wait until it succeeds in locking the mutex again. This is unconditional. When wait() returns the mutex is still locked. Then, and only then, the wait() function returns. So, the sequence of events is:

1. One thread has the mutex locked, sets some counter, variable, or any kind of mutex-protected data to the state that the other thread is waiting for. After doing so the thread signals the condition variable, and then unlocks the mutex at its leisure.

2. The other thread has locked the mutex before it wait()s on the condition variable. One of wait()'s prerequisites is that the mutex must be locked before wait()ing on the linked condition variable. So, the wait() operation unlocks the mutex "atomically". That is, there is no instance when the mutex is unlocked, and the thread is not yet waiting on the condition variable. When wait() unlocks the mutex, you are guaranteed that the thread will be waiting, and it will wake up. You can take it to the bank.

3. Once the condition variable is signaled, the wait()ing thread does not return from wait() until it can re-lock the mutex. Having received a signal from the condition variable is just the first step, the mutex must be locked again, by thread, in the final step of the wait() operation. Which, of course, only happens after the signaling thread unlocks the mutex.

When a thread gets signaled by a condition variable, it will return from wait(). But not immediately, it must wait until the thread locks the mutex again, however long it takes. It will not go "back to sleep", but wait until it has the mutex locked again, and then return. You are guaranteed that a received condition variable signal will cause the thread to return from wait(), and the mutex will be re-locked by the thread. And because the original unlock-then-wait operation was atomic, you are guaranteed to receive the condition variable signal.