RTAS’17 Supplemental Materials

This page provides the implementation and all measured overhead data for the paper:

Provided information:

Arduino Implementation

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.)

Instructions

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.

Preparation

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.

Compilation

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.

Select Experiment Mode

The sketch supports two experiment modes: one-shot mode and loop mode.

To choose which mode the sketch runs in, open the file RTAS17/config.h and either comment or uncomment the macro TABLES_IN_FLASH:

Select the Scheduling Policy

The sketch contains implementations of the following non-preemptive scheduling policies / techniques:

  1. work-conserving Fixed-Priority (FP) scheduling, realized in the file RTAS17/sched_fp.cpp;

  2. work-conserving Earliest-Deadline First (EDF) scheduling, realized in the file RTAS17/sched_edf.cpp;

  3. non-work-conserving Precautious Rate-Monotonic (PCRM) scheduling, realized in the file RTAS17/sched_pcrm.cpp;

  4. non-work-conserving Critical-Window EDF (CW-EDF), realized in the file RTAS17/sched_edf_cw.cpp;

  5. plain table-driven (TD) scheduling, realized in the file RTAS17/sched_table.cpp; and

  6. 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.

Scheduler Selection in 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:

Scheduler Selection in One-Shot Mode

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).

Generating Flash-Based Tables

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.

Example: Table-Driven Scheduling

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.

Example: Offline-Equivalence Scheduling

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.

Example: Fixed-Priority Scheduling

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

Results

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.

Overhead Data

The complete set of overheads as reported in the paper is available for download.