MC-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors

Jaewoo Lee; Kieu My Phan; Xiaozhe Gu; Jiyeon Lee; Arvind Easwaran; Insik Shin; Insup Lee

doi:10.1109/RTSS.2014.32

MC-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors

Jaewoo Lee^*, Kieu My Phan, Xiaozhe Gu, Jiyeon Lee, Arvind Easwaran, Insik Shin, Insup Lee

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

49 Citations (Scopus)

Abstract

A mixed-criticality system consists of multiple components with different criticalities. While mixed-criticality scheduling has been extensively studied for the uniprocessor case, the problem of efficient scheduling for the multiprocessor case has largely remained open. We design a fluid model-based multiprocessor mixed-criticality scheduling algorithm, called MC-Fluid, in which each task is executed in proportion to its criticality-dependent rate. We propose an exact schedulability condition for MC-Fluid and an optimal assignment algorithm for criticality-dependent execution rates with polynomial complexity. Since MC-Fluid cannot construct a schedule on real hardware platforms due to the fluid assumption, we propose MC-DP-Fair algorithm, which can generate a non-fluid schedule while preserving the same schedulability properties as MC-Fluid. We show that MC-Fluid has a speedup factor of (1 + v 5)/2 ( 1.618), which is best known in multiprocessor MC scheduling, and simulation results show that MC-DP-Fair outperforms all existing algorithms.

Original language	English
Title of host publication	Proceedings - IEEE 35th Real-Time Systems Symposium, RTSS 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	41-52
Number of pages	12
Edition	January
ISBN (Electronic)	9781479972876
DOIs	https://doi.org/10.1109/RTSS.2014.32
Publication status	Published - Jan 14 2015
Externally published	Yes
Event	35th IEEE Real-Time Systems Symposium, RTSS 2014 - Rome, Italy Duration: Dec 2 2014 → Dec 5 2014

Publication series

Name	Proceedings - Real-Time Systems Symposium
Number	January
Volume	2015-January
ISSN (Print)	1052-8725

Conference

Conference	35th IEEE Real-Time Systems Symposium, RTSS 2014
Country/Territory	Italy
City	Rome
Period	12/2/14 → 12/5/14

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

ASJC Scopus Subject Areas

Software
Hardware and Architecture
Computer Networks and Communications

Keywords

mixed-criticality
multiprocessor scheduling
schedulability analysis
scheduling algorithm

Access to Document

10.1109/RTSS.2014.32

Cite this

