Mixed-Criticality Scheduling in Compositional Real-Time Systems with Multiple Budget Estimates

In order to mitigate the pessimism in parameter estimation in real-time systems, mixed-criticality (MC) scheduling has been proposed and studied. In light of the first MC scheduling work focusing on multiple estimates on the worst-case execution times (WCETs), a few following works also have extended this approach to other dimensions, such as periods, relative deadlines, and processor speeds. Nonetheless, in most existing work on MC scheduling, a flat-structured scheduling approach is assumed, whereas compositional real-time systems with hierarchical scheduling are of great interest, especially for large-scale real-time systems. In this work, we aim to extend the fundamental ideas and frameworks of MC scheduling to another dimension, namely the budget estimation. To illustrate this approach, we form up a specific scheduling problem in the context of a single virtual processor characterized by the periodic resource model and propose a virtual-deadline-based algorithm to solve it. Furthermore, we have developed a polynomial-time schedulability test and have proved a speed-up bound for the proposed algorithm. We have also derived a range for setting the resource period to ensure schedulability when the bandwidth and task set are given. Moreover, we have conducted schedulability studies and presented our simulation experiment results to evaluate the proposed model and algorithm.