MC-Fluid: Simplified and Optimally Quantified

Abstract

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.

Meeting Name

36th IEEE Real-Time Systems Symposium, RTSS 2015 (2015: Dec. 1-4, San Antonio, TX)

Department(s)

Computer Science

Sponsor(s)

General Motors Corporation
Air Force Office of Scientific Research
Army Research Office
National Science Foundation (U.S.)

Comments

This research was supported in part by NSF grants CNS 1115284, CNS 1218693, CNS 1409175, and CPS 1446631, AFOSR grant FA9550-14-1-0161, ARO grant W911NF-14-1-0499, and a grant from General Motors Corp

Keywords and Phrases

Scheduling; Processor Scheduling; Schedules; Chlorine; Real-Time Systems; Computational Modeling; Convex Functions

International Standard Book Number (ISBN)

978-146739507-6

International Standard Serial Number (ISSN)

1052-8725

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2015 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Dec 2015

Link to Full Text

Share

 
COinS