This page provides the implementation and all measured overhead data for the paper:
We prototyped the proposed Offline Equivalence scheduler as well as a number of baseline schedulers using Arduino (version 1.6.13).
Our complete solution is available for download under a liberal open-source license (2-clause BSD).
The code and related scripts are known to work on macOS 10.11 (“Sierra”) and on recent Linux versions (e.g., Ubuntu LTS 14.04). You can compile the sketch in “loop mode” (see below) also on Windows, but the scripts needed for “one-shot mode” (see below) are not supported on Windows. (With some effort it could probably be made to work with Cygwin.)
While the implementation is largely undocumented, the code is reasonably clean and simple. It should thus not be too difficult to make sense of it for someone familiar with Arduino programming or embedded programming in general. To get started, follow these instructions.
The sketch requires an Arduino shield with an SD card adapter that is supported by the
SD module that is part of Arduino.
The sketch further expects the SD card to be structured in a particular way as given in the directory
Data/SD in the provided ZIP archive.
To run the sketch, first copy the folder
Data/SD onto an SD card and insert it into the SD card reader.
To compile an image file for Arduino, either open the provided sketch file (
RTAS17.ino) and use the Arduino IDE, or use the provided
Makefile in the
RTAS17/ folder. The latter approach requires the very flexible and general Arduino Makefile provided at
to be installed first. You may have to adjust some of the paths in
RTAS17/Makefile to suit your system’s configuration.
The sketch supports two experiment modes: one-shot mode and loop mode.
In one-shot mode, exactly one task set is run, overheads are collected, reported, and stored to the SD card, and then the system terminates. Importantly, all scheduling and irregularity tables are stored in flash memory when running in one-shot mode.
In loop mode, experiments are read from an SD card, where all experimental task sets and all scheduling and irregularity tables are stored in a simple textual format (see the
Data/SD folder in the provided ZIP archive). The sketch will loop over all experiments and, for each experiment, load the task set and all tables from the SD card into RAM.
To choose which mode the sketch runs in, open the file
RTAS17/config.h and either comment or uncomment the macro
TABLES_IN_FLASHis defined, then the sketch runs in one-shot mode (and compiles all tables into the image);
The sketch contains implementations of the following non-preemptive scheduling policies / techniques:
work-conserving Fixed-Priority (FP) scheduling, realized in the file
work-conserving Earliest-Deadline First (EDF) scheduling, realized in the file
non-work-conserving Precautious Rate-Monotonic (PCRM) scheduling, realized in the file
non-work-conserving Critical-Window EDF (CW-EDF), realized in the file
plain table-driven (TD) scheduling, realized in the file
the newly proposed Offline Equivalence (OE) scheduler, realized in the file
The active scheduling policy must be chosen at compile time. (All other inactive policies are not compiled into the image for space reasons.) How this is done depends on whether the system operates in one-shot or loop mode.
In loop mode, the scheduler is selected by defining exactly one of the following macros in the file
RTAS17/config.h, with the obvious interpretation that the chosen scheduler will be compiled into the image:
WANT_SCHED_FPfor FP scheduling;
WANT_SCHED_EDFfor EDF scheduling;
WANT_SCHED_PCRMfor PCRM scheduling;
WANT_SCHED_EDF_CWfor CW-EDF scheduling;
WANT_SCHED_TABLEfor TD scheduling; and
WANT_SCHED_OEfor OE scheduling.
In one-shot mode, the scheduler is chosen based on the macro defined in the file
RTAS17/gentab_exp.h, which is auto-generated by the tool
scripts/mk-includes.sh (see next point).
When operating in one-shot mode, all task parameters and any scheduling and irregularity tables are compiled into the image. That is, this information is not read from the SD card in one-shot mode, which is much closer to how a scheduler operates in a real embedded application (i.e., the task system is configured at compile time and stored in flash memory).
This requires all relevant include files to be prepared prior to compilation. To automate this step, we provide the script
scripts/mk-includes.sh, which takes care of preparing all files needed for one-shot mode.
For example, to prepare the system for running the 300th task set for n=9 tasks under TD scheduling, issue the following commands:
cd RTAS17 ../scripts/mk-includes.sh ../Data/SD/datan9/300 TABLE
Experiment: ../Data/SD/datan9/300 Scheduler: WANT_SCHED_TABLE #define EXP_NAME "datan9/300" #define EXP_DATA_FILE "RESULTS/datan9/300/" SCHEDULER_KEY ".csv" #define EXP_ID 300 #define WANT_SCHED_TABLE
At this point, the system is ready for compilation. The scheduling table provided in the file
Data/SD/datan9/300/tt.txt has been encoded in the file
gentab_tt.h and will be compiled into the final image.
Analogously, to prepare the system for OE scheduling, use the command:
../scripts/mk-includes.sh ../Data/SD/datan9/300 OE
Experiment: ../Data/SD/datan9/300 Scheduler: WANT_SCHED_OE #define EXP_NAME "datan9/300" #define EXP_DATA_FILE "RESULTS/datan9/300/" SCHEDULER_KEY ".csv" #define EXP_ID 300 #define WANT_SCHED_OE
The priority-inversion irregularity table provided in the file
Data/SD/datan9/300/pi.txt and the idle-time irregularity table provided in the file
Data/SD/datan9/300/it.txt have been encoded in the file
gentab_oe.h and will be compiled into the final image.
Analogously, to prepare the system for FP scheduling, use the command:
../scripts/mk-includes.sh ../Data/SD/datan9/300 FP
Experiment: ../Data/SD/datan9/300 Scheduler: WANT_SCHED_FP #define EXP_NAME "datan9/300" #define EXP_DATA_FILE "RESULTS/datan9/300/" SCHEDULER_KEY ".csv" #define EXP_ID 300 #define WANT_SCHED_FP
The sketch, in both one-shot and loop mode, writes the overheads observed into a
CSV file on the SD card. Specifically, the data is stored in the file
N is the number of tasks (3, 6, 9, or 12),
EXP-ID is a sequence number ranging from 1 to 1000, and
SCHED names the active scheduling policy.
The data is stored in the following simple format.
|Column 1||Column 2||Column 3||Column 4||Column 5||Column 6||Column 7|
|Scheduler name||Number of tasks||Experiment ID||Number of collected scheduling overhead samples||Sum of all samples (in µs)||Maximum observed sample (in µs)||Minimum observed sample (in µs)|
RTAS17/experiment.cpp for further details.
summarize.py (in the
scripts/ folder) can help with aggregating the individual per-experiment files.
The complete set of overheads as reported in the paper is available for download.