Precise Mixed-Criticality Scheduling on Varying-Speed Multiprocessors

Abstract

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.

Department(s)

Computer Science

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)

1557-9956; 0018-9340

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2022 Institute of Electrical and Electronics Engineers, All rights reserved.

Publication Date

01 Jan 2022

Link to Full Text

Share

 
COinS