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

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

On Tue, Jul 14, 2009 at 01:16:52PM -0400, James H. Anderson wrote:
> ... 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...

I have not seen the definition of PEP, but from the context of
this discussion I infer that it refers to an implementation of
priority inheritance.  As such, with pretty much any global
scheduling policy, the set of other tasks whose critical sections
could stack up is bounded only by the number of tasks in the
system.

In any case, I have misunderstood what PEP is, let me attempt
to summarize what I have inferred:

A high priority running task that would otherwise become blocked
waiting for a lower-priority lock-holding task to release the lock
can give up its prority/shot at execution to the lower-priority
task that is blocking it.  That is, when a task A is "blocked" for
a lock it can stay in the run-queue so long as the task B that is
(ultimately, transitively) blocking it is in (the same?)
run-queue.  At any point where the scheduler would choose to
execute A it instead finds B, by traversing wait-for links between
tasks, and executes B.  The priority order of the run-queue can be
based on any (partial) ordering relation, including deadlines.

A slight complexity is that if B is allowed to suspend itself
while holding a lock, and does so, one must run back and also
remove the tasks like A from the run-queue, and when B wakes up,
one must do the revers.  However, the frequency of deep nesting
of wait-for relationships seems small.

For GEDF on SMP, a question is how to handle the case where A is
blocked on one processor and B may be running on a different one.
This seems to require removing A from the run-queue when it is
detected.

Of course, the current Linux model appears not to fully support
GEDF, since run-queues are per-processor, subject to explicit
migration.  So, as infer from the preceding messages, the question
above transforms into whether to migrate A to B's processor
run-queue or to migrate B to A's processor run-queue?

Ted