Understanding Condition Variables - Isn't there always spin-waiting "somewhere"?

Question

I am going to explain my understanding of this OS construct and appreciate some polite correction.

I understand thread-safety clearly and simply.

If there is some setup where

• X: some condition
• Y: do something

and

if X
   do Y

is atomic, meaning that if at the exact moment in time

• doing Y
• not X

there is some problem.

By my understanding, the lowest-level solution of this is to use shared objects (mutexes). As an example, in the solution to the "Too Much Milk" Problem

    Thead A     |     Thread B
-------------------------------------
leave Note A    |  leave Note B
while Note B    |  if no Note A 
  do nothing    |    if no milk
if no milk      |      buy milk
  buy milk      |  remove Note B
remove Note A   |

Note A and Note B would be the shared objects, i.e. some piece of memory accessible by both threads A and B.

This is can be generalized (beyond milk) for 2-thread case like

    Thead A     |     Thread B
-------------------------------------
leave Note A    |  leave Note B
while Note B    |  if no Note A 
  do nothing    |    if X
if X            |      do Y
  do Y          |  remove Note B
remove Note A   |

and there is some way to generalize it for the N-thread case (so I'll continue referring to the 2-thread case for simplicity).

Possibly incorrect assumption #1: This is the lowest-level solution known (possible?).

Now one of the defficiencies of this solution is the spinning or busy-wait

while Note B
  do nothing

because if the do Y is an expensive task then the thread scheduler will keep switching to Thread A to perform this check, i.e. the thread is still "awake" and using processing power even when we "know" its processing is to perform a check that will fail for some time.

The question then becomes: Is there some way we could make Thread A "sleep", so that it isn't scheduled to run until Note B is gone, and then "wake up"???

The Condition Variable design pattern provides a solution and it built on top of mutexes.

Possibly incorrect assumption #2: Then, isn't there still some spinning under the hood? Is the average amount of spinning somehow reduced?

I could use a logical explanation like only S.O. can provide ;)

Answer 1

Isn't there still some spinning under the hood.

No. That's the whole point of condition variables: It's to avoid the need for spinning.

An operating system scheduler creates a private object to represent each thread, and it keeps these objects in containers which, for purpose of this discussion, we will call queues.

Simplistic explanation:

When a thread calls condition.await(), that invokes a system call. The scheduler handles it by removing the calling thread from whatever CPU it was running on, and by putting its proxy object into a queue. Specifically, it puts it into the queue of threads that are waiting to be notified about that particular condition.

There usually is a separate queue for every different thing that a thread could wait for. If you create a mutex, the OS creates a queue of threads that are waiting to acquire the mutex. If you create a condition variable, the OS creates a queue of threads that are waiting to be notified.

Once the thread's proxy object is in that queue, nothing will wake it up until some other thread notifies the condition variable. That notification also is a system call. The OS handles it (simplest case) by moving all of the threads that were in the condition variable's queue into the global run queue. The run queue holds all of the threads that are waiting for a CPU to run on.

On some future timer tick, the OS will pick the formerly waiting thread from the run queue and set it up on a CPU.

---

Extra credit:

Bad News! the first thing the thread does after being awakened, while it's still inside the condition.await() call, is it tries to re-lock the mutex. But there's a chance that the thread that signalled the condition still has the mutex locked. Our victim is going to go right back to sleep again, this time, waiting in the queue for the mutex.

A more sophisticated system might be able to optimize the situation by moving the thread directly from the condition variable's queue to the mutex queue without ever needing to wake it up and then put it back to sleep.

Answer 2

yes, on the lowest, hardware level instructions like Compare-and-set, Compare-and-swap are used, which spin until the condition is met, and only then make set (assignment). This spin is required each time we put a thread in a queue, be it queue to a mutex, to condition or to processor.

Answer 3

Then, isn't there still some spinning under the hood? Is the average amount of spinning somehow reduced?

That's a decision for the implementation to make. If spinning works best on the platform, then spinning can be used. But almost no spinning is required.

Typically, there's a lock somewhere at the lowest level of the implementation that protects system state. That lock is only held by any thread for a tiny split second as it manipulates that system state. Typically, you do need to spin while waiting for that inner lock.

A block on a mutex might look like this:

1. Atomically try to acquire the mutex.
2. If that succeeds, stop, you are done. (This is the "fast path".)
3. Acquire the inner lock that no thread holds for more than a few instructions.
4. Mark yourself as waiting for that mutex to be acquired.
5. Atomically release the inner lock and set your thread as not ready-to-run.

Notice the only place that there is any spinning in here is in step 3. That's not in the fast path. No spinning is needed after the call in step 5 does not return to this thread until the lock is conveyed to this thread by the thread that held it.

When a thread releases the lock, it checks the count of threads waiting for the lock. If that's greater than zero, instead of releasing the lock, it acquires the inner lock protecting system state, picks one of the threads recorded as waiting for the lock, conveys the lock to that thread, and tells the scheduler to run that thread. That thread then sees step 5 return from its call with now holding the lock.

Again, the only waiting is on that inner lock that is used just to track what thread is waiting for what.