Date: Fri, 19 May 2000 18:02:21 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: michael.schuster@germany.sun.com (Michael Schuster - TSC SunOS Germany) Cc: wes@softweyr.com (Wes Peters), msmith@FreeBSD.ORG (Mike Smith), cp@bsdi.com (Chuck Paterson), dfr@nlsystems.com (Doug Rabson), arch@FreeBSD.ORG Subject: Re: A new api for asynchronous task execution Message-ID: <200005191802.LAA00644@usr02.primenet.com> In-Reply-To: <3924E25D.DEB9F987@germany.sun.com> from "Michael Schuster - TSC SunOS Germany" at May 19, 2000 08:42:37 AM
next in thread | previous in thread | raw e-mail | index | archive | help
> > > > No, speaking of temporarily elevating the priority of a process holding > > > > a lock to the highest priority of all processes blocking on the lock. > > > > > > You could call this "priority lending" so that the rest of us understand > > > what you're talking about. 8) > > > > The only system I've ever worked on that implements them refer to > > them as inversion-safe or inversion-proof semaphores. I've never seen > > another name, including "priority lending", in any literature or > > article on the subject. > > 'scuse me for barging in - this sounds like what I know as "priority > inheritance" (as one solution to the priority inversion problem). Are we > talking of the same thing here? If no, what _is_ the difference? If yes, I > could probably dig up one or two papers using these terms (we do at Sun, > but that's not necessarily the place you're looking ... :-) The problem is called "priority inversion" in the literature. The abstract description states that the problem can occur when a high priority process can not run because it requires a resource held by a low priority process, which does not run to the point it releases the resource, due to it's priority. In both cases, a possible soloution is to temporarily raise the priority of the low priority process so that it can rn to the point it releases the resource. If the resource itself has reservations made by a high priority process, then the operation is called "priority inheritance", since by virtue of the low priority process using the resource, it will inherit the priority of the highest priority process holding a reservation on the ersource (in intention-mode locking, this is a SIX lock: Shared, Intention eXclusive). When the resource is released, the priority of the lower priority process is reduced to its previous value. If the resource does not have a reservation pending, and is allocated to a low priority process, then when a high priority process needs the resource, the low priority priority process is "lent" the high priority process' priority _until it releases the resource_. This operation is called "priority lending". In the general case, priority inheritance is more efficient than priority lending, IFF the resource is going to be repeatedly released and reacquired. IFF the resource is _not_ going to be released and reacquired, then one can delay, perhaps permanently, the need for a lower priority process to obtain higher priority. This permits priority lending to be more efficient, in that the processes are "truer to their intended priorities" than they might otherwise be. Priority inheritance is generally associated with Djikstra's "Banker's Algorithm", which is a prereservation of all needed resources. Priority lending is not; since Djikstra's algorithm has some potentially significant negative effects on concurrency (#1 wants "A" then "B", #2 wants "B", #2 could run to completion before #1 asks for "B", but can not run because "B" has been precomitted to #1 to avoid deadlock), priority lending is to be preferred for most cases (an exception is for resources which will be held for long periods of time, or repeatedly held and released, at which point the in-band cost of lending is once per transaction, whereas the priority inheritance setup costs can be amortized over all transactions). A FreeBSD example similar to "priority inheritance" is when a process opens /dev/io, it gains access to the I/O bus. When it closes /dev/io, this access is revoked. A FreeBSD example similar to "priority lending" is seen in the "FASTINTR" processing. Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200005191802.LAA00644>