From owner-freebsd-hackers@FreeBSD.ORG Wed Jan 18 14:31:40 2006 Return-Path: X-Original-To: freebsd-hackers@freebsd.org Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 69DCE16A41F for ; Wed, 18 Jan 2006 14:31:40 +0000 (GMT) (envelope-from deischen@freebsd.org) Received: from mail.ntplx.net (mail.ntplx.net [204.213.176.10]) by mx1.FreeBSD.org (Postfix) with ESMTP id 021D243D45 for ; Wed, 18 Jan 2006 14:31:39 +0000 (GMT) (envelope-from deischen@freebsd.org) Received: from sea.ntplx.net (sea.ntplx.net [204.213.176.11]) by mail.ntplx.net (8.13.5/8.13.5/NETPLEX) with ESMTP id k0IEVcBU011508; Wed, 18 Jan 2006 09:31:38 -0500 (EST) Date: Wed, 18 Jan 2006 09:31:38 -0500 (EST) From: Daniel Eischen X-X-Sender: eischen@sea.ntplx.net To: rookie@gufi.org In-Reply-To: <3bbf2fe10601180138m3a5ab67cx@mail.gmail.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Virus-Scanned: by AMaViS and Clam AntiVirus (mail.ntplx.net) Cc: freebsd-hackers@freebsd.org Subject: Re: How priority propagation works on read/write lock? X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: Daniel Eischen List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 18 Jan 2006 14:31:40 -0000 On Wed, 18 Jan 2006, rookie wrote: > >> This approach fails beacause you need to propagate priority for any > blocking > >> thread for any owners (if needed). > > > I'm not sure I follow -- got a simple example? > > A writer won't be able to get the write lock until _all_ of the > > current read lock owners have released the lock. It doesn't > > matter which of the readers you propagate to, eventually all > > of them will have their priority propagated. > > > > On a single CPU system, there is no advantage to propagating > > priority to all of the current readers because only one can > > run at a time. On an SMP system, the disadvantage is that you > > lose the ability for multiple read lock owners to run at the > > same time. > > Let's say: threads A, B, C own a read lock (RW1). > > After a while: > - A blocks on a write lock (D thread owns) > - B blocks on a read lock (owned by other threads, we say E1, E2, E3) > - C blocks on a mutex (owned by F) > Now if a thread G blocks on RW1 and its priority is higher than A,B,C (which > might have the same priority) priority propagation is needed to hit D, { E1, > E2, E3 } and F. If you just do priority propagation for one of them the > other would not be updated. You will eventually do priority propagation for all of them (A, B, and C) until G's priority is <= the priority of RW1. It doesn't matter if you do one at a time or all of them at once. They all (A, B, C) have to release RW1 before G can run. > > turnstiles don't hurts beacause some intrusive lists are defined involving > turnstiles and threads so a sort of "chain" like that: > > turnstile->thread->turnstile->thread... > > is provided. In the case of multple thread we could have a situation like: > thread1 thread1 > turnstile->thread2->turnstile--------------->thread2 > thread3->turnstile->thread thread3 > > And so on. > > I did a recursive algorithm for a new primitive (rwblock) which correctly > implements priority propagation for multiple owners mechanism but there are > 2 problems: > > 1) this algorithm is recursive and it's enough hard to change > 2) With a new primitive some work of integration between existing > (turnstiles) might be provided. > > Currently I'm working on both these problematics and I hope to do something > better next times. -- DE