Re: RFC for a new Scheduling policy/class in the Linux-kernel

[Ted Baker <baker@cs.fsu.edu>]

On Thu, Jul 16, 2009 at 09:17:32AM -0600, Chris Friesen wrote:

> If a high-priority task A makes a syscall that requires a lock currently
> held by a sleeping low-priority task C, and there is a medium priority B
> task that wants to run, the classic scenario for priority inversion has
> been achieved.

I think you don't really mean "sleeping" low-priority task C,
since then the priority inheritance would do no good.  I guess you
mean that C has been/is preempted by B (and for global SMP, there
is some other medicum priority task B' that is eligible to run on
A's processor).  That could be a priority inversion scenario.

BTW, if migration is allowed the probability of this kind of thing
(and hence the payoff for PIP) goes down rapidly with the number
of processors.

> I know of at least one example with millions of lines of code being
> ported to linux from another OS.  The scheduling requirements are fairly
> lax but deadlock due to priority inversion is a highly likely.  They
> compare PI and PP, see that PP requires up-front analysis, so they
> enable PI.
> 
> I suspect there are other similar cases where deadlock is the real
> issue, and hard realtime isn't a concern (but low latency may be
> desirable).  PI is simple to enable and doesn't require any thought on
> the part of the app writer.

I'm confused by your reference to deadlock.  Priority inheritance
does not prevent deadlock, even on a single processor.

> At least for POSIX, both PI and PP mutexes can suspend while the lock is
> held.  From the user's point of view, the only difference between the
> two is that PP bumps the lock holder's priority always, while PI bumps
> the priority only if/when necessary.

You are right that POSIX missed the point of priority ceilings,
by allowing suspension.

However, there is still a difference in context-switching
overhead.  Worst-case, you have twice as many context switches
per critical section with PIP as with PP.

In any case, for a multiprocessor, PP is not enough.