Artifact Abstract

Abstract: In an overhead-aware schedulability study, we show how schedulability improves when using the NJLP (this work) compared to using the FMLP in non-job-level fixed-priority (non-JLFP) systems. The NJLP is the first non-JLFP-compatible locking protocol that obtains an asymptotically optimal \(O(m)\) pi-blocking (priority-inversion blocking) bound compared to the \(O(n)\) from the FMLP, where \(m\) is the number of processors and \(n\) is the number of tasks in the system. First, we graphically visualize the improved theoretical blocking time bounds. Second, overhead data is collected on real hardware where generated graphs help visualize the overhead cost of the NJLP. Lastly, the third experiment conducts the overhead-aware schedulability study using the EDZL scheduler and the overhead data collected in the second experiment.

This artifact evaluates the tradeoff between the NJLP's increased overhead costs and lower pi-blocking bound compared to the FMLP's lower overhead cost but higher pi-blocking bound.

Experiment 1 - Analytical graphs

The purpose of this experiment is to visualize the pi-blocking difference obtained from subtracting the maximum pi-blocking due to the NJLP from the maximum pi-blocking due to the FMLP. As such, positive values show where the NJLP does better than the FMLP.

Requirements: python3, matplotlib, numpy, and any window manager that can render matplotlib.

First, download plot_blocking.py.
Usage: python plot_blocking.py lg2mmax nmax lmax

lg2mmax: plots are made for the last four \(m\in\{1,2,4,8,...,2^k\}\) where \(k=lg2mmax-1\).
nmax: the maximum number of tasks where a data point exists for every \(n\in[1,nmax]\).
lmax: the maximum length of a critical section.

To generate the exact same graph as the paper, use: python plot_blocking.py 4 60 1

Figure 8, generated using lg2mmax, nmax, lmax as \(4, 60, 1\), respectively.

The pi-blocking upper bound for the NJLP is: \((3m-1+m(H_n-H_m))L_{\max}\)
The pi-blocking upper bound for the FMLP is: \((n-1)L_{\max}\)

The visualizer plots each \(n\in[1,nmax], n\in\mathbb{N}\) on the x-axis, the chosen four values for \(m\) on the y-axis, and plots the difference between the blocking bounds on the z-axis.

The key trends to notice is that the blocking bound for the FMLP, \((n-1)L_{\max}\), does not depend on \(m\), but the NJLP has a \(3m\) factor and \(m(H_n-H_m)\). However, as \(n\) increases, the FMLP bound increases linearly while the NJLP bound increases slower according to the Harmonic number, \(H_n=\sum_{k=1}^n \frac{1}{k}\).

Experiment 2 - Overhead evaluation

Requirements: qemu, virtualbox, or bare metal hardware (detailed below). You will also need a separate machine with python3, matplotlib, and numpy.

A note on documentation. While the python scripts in this and other experiments are self-explanatory, an entire custom kernel image is not. To assist in understanding the code for this experiment, we have provided thorough comments in the litmus/sched_gsn_edf2.c file.

The process for evaluating overheads is discussed in the paper. To provide a brief overview, we first launch \(m\) background tasks that thrash the cache. Then \(n\) tasks are simultaenously released (that also thrash the cache), and tasks utilize a locking protocol (NJLP or FMLP) and the EDZL scheduler. Feather trace tools are utilized to obtain how long lock, unlock, job release, and schedule operations take. Because the NJLP requires tracking pi-blocking and the top \(m\) incomplete tasks, we observe higher overheads as there are more data structures in the kernel. As such, obtaining the NJLP's asymptotically optimal bounds comes at the cost of increased overheads.

The first step is to have a machine to run the overhead evaluation on. We recommend bare-metal hardware to minimize unrelated interference. For only graph generation and validating results, you will need python3, matplotlib, and numpy, and can skip ahead to the graph generation subsection.

Task set creation is done using Randfixedsum from Emberson et. al. in WATERS 2010.



Open your experiments folder, then edit test_overhead.py.
Make sure LIBLITMUS and FEATHER_TRACE is pointing to the correct folder.

We begin the overhead data collection with the initial parameters:
Set m=6 to the number of cores on your processor.
Set n_array = [10] (the number of real-time tasks in the system)
Set schedname = 'EDZL-NJLP' (which scheduler to use)
Set locking_protocol = 'NJLP' (which locking protocol to use)
Set numpages to the number of pages in your L3 cache.
Set Duration = 300 (in seconds)
Note, Duration can be lowered to 30 if short on time, otherwise each data set takes approximately 5 minutes (note we will be generating 20 data sets).

To obtain overhead data run: sudo python test_overhead.py
You will see a lot of output (including something that says press Enter) and you can safely ignore it.

Once the overhead data is generated, a CSV file named "n_SCHD_stats.csv" (e.g. 10_EDZL-NJLP_stats.csv) will be generated. Repeat the experiment by changing n_array for each \(n\in\{10,20,30,...,100\}\). Note, it is imperative to test only one value of \(n\) at a time because of a rare crash that we believe is related to how liblitmus manages task memory after the tasks all complete.

