This tutorial explains how to reproduce the experiments discussed in the paper
A. Biondi and B. B. Brandenburg - “Lightweight Real-Time Synchronization under P-EDF on Symmetric and Asymmetric Multiprocessors”, Proceedings of the 28th Euromicro Conference on Real-Time Systems (ECRTS 2016), July 2016.
This document is organized as follows.
Please follow the instructions detailed in each section. In case of problems or further questions, feel free to contact us by email.
The schedulability analyses presented in the paper have been implemented as part of the SchedCAT library.
SchedCAT supports Linux and Mac OSX environments. Linux is recommended.
To run the experiments, the following packages are required:
Python 2.7
Python NumPy Library
Python SciPy LIbrary
SWIG 3.0
GNU C++ compiler (G++)
GNU Multiple Precision Arithmetic Library (libgmp)
On a debian-based Linux distribution, these packages can be easily installed via the following apt command:
# apt-get install python2.7 python-dev python-numpy python-scipy swig g++ libgmp3-dev
The above command has been tested on the latest release of Ubuntu Linux (16.04).
A linear program solver is also required. SchedCAT supports IBM CPLEX (recommended) and the GNU Linear Programming Kit (GLPK).
IBM CPLEX is a commercial software. A 90-days trial version can be freely downloaded from here. Free academic licenses are also available.
GLPK is typically available as a package for most Linux distributions. On a debian-based distirbution, GLPK can be installed wih the following apt command:
# apt-get install libglpk-dev
Warning: Despite being free, open-source and easily installable, GLPK has various bugs that (in most of the cases) prevent to run the epxeriments. The demo experiment described in the following section has been teted to (likely) work with GLPK, while we recommend the use of IBM CPLEX to run all the other experiments.
The following steps explain how to run a (small) demo experiment to test the setup described in the previous section.
First, download the following zip file including SchedCAT and a set of Python scripts to run the experiments:
mkdir ~/pedf-synch; cd ~/pedf-synch
wget http://www.mpi-sws.org/~bbb/papers/ae/ecrts16/pedf-synch.zip
unzip pedf-synch.zip
Move into the SchedCAT folder, compile the source code, and move back to the root folder:
cd lib/schedcat
make
cd ../../
If IBM CPLEX is used, then a special configuration file for the Makefile must be provided. Therefore, first copy the provided file usecplex to the native/ directory before compiling, as follows:
cp usecplex ./native/.config; make
Note: If you switch solvers after having already compiled the software once, you must run make clean
before rebuilding the project.
Before launching the experiment, it is necessary to setup an environmental variable for SchedCAT:
export PYTHONPATH=$PYTHONPATH:./lib/schedcat
We are now ready to launch the demo experiment.
python -m exp -f ./confs/demo/demo.conf
This command will produce a CSV output file ./output/demo/demo.csv that contains the measured schedulability ratios for each tested analysis.
The output file should look structurally as follows, although the exact numbers will vary due to sampling noise.
#################################### DATA #######################################
TASKS no blocking MSRP-LP FIFO-PREEMPT-LP MSRP-classic
10, 1.00, 1.00, 1.00, 1.00
12, 1.00, 1.00, 1.00, 1.00
14, 0.99, 0.99, 0.98, 0.98
16, 0.97, 0.96, 0.94, 0.93
18, 0.94, 0.90, 0.90, 0.85
The first column represents the parameter varied in the experiment (number of tasks in this example) while the other columns report the schedulability ratio for each analysis. Specifically, the label no blocking refers to the P-EDF analysis where blocking is ignored, MSRP-LP considers the analysis for FIFO non-preemptive spin locks presented in Section V, FIFO-PREEMPT-LP considers the analysis for FIFO preemptive spin locks presented in Appendix B and MSRP-classic refers to the analysis for FIFO non-preemptive spin locks proposed by Gai et. al in 2001.
Warning: If using GLPK, it can happen that the experiment will hang due to the bugs discussed in the previous section.
Note that this a limitation of GLPK and not of our implementation. If this happens, please kill the python process and re-execute the command above.
Before proceeding with the next steps, it necessary to introduce the notion of configuration.
A configuration represents all the settings for the task set generators (e.g., how many processors, how many resources, etc.) and defines the experiment to be performed (e.g., varying the number of tasks from 10 to 80).
The directory ~/pedf-synch/confs/pedf-lp contains a .conf file for each configuration tested in the experimental study discussed in the paper.
The name of each .conf file contains key-value pairs with the values for (most of) the parameters.
As example, a configuration file named
sd_exp=pedf-lp-tcount__m=04__per=log-uni-10-100__nr=8__cs=short__nreq=1.conf
corresponds to a configuration for an experiment named pedf-lp-tcount that considers 4 processors (m=4), random task periods between 10 and 100 milliseconds with log-uniform distribution (per=log-uni-10-100), 8 shared resources (nr=8), short critical sections (cs=short) and at most one critical section for each task (nreq=1).
The directory ~/pedf-synch/confs/pedf-lp includes three sub-directories, each containing the configuration files for the three classes of experiments reported in the paper:
| Directory | Description |
|---|---|
| /confs/pedf-lp/tcount | Experiments on symmetric platforms (Section VI.A of the paper) |
| /confs/pedf-lp/asym | Experiments on asymmetric platform (Section VI.B of the paper) |
| /confs/pedf-lp/latsens | Experiments on latency-sensitive tasks (Section VI.C of the paper) |
The experiments for all the configurations inside a directory can be run with the following command, after performing all the steps reported in previous section:
python -m exp -p -d ./confs/pedf-lp/<directory>
Note: The configurations have been generated for the large-scale experimental study we conducted for the paper. We executed all the epxeriments on 8 machines, each one equipped with 48 cores, and it took 2 days to get the results.
Warning: If using GLPK, most likely these experiments will not terminate because of the bugs of GLPK discussed in Section 1. We recommend the use of IBM CPLEX to run the experiments in large-scale.
The following files can be found at the relative path lib/schedcat/native/src/blocking/linprog/ and contain the implementations of the analyses proposed in the paper.
| File | Description |
|---|---|
| lp_pedf_analysis.cpp | Implementation of the analyis framework for P-EDF with blocking presented in Section III |
| lp_pedf_lockfree_common.cpp | Common infrastructure for the analysis of lock-free synchronization and generic ILP constraints (Section IV.D) |
| lp_pedf_lockfree_preempt.cpp | ILP formulation for lock-free synchronization with preemptive commit loops (Section IV.E) |
| lp_pedf_lockfree_NP.cpp | ILP formulation for lock-free synchronization with non-preemptive commit loops (Appendix A) |
| lp_pedf_spinlocks_common.cpp | Common infrastructure for the analysis of spin locks and generic ILP constraints (Section V.C) |
| lp_pedf_msrp.cpp | MILP formulation for non-preemptive FIFO spin locks (Section V.D) |
| lp_pedf_spinlocks_preempt.cpp | MILP formulation for preemptive FIFO spin locks (Appendix B) |