Why does a condition variable's wait() release the associated mutex before blocking and reacquire it before returning?

Question

Stallings' Operating System book says about condition variable in Solaris,

A condition variable is used to wait until a particular condition is true. Condition variables must be used in conjunction with a mutex lock. This implements a monitor of the type illustrated in Figure
6.14 . The primitives are as follows:

cv_wait() Blocks until the condition is signaled 
cv_signal() Wakes up one of the threads blocked in cv_wait()
cv_broadcast() Wakes up all of the threads blocked in cv_wait()

cv_wait() releases the associated mutex before blocking and reacquires it before returning. Because reacquisition of the mutex may be blocked by other threads waiting for the mutex, the condition that caused the wait must be retested. Thus, typical usage is as follows:

mutex_enter(&m)
* * 
while (some_condition) { 
  cv_wait(&cv, &m); 
}
* * 
mutex_exit(&m);

This allows the condition to be a complex expression, because it is protected by the mutex.

Operating Systems: Three Easy Pieces says about condition variable:

We will often refer to these as wait() and signal() for simplicity. One thing you might notice about the wait() call is that it also takes a mutex as a parameter; it assumes that this mutex is locked when wait() is called. The responsibility of wait() is to release the lock and put the calling thread to sleep (atomically); when the thread wakes up (after some other thread has signaled it), it must re-acquire the lock before returning to the caller. This complexity stems from the desire to prevent certain race conditions from occurring when a thread is trying to put itself to sleep.

In Operating System Concepts, a signal-and-wait condition variable is implemented as:

We can now describe how condition variables are implemented as well. For each condition x, we introduce a semaphore x sem and an integer variable x count, both initialized to 0. The operation x.wait() can now be implemented as

x count++;
if (next count > 0)
signal(next);
else
signal(mutex);
wait(x sem);
x count--;

The operation x.signal() can be implemented as

if (x count > 0) {
next count++;
signal(x sem);
wait(next);
next count--;
}

This implementation is applicable to the definitions of monitors given by both Hoare and Brinch-Hansen.

Questions:

1. Why is it that "cv_wait() releases the associated mutex before blocking and reacquires it before returning" in the first book?

   What are the race conditions in "This complexity stems from the desire to prevent certain race conditions from occurring when a thread is trying to put itself to sleep" in the second book?

2. Why does the implementation of wait() in the third book not performing "releases the associated mutex before blocking and reacquires it before returning" in the first book? Is this a mistake in the third book, or is release and require not needed for a Hoare's monitor (signal-and-wait), but only needed for a Mesa's monitor (signal and continue)?

3. Why is it that "Because reacquisition of the mutex may be blocked by other threads waiting for the mutex, the condition that caused the wait must be retested" in the first book?

Thanks.

Answer 1

First of all, good work on cross-referencing this stuff across several books.

Now, all of this proceeds from understanding what the condition variable is used for in practice. And, I guess, how multi-core and multi-processor machines work. Trying to learn it in a vacuum from books describing practical solutions to problems you have never seen, is very hard.

These books aren't defining self-contained mathematical structures proceeding from axioms and pure logic. They're describing practical systems used to fix real-world problems.

If something isn't clear when you read the book (and good work on cross-referencing several books, by the way), you can always try thinking

What would break if this was different?

So, without further ado:

1. Why is it that "cv_wait() releases the associated mutex before blocking and reacquires it before returning" ...?

   Well, what would break if it didn't?

   1. You're waiting for some condition to be satisfied, that is not currently satisfied.
   2. In order for you to test the condition, the mutex must be held, because the condition is something shared with other threads.
   3. That means the other thread(s) must lock the same mutex when altering whatever shared state is associated with the condition (since unless everyone uses the same lock to protect the same data, there isn't any protection).
   4. They can't do that while you're keeping the mutex locked. So, if they're ever to satisfy the condition you are waiting for, you must unlock the mutex while you wait.
   5. When you wake up, you have to check the condition holds. It's possible that something changed again between one thread signalling and the waiter being scheduled.
   6. To check the condition, the mutex must be locked, for exactly the same reason as step 3

   So, what would break is that you'd go to sleep, still holding the mutex locked, with the condition un-satisfied - and therefore make it impossible for any other thread to satisfy the condition. You can see this just by reading through the code step-by-step.

2. Why does the implementation of wait() in the third book ...

   Can't tell you. That's pseudocode, and I don't have a copy of the book to tell me what semantics are defined for it. All those increments should be protected anyway, so either the whole thing is locked (and there is an unlock/relock hidden in one of the function calls), or that pseudocode simply doesn't address synchronization.

3. Why is it that "Because reacquisition of the mutex may be blocked by other threads waiting for the mutex, the condition that caused the wait must be retested"

   Again, why do you think?

   What does it mean if the sleeping thread, when it wakes up and tries to re-lock the mutex, is blocked because another thread already holds that mutex?

   Well, one thing it might mean is that another thread is currently changing the data protected by that mutex, right? And that change might change the condition back to false, even though we expect it was true when the signal woke us up?

   Some time elapses between calling signal() and the sleeping thread actually starting to execute, and other CPU cores can be doing their own work in that interval.