(2017) Offline Equivalence: A Non-preemptive Scheduling Technique for Resource-Constrained Embedded Real-Time Systems.
Abstract
We consider the problem of scheduling a set of nonpreemptive periodic tasks in an embedded system with a limited amount of memory. On the one hand, due to the memory limitations, a table-based scheduling approach might not be applicable, 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 paper 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 nonpreemptive tasks, and a table-transformation algorithm to reduce the number of irregularities that must be stored. In an evaluation using an Arduino board and synthetic task sets, we have observed the technique to result in a substantial reduction of scheduling overhead compared toCW-EDF, 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 static schedule.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Uncontrolled Keywords: | embedded systems;resource allocation;scheduling;Arduino board;memory limitations;non-preemptive scheduling;offline equivalence;offline scheduling algorithm;online policy;online scheduling algorithm;periodic tasks scheduling;resource-constrained embedded real-time systems;synthetic task sets;table-based scheduling;Embedded systems;Memory management;Random access memory;Runtime;Schedules;Scheduling algorithms;Windows |
| Conference: | RTAS IEEE Real-Time and Embedded Technology and Applications Symposium |
| Depositing User: | Andreas Rau |
| Date Deposited: | 22 Feb 2018 10:43 |
| Last Modified: | 18 Jul 2019 12:12 |
| Primary Research Area: | NRA5: Empirical & Behavioral Security |
| URI: | https://publications.cispa.saarland/id/eprint/1537 |
Actions
Actions (login required)
 |
View Item |