Date: Mon, 04 Oct 2004 18:26:59 -0400 From: Stephan Uphoff <ups@tree.com> To: John Baldwin <jhb@FreeBSD.org> Cc: "freebsd-arch@freebsd.org" <freebsd-arch@FreeBSD.org> Subject: Re: scheduler (sched_4bsd) questions Message-ID: <1096928819.45640.65.camel@palm.tree.com> In-Reply-To: <200410041735.39472.jhb@FreeBSD.org> References: <1095468747.31297.241.camel@palm.tree.com> <200410041657.49278.jhb@FreeBSD.org> <1096924698.45640.22.camel@palm.tree.com> <200410041735.39472.jhb@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Mon, 2004-10-04 at 17:35, John Baldwin wrote:
> 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.
No - I would like to eliminate the case where propagate_priority finds
a NULL pointer by giving the thread A that is releasing the mutex the
responsibility to assign both mutex and turnstile to B.
( and even recalculate B's priority should the implementation requires -
but I doubt it)
A runs in a critical region while this is going on and the relevant
turnstile locks are held.
B would just wake up and find out that it owns the mutex.
As an optimization one could for a higher priority thread later steal
the mutex from B before it gets a chance to run.
Stephan
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?1096928819.45640.65.camel>