FIFO with Offsets: High Schedulability with Low Overheads

Mitra Nasri; Robert Ian Davis; Bjorn  Brandenburg

doi:10.1109/RTAS.2018.00035

FIFO with Offsets: High Schedulability with Low Overheads

Mitra Nasri, Robert Ian Davis, Bjorn Brandenburg

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

The OS scheduler’s memory and runtime overheads
form crucial design constraints for embedded systems implemented
on low-cost hardware platforms. Table-driven scheduling
can provide a high level of schedulability; however, it also
consumes significant amounts of memory. By contrast, effective
non-preemptive scheduling policies, such as the non-workconserving
Critical-Window EDF (CW-EDF), have low memory
usage, but substantial runtime overheads. This paper aims to
achieve efficient and effective non-preemptive scheduling by using
a First-In-First-Out (FIFO) scheduling policy combined with a
novel offset tuning technique. This technique enables the FIFO
policy to reproduce a given feasible schedule, such as that
followed by CW-EDF, resulting in a high level of schedulability,
combined with comparatively low runtime overheads. Further,
by using a small number of offsets per task, memory overheads
are also tightly constrained. The proposed solution is evaluated
in terms of runtime overhead, memory consumption, and schedulability
ratio, using a prototype implementation on an Arduino
board. This shows that FIFO with offset tuning can match the
schedulability ratio of CW-EDF, while typically exhibiting lower
scheduling overheads and memory consumption than the stateof-the-art
Offline Equivalence technique, which is based on NonPreemptive
Fixed Priority (NP-FP) scheduling.

Original language	English
Pages	271-282
Number of pages	12
DOIs	https://doi.org/10.1109/RTAS.2018.00035
Publication status	Published - 9 Aug 2018
Event	24th IEEE Real-Time and Embedded Technology and Applications Symposium - Duration: 11 Apr 2018 → 13 Apr 2018

Conference

Conference	24th IEEE Real-Time and Embedded Technology and Applications Symposium
Abbreviated title	RTAS 2018
Period	11/04/18 → 13/04/18

Bibliographical note

Funding Information:
ACKNOWLEDGMENTS The first author is supported by a fellowshipby the Alexander von Humboldt Foundation. The authors would like to thank Schloss Dagstuhl for seminar number 17131, which initiated this work. The research in this paper is partially funded by the ESPRC grant, MCCps (EP/K011626/1). EPSRC Research Data Management: No new primary data was created during this study.

Publisher Copyright:
© 2018 IEEE.

Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.

Keywords

real-time
scheduling
FIFO
operating system
policy
efficiency
memory usage
Real time scheduling
Static scheduling
Non preemptive scheduling
Offsets
Time triggered scheduling
FIFO scheduling

Access to Document

10.1109/RTAS.2018.00035Licence: Unspecified

Cite this

@conference{2eb17ad60dcc463b922b108db4502fdb,

title = "FIFO with Offsets: High Schedulability with Low Overheads",

abstract = "The OS scheduler{\textquoteright}s memory and runtime overheadsform crucial design constraints for embedded systems implementedon low-cost hardware platforms. Table-driven schedulingcan provide a high level of schedulability; however, it alsoconsumes significant amounts of memory. By contrast, effectivenon-preemptive scheduling policies, such as the non-workconservingCritical-Window EDF (CW-EDF), have low memoryusage, but substantial runtime overheads. This paper aims toachieve efficient and effective non-preemptive scheduling by usinga First-In-First-Out (FIFO) scheduling policy combined with anovel offset tuning technique. This technique enables the FIFOpolicy to reproduce a given feasible schedule, such as thatfollowed by CW-EDF, resulting in a high level of schedulability,combined with comparatively low runtime overheads. Further,by using a small number of offsets per task, memory overheadsare also tightly constrained. The proposed solution is evaluatedin terms of runtime overhead, memory consumption, and schedulabilityratio, using a prototype implementation on an Arduinoboard. This shows that FIFO with offset tuning can match theschedulability ratio of CW-EDF, while typically exhibiting lowerscheduling overheads and memory consumption than the stateof-the-artOffline Equivalence technique, which is based on NonPreemptiveFixed Priority (NP-FP) scheduling.",

keywords = "real-time, scheduling, FIFO, operating system, policy, efficiency, memory usage, Real time scheduling, Static scheduling, Non preemptive scheduling, Offsets, Time triggered scheduling, FIFO scheduling",

author = "Mitra Nasri and Davis, {Robert Ian} and Bjorn Brandenburg",

note = "Funding Information: ACKNOWLEDGMENTS The first author is supported by a fellowshipby the Alexander von Humboldt Foundation. The authors would like to thank Schloss Dagstuhl for seminar number 17131, which initiated this work. The research in this paper is partially funded by the ESPRC grant, MCCps (EP/K011626/1). EPSRC Research Data Management: No new primary data was created during this study. Publisher Copyright: {\textcopyright} 2018 IEEE. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.; 24th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2018 ; Conference date: 11-04-2018 Through 13-04-2018",

year = "2018",

month = aug,

day = "9",

doi = "10.1109/RTAS.2018.00035",

language = "English",

pages = "271--282",

}

