Abstract
In federated scheduling of parallel real-time tasks on multiprocessor systems, high-utilization tasks are allocated dedicated processors on which they execute exclusively. Several methods exist for allocating a sufficient number of processors to guarantee that each task meets its deadline. In this paper, we propose two new strategies for allocating unit-speed cores to tasks with integer workload and deadline values. The first method can be performed in constant time for each high-utilization task, given the task's total workload, critical-path length, and deadline. The second method exploits the DAG structure of high-utilization tasks, providing a potentially better schedule in pseudo-polynomial time. We analyze and evaluate these new bounds in the context of existing techniques, and demonstrate that, in practice, they often allocate fewer processor cores. We also present a novel method for assigning an optimal number of dedicated cores to heavy tasks, describe how this method can be used in practice, and consider cases for which this is efficient.
Recommended Citation
M. Sudvarg and C. Gill, "Analysis Of Federated Scheduling For Integer-Valued Workloads," ACM International Conference Proceeding Series, pp. 12 - 23, Association for Computing Machinery (ACM), Jun 2022.
The definitive version is available at https://doi.org/10.1145/3534879.3534892
Meeting Name
RTNS '22: Proceedings of the 30th International Conference on Real-Time Networks and Systems
Department(s)
Computer Science
Publication Status
Open Access
Keywords and Phrases
federated scheduling; integer-valued tasks; parallel real-time systems; scheduling heuristics
International Standard Book Number (ISBN)
978-145039650-9
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2026 The Authors, All rights reserved.
Creative Commons Licensing
This work is licensed under a Creative Commons Attribution 4.0 License.
Publication Date
07 Jun 2022
Included in
Databases and Information Systems Commons, Other Computer Sciences Commons, Systems Architecture Commons
Comments
Acknowledgements: Many thanks to Jing Li, Abusayeed Saifullah, Chenyang Lu, and Son Dinh for insights into their work, which inspired this study. Thanks also to Sanjoy Baruah and Abhishek Singh for sharing their wealth of knowledge in the state-of-the-art.
National Science Foundation, Grant CSR-1814739 and CNS-17653503 and NASA Grant 80NSSC21K1741.