Theoretical Fundamentals of Real-time Virtualization from the Resource Management Perspective



Journal Title

Journal ISSN

Volume Title



A Virtual Machine Monitor (VMM) partitions a host physical machine into a group of Virtual Machines (VMs). Typically, a VM machine only preempts a part of a dedicated physical resource temporally or spatially. This fact greatly impacts the real-time task scheduling in VMs because most traditional real-time scheduling theories are based on dedicated resources. The real-time community has introduced some Hierarchical Real-Time Scheduling Models to address this issue. Among them, the Regularity-based Resource (RRP) Model is able to provide maximal transparency for task scheduling. However, current theoretical results on the RRP Model are still far from the complete theoretical fundamentals required by a real-time VMM. At the resource level, only a naive algorithm has been found for resource partitioning. At the task level, only the Periodic Task Model is investigated, and even for this task model, only one simple case has been considered. This work explores the RRP Model at both the resource and task levels. On the one hand, it is the first to solve the resource partitioning problem with both global and partitioned strategies. On the other hand, it solves the task scheduling problem with a strong result that the classic task scheduling problem in the RRP Model can be easily transformed into an equivalent problem on a dedicated resource. With these theory enhancements, a 2-layer real-time resource model is presented and the theoretical fundamentals of a real-time VMM are fully established from resource management perspective.



Hierarchical Real-time Scheduling, Real-time Virtualization, Temporal Resource Partition, Real-time Task Scheduling, Transparency, Regularity Bound, Schedulability Test, Utilization Bound


Portions of this document appear in: Li, Yu, and Albert MK Cheng. "Static approximation algorithms for regularity-based resource partitioning." In 2012 IEEE 33rd Real-Time Systems Symposium, pp. 137-148. IEEE, 2012. And in: Li, Yu, and Albert Mo Kim Cheng. "Transparent real-time task scheduling on temporal resource partitions." IEEE Transactions on Computers 65, no. 5 (2015): 1646-1655.