Mixed-Criticality Federated Scheduling for Parallel Real-Time Tasks
Jing Li, David K. Ferry, Shaurya Ahuja, Kunal Agrawal, Christopher D. Gill, Chenyang Lu · 2016
A mixed-criticality system comprises safety-critical and non-safety-critical tasks sharing a computational platform. Thus, different levels of assurance are required by different tasks in terms of real-time performance. In addition, as the computational demands of real-time tasks are increasing, tasks may require internal parallelism in order to complete within stringent deadlines. In this paper, we consider the problem of mixed-criticality scheduling of parallel real-time tasks and propose a novel mixed-criticality federated scheduling (MCFS) algorithm for parallel real-time tasks based on the directed acyclic graph model. MCFS is based on federated intuition for scheduling parallel real-time tasks. It strategically assigns cores and virtual deadlines to tasks in order to achieve good schedulability. For task sets with only high-utilization tasks (utilization >= 1), we prove that MCFS provides a capacity augmentation bound of 3.41 and 3.73 for dual-criticality and multi- criticality, respectively. We also show that MCFS have capacity augmentation bounds of 3.67m/(m-1) for a dual-criticality system with both high- and low-utilization tasks, which to our knowledge is the first such performance bound for parallel mixed-criticality tasks. We also present an implementation of an MCFS runtime system in Linux that supports parallel programs written in OpenMP. We conduct both numerical and empirical experiments to demonstrate the practicality of our MCFS approach.