Re: [boost] win32 mutex and condition variable algorithms

From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2006-09-20 06:58:55

Anthony Williams wrote:
[...]
> 
> Alexander Terekhov <terekhov_at_[hidden]> writes:
> 
> > Anthony Williams wrote:
> >>
> >> Alexander Terekhov <terekhov_at_[hidden]> writes:
> >>
> >> > Anthony Williams wrote:
> >> > [...]
> >> >> If A always takes the slow path when we have another waiter, then we give
> >> >> the OS more scope for ensuring that both A and B get a fair stab.
> >> >
> >> > That depends on the definition of "fair". Suppose you're running on
> >> > uniprocessor and that A is a higher priority thread than B... why
> >> > should it yield to B? Under POSIX rules (which define priority
> >> > scheduling for scheduling allocation domains of size 1, aka
> >> > "uniprocessor" domains), it shall not. With your handoff logic, A
> >> > will yield to B.
> >>
> >> Not necessarily. Both A and B will wait for the semaphore. If A is higher
> >
> > Suppose that B is already waiting on the semaphore. If that is not the
> > case, you'll get the same "starvation" scenario as with more efficient
> > lock but with added overhead of self consuming semaphore signal.
> >
> > [...]
> >> What if B is higher priority than A?
> >
> > Then A will yield to B (waiting for the semaphore) on unlock/slow-path
> > (efficient lock) and B will grab the lock (freed by A prior to
> > signaling).
> 
> You are assuming that B will wake immediately upon A's release of the

I'm assuming that A and B are in the same scheduling allocation domain 
of size 1 (i.e. they compete for the processor cycles and can't make
progress in parallel). POSIX defines neither cross-domain scheduling 
policy nor scheduling policy for domains of size > 1. Note that with 
scheduling allocation domain higher than 1, you also wouldn't want to 
hand ownership to the highest priority waiter because there might be 
any number of threads of higher priority than that waiter, any of 
which might want the lock "right now" (before unblocked thread is 
scheduled to run). So you just need to unblock and let unblocked 
thread compete for lock ownership without handoff. It is lack of 
competition for lock ownership after waiting that is the problem.

regards,
alexander.