[Xen-devel] [RFC PATCH 0/4] Repurpose SEDF Scheduler for Real-time use

[Josh Whitehead <josh.whitehead@xxxxxxxxxxxxxxx>]

NEED:
With the increased interest in embedded Xen, there is a need for a suitable
real-time scheduler.  The arinc653 scheduler currently only supports a
single core and has limited niche appeal, while the sedf scheduler is
widely consider deprecated and is currently a mess.  This patchset
repurposes the current sedf scheduler and adds a more capable and robust 
real-time scheduler suitable for embedded use to the Xen repertoire.

PROPOSED SOLUTION:
Repurposing of the sedf scheduler was accomplished by implementing the
Constant Bandwidth Server (CBS) algorithm (originally proposed by Dario
Faggioli) which is capable of properly handling mixed soft real-time and
hard real-time tasks (domains/vcpus) on the same system.

If all domains in the system are set as hard real-time domains (the default
behavior) the scheduler acts as a very simple EDF scheduler, akin to the
original version of the SEDF scheduler.  If the "soft" flag is set for a
domain it enables the CBS algorithm to set the deadlines of a domain. The
primary advantage to this algorithm being that it allows a domain/vcpu to
consume additional CPU resources when they're available (work conserving)
while not affecting the deadlines of other domains (temporal isolation) but
still enforcing the domain receives a guaranteed minimum level of service.

This functionality allows hard and soft tasks to interact in a safe and
predictable fashion without adversely impacting the performance of the
other tasks, while still making efficient use of all available system 
resources, i.e. unlike a pure EDF system there is little or no wasted time
where the CPU is sitting idle.

A full discussion of the Constant Bandwidth Server algorithm and its
behavior is located here: 
http://retis.sssup.it/~giorgio/paps/2004/rtsj04-cbs.pdf

USAGE INSTRUCTIONS:
After applying the patches the scheduler can be used just as any of the
other Xen schedulers by specifying the "sched=cbs" boot parameter.  Though
capable of booting Dom0 with "sched=cbs", the scheduler is best for testing
and development purposes in a separate CPU pool.  This is because the
scheduler is being targeted at embedded real-time systems.  Performance as
a general purpose operating system would be good, though noticeably less
than the current credit schedulers.  To achieve its full potential the CBS
scheduler would need to be applied to a specific real-time system using a 
real-time OS where the system designer had some foreknowledge of that 
systems workload.

CBS uses a resource reservation scheme where the resources provided to each
domain/vcpu are specified in milliseconds using the "period=" and "budget="
parameters in the domain's config file, or at the command line using the
"xl sched-cbs" command.  The "bandwidth" or percentage of available
processing power that is guaranteed to a domain is simply the ratio of
budget / period.  The total of these ratios for all domains being operated
by the CBS scheduler should never be >1.  Currently there are no checks
implemented preventing a user from specifying a total of ratios >1, but
failure to follow this rule will likely result in the domains in question
becoming unstable and crashing as this would be akin to specifying more
than 100% of the total available processing power.

As an example, let's look at a setup of 4 CBS operated domains: 1 hard RT
and 3 soft RT, each with a period of 40 and a budget of 10.  Each domain
has a bandwidth of 0.25 (10/40), which with 4 domains means our total
bandwidth is 1.0 meeting that requirement.  In this scenario, the hard RT
domain would be guaranteed 25% of the CPU time, but would also never be
able to use more than that.  The 3 soft RT domains would be able to use
up to 100% of the CPU depending on system load across all the domains,
but would each be guaranteed to receive 25% of the processor even under
fully loaded conditions.  While the 3 soft RT domains could make use of
all of the CPU, the CBS algorithm prevents them from causing the hard RT
domain to miss any deadlines.

Instructions for using the "xl sched-cbs" and modifying a domains period
and budget parameters are located in the xl man page.

FUTURE DEVELOPMENT:
Though useful in its current state, there are a few additional features 
and modifications we'd like to make in the future:

1) More efficient multiprocessor support that makes better use of
available cores.  This would likely be accomplished through the use of a
global EDF queue for all available PCPUs.  Though the current version
does recognize and use multiple cores it takes some creative assigning
and pinning by the user to use them efficiently, the goal of this change
would be to have this load balancing occur seamlessly and automatically.

2) VCPU level parameter assignments instead of the current domain level
assignments.  This would allow for more accurate and efficient division of
resources amongst domains and cpu pools.  Currently all vcpus within a
domain must use the same period and budget parameters.

3) Alternate scheduling algorithms (e.g. Total Bandwidth Server) could now
be implemented in this scheduler with relative ease given the
simplification of the underlying EDF scheduler that was done as part of
this patchset.  This would further expand the capabilities of Xen in
embedded real-time systems and give developers more options to fit their
individual system requirements.

Josh Whitehead (1):
  Implement cbs algorithm, remove extra queues, latency scaling, and
    weight support from sedf

Robbie VanVossen (3):
  Add cbs parameter support to xl tool stack, remove defunct sedf
    parameters
  Updated comments/variables to reflect cbs, fixed formatting and
    confusing comments/variables
  Changed filenames with sedf to cbs to reflect the actual scheduler

 docs/man/xl.cfg.pod.5               |   21 +-
 docs/man/xl.pod.1                   |    4 +-
 docs/man/xlcpupool.cfg.pod.5        |    4 +-
 docs/misc/xen-command-line.markdown |    2 +-
 tools/examples/cpupool              |    2 +-
 tools/libxc/Makefile                |    2 +-
 tools/libxc/xc_cbs.c                |   70 ++
 tools/libxc/xc_sedf.c               |   78 --
 tools/libxc/xenctrl.h               |   16 +-
 tools/libxl/libxl.c                 |   61 +-
 tools/libxl/libxl.h                 |    5 +-
 tools/libxl/libxl_create.c          |   61 --
 tools/libxl/libxl_types.idl         |    7 +-
 tools/libxl/xl.h                    |    2 +-
 tools/libxl/xl_cmdimpl.c            |  100 +--
 tools/libxl/xl_cmdtable.c           |   18 +-
 tools/python/README.XendConfig      |    4 +-
 tools/python/xen/lowlevel/xc/xc.c   |   56 +-
 xen/common/Makefile                 |    2 +-
 xen/common/sched_cbs.c              |  917 +++++++++++++++++++++
 xen/common/sched_sedf.c             | 1541 -----------------------------------
 xen/common/schedule.c               |    2 +-
 xen/include/public/domctl.h         |   12 +-
 xen/include/public/trace.h          |    2 +-
 xen/include/xen/sched-if.h          |    2 +-
 25 files changed, 1120 insertions(+), 1871 deletions(-)
 mode change 100644 => 100755 docs/man/xl.cfg.pod.5
 create mode 100755 tools/libxc/xc_cbs.c
 delete mode 100644 tools/libxc/xc_sedf.c
 mode change 100644 => 100755 tools/libxc/xenctrl.h
 mode change 100644 => 100755 tools/libxl/libxl.c
 mode change 100644 => 100755 tools/libxl/libxl.h
 mode change 100644 => 100755 tools/libxl/libxl_types.idl
 mode change 100644 => 100755 tools/libxl/xl_cmdimpl.c
 mode change 100644 => 100755 tools/libxl/xl_cmdtable.c
 mode change 100644 => 100755 tools/python/xen/lowlevel/xc/xc.c
 create mode 100644 xen/common/sched_cbs.c
 delete mode 100644 xen/common/sched_sedf.c
 mode change 100644 => 100755 xen/include/public/domctl.h

-- 
1.7.9.5


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel