FIFO with Offsets: High Schedulability with Low Overheads

Mitra Nasri, Robert I. Davis, Björn B. Brandenburg

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)


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-work-conserving 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 state-of-the-art Offline Equivalence technique, which is based on Non-Preemptive Fixed Priority (NP-FP) scheduling.

Original languageEnglish
Title of host publication2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)
PublisherInstitute of Electrical and Electronics Engineers
Number of pages12
ISBN (Electronic)978-1-5386-5295-4
Publication statusPublished - 9 Aug 2018
Externally publishedYes
Event24th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2018 - Porto, Portugal
Duration: 11 Apr 201813 Apr 2018
Conference number: 24


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


  • FIFO scheduling
  • Non preemptive scheduling
  • Offsets
  • Real time scheduling
  • Static scheduling
  • Time triggered scheduling


Dive into the research topics of 'FIFO with Offsets: High Schedulability with Low Overheads'. Together they form a unique fingerprint.

Cite this