[Techtalk] Theory vs. practice

[Val Henson]

On Tue, Jan 15, 2002 at 12:43:36PM -0800, Kai MacTane wrote:
> 
> Okay, I've just gotta ask: what *is* priority inversion? I suspect that 
> when you explain what it is, it will become obvious why it's a problem, but 
> if not, feel free to throw that in, too.

Now _this_ is techtalk. :):):)

I'm going to go the analogy route here.  Imagine a bank that has three
types of account holders, Platinum, Gold, and Silver.  This bank just
ran out of cash.  In line is a woman who has a Platinum account who
wants to withdraw $100 in cash.  Behind her is the cliche, an old lady
with $50 in pennies and a Gold account.  Behind her in line is a man
with a Silver account who wants to deposit $100 in cash.  Exactly one
teller is working.

Teller = CPU
Platinum woman = high priority process
Gold lady = medium priority process
Silver man = low priority process
Cash = a resource (a lock, a memory page, whatever)

Assume that the bank processes customers in strict priority order -
Platinum first, Gold second, Silver last.  So the Platinum woman asks
for $100.  She's told to wait for just a minute, over in that chair
with "Wait queue" printed on it.  Next, the Gold lady dumps her $50 in
pennies on the counter and the teller spends the next 3 hours counting
it.  Next, the Silver man deposits his $100, and the teller "wakes up"
the Platinum lady, who can now get her $100.

What's wrong with this picture?  A Platinum account holder just spent
3 hours waiting for a Gold account holder, when theoretically, the
Platinum holder should have had first priority.  This is called
priority inversion, when a low priority process holds a resource
needed by a high priority process, but the low priority process never
releases the resource because a medium priority process is hogging the
CPU.  And that medium priority process can have an infinite amount of
work to do, making it possible that neither the low or high priority
process will _ever_ run again.  This isn't a theoretical problem - one
of the many Mars Lander debacles was caused by a priority inversion
deadlock.

Linux gets around this by introducing the concept of "fairness" (I'm
ignoring the "realtime" priorities).  Each process does eventually get
to run for a while, even if a higher priority process still wants the
CPU.  It's very egalitarian. :)

The problem with a preemptive Linux kernel is that the goal is to
allow a lower priority process to be preempted at any time, even when
it's executing kernel code, and lose the CPU.  This can easily lead to
a low priority process never getting a chance to run, which leads to
priority inversion and deadlock.  The answer I've been hearing is,
"Oh, it'll get to run eventually."  No, that's the whole point - you
never know how many old ladies with huge bags of pennies and Gold
accounts are hogging the processor.

Some people say priority inheritance is the cure.  Anyone want to hear
about that? :)

-VAL