Mixed-Criticality Federated Scheduling for Parallel Real-Time Tasks

Jing Li, David Ferry, Shaurya Ahuja, Kunal Agrawal, Christopher Gill, Chenyang Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2016 IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781467386395
DOIs
StatePublished - Apr 27 2016
Externally publishedYes
EventIEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016 - Vienna, Austria
Duration: Apr 11 2016Apr 14 2016

Publication series

Name2016 IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016 - Proceedings

Other

OtherIEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016
Country/TerritoryAustria
CityVienna
Period4/11/164/14/16

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Mixed-Criticality Federated Scheduling for Parallel Real-Time Tasks'. Together they form a unique fingerprint.

Cite this