Date: Mon, 4 Oct 2004 17:35:39 -0400 From: John Baldwin <jhb@FreeBSD.org> To: freebsd-arch@FreeBSD.org Cc: Stephan Uphoff <ups@tree.com> Subject: Re: scheduler (sched_4bsd) questions Message-ID: <200410041735.39472.jhb@FreeBSD.org> In-Reply-To: <1096924698.45640.22.camel@palm.tree.com> References: <1095468747.31297.241.camel@palm.tree.com> <200410041657.49278.jhb@FreeBSD.org> <1096924698.45640.22.camel@palm.tree.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Monday 04 October 2004 05:18 pm, Stephan Uphoff wrote:
> On Mon, 2004-10-04 at 16:57, John Baldwin wrote:
> > 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.
>
> Yep.
Actually, note that they will stop spinning when they notice the owner change
currently, so you could still use the lock == MTX_CONTESTED trick to get the
adaptive waiters to stop spinning. Actually, giving the lock away explicitly
will also make them stop spinning. You just might not pick the absolute best
candidate to give it 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.
>
> Not with the right locking.
Err, if there is a solution for this case then it will fix the adaptive case
as well; they are the same problem.
> They will just donate their priority to B.
> We could improve this by implement "lock stealing" where another thread
> with higher priority steals the lock before B becomes aware that he owns
> it.
The problem is that there is still a window before they can donate their
priority to B, which is the same window as you mentioned before, though there
is a slight difference in that these threads are executing and might have a
shot at the lock. If they don't get it they will be waiting on the turnstile
lock before they can lend their priority to the new owner.
So I guess what you would like to do is in propigate_priority(), when the
thread pointer is NULL, you want to take the highest priority waiter and give
the lock to it. Of course, there might not be any waiters in the adaptive
case, so you can never fully eliminate the race. I wouldn't mind turning
MUTEX_WAKE_ALL on by default instead if that makes a difference.
--
John Baldwin <jhb@FreeBSD.org> <>< http://www.FreeBSD.org/~jhb/
"Power Users Use the Power to Serve" = http://www.FreeBSD.org
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200410041735.39472.jhb>