TY - CONF

T1 - FIFO with Offsets: High Schedulability with Low Overheads

AU - Nasri, Mitra

AU - Davis, Robert Ian

AU - Brandenburg, Bjorn

N1 - Funding Information: ACKNOWLEDGMENTS The first author is supported by a fellowshipby the Alexander von Humboldt Foundation. The authors would like to thank Schloss Dagstuhl for seminar number 17131, which initiated this work. The research in this paper is partially funded by the ESPRC grant, MCCps (EP/K011626/1). EPSRC Research Data Management: No new primary data was created during this study. Publisher Copyright: © 2018 IEEE. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.

PY - 2018/8/9

Y1 - 2018/8/9

N2 - The OS scheduler’s memory and runtime overheadsform crucial design constraints for embedded systems implementedon low-cost hardware platforms. Table-driven schedulingcan provide a high level of schedulability; however, it alsoconsumes significant amounts of memory. By contrast, effectivenon-preemptive scheduling policies, such as the non-workconservingCritical-Window EDF (CW-EDF), have low memoryusage, but substantial runtime overheads. This paper aims toachieve efficient and effective non-preemptive scheduling by usinga First-In-First-Out (FIFO) scheduling policy combined with anovel offset tuning technique. This technique enables the FIFOpolicy to reproduce a given feasible schedule, such as thatfollowed by CW-EDF, resulting in a high level of schedulability,combined with comparatively low runtime overheads. Further,by using a small number of offsets per task, memory overheadsare also tightly constrained. The proposed solution is evaluatedin terms of runtime overhead, memory consumption, and schedulabilityratio, using a prototype implementation on an Arduinoboard. This shows that FIFO with offset tuning can match theschedulability ratio of CW-EDF, while typically exhibiting lowerscheduling overheads and memory consumption than the stateof-the-artOffline Equivalence technique, which is based on NonPreemptiveFixed Priority (NP-FP) scheduling.

AB - The OS scheduler’s memory and runtime overheadsform crucial design constraints for embedded systems implementedon low-cost hardware platforms. Table-driven schedulingcan provide a high level of schedulability; however, it alsoconsumes significant amounts of memory. By contrast, effectivenon-preemptive scheduling policies, such as the non-workconservingCritical-Window EDF (CW-EDF), have low memoryusage, but substantial runtime overheads. This paper aims toachieve efficient and effective non-preemptive scheduling by usinga First-In-First-Out (FIFO) scheduling policy combined with anovel offset tuning technique. This technique enables the FIFOpolicy to reproduce a given feasible schedule, such as thatfollowed by CW-EDF, resulting in a high level of schedulability,combined with comparatively low runtime overheads. Further,by using a small number of offsets per task, memory overheadsare also tightly constrained. The proposed solution is evaluatedin terms of runtime overhead, memory consumption, and schedulabilityratio, using a prototype implementation on an Arduinoboard. This shows that FIFO with offset tuning can match theschedulability ratio of CW-EDF, while typically exhibiting lowerscheduling overheads and memory consumption than the stateof-the-artOffline Equivalence technique, which is based on NonPreemptiveFixed Priority (NP-FP) scheduling.

KW - real-time

KW - scheduling

KW - FIFO

KW - operating system

KW - policy

KW - efficiency

KW - memory usage

KW - Real time scheduling

KW - Static scheduling

KW - Non preemptive scheduling

KW - Offsets

KW - Time triggered scheduling

KW - FIFO scheduling

UR - https://www-users.cs.york.ac.uk/~robdavis/papers/RTAS2018FIFOoffsets.pdf

UR - https://www-users.cs.york.ac.uk/~robdavis/

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

U2 - 10.1109/RTAS.2018.00035

DO - 10.1109/RTAS.2018.00035

M3 - Paper

SP - 271

EP - 282

T2 - 24th IEEE Real-Time and Embedded Technology and Applications Symposium

Y2 - 11 April 2018 through 13 April 2018

ER -

FIFO with Offsets: High Schedulability with Low Overheads

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Mixed Criticality Cyber- Physical Systems

Cite this

FIFO with Offsets: High Schedulability with Low Overheads

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Projects

Mixed Criticality Cyber- Physical Systems

Cite this