Message-ID: <20090715205503.GA14993@cs.fsu.edu>
Date:	Wed, 15 Jul 2009 16:55:03 -0400
From:	Ted Baker <baker@...fsu.edu>
To:	"James H. Anderson" <anderson@...unc.edu>
Cc:	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Chris Friesen <cfriesen@...tel.com>,
	Raistlin <raistlin@...ux.it>,
	Douglas Niehaus <niehaus@...c.ku.edu>,
	Henrik Austad <henrik@...tad.us>,
	LKML <linux-kernel@...r.kernel.org>, Ingo Molnar <mingo@...e.hu>,
	Bill Huey <billh@...ppy.monkey.org>,
	Linux RT <linux-rt-users@...r.kernel.org>,
	Fabio Checconi <fabio@...dalf.sssup.it>,
	Thomas Gleixner <tglx@...utronix.de>,
	Dhaval Giani <dhaval.giani@...il.com>,
	Noah Watkins <jayhawk@....ucsc.edu>,
	KUSP Google Group <kusp@...glegroups.com>,
	Tommaso Cucinotta <cucinotta@...up.it>,
	Giuseppe Lipari <lipari@...is.sssup.it>,
	Bjoern Brandenburg <bbb@...unc.edu>
Subject: Re: RFC for a new Scheduling policy/class in the Linux-kernel

On Tue, Jul 14, 2009 at 12:54:13PM -0400, James H. Anderson wrote:
> 
> ... Ted Baker did some work on an algorithm called EDZL
> (EDF until zero laxity) that is essentially a hybrid of these two
> algorithms.  In simulations we've done (not based on real implementations),
> EDZL exhibits really low tardiness (almost non-existent).  EDZL may
> give you the benefits of using laxities where useful and be easier
> to implement (but that's just my guess)

Yes, EDZL is a simple extension of EDF.  If you have a WCET
estimate for a task, you just apply EDF until/unless the task
reaches zero laxity.  If it reaches zero laxity you bump it to a
fixed priority level that is above all EDF tasks.  It seems very
good in simulations, in terms of schedulabilty, number of context
switches, and number of task migration.  It never deviates from
EDF except in cases where a deadline would otherwise be missed.
Therefore all EDF schedulability tests are valid for EDZL.  In
addition, we have some tighter tests.  EDZL never causes more than
one context switch more than EDF, when a task goes from positive
laxity to zero laxity.  This does not happen often.  It is much
lower overhead than least-laxity-first, since there is no
possibility of getting into a time-slicing situtation among tasks
with equal laxity.  It is also nice because in many cases the
scheduler will not know the WCET of a task, and so it is
impossible to compute laxity.  In those cases, you just use EDF.
The two policies (EDF and EDZL) are completely compatible and
interoperable.

I hope that Linux will not pursue EDF or EDZL in only a narrow
sense, as simple priority scheduling algorithms, without providing
for bandwidth guaranteees and limits.

By bandwith "guarantee" I mean that the task/scheduling entity is
guaranteed to be able to at least *compete* at a certain level for
a certain percentage of the CPU, if we cannot (better) provide an
admission control mechanism that guarantees it will actually get a
certain percentage of the CPU.

By bandwidth "limit" I mean that there is an enforced bound
on the percentage of processor time a task/scheduling entity
may consume.  

For example, in the fixed-priority domain, we have Sporadic
Server.  This guarantees the server a chance to compete at its top
priority for at least sched_ss_init_budget time in every
sched_ss_repl_period time, at sched_priority, within some
tolerance.  It also should not be permitted to use more than
sched_ss_init_budget time in every sched_ss_repl_period time, at
sched_priority, within some tolerance.

In the deadline scheduling domain, we have algorithms like
Constant Bandwidth Server (and some improved variants) that
provide similar gurantees and limites, in terms of deadlines.  (I
recall seeing one very good version in a paper I recently saw,
which I could seek out and provide to the list if there is
interest.)

These so-called "aperiodic server scheduling" algorithms are
critically needed in a system like Linux that is open (in the
sense of being able to host a dynamic mix of uncoordinated
applications), and based on a thread programming model (as copared
to the job/task models used in scheduling theory).  With the
thread abstraction one generally cannot give the scheduler WCET
bounds, and sometimes cannot give deadlines, since the threads
will wake up and go to sleep according to their own internal logic
(all the OS sees is the system calls).  However, if the
application is guaranteed a chance to at least compete at a high
enough priority for a certain bandwidth (and, preferably, actually
be guaranteed that bandwidth, by admission control), it is
possible to write real-time applications. In order to be able to
make such a guarantee, one must be able to limit the CPU usage of
all other threads.  This means, in effect, that *all*
tasks/scheduling entities above a certain priority level must be
scheduled according to a bandwidth-limiting algorithm.

The present Linux "RT throttling" mechanism seems to be an attempt
to achieve something similar (preventing RT tasks from shutting
out other work, by reserving some bandwidth for non-RT tasks).
However, it is done so grossly as to be unsatisfactory for
real-time applications.  The better way to do this would be to
enforce a bandwidth limit on each task with real-time priority --
using the budget amount and replenishment interval required by
that task -- and enforce by admission control that the real-time
tasks do not exceed some configurable percent of the total system
utilization.

Of course, the POSIX standard does not recognize any budget and
replenishment interval for policies other than SCHED_SPORADIC, but
the same problem exists with respect to the present "RT
throttling" mechanism.  It would be possible to provide legal
implementation-defined extensions for the operations that take a
struct sched_param to look at these additional sched_param fields
for other policies such as SCHED_FIFO and SCHED_OTHER, and to
provide default values when they are not specified.  The amount of
capacity to be reserved for system internal use could be
configured, using some combination of kernel compile-time macros,
boot parameters, and the /proc interface.  User defaults could be
configured using extensions to the setrlimit() interface.

Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists