[Xen-devel] [Design RFC] Towards work-conserving RTDS scheduler

[Meng Xu <mengxu@xxxxxxxxxxxxx>]

Hi Dario,

I'm thinking about changing the current RTDS scheduler to
work-conserving version as we briefly discussed before.
Below is a design of the work-conserving RTDS.
I'm hoping to get your feedback about the design ideas first before I
start writing it in code.

I think the code change should not be a lot as long as we don't
provide the functionality of switching between work-conserving and
non-work-conserving. Because the following design will keep the
real-time property of the current RTDS scheduler, I don't see the
reason why we should let users switch to non-work-conserving version.
:-)

Thank you very much and looking forward to your comments!

--- Below is the design ---

*** Motivation ***
A scheduler is working-conserving if the scheduler always pick a
"task" (i.e., VCPU in RTDS scheduler case) as long as there still
exists a pending "task" that has not finished.

The current RTDS scheduler is not work-conserving. The
non-work-conserving property of the current RTDS scheduler prevents
the scheduler from utilizing the system's *idle* resource.

For example, when there is only one VCPU with period = 10ms and budget
= 4ms, on one CPU, scheduled by the RTDS scheduler, the VCPU can only
get 4ms for every 10ms. This leaves the CPU idle for 6ms in every
10ms. This is OK/safe because we assume the system administrator has
already known the workload on the VCPU and believes the VCPU (period =
10ms, budget = 4ms) is enough to provide real-time guarantee to the
workload on the VCPU.

However, we can further improve the system's average performance
without breaking the real-time property of the RTDS scheduler by
utilizing the idle resource.

*** Current RTDS scheduler in Xen ***
1) VCPU model: Each VCPU has period and budget
2) Scheduling policy: gEDF
3) Server mechanism: Deferrable server
4) Behavior: When VCPUs are schedulable on M cores, each VCPU is
guaranteed to be able to provide budget time in each period. Each VCPU
can run for * at most * budget time in each period

*** Observations of current RTDS scheduler ***

1) gEDF is work-conserving algorithm, but
2) Deferrable server is not “work-conserving”: When system has idle
resource, the deferrable server is not allowed to over-run. This
property of deferrable server prevent the RTDS scheduler from using
the idle resource in the system to improve the average response time
of VCPUs.

*** Requirement of the work-conserving RTDS scheduler ***
1) The new RTDS scheduler should be work-conserving, of course.
2) The new RTDS scheduler should not break any real-time guarantee
provided by the current RTDS scheduler.

*** Design of  Work-Conserving RTDS Scheduler ***
VCPU model
1) (Period, Budget): Guaranteed <Budget> time for each <Period>
2) Priority index: It indicates the current  priority level of the
VCPU. When a VCPU’s budget is depleted in the current period, its
priority index will increase by 1 and its budget will be replenished.
3) A VCPU’s budget and priority index will be reset at the beginning
of each period

Scheduling policy: modified gEDF
1) Priority comparison:
   a) VCPUs with lower priority index has higher priority than VCPUs
with higher priority index
   b) VCPUs with same priority index uses gEDF policy to decide the
priority order
2) Scheduling point
   a) VCPU’s budget is depleted for the current priority index
   b) VCPU starts a new period
   c) VCPU is blocked or waked up
3) Scheduling decision is made when scheduler is invoked
    a) Always pick the current M highest-priority VCPUs to run on the M cores.

-----------
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

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