lkml.org 
[lkml]   [1999]   [Jul]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: priority inversion
On Sat, Jul 31, 1999 at 09:39:55PM +0200, Bernd Paysan wrote:
> On Fri, 30 Jul 1999 yodaiken@chelm.cs.nmt.edu wrote:
> I can't figure out how to do a schedule() in 5 instructions (that's what's
> needed when process X can't get resource Y). The common case is when you
> can get your lock in the first step, and that's 5 instructions. If
> something goes wrong, your last instruction is a taken branch, and it can
> either take you back to try again (spin lock), or take you somewhere else
> (traditional lock, with falling asleep).
>
> Because of the design of spin-locks (locking should always only take a
> short time, because others actively poll to get that lock), preempting a
> process while it has a lock is just not an option. It hurts, then don't do
> it.

I thought you had advocated getting rid of spin_locks altogether.
>
> But since the Linux kernel still has normal locks, we either go to
> eliminate those altogether, or think about priority inheritence for them.

So look at Andrea and Linus's disgusting but good semaphore down. The good
(better be common) case is atomic decrement + failed branch (to
take advantage of branch prediction).
Now, if we add priority
inversion, this case better also prepare for a later
priority promotion. Right? And preparing for a priority promotion is not
a simple atomic decrement. At the very least, you have
to set a variable identifying yourself -- atomically. So your claim that
the common case is unchanged seems dubious. Once we admit that the
common case suffers we can discuss cost vs benefit. But before then,
it's no point.

> > If you can't read postscript, I can send you PDF.
>
> Have you really read the paper (I think you have written it)? The author
> proposes several lock-free strategies to overcome the problem. Actually,
> Linux doesn't use these lock-free strategies (at least not all over the
> place, there are still locks), although it would be really nice if it
> does.

Lock free is good. And serialization, also well known, used in Linux kernel
and discussed in the paper is also good. So are atomic operations.
But Linux's most effective strategy for dealing with priority inversion
is realization that there is no such thing in a general purpose OS.
The general purpose OS does not, should not, and cannot, promise to
always execute the highest priority runnable task. instead, it promises
that higher priority tasks will, in the average, run before lower
priority tasks. That's a good strategy and produces good results.
The theory that strict priority scheduling is critical is really shaky
even for realtime systems and is absurd for general purpose systems.

The big advantage of priority based RT systems is that they are easy to
analyze if you ignore all the difficult things -- like i/o, os overhead,
shared resources .... In other words, for simple systems, priority is
a sometimes useful organizing tool, and for academic papers, priority is
a nice abstraction that one can write papers about.


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:53    [W:0.038 / U:1.140 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site