Different Server Schemes
In Xen, every guestOS is referred to as a Domain. Every domain can be equipped with one or more VCPUs, depending on the number of physical cores and configuration. the Xen scheduler schedules VCPU, just as the guest OS scheduler schedules tasks. Each VCPU has three parameters: budget, period, and priority. When a guest OS executes, it consumes its budget. A VCPU is eligible to run only if it has remaining budget. Different server algorithms differ in the way the budget is consumed and replenished. Eligible VCPUs are scheduled based on preemptive fixed priority scheduling. 
  • A Deferrable Server (DS) is invoked with a fixed period. If the VCPU has tasks ready, it executes them until either the tasks complete or the budget is exhausted. When the guest OS is idle, its budget is preserved until the start of its next period when its budget is replenished.
  • A Periodic Server (PES) is also invoked with a fixed period. In contrast to a DS, when a VCPU has no task to run, its budget idles away, as if it had an idle task that consumes its budget.  (We implemented three different variants of PES under RT-XEN 0.3. Please refer to Publications for more detail.)
  • A Polling Server (POS) is also referred to as a Discarding Periodic Server [5]. Its only difference with a PES is that a POS discards its remaining budget immediately when it has no tasks to run.
  • A Sporadic Server (SS) differs from the other servers in that it is not invoked with a fixed period, but rather its budget is replenished only after it has been used. A SS employs more complicated rules for budget replenishment. We implement the enhanced SS algorithm proposed in [6] in RT-Xen's sporadic server scheduler. Readers are referred to [6] for details.

Hierarchical Scheduling
Hierarchical Scheduling was first introduced in [3] as the notion of "Open System". It includes two level schedulers: Root scheduler and Leaf scheduler. In [3], Earliest Deadline First(EDF) was used as the root scheduler and constant utilization was used as the leaf scheduler. [4] further extends it to includes Sporadic Server as a root scheduler. A typical picture illustrate this from [4] is:

Compositional Scheduling Analysis
In Compositional Scheduling Analysis (CSA), the system consists of a set of components, where each component is composed of either a set of subcomponents or a set of tasks. Each component is defined by C = (W;R ; A), where: W is a workload, i.e., a set of tasks (components); R is a resource interface; and A is a scheduling policy used to schedule W; which is Rate Monotonic (RM) in our setting.

Periodic Resource Model (PRM). A periodic resource model (PRM) R is defined by = (P, B), where P is the resource period and B is the execution budget guaranteed by  over every . P time  units. The minimum resource guaranteed by a PRM  is captured by a supply bound function (SBF) [7]. PRM is used for uniprocesor.

Multi Periodic Resource model (MPR). A periodic resource model (MPR) R is defined by = (\Pi, \Theta, m'), where \Pi is the resource period and \Theta is the total budget that can be served by at most m' CPUs during any \Pi time interval. The minimum resource guaranteed by a MPR  is captured by a supply bound function (SBF) [10]. MPR is used for multiprocessor.

Please refer to literature [9] and [10] for the details of computing the resource interface of a component on uniprocessor and multiprocessor, respectively.

How RT-Xen Provides Real-Time Guarantees Using Compositional Schedulability Analysis
RT-Xen is a two-level hierarchical scheduling system: each guest domain is a leaf component and the hypervisor of RT-Xen is the top-level component. Each domain on RT-Xen has its own schedulers to schedule tasks inside it and each domain runs on several VCPUs, which are scheduled by the hypervisor of RT-Xen on physical cores.  We need to apply the compositional scheduling analysis to properly configure the parameters of each domain, i.e., the parameters (period, budget) of each VCPU of the domain, to provide real-time guarantee to the tasks inside each domain (i.e., to guarantee tasks inside each domain are schedulable). 

Suppose we have a two-level hierarchical system, we follow the following steps to run this two-level hierarchical system on RT-Xen to guarantee its real-time performance:
    1) Extract the periodic task information of each domain into an XML file, which describes the task information and schedulers in this two-level hierarchical system; and use the CARTS tool (a tool for Compositional Analysis of Real-Time Systems) to compute the interface of each leaf component and the top component. If the top component's interface requires more cores than the hardware can provide, this two-level hierarchical system may not be schedulable on this hardware. If the top component's interface requires no more cores than the hardware can provide, this two-level hierarchical system is guaranteed schedulabled on this hardware (without platform overhead into consideration). The CARTS tool will also provide the parameters of each VCPU of each domain in the output file (an XML file). Please refer to the papers [9] and [10] for details of how CARTS computed the interface of each component.
    2) Use the output computed by CARTS to configure the parameters (period, budget) of each VCPU of each domain on RT-Xen;
    3) Run the tasks in each domain (which uses LITMUSRT as its Real-Time OS) on RT-Xen and record their deadline miss by using the feature trace tool provided by LITMUSRT.

Note: Please refer to paper [11] for more details of how to apply compositional schedulability analysis to provide real-time guarantee on RT-Xen.


[1] B. Sprunt, “Aperiodic task scheduling for real-time systems,” Ph.D. dissertation, Carnegie Mellon University, 1990.

[2] Jane W. S. Liu, "Real-Time Systems"

[3] Z. Deng and J. W. s. Liu, “Scheduling real-time applications in an open environment,” in in Proceedings of the 18th IEEE Real-Time Systems Symposium, IEEE Computer. Society Press, 1997, pp. 308–319.

[4] T.-W. Kuo and C.-H. Li, “A fixed-priority-driven open environment for real-time applications,” Real-Time Systems Symposium, IEEE International, vol. 0, p. 256, 1999.

[5] R. Davis and A. Burns, “Hierarchical fixed priority preemptive scheduling,” in Real-Time Systems Symposium, 2005. RTSS 2005. 26th IEEE International. IEEE, 2006, pp. 10–398.

[6] M. Stanovich, T. Baker, A. Wang, and M. Harbour, “Defects of the POSIX Sporadic Server and How to Correct Them,” in Real-Time and Embedded Technology and Applications Symposium (RTAS), 2010 16th IEEE. IEEE, 2010, pp. 35–45.

[7] I. Shin and I. Lee, “Periodic resource model for compositional real-time guarantees,” in RTSS ’03: Proceedings of the 24th IEEE International Real-Time Systems Symposium. Washington, DC, USA: IEEE Computer Society, 2003, p. 2.

[8] J. Lehoczky, L. Sha, and Y. Ding, “The rate monotonic scheduling algorithm: exact characterization and average case behavior,” in Real Time Systems Symposium, 1989., Proceedings., dec 1989, pp. 166 –171.

[9] I. Shin and I. Lee, “Compositional real-time scheduling framework with periodic model,” ACM Trans. Embed. Comput. Syst., vol. 7, no. 3, pp. 1–39, 2008.

[10] A. Easwaran, I. Shin, and I. Lee. Optimal virtual cluster-based multiprocessor scheduling. Real-Time Systems, 43(1):25–59, 2009.

[11] S. Xi, M. Xu, C. Lu, L.T.X. Phan, C. D. Gill, O. Sokolsky and I. Lee, Real-Time Multi-Core Virtual Machine Scheduling in Xen, ACM International Conference on Embedded Software (EMSOFT'14), October 2014