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

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

On Thu, Jul 16, 2009 at 08:46:52AM -0600, Chris Friesen wrote:

> > So, it seems most logical and simplest to leave the charges where
> > they naturally occur, on B.  That is, if you allow priority
> > inheritance, you allow tasks to sometimes run at higher priority
> > than they originally were allocated, but not to execute more 
> > than originally budgeted.

> In this scenario, we're going to disrupt B's scheduling pattern by
> forcing it to borrow from its future cpu allocation in order to free up
> the lock.  It will then be forced to block for a while to make up for
> the over-use of it's cpu budget.

I guess by "disrupting" B's scheduling pattern, you mean only in
the sense of delayed budget enforcement.  That is, finishing the
critical sections is something that B would do next in any case,
and something that B would need to consume CPU time to do in any
case.  It is B doing its own normal work, but just getting
a chance to complete that work sooner than it might otherwise.

In this situation, you do want to allow B's budget to go negative
(borrowing against B's future CPU budget to do B's work) rather
than charging the task A who loaned B priority, since otherwise B
ends up getting a still bigger windfall (charging B's work to A's
budget).

Ted

BTW. I believe I understood what you are saying here, but I
noticed that we are using words in different ways, especially
"block" and "sleep", and I'm not sure about some of the other messages.

It would be helpful if we had some common terminology.  In
particular, it might be useful to agree on distinct names for the
following following different reasons for a task not to be
executing.

1) actively looping on spin-lock, using CPU cycles
2) waiting for a condition or event,
   like timer or I/O completion, not using CPU cycles,
   not allowed to execute until the event or condition occurs
3) waiting for a CPU budget replenishment,
   not using CPU cycles, 
4) conceptually allowed to execute, but preempted on all available
   processors (by higher priority or non-preemptable tasks)
5) conceptually allowed to execute, but prevented from executing
   by lower-priority tasks that are not currently preemptable

Ted