FIFO with Offsets: High Schedulability with Low Overheads

Research output: Contribution to conferencePaper




Conference24th IEEE Real-Time and Embedded Technology and Applications Symposium
Abbreviated titleRTAS 2018
Conference date(s)11/04/1813/04/18

Publication details

DatePublished - 11 Apr 2018
Number of pages12
Original languageEnglish


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.

    Research areas

  • real-time, scheduling, FIFO, operating system, policy, efficiency, memory usage

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations