[Xen-devel] Introduce rtds real-time scheduler for Xen

[Meng Xu <xumengpanda@xxxxxxxxx>]

This serie of patches adds rtds real-time scheduler to Xen.

In summary, It supports:
1) Preemptive Global Earliest Deadline First scheduling policy by
using a global RunQ for the scheduler;
2) Assign/display VCPUs' parameters of each domain (All VCPUs of each
domain have the same period and budget);
3) Supports CPU Pool
Note:
 a)  Although the toolstack only allows users to set the paramters of
all VCPUs of the same domain to the same number, the scheduler
supports to schedule VCPUs with different parameters of the same
domain. In Xen 4.6, we plan to support assign/display each VCPU's
parameters of each domain.
 b)  Parameters of a domain at tool stack is in microsecond, instead
of millisecond.

The status of this patch set is as follows:
[PATCH v4 1/4] xen: add real time scheduler rtds
      Acked-by: Jan Beulich <jbeulich@xxxxxxxx>

[PATCH v4 2/4] libxc: add rtds scheduler
    Reviewed-by: Dario Faggioli <dario.faggioli@xxxxxxxxxx>
    Acked-by: Ian Campbell <ian.campbell@xxxxxxxxxx>
    Acked-by: George Dunlap <george.dunlap@xxxxxxxxxxxxx>

[PATCH v4 3/4] libxl: add rtds scheduler
     Reviewed-by: Dario Faggioli <dario.faggioli@xxxxxxxxxx>
     Reviewed-by: George Dunlap <george.dunlap@xxxxxxxxxxxxx>

[PATCH v4 4/4] xl: introduce rtds scheduler
     Reviewed-by: Dario Faggioli <dario.faggioli@xxxxxxxxxx>
     Reviewed-by: George Dunlap <george.dunlap@xxxxxxxxxxxxx>
     Acked-by: Ian Campbell <ian.campbell@xxxxxxxxxx>

-----------------------------------------------------------------------------------------------------------------------------
TODO after Xen 4.5:
    a) Burn budget in finer granularity instead of 1ms; [medium]
    b) Use separate timer per vcpu for each vcpu's budget
replenishment, instead of scanning the full runqueue every now and
then [medium]
    c) Handle time stolen from domU by hypervisor. When it runs on a
machine with many sockets and lots of cores, the spin-lock for global
RunQ used in rtds scheduler could eat up time from domU, which could
make domU have less budget than it requires. [not sure about
difficulty right now] (Thank Konrad Rzeszutek to point this out in the
XenSummit. :-))
    d) Toolstack supports assiging/display each VCPU's parameters of
each domain.

-----------------------------------------------------------------------------------------------------------------------------
The design of this rtds scheduler is as follows:

This scheduler follows the Preemptive Global Earliest Deadline First
(EDF) theory in real-time field.
At any scheduling point, the VCPU with earlier deadline has higher
priority. The scheduler always picks the highest priority VCPU to run on a
feasible PCPU.
A PCPU is feasible if the VCPU can run on this PCPU and (the PCPU is
idle or has a lower-priority VCPU running on it.)

Each VCPU has a dedicated period and budget.
The deadline of a VCPU is at the end of each period;
A VCPU has its budget replenished at the beginning of each period;
While scheduled, a VCPU burns its budget.
The VCPU needs to finish its budget before its deadline in each period;
The VCPU discards its unused budget at the end of each period.
If a VCPU runs out of budget in a period, it has to wait until next period.

Each VCPU is implemented as a deferable server.
When a VCPU has a task running on it, its budget is continuously burned;
When a VCPU has no task but with budget left, its budget is preserved.

Queue scheme:
A global runqueue and a global depletedq for each CPU pool.
The runqueue holds all runnable VCPUs with budget and sorted by deadline;
The depletedq holds all VCPUs without budget and unsorted.

Note: cpumask and cpupool is supported.

If you are intersted in the details of the design and evaluation of
this rt scheduler, please refer to our paper "Real-TimeMulti-Core
Virtual Machine Scheduling in Xen"
(http://www.cis.upenn.edu/~mengxu/emsoft14/emsoft14.pdf), which will
be published in EMSOFT14. This paper has the following details:
    a) Desgin of this scheduler;
    b) Measurement of the implementation overhead, e.g., scheduler
overhead, context switch overhead, etc.
    c) Comparison of this rt scheduler and credit scheduler in terms
of the real-time performance.

If you are interested in other real-time schedulers in Xen, please
refer to the RT-Xen project's website
(https://sites.google.com/site/realtimexen/). It also supports
Preemptive Global Rate Monotonic schedulers.
-----------------------------------------------------------------------------------------------------------------------------
We tested the following commands/scenarios:
#xl list
#xl sched-rtds
//set VCPUs' parameters of each domain to new value
#xl sched-rtds -d Domain-0 -p 20000 -b 10000

// list cpupool information
#xl cpupool-list

//create a cpupool test
#xl cpupool-cpu-remove Pool-0 3
#xl cpupool-cpu-remove Pool-0 2
#xl cpupool-create name=\"test\" sched=\"rtds\"
#xl cpupool-cpu-add test 3
#xl cpupool-cpu-add test 2

//migrate vm1 from cpupool Pool-0 to cpupool test.
#xl cpupool-migrate vm1 test

We also tested the scenarios:
1) System boots with rtds scheduler, create a cpupool with credit
scheduler, and migrate a domU vm1 to the new cpupool;
    #xl cpupool-cpu-remove Pool-0 3
    #xl cpupool-create name=\"test\" sched=\"credit\"
    #xl cpupool-cpu-add test 3
    #xl cpupool-migrate vm1 test
2) System boots with credit scheduler, create a cpupool with rtds
scheduler and migrate a domU vm1 to the new cpupool;
    #xl cpupool-cpu-remove Pool-0 3
    #xl cpupool-cpu-remove Pool-0 2
    #xl cpupool-create name=\"test\" sched=\"rtds\"
    #xl cpupool-cpu-add test 3
    #xl cpupool-cpu-add test 2
    #xl cpupool-migrate vm1 test

-----------------------------------------------------------------------------------------------------------------------------
Any comment, question, and concerns are more than welcome! :-)

Thank you very much!

Best,

Meng

---
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
http://lists.xen.org/xen-devel