Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling using Schedule Abstraction Graph (SAG)
This repository contains the implementations of response-time analysis for sets of preemptive jobs scheduled globally on a system with identical cores. The analysis is described in the following paper:
- P. Gohari, J. Voeten, and M. Nasri “Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling”, Euromicro Conference on Real-Time Systems (ECRTS), 2024.
- A modern C++ compiler supporting the C++14 standard. Recent versions of
clang
andg++
on Linux is known to work. - The CMake build system. For installation using
apt
(Ubuntu, Debian...):
sudo apt-get -y install cmake
-
A POSIX OS. Linux and macOS are both known to work.
-
The Intel Thread Building Blocks (TBB) library and parallel runtime.
-
The jemalloc scalable memory allocator. Alternatively, the TBB allocator can be used instead; see build options below.
These instructions assume a Linux host.
To compile the tool, first generate an appropriate Makefile
with cmake
and then use it to actually build the source
tree.
# (1) enter the build directory
cd build
# (2) generate the Makefile
cmake ..
# (3) build everything
make -j
The last step yields the main binary rt_analysis
in the build/
directory.
The build can be configured in a number of ways by passing options via the -D
flag to cmake
in step (2).
To enable debug builds, pass the DEBUG
option to cmake
.
cmake -DDEBUG=yes ..
To enable the collection of schedule graphs (the -g
option in rt_analysis
), set the option COLLECT_SCHEDULE_GRAPHS
to yes
.
cmake -DCOLLECT_SCHEDULE_GRAPHS=yes ..
Note that enabling COLLECT_SCHEDULE_GRAPHS
turns off parallel analysis, i.e., the analysis becomes single-threaded, so
don't turn it on by default. It is primarily a debugging aid.
By default, rt_analysis
uses the default libc
allocator (which is a tremendous scalability bottleneck).
To use the jemalloc
or Intel TBB
allocator instead, pass the USE_JE_MALLOC
or USE_TBB_MALLOC
option to cmake
.
The tool operates on classical SAG CSV files with a fixed column order. For more details, see the examples in
the examples/
folder.
Job set input CSV files describe a set of jobs, where each row specifies one job. The following columns are required.
- Task ID — an arbitrary numeric ID to identify the task to which a job belongs
- Job ID — a unique numeric ID that identifies the job
- Release min — the earliest-possible release time of the job (equivalently, this is the arrival time of the job)
- Release max — the latest-possible release time of the job (equivalently, this is the arrival time plus maximum jitter of the job)
- Cost min — the best-case execution time of the job (can be zero)
- Cost max — the worst-case execution time of the job
- Deadline — the absolute deadline of the job
- Priority — the priority of the job (EDF: set it equal to the deadline)
All numeric parameters can be 64-bit integers (preferred) or floating point values (slower, not recommended).
To run the tool on a given set, pass the filename as an argument and provide the number of (identical) processors (cores) via the -m
option.
For example, to analyze the job set in examples/fig1-pr.csv for a system with two cores, run the
following command:
./build/rt_analysis examples/fig1-pr.csv -m 2
examples/fig1-pr.csv, 1, 5, 24, 30, 7, 0.000044, 6.023438, 0, 2
See the builtin help (rt_analysis -h
) for further options.
The output is provided in CSV format and consists of the following columns:
- The input file name.
- The schedulability result:
- 1 if the job is is schedulable (i.e., the tool could prove the absence of deadline misses),
- 0 if it is not, or if the analysis timed out, if it reached the depth limit, or if the analysis cannot prove the absence of deadline misses (while the RTSS'17 analysis is exact, the ECRTS'19 analysis is only sufficient, but not exact).
- The number of jobs in the job set.
- The number of states that were explored.
- The number of edges that were discovered.
- The maximum “exploration front width” of the schedule graph, which is the maximum number of unprocessed states that are queued for exploration (at any point in time).
- The CPU time used in the analysis (in seconds).
- The peak amount of memory used (as reported by
getrusage()
), divided by 1024. Due to non-portable differences ingetrusage()
, on Linux this reports the memory usage in megabytes, whereas on macOS it reports the memory usage in kilobytes. - A timeout indicator: 1 if the state-space exploration was aborted due to reaching the time limit (as set with
the
-l
option); 0 otherwise. - The number of processors assumed during the analysis.
Pass the --header
flag to rt_analysis
to print out column headers.
The analysis computes for each job the earliest and latest possible completion times, from which it is trivial to infer
minimum and maximum response times. To obtain this information, pass the -r
option to rt_analysis
.
If invoked on an input file named foo.csv
, the completion times will be stored in a file foo.rta.csv
and follow the
following format, where each row corresponds to one job in the input job set.
- Task ID
- Job ID
- BCCT, the best-case completion time
- WCCT, the worst-case completion time
- BCRT, the best-case response time (relative to the minimum release time)
- WCRT, the worst-case response time (relative to the minimum release time)
Note that the analysis by default aborts after finding the first deadline miss, in which case some of the rows may report nonsensical default values.
- The parallel version of the analysis is implemented using Intel's Thread Building Blocks (TBB) library. The analysis is parallelized at the level of the state-space exploration, where each thread processes a different state. However, the analysis is not tested with parallel option enabled. Use it at your own risk.
With your feedback and conversation, you can assist me in developing this framework.
- Open pull request with improvements
- Discuss feedback and bugs in issues
The code is released under a 3-clause BSD license.
Schedule Abstraction Graph (SAG) was originally introduced by Nasri et al. [1][2][3]. This implementation made use of the original tool which was developed by Björn Brandenburg. It is now being maintained by Geoffrey Nelissen. For more information, please visit Schedule Abstraction Framework page.
-
[1] M. Nasri and B. Brandenburg, “An Exact and Sustainable Analysis of Non-Preemptive Scheduling”, Proceedings of the 38th IEEE Real-Time Systems Symposium (RTSS 2017), pp. 12–23, December 2017.
-
[2] M. Nasri, G. Nelissen, and B. Brandenburg, “A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling”, Proceedings of the 30th Euromicro Conference on Real-Time Systems (ECRTS 2018), pp. 9:1–9:23, July 2018.
-
[3] M. Nasri, G. Nelissen, and B. Brandenburg, “Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks under Global Scheduling”, Proceedings of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019), pp. 21:1–21:23, July 2019.