This guide explains how to reproduce the overhead and migration-rate experiments discussed in Section VII of the paper
B. Brandenburg and M. Gül, “Global Scheduling Not Required: Simple, Near-Optimal Multiprocessor Real-Time Scheduling with Semi-Partitioned Reservations”, Proceedings of the 37th IEEE Real-Time Systems Symposium (RTSS 2016), to appear, December 2016.
The proposed scheduling approach based on semi-partitioned reservations was implemented and evaluated in LITMUSRT, which is an extension of the Linux kernel. This document explains how to compile, install, and run LITMUSRT, and how to collect and process overhead measurements. It is organized as follows:
See also: Part 1 of the Artifact Evaluation instructions.
Please follow the instructions detailed in each section. In case of problems or further questions, feel free to contact us by email.
The paper reports empirical data measured on a particular hardware platform available at the time of writing in the lab of MPI-SWS. To reproduce the exact numbers reported in the paper, it would be necessary to have access to this particular machine, or one identical to it. The focus of this document is hence how to obtain measurements like those reported in the paper, and not on reproducing the exact numbers (i.e., the goal is to observe the same basic trends).
We provide instructions both for running the full experiments, which however requires access to a 44-core machine, and for running toy experiments, for which a 4-core machine suffices. We hope that running the 4-core toy experiments may be sufficient to establish that the provided implementation, instructions, and the general measurement procedure work.
In a pinch, it’s also possible to use a virtual machine with four virtual cores to run the toy experiments. For convenience, we provide such a ready-made VM for use with VirtualBox. However, in a virtual machine, all collected data will be bogus due to virtualization overheads.
On the experimental platform, to approximate our settings, disable all architectural features that cause unpredictability such as hyper-threading, cache prefetching, and “turbo boost” (in the BIOS).
To reproduce our setup exactly, the experiments should be run on a Dell PowerEdge R630 server with two sockets, each containing a 22-core Intel Xeon CPU E5–2699 v4 processor clocked at 2.2 GHz.
To conduct overhead experiments similar to those reported in the paper, the following software components are needed:
liblitmus user-space library, which provides the necessary tools for working with a LITMUSRT kernel. The liblitmus library also comes with rtspin, a tool for simulating CPU-bound, periodic real-time tasks, which is employed as the workload in the experiments.feather-trace-tools project, a collection of tracing and and analysis tools used to collect overheads under LITMUSRT.We provide two ways of obtaining a suitable setup for running experiments.
We provide a ready-made Ubuntu VM that comes with the kernel and all necessary tools pre-installed. Using this VM is the easiest way; however, it comes with the disadvantage that all measurements from within the VM will be bogus due to virtualization overheads.
Alternatively, we provide items 2–7 together in a single archive, which can be used to manually compile and install LITMUSRT and the supporting libraries on essentially any Linux system. Detailed installation instructions are provided below.
While the first approach is much simpler and doesn’t require knowledge of how to configure & install a custom kernel, the second approach has the advantage that it yields realistic overheads.
To use the ready-made VM, simply download and extract the provided VM image:
wget http://www.litmus-rt.org/ae/litmus-2016.1-with-semi-part-reservations.qcow.tgz
tar xzf litmus-2016.1-with-semi-part-reservations.qcow.tgz
This should result in a disk image file named litmus-2016.1.qcow.
The provided disk image is intended for use with VirtualBox. If required download and install the latest version of VirtualBox.
Finally, create a new Linux VM in VirtualBox using the downloaded disk image, which is named litmus-2016.1.qcow. For detailed instructions, refer to the LITMUSRT tutorial, and in particular to the VM setup instructions.
Make sure give the VM is configured to have four virtual cores, and at least 2 GiB of RAM.
After booting into the VM, use the following credentials to log in:
litmuslitmusAll relevant tools can be found in /usr/local/litmus/sp-res.
Once logged in, open a terminal and double-check that the VM has indeed four virtual processors by running the following command inside the VM:
grep CPU /proc/cpuinfo | wc -l
The expected output is 4.
Continue with Step 9.
To manually set up the software environment, carry out the following step-by-step instructions on the Linux host that will be used for the experiments. All instructions have been tested on a machine running Ubuntu Linux 14.04 LTS. In principle, it should be possible to use just about any Linux distribution. However, with different compiler versions comes the risk of compilation failures due to newly added warnings (liblitmus is compiled with -Werror). We thus generally recommend to use Ubuntu Linux 14.04 LTS for the purpose of replicating the following instructions.
Prerequisites: manual installation requires prior expertise in working with the Linux kernel. A tutorial on Linux kernel development and detailed instructions on how to compile and configure a Linux kernel that actually works on a given hardware platform is necessarily beyond the scope of this document. Thus, in the following, basic familiarity with Linux kernel development and the compilation and installation of custom Linux kernels on behalf of the evaluator is assumed.
Support: we’ve made all efforts to make reproducing our work as painless as possible, but working with kernels does come with some challenges. In case of problems, please feel free to contact us by email.
Make sure the Linux host is set up for Linux kernel development. This means installing the typical Unix C development chain, including gcc, make, etc. Any Linux installation that can compile a vanilla Linux kernel should also be able to compile the provided version of LITMUSRT.
In the following, we assume that /usr/local/litmus will be used as the working directory for the experiments. Set it up as follows:
cd /usr/local
sudo mkdir litmus
sudo chown $USER litmus
Download and unpack the prepared archive.
cd /usr/local/litmus
wget http://www.mpi-sws.org/~bbb/papers/ae/rtss16/sp-res-litmus.tgz
tar xzf sp-res-litmus.tgz
This creates a folder named sp-res in /usr/local/litmus. To verify this, run the following command:
ls -gGh /usr/local/litmus/sp-res
The following contents should be visible:
drwxr-xr-x 2 2 Jul 26 22:36 data
drwxr-xr-x 6 19 Jul 26 22:35 feather-trace-tools
-rw-r--r-- 1 106K Jul 26 23:18 kernel-config-dell-r630
-rw-r--r-- 1 112K Jul 27 13:19 kernel-config-virtualbox
drwxrwxr-x 9 16 Jul 26 22:42 liblitmus
-rw-r--r-- 1 639K Jul 26 22:27 litmus-rt-with-semi-part-reservations.patch
drwxr-xr-x 5 5 Jul 27 13:24 workloads
Download and extract Linux version 4.1.3 in the folder extracted from the archive (i.e., /usr/local/litmus/sp-res/).
cd /usr/local/litmus/sp-res/
# Download the Linux kernel sources
wget https://www.kernel.org/pub/linux/kernel/v4.x/linux-4.1.3.tar.gz
# Unpack Linux archive into linux-4.1.3
tar xzf linux-4.1.3.tar.gz
# Rename directory into litmus-rt
mv linux-4.1.3 litmus-rt
Do not skip the last step: the directory containing Linux must be called litmus-rt in order for the provided build system to work.
The provided archive contains a single patch that includes both the LITMUSRT base system and the modifications specific to this paper. Apply this patch with the patch utility.
cd /usr/local/litmus/sp-res/litmus-rt/
patch -p1 < ../litmus-rt-with-semi-part-reservations.patch
Our implementation of a reservation framework capable of semi-partitioning can be found in the file litmus/sched_espresso.c and the folder litmus/reservations.
Note: This is the step where prior experience with configuring and compiling the Linux kernel is required.
Prior to compilation, the Linux kernel must configured. In general, it is not possible to tell in advance which configuration options will be required for the hardware platform on which the artifact is going to be evaluated. We thus cannot provide precise instructions for this step.
We provide the following guidelines:
CONFIG_PREEMPT).With regard to configuration options specific to LITMUSRT, there is a configuration group at the very end of the configuration. In these LITMUSRT settings, make sure overhead tracing is enabled (CONFIG_SCHED_OVERHEAD_TRACE=y) and debug tracing is disabled (CONFIG_SCHED_DEBUG_TRACE not set).
After the kernel has been configured, the last couple of lines of the kernel’s .config file should look like this:
#
# LITMUS^RT
#
#
# Scheduling
#
CONFIG_PLUGIN_CEDF=y
CONFIG_PLUGIN_PFAIR=y
CONFIG_RELEASE_MASTER=y
CONFIG_PREFER_LOCAL_LINKING=y
CONFIG_LITMUS_QUANTUM_LENGTH_US=1000
# CONFIG_BUG_ON_MIGRATION_DEADLOCK is not set
#
# Real-Time Synchronization
#
CONFIG_NP_SECTION=y
CONFIG_LITMUS_LOCKING=y
#
# Performance Enhancements
#
# CONFIG_SCHED_CPU_AFFINITY is not set
# CONFIG_ALLOW_EARLY_RELEASE is not set
# CONFIG_EDF_TIE_BREAK_LATENESS is not set
CONFIG_EDF_TIE_BREAK_LATENESS_NORM=y
# CONFIG_EDF_TIE_BREAK_HASH is not set
# CONFIG_EDF_PID_TIE_BREAK is not set
#
# Tracing
#
CONFIG_FEATHER_TRACE=y
CONFIG_SCHED_TASK_TRACE=y
CONFIG_SCHED_TASK_TRACE_SHIFT=13
# CONFIG_SCHED_LITMUS_TRACEPOINT is not set
CONFIG_SCHED_OVERHEAD_TRACE=y
CONFIG_SCHED_OVERHEAD_TRACE_SHIFT=24
# CONFIG_SCHED_DEBUG_TRACE is not set
# CONFIG_REPORT_TIMER_LATENCY is not set
For reference, the provided archive sp-res-litmus.tgz includes two sample kernel configurations:
kernel-config-dell-r630, which is the configuration that we used on our machine for the experiments reported on in the paper; andkernel-config-virtualbox, which is a configuration known to work under Ubuntu 14.04 LTS and VirtualBox.To use the latter configuration as a starting point, copy the file into the kernel source code directory and rename it to .config.
cp -v ../kernel-config-virtualbox .config
If the configured kernel fails to boot or run correctly, this is most likely a configuration problem unrelated to LITMUSRT. When it doubt, first configure and boot a kernel without the LITMUSRT patch.
In the unlikely case that the system boots correctly using a vanilla Linux 4.1.3 kernel (i.e., a kernel without the LITMUSRT path), but fails to boot with LITMUSRT using the same configuration, please contact the LITMUSRT mailing list or the authors.
Once the kernel has been configured, simply compile and install it like any other Linux kernel.
make bzImage modules
sudo make modules_install install
Note that the second step requires root privileges.
Note: Depending on which bootloader the system uses (e.g., grub2 or lilo), it may be necessary to run another utility at this point to update the bootloader configuration. In some cases, it may even be necessary to manually edit the bootloader configuration. As this is highly distribution-dependent, we do not provide any detailed instructions for this step. (On Debian- and Ubuntu-based systems, no manual configuration should be needed.)
Change to the directory of the provided liblitmus and run make. It should find the kernel in ../litmus-rt automatically.
cd /usr/local/litmus/sp-res/liblitmus
make
Change to the directory of the provided feather-trace-tools and run make. It should find the kernel in ../litmus-rt automatically.
cd /usr/local/litmus/sp-res/feather-trace-tools
make
At this point, the software is ready to run experiments.
Reboot the system and select the just-installed LITMUSRT kernel in the menu of the boot loader.
Again, how this exactly works is specific to the particular flavor of Linux installed on the evaluation machine; it will be a familiar step to anyone who is comfortable with compiling and installing custom Linux kernels. On Ubuntu, the newly installed kernel can be found in the submenu labeled “Advanced Options for Ubuntu” under the name “Ubuntu, with Linux 4.1.3”.
Once the kernel has booted, verify that it is indeed the right kernel by inspecting the list of loaded scheduler plugins with the following command.
cat /proc/litmus/plugins/loaded
This should produce the following output (in some order):
PFAIR
C-EDF
ESPRESSO
P-RES
P-FP
PSN-EDF
GSN-EDF
Linux
The plugin ESPRESSO is the reservation framework with support for semi-partitioned scheduling that will be used in the experiments. The plugins P-FP, PSN-EDF, and GSN-EDF are the partitioned fixed-priority, partitioned EDF, and global EDF plugins, respectively, which will be used as a baseline. However, these plugins will be automatically activated at the right times by the provided experiment scripts, as discussed below.
At this point, either the provided VM has been successfully launched (Alternative 1), or the manually installed LITMUSRT kernel has successfully booted (Alternative 2). In either case, it is now possible to run the provided experiments to collect overhead samples, as described in the following.
Running experiments requires superuser privileges. Thus, first open a root shell. For example, with sudo:
sudo -s
In the root shell, we need to set the PATH environmental variable to ensure that the experiment scripts can find all required tools. In particular, we need to add the liblitmus and the feather-trace-tools directories to the search path.
export PATH=/usr/local/litmus/sp-res/liblitmus:$PATH
export PATH=/usr/local/litmus/sp-res/feather-trace-tools:$PATH
Check that the path was set up correctly by locating the rtspin and ftcat utilities:
which rtspin
# expected output:
# /usr/local/litmus/sp-res/liblitmus/rtspin
which ftcat
# expected output:
# /usr/local/litmus/sp-res/feather-trace-tools/ftcat
Finally, we can launch an experiment. The archive comes both with all workloads used in the experiments reported in the paper, and with toy experiments that allow trying out the kernel if no 44-core machine is available.
There is a shell script for each experiment that takes care of everything: setting up the experiment, creating reservations, launching rtspin processes with appropriate parameters, starting overhead tracing, and tearing everything down again at the end of the experiments.
The experiment scripts are provided in the folder workloads/ of the provided archive. They are organized by core count and type of experiment:
workloads/full contains experiment scripts for measuring overheads on the 44-core platform;workloads/toy contains experiment scripts for measuring overheads on test platforms with (at least) four cores;workloads/mig-full contains experiment scripts for measuring migration rates on the 44-core platform; andworkloads/mig-toy contains experiment scripts for measuring migration rates test platforms with (at least) four cores.For now, consider only the scripts for overhead measurements (in the directories sp-res/workloads/full and sp-res/workloads/toy); migration-rate experiments will be discussed later in this guide.
The file names of the shell scripts reflect the parameters of the workload. For example, the file workloads/toy/litmus-workload_m=04_n=05_u=75_seq=08_sched=ESPRESSO.sh is for m=4 processor cores, launches a workload consisting of n=5 tasks, uses the ESPRESSO plugin (i.e., the semi-partitioned reservation framework), and has a total utilization of 75%. The seq tag is simply a sequence number; there are 10 scripts for each parameter combination.
To launch an experiment, simply run the corresponding script from the root shell.
Each experiment script produces raw overhead sample files in the directory in which it is launched. We therefore first move to the (still empty) data/ directory.
When using the example experiments for four cores:
cd /usr/local/litmus/sp-res/data
../workloads/toy/litmus-workload_m=04_n=05_u=75_seq=08_sched=ESPRESSO.sh
When using the full experiments for 44 cores:
cd /usr/local/litmus/sp-res/data
../workloads/full/litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh
Each experiment runs for 30 seconds (plus a few seconds for setup and teardown). When the experiment is done, the shell script will terminate.
For example, this is what it should look like after the experiment has completed (44-core example):
root@rts44:/usr/local/litmus# cd /usr/local/litmus/sp-res/data
root@rts44:/usr/local/litmus/sp-res/data# ../workloads/full/litmus-workload_m\=44_n\=88_u\=85_seq\=01_sched\=ESPRESSO.sh
litmus-workload_m=44_n=88_u=85_seq=01_sched=ESPRESSO.sh
Waiting for overhead tracer to finish launching...
Released 88 real-time tasks.
root@rts44:/usr/local/litmus/sp-res/data#
The experiment script generated a bunch of data files that contain overhead samples that were collected with Feather-Trace, the overhead tracing framework built into LITMUSRT. At this point, (at least) the following files should be visible in the data/ directory (44-core example).
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_cpu=0.bin
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_cpu=1.bin
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_cpu=2.bin
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_cpu=3.bin
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_cpu=4.bin
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_msg=0.bin
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_msg=1.bin
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_msg=2.bin
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_msg=3.bin
overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=88_u=85_seq=01_msg=4.bin
The script creates two files for each processor; the total number of files created hence depends on size of the experimental platform.
The above example ran a workload under the new ESPRESSO reservation framework. To get data for one of the baseline schedulers, run the same experiment again, but this time under the global EDF (GSN-EDF) scheduler.
When using the example experiments for four cores:
cd /usr/local/litmus/sp-res/data
../workloads/toy/litmus-workload_m=04_n=05_u=75_seq=08_sched=GSN-EDF.sh
When using the full experiments for 44 cores:
cd /usr/local/litmus/sp-res/data
../workloads/full/litmus-workload_m=44_n=45_u=75_seq=08_sched=GSN-EDF.sh
Again, the output should look something like this (44-core example):
root@rts44:/usr/local/litmus/sp-res/data# ../workloads/full/litmus-workload_m\=44_n\=88_u\=85_seq\=01_sched\=GSN-EDF.sh
litmus-workload_m=44_n=88_u=85_seq=01_sched=GSN-EDF.sh
Waiting for overhead tracer to finish launching...
Released 88 real-time tasks.
root@rts44:/usr/local/litmus/sp-res/data#
At this point, as many experiments as desired may be run. For example, to run all provided workloads, execute the following command.
for x in `ls ../workloads/XXX/*.sh`
do
echo ====
date
$x
done
(Replace XXX with full or toy, as appropriate.)
Obviously, running all workloads will take many hours and generate many gigabytes of data.
Attempting to run all experiments poses non-trivial data management challenges and requires substantial time. As a more manageable, limited scope, we suggest to run four experiments under each of the considered schedulers, including both configurations with few and many tasks, to generate some representative data for subsequent analysis.
When using the example experiments for four cores, this can be accomplished with the following command:
for x in `ls ../workloads/toy/litmus-workload_m\=04_n\={5,6,8,40}_*u=95_*seq=03*.sh`
do
echo ====
date
$x
done
When using the full experiments for 44 cores, this can be accomplished with the following command:
for x in `ls ../workloads/full/litmus-workload_m\=44_n\={45,66,88,440}_*u=95_*seq=03*.sh`
do
echo ====
date
$x
done
Once a satisfactory amount of data has been collected, the overhead statistics reported in the paper can be obtained with the tools provided in feather-trace-tools/.
The following steps are based on the LITMUSRT overhead tracing tutorial. The focus here is on documenting how to obtain the desired statistics, not on explaining why each step is necessary or what precisely it does. For a more in-depth explanation, please refer to the LITMUSRT tracing tutorial.
In the first processing step, the raw trace files are cleaned up and prepared for further processing.
ft-sort-traces overheads_*.bin 2>&1 | tee -a overhead-processing.log
In particular, as part of the tracing process, some samples may be reordered (although this almost never happens with recent version of LITMUSRT). Preprocessing the traces with ft-sort-traces ensures that any reordered samples are re-arranged, which simplifies the next steps.
The files ending with the extension .bin are raw trace files in a kernel-defined binary format. Before extracting meaningful statistics, we need to extract the actual data samples.
ft-extract-samples overheads_*.bin 2>&1 | tee -a overhead-processing.log
This step creates a bunch of .float32 files (one for each trace and overhead type), which contain raw overhead samples in a format that can be easily parsed and processed with NumPy (hence the name float32).
At this point, we have many per-processor, per-task-count, per-utilization, etc. files. We are interested in aggregate overhead values across all tested scenarios. Hence we need to combine the individual sample files.
ft-combine-samples --std overheads_*.float32 2>&1 | tee -a overhead-processing.log
This step creates a number of combined overhead files, one for each tested scheduler and each observed type of overhead.
ls combined-overheads_*.float32
The following files should be listed (44-core example):
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=CXS.float32
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=RELEASE.float32
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=RELEASE-LATENCY.float32
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=SCHED2.float32
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=SCHED.float32
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=SCHED-TIMER.float32
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=SEND-RESCHED.float32
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=SEND-XCALL.float32
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=TIMER-LATENCY.float32
combined-overheads_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_overhead=XCALL.float32
combined-overheads_host=rts44_scheduler=GSN-EDF_trace=litmus-workload_m=44_overhead=CXS.float32
combined-overheads_host=rts44_scheduler=GSN-EDF_trace=litmus-workload_m=44_overhead=RELEASE.float32
combined-overheads_host=rts44_scheduler=GSN-EDF_trace=litmus-workload_m=44_overhead=RELEASE-LATENCY.float32
combined-overheads_host=rts44_scheduler=GSN-EDF_trace=litmus-workload_m=44_overhead=SCHED2.float32
combined-overheads_host=rts44_scheduler=GSN-EDF_trace=litmus-workload_m=44_overhead=SCHED.float32
combined-overheads_host=rts44_scheduler=GSN-EDF_trace=litmus-workload_m=44_overhead=SEND-RESCHED.float32
combined-overheads_host=rts44_scheduler=P-FP_trace=litmus-workload_m=44_overhead=CXS.float32
combined-overheads_host=rts44_scheduler=P-FP_trace=litmus-workload_m=44_overhead=RELEASE.float32
combined-overheads_host=rts44_scheduler=P-FP_trace=litmus-workload_m=44_overhead=RELEASE-LATENCY.float32
combined-overheads_host=rts44_scheduler=P-FP_trace=litmus-workload_m=44_overhead=SCHED2.float32
combined-overheads_host=rts44_scheduler=P-FP_trace=litmus-workload_m=44_overhead=SCHED.float32
combined-overheads_host=rts44_scheduler=P-FP_trace=litmus-workload_m=44_overhead=SEND-RESCHED.float32
combined-overheads_host=rts44_scheduler=PSN-EDF_trace=litmus-workload_m=44_overhead=CXS.float32
combined-overheads_host=rts44_scheduler=PSN-EDF_trace=litmus-workload_m=44_overhead=RELEASE.float32
combined-overheads_host=rts44_scheduler=PSN-EDF_trace=litmus-workload_m=44_overhead=RELEASE-LATENCY.float32
combined-overheads_host=rts44_scheduler=PSN-EDF_trace=litmus-workload_m=44_overhead=SCHED2.float32
combined-overheads_host=rts44_scheduler=PSN-EDF_trace=litmus-workload_m=44_overhead=SCHED.float32
combined-overheads_host=rts44_scheduler=PSN-EDF_trace=litmus-workload_m=44_overhead=SEND-RESCHED.float32
When using the four-core example workloads, a similar set of files should be created, but the names will contain m=04 instead of m=44 for obvious reasons.
Dependencies: this step requires the tool ft-compute-stats to be run, which depends on Python 2.7 and NumPy. On Debian-based distributions, the required packages can be installed with the command sudo apt install python2.7 python-numpy.
Figure 7 shows scheduling overhead, context-switch overhead, and release overhead under each of the considered scheduling approaches as a CDF. A CSV file suitable for recreating these figures can be easily obtained with the following command:
ft-compute-stats --hist -b 25 -n --percent -c combined-overheads_*.float32 > stats-cdf.csv
The file stats-cdf.csv now contains the raw data needed to render Figure 7. A precise legend, which indicates for each column which overhead and scheduler it reflects, can be found at the bottom of the generated file.
Plots similar to those shown in Figure 7 and 8(a) can now be created using any spreadsheet applications such as OpenOffice Calc, Microsoft Excel, or Apple Numbers by importing stats-cdf.csv and by selecting and visualizing the the appropriate columns. Specifically, the figures show the following overhead types:
SCHED overhead type;CXS overhead type;RELEASE overhead type; andSCHED-TIMER, XCALL, and SCHED overhead types for the ESPRESSO scheduler.For ease of use, it’s convenient to generate CSV files containing only the relevant overhead types. This can be accomplished with the following commands:
ft-compute-stats --hist -b 25 -n --percent -c combined-overheads_*_overhead=SCHED.float32 > stats-cdf-7a.csv
ft-compute-stats --hist -b 25 -n --percent -c combined-overheads_*_overhead=CXS.float32 > stats-cdf-7b.csv
ft-compute-stats --hist -b 25 -n --percent -c combined-overheads_*_overhead=RELEASE.float32 > stats-cdf-7c.csv
ft-compute-stats --hist -b 25 -n --percent -c combined-overheads_*scheduler=ESPRESSO_*_overhead={SCHED-TIMER,XCALL,SCHED}.float32 > stats-cdf-8a.csv
The figures may now be replicated with any plotting tool from the files stats-cdf-7a.csv, stats-cdf-7b.csv, stats-cdf-7c.csv, and stats-cdf-8a.csv.
While the absolute data points will naturally differ from system to system, the general shape of the curves should resemble the trends shown and discussed in the paper.
Figure 8(b) in the paper reports the effective average migration rates for various levels of available slack (i.e., average WCET under-runs). In the following, we discuss how to obtain the required data.
To measure the migration rate of a task set, a different tracing setup is required: instead of tracing overheads (with LITMUSRT’s built-in Feather-Trace facility), the actual runtime schedule is traced (with sched_trace, another tracing facility built into LITMUSRT).
To automate the required setup, we provide appropriate scripts in the directories sp-res/workloads/mig-full and sp-res/workloads/mig-toy.
These scripts are named and work just as the corresponding overhead-measurement scripts.
For example, when using a 44-core platform, simply run the script litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh to obtain some schedule traces (44-core example).
# ../workloads/mig-full/litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh
litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh
Waiting for schedule tracer to finish launching...
Released 45 real-time tasks.
When using the four-core example workloads, simply run litmus-workload_m=04_n=05_u=75_seq=08_sched=ESPRESSO.sh instead.
This will generate a number of files named schedule_*.bin (44-core example).
schedule_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=45_u=75_seq=08_cpu=0.bin
schedule_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=45_u=75_seq=08_cpu=2.bin
schedule_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=45_u=75_seq=08_cpu=1.bin
schedule_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=45_u=75_seq=08_cpu=3.bin
...
These files contain the information that is required to reconstruct the timeline. Information for a particular trace can be extracted with the st-jobs-stats utility (44-core example).
st-job-stats -m -r schedule_host\=rts44_scheduler\=ESPRESSO_trace\=litmus-workload_m\=44_n\=45_u\=75_seq\=08_cpu\=*.bin > example-jobs-stats.csv
The file example-job-stats.csv then contains information such as the following:
# Task, Job, Period, Response, DL Miss?, Lateness, Tardiness, Forced?, ACET, Preemptions, Migrations
# task NAME=rtspin PID=31071 COST=77.29 PERIOD=125.00 CPU=185
31071, 3, 125.00, 69.40, 0, -55.60, 0.00, 0, 69.34, 0, 0
31071, 4, 125.00, 69.56, 0, -55.44, 0.00, 0, 69.49, 1, 0
31071, 5, 125.00, 69.60, 0, -55.40, 0.00, 0, 69.53, 1, 0
31071, 6, 125.00, 69.38, 0, -55.62, 0.00, 0, 69.32, 2, 0
31071, 7, 125.00, 69.54, 0, -55.46, 0.00, 0, 69.47, 1, 0
31071, 8, 125.00, 69.48, 0, -55.52, 0.00, 0, 69.41, 1, 0
31071, 9, 125.00, 69.59, 0, -55.41, 0.00, 0, 69.52, 1, 0
31071, 10, 125.00, 69.56, 0, -55.44, 0.00, 0, 69.50, 1, 0
[...]
The last two columns reflect the number of preemptions and migrations incurred by each job. Figure 8(b) depicts normalized summary statistics derived from the last columns of many such traces. We next discuss how to obtain all traces.
By default, the scripts in the directories sp-res/workloads/mig-full and sp-res/workloads/mig-toy launch rtspin processes that do not (intentionally) vary their execution time from job to job, and that consume almost their entire budget (i.e., each job exhibits a near-WCET execution time and leaves almost no slack).
To automatically vary the amount of slack generated by rtspin processes, we provide the script run-with-slack.sh. To run a particular script several times while varying the average amount of slack available, simply pass the name of the to-be-executed workload script to run-with-slack.sh.
For example, running the following command on a 44-core platform
run-with-slack.sh ../workloads/mig-full/litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh
produces the following output:
:::::: Baseline ::::::
litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh
Waiting for schedule tracer to finish launching...
Released 45 real-time tasks.
:::::: under-run target = 1.00 ::::::
litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh
Waiting for schedule tracer to finish launching...
Released 45 real-time tasks.
:::::: under-run target = 0.50 ::::::
litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh
Waiting for schedule tracer to finish launching...
Released 45 real-time tasks.
:::::: under-run target = 0.66 ::::::
litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh
Waiting for schedule tracer to finish launching...
Released 45 real-time tasks.
:::::: under-run target = 0.20 ::::::
litmus-workload_m=44_n=45_u=75_seq=08_sched=ESPRESSO.sh
Waiting for schedule tracer to finish launching...
Released 45 real-time tasks.
When using the four-core example workloads, simply run instead the following command:
run-with-slack.sh ../workloads/mig-toy/litmus-workload_m=04_n=05_u=75_seq=08_sched=ESPRESSO.sh
This produces trace-data files with different _underrun=XXX_ parameters (44-core example):
schedule_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=45_u=75_seq=08_underrun=000_cpu=1.bin
schedule_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=45_u=75_seq=08_underrun=020_cpu=1.bin
schedule_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=45_u=75_seq=08_underrun=050_cpu=1.bin
schedule_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=45_u=75_seq=08_underrun=066_cpu=1.bin
schedule_host=rts44_scheduler=ESPRESSO_trace=litmus-workload_m=44_n=45_u=75_seq=08_underrun=100_cpu=1.bin
There is one file for each workload, each processor, and each under-run target.
At this point, as many experiments as desired may be run. For example, to run all workloads that make use of semi-partitioned reservations under the proposed scheduler (the ESPRESSO plugin), simply execute the following command:
for x in `ls ../workloads/mig-XXX/with-semi-part/*_sched=ESPRESSO.sh`
do
echo ====
date
run-with-slack.sh $x
done
(Replace XXX with full or toy, as appropriate.)
Obviously, running all workloads will again take many hours and generate thousands of files and many gigabytes of data.
As before, in the interest of time, we suggest to run only a small selection of workloads to generate some example data suitable for further processing.
When using the example experiments for four cores, this can be accomplished with the following command:
for x in `ls ../workloads/mig-toy/litmus-workload_m\=04_n\=0{5,6,8}_*u=95_*seq=03*_sched=ESPRESSO.sh`
do
echo ====
date
run-with-slack.sh $x
done
When using the full experiments for 44 cores, instead use this command:
for x in `ls ../workloads/mig-full/litmus-workload_m\=44_n\={45,66,88}_*u=95_*seq=03*_sched=ESPRESSO.sh`
do
echo ====
date
run-with-slack.sh $x
done
Once a sufficient number of traces has been obtained, the final step is to extract the desired aggregate measure of migration rates. To this end, carry out the following three steps.
First, for each trace, run st-job-stats to extract the raw number of migrations for each job.
for trace in `ls schedule_*scheduler=ESPRESSO_*.bin | sed 's/_cpu=.*bin//g' | sort | uniq`
do
echo Processing ${trace}...
st-job-stats -m -r ${trace}_cpu=*.bin > job-stats-${trace}.csv
done
Second, compute the total number of observed migrations for each slack level.
for ulevel in `ls job-stats-*.csv | sed -e 's/.*_underrun=\([0-9]*\).*/\1/' | sort | uniq`
do
echo Processing job-stats-*_underrun=${ulevel}.csv...
grep -v '#' job-stats-*_underrun=${ulevel}.csv | \
awk 'BEGIN { total = 0} { total += $NF} END { print total}' \
> total-migrations_underrun=${ulevel}.txt
done
Third, normalize the total number of migrations with regard to the trace length (30 seconds per trace) and the number of cores (44 for the full experiments, 4 for the example experiments).
For the full experiments on the 44-core platform, run the following command:
(for ulevel in `ls total-migrations_*.txt | sed -e 's/.*_underrun=\([0-9]*\).*/\1/' | sort | uniq`
do
perl -e 'print $ARGV[0], ", ", $ARGV[1], ", ", $ARGV[1]/30.0/44, "\n"' $ulevel `cat total-migrations_underrun=${ulevel}.txt`
done) > migration-rates.csv
For the example experiments on a 4-core platform, run the following commands:
(for ulevel in `ls total-migrations_*.txt | sed -e 's/.*_underrun=\([0-9]*\).*/\1/' | sort | uniq`
do
perl -e 'print $ARGV[0], ", ", $ARGV[1], ", ", $ARGV[1]/30.0/4, "\n"' $ulevel `cat total-migrations_underrun=${ulevel}.txt`
done) > migration-rates.csv
The resulting file migration-rates.csv contains the average number of migrations per second per core in the last column.
To replicate Figure 8(b), simply visualize the data in the first and last columns of the file migration-rates.csv as a bar diagram, using a data visualization tool of your choice.
The different under-run levels correspond to the average amount of available slack as follows:
| under–run level | available slack on average |
|---|
0% | 0%
20% | 10%
50% | 25%
75% | 33%
100% | 50%
(To understand why, see the explanation of the -U option of rtspin by running rtspin -h.)
Note that, unless all workloads are run, the magnitude of the rates will not closely match the numbers given in the paper. However, when running the experiments on real hardware, the same trend should be apparent: a significant decrease in the number of migrations as the average amount of available slack increases.
When running the experiments in a virtual machine, counterintuitive trends may be observed due to virtualization overheads (which can interfere with the experimental setup and cause deadline misses and general unpredictability).