Background

About 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:

RT-XEN
We assume that every guest OS is equipped with one virtual CPU (VCPU), and are all pinned on one specific physical CPU (PCPU). In DS, PES, and POS, each VCPU has three parameters: budget, period, and priority. SS requires each VCPU to record two more parameters: status, and the total amount of budget consumed since the last execution.

Every PCPU is equipped with three queues: a Run Queue (RunQ), a Ready Queue (RdyQ), and a Replenishment Queue (RepQ). The RunQ and RdyQ are used to store active VCPUs (the guest OS is not paused). The RunQ holds VCPUs that have tasks to run (regardless of budget), sorted according to priority. Every time do_schedule is triggered, it inserts the currently running VCPU back into the RunQ or RdyQ, then picks the highest priority VCPU with a positive budget from the RunQ, and runs it for one quantum (we choose the quantum to be 1 ms). The RdyQ holds VCPUs that have no task to run, but may still have budgets. It is used for PES, e.g, when a VCPU A goes to the RdyQ and still has budget, if the current running VCPU has lower priority than A, A's budget needs to be consumed as well.
The RepQ stores replenishment information for all the VCPUs on the specific PCPU. Every element in RepQ contains three parameters: the VCPU to replenish, the replenishment time, and the replenishment amount. At each scheduling quantum, the RepQ is checked and any current replenishment is performed. If the VCPU replenished has higher priority than the current running one, an interrupt is also raised to trigger the do_schedule function which performs the context switch. For DS, PES, and POS, the RepQ is independent of the VCPU's actual execution: every VCPU receives a replenishment with a fixed period. For SS, insertion into the RepQ is dynamically decided by the status of the VCPU.




Compositional Scheduling Architecture
In a 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. 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].

Schedulability condition. The request bound functions (RBF_{W,i}) of W and task index i  is bounded to maximum resource request for any time interval t as given by  [8]. Following lemma states the schedulability condition of C based on rbf_{W,i} and sbf [9]:
Lemma 1: Given a component C = (W,R, RM ) with W = {T_1, T_2, ... , T_n} and T_i = (p_i, e_i) for all 1<= i <= . n. Then, C is schedulable ( can feasibly schedule W) iff for all i, 1<=. i<= n;  exists t in [0, p_i] s.t. sbf(t) .<= rbf_{W,i}(t).

References

[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.