From owner-freebsd-hackers@FreeBSD.ORG Wed Jan 18 09:39:29 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 A2E1316A43A for ; Wed, 18 Jan 2006 09:39:27 +0000 (GMT) (envelope-from asmrookie@gmail.com) Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.197]) by mx1.FreeBSD.org (Postfix) with ESMTP id 5303043E4D for ; Wed, 18 Jan 2006 09:38:35 +0000 (GMT) (envelope-from asmrookie@gmail.com) Received: by zproxy.gmail.com with SMTP id 9so1576672nzo for ; Wed, 18 Jan 2006 01:38:35 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:references; b=VDP5FgZalcR8/MPPjjUpQdan/hQiwBVWY3SFGLrOnry2TB7LDO5DGYFG05Za5WPqPcbzdi7PgnMcvrY3lhgWUCPNnHWCnYC5Tq75gUYGqBHzqnwppHodszjFMJTtrM7esiEI4tUm2qk80oRN7ycq2nggszhXVG8VfFOCSr9FSEI= Received: by 10.36.39.5 with SMTP id m5mr6517700nzm; Wed, 18 Jan 2006 01:38:34 -0800 (PST) Received: by 10.36.43.4 with HTTP; Wed, 18 Jan 2006 01:38:34 -0800 (PST) Message-ID: <3bbf2fe10601180138m3a5ab67cx@mail.gmail.com> Date: Wed, 18 Jan 2006 10:38:34 +0100 From: rookie To: deischen@freebsd.org In-Reply-To: MIME-Version: 1.0 References: <3bbf2fe10601171111x7432a2aaj@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline X-Content-Filtered-By: Mailman/MimeDel 2.1.5 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: rookie@gufi.org 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 09:39:30 -0000 >> 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 (whic= h 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. 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. Cheers, Attilio -- Peace can only be achieved by understanding - A. Einstein