Elastic Scheduling For Harmonic Task Systems
Abstract
Elastic scheduling is a framework to reduce task utilizations (often by increasing periods) in response to system overload. This paper extends elastic scheduling to uniprocessor scheduling of implicit-deadline task sets for which periods must remain harmonic. We argue that for tasks with periods constrained to continuous intervals, the problem of selecting harmonic periods from those intervals is unlikely to have a polynomial time solution. However, we outline an approach that is pseudo-polynomial in the range of acceptable periods. We then show that the problem of elastic scheduling is NP-hard with harmonic constraints. Nonetheless, if a total order is imposed on task periods (a natural restriction in many applications with execution pipelines that synchronize input data sources), the problem can be reduced offline to a lookup table, enabling polynomial-Time online adaptation if available CPU bandwidth changes. We implement the proposed algorithm in two real-world applications: The Fast Integrated Mobility Spectrometer (FIMS) and ORB-SLAM3. We demonstrate that elastic scheduling allows FIMS to adjust its execution to avoid missing deadlines on a SWaP-constrained computational platform, and that it improves ORB-SLAM3's localization results by as much as lO.4x when available CPU bandwidth changes dynamically during runtime.
Recommended Citation
M. Sudvarg et al., "Elastic Scheduling For Harmonic Task Systems," Proceedings of the IEEE Real Time and Embedded Technology and Applications Symposium Rtas, pp. 334 - 347, Institute of Electrical and Electronics Engineers, Jan 2024.
The definitive version is available at https://doi.org/10.1109/RTAS61025.2024.00034
Department(s)
Computer Science
Keywords and Phrases
elastic scheduling; harmonic periods; harmonic tasks; period assignment; period ranges; real-Time systems
International Standard Serial Number (ISSN)
1545-3421
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2026 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 Jan 2024
Comments
Acknowledgement: This research was supported by NSF grants CPS-2229290, CNS-2141256, CNS-2038995, and CNS-2238635; a Washington University CSE/EECE seed grant; and Swedish Research Council grant 2018-04446.