MC-Fluid: Simplified and Optimally Quantified
The fluid scheduling model allows for schedules in which an individual task may be assigned a fraction of a processor at each time instant. These assignments are subject to the constraints that no fraction exceeds one and the sum of all the assigned fractions do not exceed the sum of the computing capacities of all the processors at any instant. An algorithm, MC-Fluid, has recently been proposed for scheduling systems of mixed-criticality implicit-deadline sporadic tasks under the fluid scheduling model. MC-Fluid has been shown to have a speedup bound no worse than (1 + √5)/2 or ≈ 1.618 for scheduling dual-criticality systems.
We derive here a simplified variant of MC-Fluid called MCF, that has run-time linear in the number of tasks. We prove that this simplified variant has a speedup bound no worse than 4/3 for dual-criticality systems, and show that this implies that MCFluid, too, has a speedup bound no worse than 4/3. We know from prior results in uniprocessor mixed-criticality scheduling that no algorithm may have a speedup bound smaller than 4/3, allowing us to conclude that MCF and MC-Fluid are in fact speedup-optimal for dual-criticality scheduling.
S. K. Baruah et al., "MC-Fluid: Simplified and Optimally Quantified," Proceedings of the 36th IEEE Real-Time Systems Symposium (2015, San Antonio, TX), pp. 327-337, Institute of Electrical and Electronics Engineers (IEEE), Dec 2015.
The definitive version is available at https://doi.org/10.1109/RTSS.2015.38
36th IEEE Real-Time Systems Symposium, RTSS 2015 (2015: Dec. 1-4, San Antonio, TX)
General Motors Corporation
Air Force Office of Scientific Research
Army Research Office
National Science Foundation (U.S.)
Keywords and Phrases
Scheduling; Processor Scheduling; Schedules; Chlorine; Real-Time Systems; Computational Modeling; Convex Functions
International Standard Book Number (ISBN)
International Standard Serial Number (ISSN)
Article - Conference proceedings
© 2015 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
01 Dec 2015