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.
T. She et al., "Precise Scheduling of Mixed-Criticality Tasks on Varying-Speed Multiprocessors," Proceedings of the 2021 ACM International Conference on Real-Time Networks and Systems (2021, Nantes, France), pp. 134-143, Association for Computing Machinery (ACM), Apr 2021.
The definitive version is available at https://doi.org/10.1145/3453417.3453428
29th International Conference on Real-Time Networks and Systems, RTNS'2021 (2021: Apr. 7-9, Nantes, France)
Keywords and Phrases
Fluid Scheduling.; Mixed-Criticality Systems; Precise Scheduling; Varying-Speed Platform; Virtual Deadlines
International Standard Book Number (ISBN)
Article - Conference proceedings
© 2021 Association for Computing Machinery (ACM), All rights reserved.
09 Apr 2021