Hierarchical Real-Time Scheduling In Paravirtualized Systems: Design, Implementation, And Optimization



Journal Title

Journal ISSN

Volume Title



In a virtualized system, the efforts to efficiently partition physical resources into a set of Virtual Machines (VMs) and temporally schedule them using real-time scheduling techniques have led to the design of the Hierarchical Real-Time Scheduling Framework (HiRTS). This framework specifies real-time performance guarantees at both the application (task level) and the VM level (resource level). The ARINC 653 standard specifies a cyclic scheduling policy for VMs to guarantee the real-time performance of its tasks. Adhering to the specifications of the HiRTS and ARINC 653, the Regularity-based Resource Partitioning (RRP) model was proposed that introduced the concept of regularity and availability factor to provide a near-ideal computational resource supply to all its VMs, while maintaining real-time performance guarantees of the VMs and its applications. In this dissertation, we aim at advancing the theoretical research carried out in the field of RRP, by proposing an optimal resource partitioning algorithm ideally suited for embedded virtualized systems. We also propose a greedy approximation-based resource partitioning algorithm that is well suited for large-scale virtualized systems. Further, to make the theoretically superior RRP model ready for industrial use, we for the first time implement the RRP model on a popular x-86 open-source soft real-time Xen hypervisor. This implementation includes the design of the resource partitioning algorithms along with numerous ARINC 653 standard-specific real-time VM schedulers, collectively referred to as RRP-Xen. In addition, we design and implement the proposed algorithms on an embedded hard real-time hypervisor, XtratuM. To cater to the static reconfiguration requests from the applications to its VM, we further propose a One-Hop Reconfiguration (OHR) technique exclusively designed for XtratuM. Numerous experiments were carried out to evaluate the soft and hard real-time performance of RRP on Xen and XtratuM hypervisors respectively. We further propose a fault-tolerant technique for RRP-based virtualized system to handle transient hardware faults. The proposed technique comprises of a checkpointing VM followed by a redundancy VM prepared for re-execution to satisfy task deadlines despite the occurrence of faults. Theoretical analysis and simulation-based experiments show the effectiveness of the proposed technique while incurring minimal overhead.



Virtualization, Real-time Systems, Operating Systems, Fault-Tolerance


Portions of this document appear in: Dai, Guangli, Pavan Kumar Paluri, Albert Mo Kim Cheng, and Bozheng Liu. "Regularity-Based Virtualization under the ARINC 653 Standard for Embedded Systems." IEEE Transactions on Computers (2021); and in: Paluri, Pavan Kumar, Guangli Dai, and Albert Mo Kim Cheng. "Arinc 653-inspired regularity-based resource partitioning on xen." In Proceedings of the 22nd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems, pp. 134-145. 2021; and in: Cheng, Albert MK, Guangli Dai, Pavan Kumar Paluri, Mansoor Ansari, Darrel Knape, and Yu Li. "Fault-tolerant regularity-based real-time virtual resources." In 2019 IEEE 25th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pp. 1-12. IEEE, 2019.