Lee, J., Phan, K. M., Gu, X., Lee, J., Easwaran, A., Shin, I., & Lee, I. (2015). MC-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors. In Proceedings - IEEE 35th Real-Time Systems Symposium, RTSS 2014 (January ed., pp. 41-52). Article 7010473 (Proceedings - Real-Time Systems Symposium; Vol. 2015-January, No. January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/RTSS.2014.32

@inproceedings{a8e2cb899bba442da6bb35ec6972bf82,

title = "MC-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors",

abstract = "A mixed-criticality system consists of multiple components with different criticalities. While mixed-criticality scheduling has been extensively studied for the uniprocessor case, the problem of efficient scheduling for the multiprocessor case has largely remained open. We design a fluid model-based multiprocessor mixed-criticality scheduling algorithm, called MC-Fluid, in which each task is executed in proportion to its criticality-dependent rate. We propose an exact schedulability condition for MC-Fluid and an optimal assignment algorithm for criticality-dependent execution rates with polynomial complexity. Since MC-Fluid cannot construct a schedule on real hardware platforms due to the fluid assumption, we propose MC-DP-Fair algorithm, which can generate a non-fluid schedule while preserving the same schedulability properties as MC-Fluid. We show that MC-Fluid has a speedup factor of (1 + v 5)/2 ( 1.618), which is best known in multiprocessor MC scheduling, and simulation results show that MC-DP-Fair outperforms all existing algorithms.",

keywords = "mixed-criticality, multiprocessor scheduling, schedulability analysis, scheduling algorithm",

author = "Jaewoo Lee and Phan, {Kieu My} and Xiaozhe Gu and Jiyeon Lee and Arvind Easwaran and Insik Shin and Insup Lee",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 35th IEEE Real-Time Systems Symposium, RTSS 2014 ; Conference date: 02-12-2014 Through 05-12-2014",

year = "2015",

month = jan,

day = "14",

doi = "10.1109/RTSS.2014.32",

language = "English",

series = "Proceedings - Real-Time Systems Symposium",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "January",

pages = "41--52",

booktitle = "Proceedings - IEEE 35th Real-Time Systems Symposium, RTSS 2014",

address = "United States",

edition = "January",

}

Lee, J, Phan, KM, Gu, X, Lee, J, Easwaran, A, Shin, I & Lee, I 2015, MC-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors. in Proceedings - IEEE 35th Real-Time Systems Symposium, RTSS 2014. January edn, 7010473, Proceedings - Real-Time Systems Symposium, no. January, vol. 2015-January, Institute of Electrical and Electronics Engineers Inc., pp. 41-52, 35th IEEE Real-Time Systems Symposium, RTSS 2014, Rome, Italy, 12/2/14. https://doi.org/10.1109/RTSS.2014.32

MC-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors. / Lee, Jaewoo; Phan, Kieu My; Gu, Xiaozhe et al.
Proceedings - IEEE 35th Real-Time Systems Symposium, RTSS 2014. January. ed. Institute of Electrical and Electronics Engineers Inc., 2015. p. 41-52 7010473 (Proceedings - Real-Time Systems Symposium; Vol. 2015-January, No. January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - MC-fluid

T2 - 35th IEEE Real-Time Systems Symposium, RTSS 2014

AU - Lee, Jaewoo

AU - Phan, Kieu My

AU - Gu, Xiaozhe

AU - Lee, Jiyeon

AU - Easwaran, Arvind

AU - Shin, Insik

AU - Lee, Insup

PY - 2015/1/14

Y1 - 2015/1/14

N2 - A mixed-criticality system consists of multiple components with different criticalities. While mixed-criticality scheduling has been extensively studied for the uniprocessor case, the problem of efficient scheduling for the multiprocessor case has largely remained open. We design a fluid model-based multiprocessor mixed-criticality scheduling algorithm, called MC-Fluid, in which each task is executed in proportion to its criticality-dependent rate. We propose an exact schedulability condition for MC-Fluid and an optimal assignment algorithm for criticality-dependent execution rates with polynomial complexity. Since MC-Fluid cannot construct a schedule on real hardware platforms due to the fluid assumption, we propose MC-DP-Fair algorithm, which can generate a non-fluid schedule while preserving the same schedulability properties as MC-Fluid. We show that MC-Fluid has a speedup factor of (1 + v 5)/2 ( 1.618), which is best known in multiprocessor MC scheduling, and simulation results show that MC-DP-Fair outperforms all existing algorithms.

AB - A mixed-criticality system consists of multiple components with different criticalities. While mixed-criticality scheduling has been extensively studied for the uniprocessor case, the problem of efficient scheduling for the multiprocessor case has largely remained open. We design a fluid model-based multiprocessor mixed-criticality scheduling algorithm, called MC-Fluid, in which each task is executed in proportion to its criticality-dependent rate. We propose an exact schedulability condition for MC-Fluid and an optimal assignment algorithm for criticality-dependent execution rates with polynomial complexity. Since MC-Fluid cannot construct a schedule on real hardware platforms due to the fluid assumption, we propose MC-DP-Fair algorithm, which can generate a non-fluid schedule while preserving the same schedulability properties as MC-Fluid. We show that MC-Fluid has a speedup factor of (1 + v 5)/2 ( 1.618), which is best known in multiprocessor MC scheduling, and simulation results show that MC-DP-Fair outperforms all existing algorithms.

KW - mixed-criticality

KW - multiprocessor scheduling

KW - schedulability analysis

KW - scheduling algorithm

UR - http://www.scopus.com/inward/record.url?scp=84936936796&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84936936796&partnerID=8YFLogxK

U2 - 10.1109/RTSS.2014.32

DO - 10.1109/RTSS.2014.32

M3 - Conference contribution

AN - SCOPUS:84936936796

T3 - Proceedings - Real-Time Systems Symposium

SP - 41

EP - 52

BT - Proceedings - IEEE 35th Real-Time Systems Symposium, RTSS 2014

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 2 December 2014 through 5 December 2014

ER -

Lee J, Phan KM, Gu X, Lee J, Easwaran A, Shin I et al. MC-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors. In Proceedings - IEEE 35th Real-Time Systems Symposium, RTSS 2014. January ed. Institute of Electrical and Electronics Engineers Inc. 2015. p. 41-52. 7010473. (Proceedings - Real-Time Systems Symposium; January). doi: 10.1109/RTSS.2014.32

MC-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this