FIFO with Offsets: High Schedulability with Low Overheads

The OS scheduler’s memory and runtime overheadsform crucial design constraints for embedded systems implementedon low-cost hardware platforms. Table-driven schedulingcan provide a high level of schedulability; however, it alsoconsumes significant amounts of memory. By contrast, effectivenon-preemptive scheduling policies, such as the non-workconservingCritical-Window EDF (CW-EDF), have low memoryusage, but substantial runtime overheads. This paper aims toachieve efficient and effective non-preemptive scheduling by usinga First-In-First-Out (FIFO) scheduling policy combined with anovel offset tuning technique. This technique enables the FIFOpolicy to reproduce a given feasible schedule, such as thatfollowed 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 overheadsare also tightly constrained. The proposed solution is evaluatedin terms of runtime overhead, memory consumption, and schedulabilityratio, using a prototype implementation on an Arduinoboard. This shows that FIFO with offset tuning can match theschedulability ratio of CW-EDF, while typically exhibiting lowerscheduling overheads and memory consumption than the stateof-the-artOffline Equivalence technique, which is based on NonPreemptiveFixed Priority (NP-FP) scheduling.