scheduler (sched_4bsd) questions

[Stephan Uphoff]

On Mon, 2004-10-04 at 14:03, John Baldwin wrote:
> On Monday 04 October 2004 01:34 pm, Stephan Uphoff wrote:
> > On Mon, 2004-10-04 at 11:31, John Baldwin wrote:
> > > On Friday 01 October 2004 12:13 am, Stephan Uphoff wrote:
> > > > On Wed, 2004-09-29 at 18:14, Stephan Uphoff wrote:
> > > > > I was looking at the MUTEX_WAKE_ALL undefined case when I used the
> > > > > critical section for turnstile_claim().
> > > > > However there are bigger problems with MUTEX_WAKE_ALL undefined
> > > > > so you are right - the critical section for turnstile_claim is pretty
> > > > > useless.
> > > >
> > > > Arghhh !!!
> > > >
> > > > MUTEX_WAKE_ALL is NOT an option in GENERIC.
> > > > I recall verifying that it is defined twice. Guess I must have looked
> > > > at the wrong source tree :-(
> > > > This means yes - we have bigger problems!
> > > >
> > > > Example:
> > > >
> > > > Thread A holds a mutex x contested by Thread B and C and has priority
> > > > pri(A).
> > > >
> > > > Thread C holds a mutex y and pri(B) < pri(C)
> > > >
> > > > Thread A releases the lock wakes thread B but lets C on the turnstile
> > > > wait queue.
> > > >
> > > > An interrupt thread I tries to lock mutex y owned by C.
> > > >
> > > > However priority inheritance does not work since B needs to run first
> > > > to take ownership of the lock.
> > > >
> > > > I is blocked :-(
> > >
> > > Ermm, if the interrupt happens after x is released then I's priority
> > > should propagate from I to C to B.
> >
> > There is a hole after the mutex x is released by A - but before B can
> > claim the mutex. The turnstile for mutex x is unowned and interrupt
> > thread I when trying to donate its priority will run into:
> >
> > 	if (td == NULL) {
> > 			/*
> > 			 * This really isn't quite right. Really
> > 			 * ought to bump priority of thread that
> > 			 * next acquires the lock.
> > 			 */
> > 			return;
> > 		}
> >
> > So B needs to run and acquire the mutex before priority inheritance
> > works again and does not get a priority boost to do so.
> >
> > This is easy to fix and MUTEX_WAKE_ALL can be removed again at that time
> > - but my time budget is limited and Peter has an interesting bug left
> > that has priority.
> 
> Isn't this handled by the mtx_lock == MTX_CONTESTED case that calls into 
> turnstile_claim() which bumps the priority of the new owner to the highest 
> priority waiting thread?  I guess this won't happen until B gets to run again 
> which is the problem.  You don't know which thread is going to get the lock, 
> so what do you do?  You don't even have a way to get to the threads that you 
> might have just woken up.

The solution is for A not to release the lock but to re-assign it to B.
However I have the feeling there will be some (bad?) interaction with
adaptive mutexes and did not have time to think about it.
 
> BTW, Solaris uses MUTEX_WAKE_ALL by default, but for performance reasons.  It 
> is a kernel option because the idea was to benchmark it both ways and then 
> choose the default based on those numbers.  It's off by default as the 
> wake-one was the original behavior.  I'm pretty sure BSD/OS has this same 
> issue.