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

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

On Tue, Jul 14, 2009 at 12:24:26PM -0600, Chris Friesen wrote:

> > - that A's budget is not diminished.
> 
> If we're running B with A's priority, presumably it will get some amount
> of cpu time above and beyond what it would normally have gotten during a
> particular scheduling interval.  Perhaps it would make sense to charge B
> what it would normally have gotten, and charge the excess amount to A?

First, why will B get any excess time, if is charged?  There will
certainly be excess time used in any context switch, including
premptions and blocking/unblocking for locks, but that will come
out of some task's budget. Given the realities of the scheduler,
the front-end portion of the context-switch will be charged to the
preempted or blocking task, and the back-end portion of the
context-switch cost will be charged to the task to which the CPU
is switched.  In a cross-processor proxy situation like the one
above we have four switches: (1) from A to C on processor #1; (2)
from whatever else (call it D) that was running on processor #2 to
B, when B receives A's priority; (3) from B back to D when B
releasse the lock; (4) from C to A when A gets the lock.  A will
naturally be charged for the front-end cost of (1) and the
back-end cost of (4), and B will naturally be charged for the
back-end cost of (2) and the front-end cost of (3).

The budget of each task must be over-provisioned enough to
allow for these additional costs.  This is messy, but seems
unavoidable, and is an important reason for using scheduling
policies that minimize context switches.

Back to the original question, of who should be charged for
the actual critical section.

>From the schedulability analysis point of view, B is getting
higher priority time than it normally would be allowed to execute,
potentially causing priority inversion (a.k.a. "interference" or
"blocking") to a higher priority task D (which does not even share
a need for the lock that B is holding) that would otherwise run on
the same processor as B.  Without priority inheritance this kind
of interferfence would not happen.  So, we are benefiting A at the
expense of D. In the analysis, we can either allow for all such
interference in a "blocking term" in the analysis for D, or we
might call it "preemption" in the analysis of D and charge it to A
(if A has higher priority than D).  Is the latter any better?  I
think not, since we now have to inflate the nominal WCET of A to
include all of the critical sections that block it.

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.

Ted