FIFO with Offsets - High Schedulability with Low Overheads.

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

Research output: Contribution to conferencePaper

2 Citations (Scopus)

Abstract

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
Pages271-282
Number of pages12
DOIs
Publication statusPublished - 8 Aug 2018
Externally publishedYes

Bibliographical note

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api 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.

Keywords

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

Fingerprint

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

Cite this