TY - GEN
T1 - Mixed-Criticality Federated Scheduling for Parallel Real-Time Tasks
AU - Li, Jing
AU - Ferry, David
AU - Ahuja, Shaurya
AU - Agrawal, Kunal
AU - Gill, Christopher
AU - Lu, Chenyang
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/4/27
Y1 - 2016/4/27
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84971349944&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84971349944&partnerID=8YFLogxK
U2 - 10.1109/RTAS.2016.7461340
DO - 10.1109/RTAS.2016.7461340
M3 - Conference contribution
AN - SCOPUS:84971349944
T3 - 2016 IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016 - Proceedings
BT - 2016 IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016
Y2 - 11 April 2016 through 14 April 2016
ER -