Once you have obtained overhead measurements for each \(n\in\{10,20,30,...,100\}\), repeat the experiment but for the next set of results, set both schedname = 'EDZL' and locking_protocol = 'FMLP'.

The generated files can then be used to create graphs. The CSV files that are generated contain data on how long a context switch, lock, unlock, schedule, and release operation takes. Feather-trace-tools and our provided python scripts parse through the data and store the max and various percentile measurements observed.

Experiment 2 - Graph generation

Requirements: python3, matplotlib, numpy. Note: the machine uses python2, so we recommend generating graphs on a different machine. You can install openssh-server and use sftp or any other means to retrieve the csv files generated above.
We provide previously generated overhead data here: exp2-results.zip. This data can be used to generate the graphs in the paper.

To generate the graphs, download parse_overheads.py and place it in the same folder as all of the csv files. Then run the python script and it should output something similar to Figure 9 in the paper (as two files: lock_overhead_plot.pdf and sched_overhead_plot.pdf).

What needs to be verified here is that the overheads of tracking pi-blocking for the NJLP (Track) is often higher than the overheads when not tracking pi-blocking (Untrack). Specifically, we look at release and scheduling overheads.

Experiment 3 - Schedulability study overview

Requirements: python3, matplotlib, numpy, g++ (c++14 support), make, and overhead data from experiment 2.
You may also download prerecorded overhead data from exp2-results.zip. Note, overhead generation was done with python2, and as such, the results from experiment 2 need to be moved to a system with python3.

This schedulability study determines how frequently schedulable the same task set is when utilizing the NJLP versus the FMLP. Because the NJLP is intended for non-job-level-fixed-priority schedulers, we use the EDZL schedulability test by Lee and Shin (2012). We use the same task generation as experiment 2 (Emberson et. al.).

Task set generation information: Task sets were randomly generated with the number of tasks \(n\) randomly selected from \([2m, 25]\) (small), \([4m, 50]\) (medium), or \([8m, 100]\) (large), and \emph{normalized utilization}, \(\sum_{i = 1}^{n}\frac{C_i}{T_i \cdot m}\), in \(\{0.2, 0.3, ..., 0.9\}\). Each task's utilization was generated using the method from Emberson et. al., and its period is selected randomly from \([3, 33]ms\) (short), \([10, 100]ms\) (moderate), or \([50, 500]ms\) (long). Each task was defined to have an implicit deadline, \(D_i = T_i\), and its execution cost was obtained by multiplying its utilization and period.

As described in the paper, overheads are added to the task set. Then, schedulability is determined for each of the tasks described above for both the NJLP and FMLP.

Experiment 3 - Graph generation

(1) Download exp3.zip, extract, and compile.
mkdir ~/experiments/exp3
cd ~/experiments/exp3
wget https://www.cs.unc.edu/~swali/rtas25/exp3.zip
unzip exp3.zip
make

(2) Usage: ./edzl_test folder csvname blocking
folder: the folder that contains experiment 2's results.
csvname: for NJLP, the csvname will be EDZL-NJLP_stats.csv, FMLP will be EDZL_stats.csv.
blocking: for NJLP, 1, for FMLP, 0.

Generate schedulability tests for both the FMLP and NJLP.
sudo ./edzl_test ../ EDZL_stats.csv 0
sudo ./edzl_test ../ EDZL-NJLP_stats.csv 1
* We use sudo here because the overhead files are likely still owned by root, but if you change permissions, you do not need to sudo.

This will generate files in the following format: tsksetsize_periodtype_reqlen_p_q_lock.csv.
tsksetsize: The task set size where small, medium, and large is denoted by 12, 24, and 48, respectively.
periodtype: The period length where short, moderate, and long periods are denoted by 3.0, 10.0, and 50.0, respectively.
reqlen: The request length where short and long is denoted by 1.0 and 5.0, respectively.
p: The probability of selecting a task for locking, set to 0.5.
q: The number of resources in the system (1, 2, or 3).
lock: Will be either NJLP or FMLP.


Thus, the CSV's filename shows which parameters were used to generate the data. In the CSV, the percentage of task sets that were schedulable for each normalized utilization level from 0.2 to 0.9 are listed. A task set is schedulable based upon the schedulability tests for EDZL. Each task in the task set is inflated by its pi-blocking time for the locking protocol used.

Once all files are generated, run plot_schedulability.py.
python plot_schedulability.py
This will generate the schedulability graphs for all of the task generation combinations as described in the paper. To compare against Figure 10, use the specified PDF:
Inset a: 48_50.0_5.0_0.50_1_plot.pdf
Inset b: 12_50.0_5.0_0.50_1_plot.pdf
Inset c: 24_3.0_1.0_0.50_1_plot.pdf
Inset d: 24_10.0_1.0_0.50_1_plot.pdf

Figure 10:


What needs to be verified here is that under small task sets, the FMLP performs well, but under larger task sets, the NJLP performs better.

Instructions on moving files between machines.

When using either a virtual machine image or bare metal hardware, you will need to move files back and forth between that machine and a machine that has python3. This is because overhead data is gathered using a machine that uses python2 because feather-trace-tools also requires python2 while the graph generation uses python3. To make sure there are no issues with this, we suggest the following ways to move files out of the vm/ssh machine.