A criticality-aware mapping of real-time virtual machines to multi-core processors

The manual partitioning of virtual machines with real-time requirements onto a multi-core platform is expensive, does not guarantee to find an optimal solution, and does not scale with regard to the upcoming higher number of both virtual machines and processor cores. This work proposes an algorithmic solution. As a prerequisite, the partitioning problem is defined in a formal manner by the abstraction of computation time demand of virtual machines and computation time supply of a shared processor core. In particular, we propose a branch-and-bound partitioning algorithm that systematically generates and evaluates candidate solutions. Combined with a computation time server based scheduling of the virtual machines that are mapped to the same core, it is guaranteed that the computation time demand of all virtual machines is satisfied. The utilization is optimized by transforming to harmonic server periods. The partitioning either minimizes the required number of cores or maximizes the distribution of critical virtual machines. The different outcomes of the algorithm according to these two goals are illustrated exemplarily and evaluated with random workloads.