Linear-time Admission Control For Elastic Scheduling

Author

• Marion Sudvarg, Missouri University of Science and TechnologyFollow
• Chris Gill
• Sanjoy Baruah

Abstract

Prior algorithms that have been proposed for the uniprocessor implementation of systems of elastic tasks have computational complexity quadratic (O(n²)) in the number of tasks n, for both initialization and for admitting new tasks during run-time. We present a more efficient implementation in which initialization takes quasilinear (O(nlog n)), and on-line admission control, linear (O(n)), time.

Recommended Citation

M. Sudvarg et al., "Linear-time Admission Control For Elastic Scheduling," Real Time Systems, vol. 57, no. 4, pp. 485 - 490, Springer, Oct 2021.

The definitive version is available at https://doi.org/10.1007/s11241-021-09373-4

Department(s)

Computer Science

Comments

National Science Foundation, Grant None

Keywords and Phrases

Admission control; Elastic tasks; Preemptive uniprocessor scheduling

International Standard Serial Number (ISSN)

1573-1383; 0922-6443

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2026 Springer, All rights reserved.

Publication Date

01 Oct 2021