FIFO with Offsets - High Schedulability with Low Overheads.

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

Onderzoeksoutput: Bijdrage aan congresPaper

2 Citaten (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.

Originele taal-2Engels
Aantal pagina's12
StatusGepubliceerd - 8 aug 2018
Extern gepubliceerdJa

Bibliografische nota

DBLP's bibliographic metadata records provided through are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.


Duik in de onderzoeksthema's van 'FIFO with Offsets - High Schedulability with Low Overheads.'. Samen vormen ze een unieke vingerafdruk.

Citeer dit