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.

I. Introduction

Real-time systems design is often aiming for providing guarantees for meeting deadlines in all possible scenarios. As a result, significant pessimism usually exists in real-time scheduling analysis and design. The system parameters, e.g., the needed execution time for a piece of code, are provisioned as upper bounds, which are often not tight, on the worst case. Consequently, while the system design and certification need to follow these pessimistic provisioned system parameters, computing resources might be significantly underutilized in practice due to the potentially huge gap between the general scenario during runtime and the worst-case provision used for analysis, design, and certification. One approach to mitigate such pessimism is mixed-criticality (MC) scheduling [11], [63]. Under MC scheduling, tasks are grouped to two distinct criticality levels—HI (stands for high criticality) and LO (stands for low criticality), and each system parameter might have two estimates—a more pessimistic one that provides an absolutely safe bound on even the worst-case scenario, and a less pessimistic one that covers a dominant majority of scenarios in practice (e.g., take the observed worst case in measurement-based experiments). An MC scheduler is designed based on the criticality levels and system parameter estimates, and needs to guarantee that the deadlines of all tasks (i.e., both HI- and LO-tasks) are met in "normal" scenarios in common practice while the deadlines of all HI-tasks are still met even if any pathological extreme cases do happen.