FIFO with Offsets: High Schedulability with Low Overheads

Mitra Nasri, Robert Ian Davis, Bjorn Brandenburg

Research output: Contribution to conferencePaperpeer-review


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 languageEnglish
Number of pages12
Publication statusPublished - 9 Aug 2018
Event24th IEEE Real-Time and Embedded Technology and Applications Symposium -
Duration: 11 Apr 201813 Apr 2018


Conference24th IEEE Real-Time and Embedded Technology and Applications Symposium
Abbreviated titleRTAS 2018

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 2019 Elsevier B.V., All rights reserved.


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

Cite this