Re: [boost] win32 mutex and condition variable algorithms

From: David Abrahams (dave_at_[hidden])
Date: 2006-09-21 10:51:07

"Peter Dimov" <pdimov_at_[hidden]> writes:

> David Abrahams wrote:
>> "Peter Dimov" <pdimov_at_[hidden]> writes:
>>
>>> Anthony Williams wrote:
>>>
>>>> The case given in Alexander's email above is:
>>>>
>>>>    A: lock [lockcount == 0]
>>>>    B: lock [lockcount == 1, slow path]
>>>>    A: unlock [lockcount == 0, slow path/post sema]
>>>>    A: lock - [lockcount == 1, slow path]
>>>>
>>>> He claims that the second A: lock takes the slow path, when it could
>>>> have taken the fast path because the lock is free. I disagree. The
>>>> lock is NOT free, since B is waiting on it. If A can take the fast
>>>> path here, that's opening the door for B to be starved.
>>>
>>> This is correct. The mutex does not guarantee fairness (for the above
>>> definition of fairness) at the expense of performance. It is indeed
>>> true that in heavily contended scenarios thread A can finish well
>>> ahead of thread B; however, the total time taken by threads A+B can
>>> be (and is) significantly less than that with the "fairer" CS design.
>>
>> Probably dumb question: does this reasoning apply when A and B need to
>> run "continuously" (e.g. in a server)?
>
> I think that it does, because A and B are roles, not permanent labels. At 
> the last lock above, A is the currently running thread; B is a thread that 
> is currently blocked on the mutex. Since the scheduler distrubutes the 
> "currently running" role among the threads based on its notion of fairness, 
> a synchronization primitive that favors the currently running thread is as 
> fair as the scheduler in the long run.

I get it: A fair scheduler will force context switches at arbitrary
points (e.g. on some timer interval) anyway, so there's no point in
_encouraging_ an expensive context switch where access to resources
needs to be arbitrated.

Now that I said it so simply, I buy 100% into the arguments you and
Alexander have been putting forth... so I must be missing something
:).  Nothing in threading is supposed to be simple.

OK, so here's what I think I missed: B is blocking on a resource.  The
scheduler only distributes the running role among the ready threads.
If B never becomes ready, it starves.  The only way B can become ready
is if A releases its lock to the system, so I guess the question is,
does A's unlock actually move B into the ready state, or at least
cause the scheduler to try to ready B in its next timeslice?

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com