Precise Mixed-Criticality Scheduling on Varying-Speed Multiprocessors
While traditional real-time systems analysis requires single pessimistic estimates to represent system parameters, the mixed-criticality (MC) design proposes to use multiple estimates of system parameters with different levels of pessimism, resulting in low critical workloads sacrificed at run-time in order to provide guarantees to high critical workloads. Shortcomings of the MC design were improved recently by the precise MC scheduling technique in which the processor speed is increased at run-time to provide guarantees to both low and high critical workloads. Aiming to extend the precise MC scheduling to multiprocessor computing platforms, this paper proposes three novel scheduling algorithms that are based on virtual-deadline and fluid-scheduling approaches. We prove the correctness of our proposed algorithms through schedulability analysis and also present their theoretical effectiveness via speedup bounds and approximation factor calculations. Finally, we evaluate their performance experimentally via randomly generated task sets and demonstrate that the fluid-scheduling algorithms outperform the virtual-deadline algorithm.
S. Vaidhun et al., "Precise Mixed-Criticality Scheduling on Varying-Speed Multiprocessors," IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers (IEEE), Jan 2022.
The definitive version is available at https://doi.org/10.1109/TC.2022.3197078
Keywords and Phrases
Approximation Algorithms; Computational Modeling; Fluid Scheduling; Job Shop Scheduling; Mixed-Criticality Real-Time Systems; Multiprocessors; Precise Scheduling; Processor Scheduling; Real-Time Systems; Switches; Task Analysis; Varying-Speed Platform
International Standard Serial Number (ISSN)
Article - Journal
© 2022 Institute of Electrical and Electronics Engineers, All rights reserved.
01 Jan 2022