How can multiple threads (that are waiting on a condition variable) acquire the relevant lock when condition_all() is called?

Question

From theory, a waiting thread (let's say Thread_1) first acquires a mutex, then waits on the condition variable by calling wait(). The call to wait() immediately unlocks the mutex. When the other thread (let's say Thread_2) calls notify(), the waiting thread (Thread_1) is waken up and the same mutex is locked before the wait(..) call returns.

Now let's say multiple threads are waiting on a condition variable at a given time (let's say Thread_1, Thread_2 and Thread_3). Now another thread (Thread_4) calls notify_all(), that will notify all 3 threads that are waiting for the condition variable. When they are waken up, how can all 3 of them lock the mutex, that should happen before the wait(...) call returns? Only one thread (out of the 3 waiting threads) can acquire the mutex. Then what is the purpose of notify_all(), if it can unblock only one thread? What is the difference in results (from waiting threads' point of view) between notify() and notify_all()?

Answer 1

How can all three of them lock the mutex?

They lock it one at a time, just like always.

A wait(...) function could be implemented like this:

def wait(cond_var, mutex):
    tricky_internal_wait(cond_var, mutex)
    lock(mutex)

The tricky_internal_wait(c,m) function would atomically unlock the mutex and block the calling thread on a queue associated with cond_var, but there's no reason why the lock(mutex) call at the end of it needs to be any different from the ordinary lock(mutex).

When the cond_var is notified in the example above, the thread would wake up, and then it would call lock(mutex), and then if some other thread already had locked the mutex, the OS would block the caller on a queue associated with mutex. The caller could not return from the wait() call until it returned from the lock() call, and it could not return from lock() until the mutex became available and the caller acquired it. Just like how lock() always works.

A practical implementation of wait(c,m) probably would do things more efficiently: It probably would move the thread directly from the cond_var queue to the mutex queue without ever waking the thread up if the mutex already was in use by some other thread.

---

Then what is the purpose of notify_all(), if it can unblock only one thread?

It doesn't unblock only one. It unblocks all of them,...

...One-at-a-time.

Suppose that some thread T calls notify_all(cond_var) while threads X, Y, and Z all are awaiting the condition in foobar():

def foobar():
    lock(mutex)
    while condition_is_not_satisfied():
        wait(cond_var, mutex)
    do_some_thing_that_requires_condition_to_be_satisfied()
    unlock(mutex)

Maybe thread Z will be the first to return from the wait() call. It will check again to see that the condition really is satisfied, and then it will do the thing, and then it will unlock the mutex and return from foobar().

Until thread Z unlocks the mutex and returns, threads X and Y will be unable to return from the wait() call.

Maybe after Z unlocks the mutex, the next one to return from the wait() will be X. X will then check to see if the condition is satisfied. Maybe the action of Z means that the condition is not satisifed any longer. In that case, X will wait() again and the wait() call will release the mutex. Or, maybe the condition still is satisifed, and X will do the thing, and explicitly unlock the mutex and return from foobar().

Either way, thread X will release the mutex, and then thread Y will be able to return from the wait() call...

...and so it goes.