scheduler (sched_4bsd) questions

[John Baldwin]

On Monday 04 October 2004 04:40 pm, Stephan Uphoff wrote:
> 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.

Yes, for adaptive mutexes this breaks because you don't know who is adaptively 
spinning on it to compare their priorities to know who to give the lock to.  
Threads on other CPUs that are trying to acquire the lock at the same time 
have the same problem even w/o adaptive mutexes.

-- 
John Baldwin <jhb at FreeBSD.org>  <><  http://www.FreeBSD.org/~jhb/
"Power Users Use the Power to Serve"  =  http://www.FreeBSD.org