Mixed-criticality federated scheduling for parallel real-time tasks

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

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


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. As the computational demands of real-time tasks increase, 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 tasks modeled by a directed acyclic graph. MCFS is based on federated intuition for scheduling parallel real-time tasks. It strategically assigns cores and virtual deadlines to tasks to achieve good schedulability. For high-utilization tasks (utilization ≥ 1), we prove that MCFS provides a capacity augmentation bound of 2+2 and (5+5)/2 for dual- and multi-criticality, respectively. We show that MCFS has a capacity augmentation bound of 11 m/ (3 m- 3) for dual-criticality systems with both high- and low-utilization tasks. For high-utilization tasks, we further provide a MCFS-Improve algorithm that has the same bound but can admit many more task sets in practice. Results of numerical experiments show that MCFS-Improve significantly improves over MCFS for many different workload settings. We also present an implementation of a MCFS runtime system in Linux that supports parallel programs written in OpenMP. Our implementation provides graceful degradation and recovery features. We conduct empirical experiments to demonstrate the practicality of our MCFS approach.

Original languageEnglish (US)
Pages (from-to)760-811
Number of pages52
JournalReal-Time Systems
Issue number5
StatePublished - Sep 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modeling and Simulation
  • Computer Science Applications
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering


  • Capacity augmentation bound
  • Mixed-criticality federated scheduling
  • Mixed-criticality real-time system
  • Parallel real-time tasks


Dive into the research topics of 'Mixed-criticality federated scheduling for parallel real-time tasks'. Together they form a unique fingerprint.

Cite this