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

["James H. Anderson" <anderson@cs.unc.edu>]

On Tue, 14 Jul 2009, Peter Zijlstra wrote:

> On that, how does the priority ceiling/protection protocol extend to
> deadline schedulers?

Sorry -- I should have responded to this.

These things are pretty easy to extend to deadline scheduling if
partitioning is assumed, and this has been done.  However, it is not
easy to do under global scheduling.  Having tasks pinned to processors
(partitioning) makes it much easier to compute blocking terms (it's much
easier to predict what is happening on each processor at any time).
Without this, it is *really* hard to compute reasonable blocking
terms.  Even doing something as mundane as avoiding deadlocks without a lot
of overhead may not be trivial.  At the time we developed the FMLP
(a couple of years ago), there was *no* published locking protocol (to my
knowledge) that worked under GEDF.  To my knowledge, the FMLP is still the
only one that works under GEDF.  (BTW, I should say that I am not
familiar with the PEP protocol that has been discussed in this thread.
I assume it doesn't work under GEDF, or you wouldn't have asked the
question.)

BTW, FIFO waiting makes blocking terms in the global case much easier
to compute: once a lock request is initiated, the set of blocking lock
requests (onces initiated earlier) is fixed.  (This is actually a bit
of an over-simplification if waiting is by suspending.)  With priority-based
waiting, higher-priority requests can come later.  Determining a
reasonable bound on the number of such requests is hard.

You can find references to papers by others in our FMLP papers.

-Jim