This page provides the implementation and all measured overhead data for the paper:
Provided information:
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_FLASH:
TABLES_IN_FLASH is 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:
RTAS17/sched_fp.cpp;work-conserving Earliest-Deadline First (EDF) scheduling, realized in the file RTAS17/sched_edf.cpp;
non-work-conserving Precautious Rate-Monotonic (PCRM) scheduling, realized in the file RTAS17/sched_pcrm.cpp;
non-work-conserving Critical-Window EDF (CW-EDF), realized in the file RTAS17/sched_edf_cw.cpp;
plain table-driven (TD) scheduling, realized in the file RTAS17/sched_table.cpp; and
the newly proposed Offline Equivalence (OE) scheduler, realized in the file RTAS17/sched_oe.cpp.
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_FP for FP scheduling;WANT_SCHED_EDF for EDF scheduling;WANT_SCHED_PCRM for PCRM scheduling;WANT_SCHED_EDF_CW for CW-EDF scheduling;WANT_SCHED_TABLE for TD scheduling; andWANT_SCHED_OE for 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
Expected output:
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
Expected output:
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
Expected output:
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 RESULTS/datan<N>/<EXP-ID>/<SCHED>.CSV, where 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) |
See write_results() in RTAS17/experiment.cpp for further details.
The scripts merge.sh and 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.