Re: [boost] win32 mutex and condition variable algorithms

From: Peter Dimov (pdimov_at_[hidden])
Date: 2006-09-20 07:18:35

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.

As far as I know, most contemporary mutexes do the same, they give priority 
to thread A not only because it can take the fast path, but also because (a) 
its cache is hot and (b) it's better to minimize context switches.