[Techtalk] Priority inheritance

[Val Henson]

On Tue, Jan 15, 2002 at 02:48:19PM -0800, Laurel Fan wrote:
> How about letting those who haven't learned the known solutions try to
> work it out first?  Anyone care to take a guess? Or a partial guess?

Ding ding ding!  Time's up! (Good idea, Laurel.)  I'll be replying
individually to each of the other emails with questions, but here's
the overall explanation.

Priority inheritance (as many people correctly guessed) is when a
lower priority process inherits the priority of any higher-priority
processes waiting on a resource that it holds.  In our bank analogy,
the Silver man with $100 inherits the Platinum priority from the woman
who needs $100.

Some people have already thought about how you would implement this,
and you're on the right track.  Priority inheritance requires a lot of
accounting.  Going back to our bank analogy, let's assume you can only
get money by withdrawing it from the bank.  What you would do is keep
a list of everyone who withdraws money from the bank, and when you run
out, you convert everyone on that list to the priority of the person
waiting for money.

And what happens when a Platinum process needs something from a Gold
process, and that Gold process needs something from a Silver process
before it can go any farther?  The Silver process should inherit the
Platinum priority through the Gold process.  So you can't just check
everyone on one waiting list, you have to check the waiting list of
each process on the waiting list, recursively.

Next, we have the issue of non-exclusive resources.  Only one person
can have a particular $100, but what if we're sharing a resource - for
example, two people both are reading one checkbook?  Solutions exist,
but they're complicated and imperfect.

Finally, let's get back to the reason we wanted preemption and
priority inheritance in the first place: We want higher priority tasks
to run as soon as possible - we want "realtime" response.  But there's
nothing that prevents having your high priority task A waiting on task
B, which is waiting on task C, which is waiting on task D, which is
waiting on task E... All the way down to little task Z, which now has
the highest priority, but still needs to finish counting its pennies
before it will let go of the resource that task Y is waiting on.  So,
with priority inheritance, you still may have to wait a long long time
for your high priority task A to run.

The discussion of priority inheritance in "UNIX Internals" by Vahalia
ends with this sentence:

"These drawbacks limit the usefulness of this protocol to a small set
of applications." (p. 138)

Anyone here think that Linux runs a small set of applications? :)

Hmm, possible next topic: How do you get your realtime and your *nix,
too? :)

-VAL