When a thread is waiting on some condition, your goal should be to only wake it up if that condition is actually true - that is, the thread really gets to run. In reverse order of badness :
1. Wakeup condition polling. This is the worst and is very common. You're essentially just using
the thread wakeup to say "hey your condition *might* be set, check it yourself".
The suspect code looks something like :
while( ! condition )
these threads can waste a ton of cycles just waking up, checking their condition, then going back to sleep.
One of the common ways to get nasty wake-polling is when you are trying to just wake one thread, but you have to do a broadcast due to the possibility of a missed wakeup (as in the naive semaphore from waitset ).
Of course any usage of cond_var is a wake-poll loop. I really don't like cond_var as an API or a programming pattern. It encourages you to write wakee-side condition checks. Whenever possible, waker-side condition checks are better. (See previous notes on cond vars such as : In general, you should prefer to use the CV to mean "this condition is set" , not "hey wakeup and check your condition").
(ADDENDUM : in fact I dislike cond_var so much I wrote a proposal on an alternative cond_var api ).
Now it's worth breaking this into two sub-categories :
1.A. Wake-polling when it is extremely likely that you get to run immediately.
This is super standard and is not that bad. At root, what's happening here is that under normal conditions, the wakeup means the condition is true and you get to run. The loop is only needed to catch the race where someone stole your wakeup.
For example, the way
semaphore on futex is a classic wake-poll. The core loop is :
if ( try_wait() ) break;
futex_wait( & sem->value, 0 ); // wait if sem value == 0
If there's no contention, you wake from the wait and get to try_wait (dec the count) and proceed. The only
time you have to loop is if someone else raced in and dec'ed the count before you. (see also in that same
post a discussion of why you actually *want* that race to happen, for performance reasons).
The reason this is okay is because the futex semaphore only has to do a wake 1 when it signals. If it had to do a broadcast, this would be a bad loop. (and note that the reason it can do a broadcast is due to the special nature of the futex wait, which ensures that the single thread signal actually goes to someone who needs it!) (see : cbloom rants 08-01-11 - Double checked wait ).
1.B. Wake-polling when it is unlikely that you get to run.
This is the really bad one.
As I've noted previously (
cbloom rants 07-26-11 - Implementing Event WFMO )
this is a common way for people to implement WFMO. The crap implementation basically looks like this :
while ( any events in array not set )
wait on an unset event in array
What this does is any time one of the events in the set triggers, it wakes up all the waiters that are waiting
on it in an array, checks the array, and they go back to sleep.
Obviously this is terrible, it causes bad "thread thrashing" - tons of wakeups and immediate sleeps just to get one thread to eventually run.
2. "Direct Handoff" - minimal wakes. This is the ideal; you only wake a thread when you absolutely know it gets to run.
When only a single thread is waiting on the condition, this is pretty easy, because there's no issue of "stolen wakeups". With multiple threads waiting, this can be tricky.
The only way to really robustly ensure that you have direct handoff is by making the wakeup ensure the condition.
At the low level, you want threading primitives that don't give you unnecessary wakeups. eg. we don't like the pthreads cond_var
that has you call :
as two separate calls, which means you can wake from the condvar and immediately fail to get the mutex and go back to sleep. Prefer a
single call :
which only wakes you when you get a cv signal *and* can acquire the mutex.
At the high level, the main thing you should be doing is *waker* side checks.
eg. to do a good WFMO you should be checking for all-events-set on the *waker* side. To do this you must create a proxy event for the set when you enter the wait, register all the events on the proxy, and then you only signal the proxy when they are all set. When one of them is set, it does the checking. That is, the checking is moved to the signaller. The advantage is that the signalling thread is already running.