Mitra Nasri

Offline Equivalence: A Non-Preemptive Scheduling Technique for Resource-Constrained Embedded Real-Time Systems
Max Planck Institute for Software Systems, Germany
16, May, 2017 11:30-12:15 (45 minutes)
CISTER, Porto, Portugal


Embedded systems subject to severe cost, power, or energy constraints usually have only very limited processing capacity and small memories. Since these systems are usually mass produced, saving money in any hardware component will increase the total profit. Due to limited processing power and memory, these systems execute their functions non-preemptively because typically they do not have an operating system to support preemption. Two possible choices of scheduling tasks in these systems are table-based scheduling and online scheduling. However, on the one hand, a table-based scheduling approach might not be applicable due to limited memory, and on the other hand, the existing online non-preemptive scheduling algorithms are either not efficient in terms of the schedulability ratio, or suffer from considerable runtime overhead.
To arrive at a compromise, this talk proposes an online policy that is equivalent to a given offline table to combine some of the advantages of both online and offline scheduling: we first consider a low-overhead online scheduling algorithm as a baseline, and then identify any irregular situations where a given offline table differs from the schedule generated by the online algorithm. We store any such irregularities in tables for use by the online scheduling algorithm, which then can recreate the table at runtime. To generate suitable tables, we provide an offline scheduling algorithm for non-preemptive tasks, and a table-transformation algorithm to reduce the number of irregularities that must be stored. We evaluate the proposed solution using an Arduino hardware board. Our technique result in a substantial reduction of scheduling overhead compared to the online scheduler that achieves the highest schedulability ratio, while having to store on average only a few dozen to a few hundreds of bytes of the offline schedule.

CISTER's participants:
Mitra Nasri

S101 Auditorium/Seminar Room
1st Floor