Re: [Boost-users] [Boost.Thread] Scheduling

From: Zeljko Vrba (zvrba_at_[hidden])
Date: 2008-08-11 15:31:08

On Mon, Aug 11, 2008 at 06:27:05PM +0200, Ruediger Berlich wrote:
> 
> first of all, thanks for your answer!
> 
Thanks to Patrick and you for questioning my judgement :-)

First, the shorter part, about the book: "PThreads Primer: A Guide To
Multithreaded Programming".  If you search google for "pthreads primer"
(without the quotes), you might get lucky :-)

I haven't read the whole of it, but the table of contents indicates that it's
quite comprehensive; among other stuff it has a section on scheduling from
which I quote:

"There are times when you will want to deal with scheduling directly, but those
times are few and far between for any of the libraries. If you find yourself
thinking about this a lot, you're probably doing something wrong."

Other suggested reading is an article by Per Brinch Hansen:
"Concurrent Programming Concepts"

> 
> http://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html
> 
> And Anthony writes "By rewriting the function so that the notification comes
> after the mutex is unlocked, the waiting thread will be able to acquire the
> mutex without blocking"
> 
I feel uneasy about this, because if you have three threads operating on the
same queue, the following might happen:

A: wait_and_pop; sleeps and unlocks the mutex 
B: push; unlocks the mutex, gets preempted by C
C: wait_and_pop: mutex is unlocked; manages to pop the item, making the stack
   empty
B: gets scheduled; signals the condvar; A gets a spurious wakeup

Turns out that this "optimization" is not an optimization after all -- short
mutex contention need not lead to sleep, while spurious wakeup most certainly
will induce an unnecessary context switch.  Anyway, this is premature
optimization.

Even worse:

A: push; unlock; gets preempted
B: wait_and_pop: succeeds, making the queue empty; unlocks the mutex
A: gets scheduled again, notifies the condvar which has no waiters
C: wait_and_pop: acquires mutex, sleeps on the condvar

Tadam!  A signal got lost.  In this example it might not seem as a big deal,
but I could probably think of a slightly more complex example where it might
matter..

And signalling on was_empty is actually bad design, IMHO.  That boolean should
be substituted by an integer "nwaiters" which would be incremented before
wait(), and decremented just before wait_and_pop returns.  Similarly, the
signal should be sent when nwaiters > 0 (Having the above boolean is hardly
better than unconditional signaling; even though the stack was empty, there's
no guarantee that there are any waiters there.) 

> 
> In order to reach the part where the notification happens, the function must
> have locked the mutex first (and unlocked it right before the
>
Actually, I think that your reasoning is correct in this particular case.