FIFO with Offsets: High Schedulability with Low Overheads

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

11 Citaten (Scopus)

Samenvatting

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
Titel2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)
UitgeverijInstitute of Electrical and Electronics Engineers
Pagina's271-282
Aantal pagina's12
ISBN van elektronische versie978-1-5386-5295-4
DOI's
StatusGepubliceerd - 9 aug. 2018
Extern gepubliceerdJa
Evenement24th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2018 - Porto, Portugal
Duur: 11 apr. 201813 apr. 2018
Congresnummer: 24

Congres

Congres24th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2018
Verkorte titelRTAS 2018
Land/RegioPortugal
StadPorto
Periode11/04/1813/04/18

Vingerafdruk

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

Citeer dit