Precise Scheduling of Mixed-Criticality Tasks on Varying-Speed Multiprocessors


In conventional real-time systems analysis, each system parameter is specified by a single estimate, which must pessimistically cover the worst case. Mixed-criticality (MC) design has been proposed to mitigate such pessimism by providing a single system parameter with multiple estimates, which often lead to low-critical and high-critical modes. The majority of the works on MC scheduling is based on the approach that low-critical workloads are (fully or partially) sacrificed at the transition instant from low- to high-critical mode. Recently, another approach called precise MC scheduling has been investigated, where no low-critical workload is sacrificed at the mode switch, but instead a processor speed boosting is committed. In this paper, we extend the work on uniprocessor precise MC scheduling to multiprocessor platforms. To tackle this new scheduling problem, we propose two novel algorithms based on the virtual-deadline and fluid-scheduling approaches. For each approach, we present a sufficient schedulability test and prove its correctness. We also evaluate their effectiveness theoretically with speedup bounds and approximation factors as well as experimentally via randomly generated task sets.

Meeting Name

29th International Conference on Real-Time Networks and Systems, RTNS'2021 (2021: Apr. 7-9, Nantes, France)


Computer Science


National Science Foundation, Grant CCF-1659807

Keywords and Phrases

Fluid Scheduling.; Mixed-Criticality Systems; Precise Scheduling; Varying-Speed Platform; Virtual Deadlines

International Standard Book Number (ISBN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2021 Association for Computing Machinery (ACM), All rights reserved.

Publication Date

09 Apr 2021