Introduce rtds real-time scheduler for Xen

[Meng Xu <mengxu@cis.upenn.edu>]

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: 1)  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.
      2)  Parameters of a domain at tool stack is in microsecond, instead of millisecond.

Compared with the PATCH v2, this set of patch has the following modifications:
    a) Split one global RunQ to two queues: runq and depletedq, instead of using flag_vcpu;
    b) Remove prv->cpus and use cpupool_scheduler_cpumask to get the valid cpus for the scheduler; (one scheduler per cpupool)
    c) Remove unnecessary printk in sched_rt.c;
    d) Change the scheduler's name from rt to rtds;
    e) Miscellous modification, such as removing trailing spaces.

[PATCH v3 1/4] xen: add real time scheduler rtds
[PATCH v3 2/4] libxc: add rtds scheduler
[PATCH v3 3/4] libxl: add rtds scheduler
[PATCH v3 4/4] xl: introduce rtds scheduler
-----------------------------------------------------------------------------------------------------------------------------
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-Time Multi-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.
-----------------------------------------------------------------------------------------------------------------------------
One scenario to show the functionality of this rtds scheduler is as follows:
//list the domains
#xl list
Name                                        ID   Mem VCPUs  State   Time(s)
Domain-0                                     0  3344     4     r-----     146.1
vm1                                          1   512     2     r-----     155.1

//list VCPUs' parameters of each domain in cpu pools using rtds scheduler
#xl sched-rtds
Cpupool Pool-0: sched=EDF
Name                                ID    Period    Budget
Domain-0                             0     10000      4000
vm1                                  1     10000      4000

//set VCPUs' parameters of each domain to new value
xl sched-rtds -d Domain-0 -p 20000 -b 10000
//Now all vcpus of Domain-0 have period 20000us and budget 10000us.
#xl sched-rtds
Cpupool Pool-0: sched=EDF
Name                                ID    Period    Budget
Domain-0                             0     20000     10000
vm1                                  1     10000      4000

// list cpupool information
#xl cpupool-list
Name               CPUs   Sched     Active   Domain count
Pool-0               4     rtds       y          2
#xl cpupool-list -c
Name               CPU list
Pool-0             0,1,2,3

//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
#xl cpupool-list
Name               CPUs   Sched     Active   Domain count
Pool-0               2     rtds       y          2
test                 2     rtds       y          0

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

//now vm1 is in cpupool test
# xl sched-rtds
pupool Pool-0: sched=EDF
Name                                ID    Period    Budget
Domain-0                             0     20000     10000
Cpupool test: sched=EDF
Name                                ID    Period    Budget
vm1                                  1     10000      4000

-----------------------------------------------------------------------------------------------------------------------------
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/