https://ieeexplore.ieee.org/abstract/document/6583914
https://pt.slideshare.net/xen_com_mgr/real-time-support-for-xen
Real-time support is an inherent requirement for mobile virtualization. However, it is also a challenge because scheduling is performed at two different layers in virtualization.To guarantee real-time scheduling, this paper addresses inter-VM/intra-VM schedulability for Xen-ARM virtual machines. The main contribution of this paper is the analysis that accounts for quantization overhead. In addition, this paper presents an exact and efficient parameterization of a real-time virtual machine using the SH-quantization algorithm. Through our experiments and numerical evaluations, we show that SH-quantization guarantees intra-VM schedulability. In addition to the case of a single guest OS, the hypervisor provides a inter-VM schedulability test to cover multiple virtual machines. In summary, the SH- quantization algorithm and inter-VM schedulability guarantees the deadlines of all real-time tasks for all Xen-ARM virtual machines, which means that real-time scheduling is possible in Xen-ARM-based mobile virtual machines.
Xen-ARM has two types of schedulers: a fair-share scheduler, Credit; and a real-time scheduler, SEDF.
Small scheduling tick size is harmful because frequent tick interferes with CPUs power saving mode, and it incurs considerable TLB, cache flush overheads. On the other hand, large scheduling tick size is bad for responsiveness because the large scheduling tick size implies the longer scheduling latency.
Xen-ARM has a real-time scheduler, SEDF (Simple Earliest Deadline First) to support RT guest OSs. To use SEDF, each guest OS, at first, has to provide its own scheduling parameter (period, execution slice, relative dead- line) to Xen-ARM, then Xen-ARM sorts the guest OSs by their given deadlines and selects the guest OS that has the earliest deadline. So, SEDF guarantees real-time scheduling among RT guest OSs with inter-VM schedulability.
However, SEDF cannot guarantee task execution inside a guest OS, intra-VM schedulability. To guarantee real- time deadlines of RT tasks, intra-VM schedulability has to be explicitly defined as well as inter-VM schedulability. Concisely, we need two distinct schedulability in order for Xen-ARM virtualization to ensure real-timeness, provided that Xen-ARM uses SEDF: 1) intra-VM schedulability for guaranteeing the deadlines of real-time tasks within a RT guest OS, and 2) inter-VM schedulability for incorporating multiple real-time guest OSs. To guarantee intra-VM schedulability, we need an algorithm that obtains the CPU bandwidth-optimal scheduling parameter of a guest OS
Our paravirtualization includes the following two modifications. First, a real-time guest OS is modified so that it schedules periodic task with physical time. In virtualization there are two notions of time: physical time and virtual time. The hypervisor accounts the physical time whenever physical timer interrupts occur. Note that physical interrupts are not directly delivered to a guest OS. Instead, a guest OS receives virtual timer interrupts only when it is scheduled by the hypervisor. Thus, virtual time runs slower than physical time, and a guest OS cannot accurately account the physical time by virtual timer interrupts. Virtual timer interrupts account the actual execution time consumed by the guest OS, which is the notion of virtual time
A real-time OS usually implements a periodic task by software timer, which requires physical time information. That is, when we make sleep() call, then the time given with the call is physical time, not virtual time. Therefore, software timer implementation has to be based on the physical time, rather than virtual time.
In the original uC/OS-II, software timer implementation is tightly coupled with scheduler. Each task has its task control block (TCB) that maintains remaining sleep time. Whenever a timer interrupt is triggered, the scheduler traverses the entire TCBs and decrements the remaining sleep time of tasks by 1.
In our xeno-uC/OS-II, we modify the calculation of remaining sleep time so that the scheduler awakes a task by physical time as follows. Firstly, whenever virtual timer interrupt is triggered, xeno-uC/OS-II updates the physical time as well as virtual time. In Xen-ARM, the physical time information is stored in VCPU structure. Secondly, it calculates the physical time passage by subtracting the last execution time from the current physical time. Then, it stores the current physical time so that it can be used to calculate the next physical time passage. Next, xeno-uC/OS-II traverses TCBs and decrements the remaining sleep time of tasks by the physical time passage, instead of 1. Finally, it invokes the scheduler so that it can awake tasks with physical time
Second, the guest OS is modified so that it explicitly requests real-time scheduling using the SH-quantization algorithm.
To use the SH-quantization algorithm, we introduce a new interface in order for Xen-ARM to directly use the algorithm. Listing ?? is the interface that enables Xen-ARM to support real-time scheduling. The interface is called from xeno-μC/OS-II since it has the information of its real-time tasks. The algorithm requires three input parameters from the guest OS, so the interface has three input parameters. Whenever the input parameters (Algo, Pmin, Uw) are changed, then the guest OS requests a new real- time scheduling for Xen-ARM. Then, Xen-ARM calculates the scheduling parameter for the guest OS through our algorithm. The SH_quantization() function returns with a feasible scheduling parameter (new_param) that includes the period (new_param.u.sedf.period) and execution slice (new_param.u.sedf.slice) from SH-quantization. Finally, the guest OS requests Xen-ARM to change the scheduling parameter via additional hypercall, sched_adjdom. Similarly to the other real-time schedulers, the scheduling parameter calculation can be done at offline, particularly when the real-time workload is usually fixed. Yet, online calculation has an advantage in cases when the workload changes over time. The algorithm is performed only when the task set is changed; thus, it would not be frequently invoked if the workload is not changed.
https://wiki.xenproject.org/wiki/Archived/Xen_ARM_(PV)
http://www-archive.xenproject.org/downloads/Wiki/XenARM/