From owner-freebsd-arch@FreeBSD.ORG Mon Oct 4 21:18:21 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 D532F16A4CF for ; Mon, 4 Oct 2004 21:18:21 +0000 (GMT) Received: from duchess.speedfactory.net (duchess.speedfactory.net [66.23.201.84]) by mx1.FreeBSD.org (Postfix) with SMTP id 800BF43D45 for ; Mon, 4 Oct 2004 21:18:21 +0000 (GMT) (envelope-from ups@tree.com) Received: (qmail 4101 invoked by uid 89); 4 Oct 2004 21:18:20 -0000 Received: from duchess.speedfactory.net (66.23.201.84) by duchess.speedfactory.net with SMTP; 4 Oct 2004 21:18:20 -0000 Received: (qmail 4080 invoked by uid 89); 4 Oct 2004 21:18:19 -0000 Received: from unknown (HELO palm.tree.com) (66.23.216.49) by duchess.speedfactory.net with SMTP; 4 Oct 2004 21:18:19 -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 i94LIImt045876; Mon, 4 Oct 2004 17:18:18 -0400 (EDT) (envelope-from ups@tree.com) From: Stephan Uphoff To: John Baldwin In-Reply-To: <200410041657.49278.jhb@FreeBSD.org> References: <1095468747.31297.241.camel@palm.tree.com> <200410041403.06187.jhb@FreeBSD.org> <1096922414.45640.6.camel@palm.tree.com> <200410041657.49278.jhb@FreeBSD.org> Content-Type: text/plain Message-Id: <1096924698.45640.22.camel@palm.tree.com> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.4.6 Date: Mon, 04 Oct 2004 17:18:18 -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 21:18:22 -0000 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. > > 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. 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. Stephan