From owner-freebsd-arch@FreeBSD.ORG Mon Oct 4 22:27:03 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 676DC16A4D8 for ; Mon, 4 Oct 2004 22:27:03 +0000 (GMT) Received: from duchess.speedfactory.net (duchess.speedfactory.net [66.23.201.84]) by mx1.FreeBSD.org (Postfix) with SMTP id 9863C43D53 for ; Mon, 4 Oct 2004 22:27:02 +0000 (GMT) (envelope-from ups@tree.com) Received: (qmail 13329 invoked by uid 89); 4 Oct 2004 22:27:01 -0000 Received: from duchess.speedfactory.net (66.23.201.84) by duchess.speedfactory.net with SMTP; 4 Oct 2004 22:27:01 -0000 Received: (qmail 13316 invoked by uid 89); 4 Oct 2004 22:27:01 -0000 Received: from unknown (HELO palm.tree.com) (66.23.216.49) by duchess.speedfactory.net with SMTP; 4 Oct 2004 22:27:01 -0000 Received: from [127.0.0.1] (localhost.tree.com [127.0.0.1]) by palm.tree.com (8.12.10/8.12.10) with ESMTP id i94MQxmt046158; Mon, 4 Oct 2004 18:26:59 -0400 (EDT) (envelope-from ups@tree.com) From: Stephan Uphoff To: John Baldwin 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> Content-Type: text/plain Message-Id: <1096928819.45640.65.camel@palm.tree.com> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.4.6 Date: Mon, 04 Oct 2004 18:26:59 -0400 Content-Transfer-Encoding: 7bit cc: Peter Holm cc: Julian Elischer cc: "freebsd-arch@freebsd.org" Subject: Re: scheduler (sched_4bsd) questions X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 04 Oct 2004 22:27:03 -0000 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