Minimal EDF deadlines by convex hull

This repository contains the C code to prune the unnecessary deadlines of an EDF scheduled real-time task. The theory supporting the implemented method is published in the following paper

• Bini, Enrico. "Cutting the Unnecessary Deadlines in EDF." Proceedings of the 25th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). 2019. DOI: 10.1109/RTCSA.2019.8864569. Outstanding paper award

This work is dedicated to the memory of Laurent George, who prematurely passed away. Laurent, together with Jean-François Hermant, proposed a Linear Programming (LP) based method to reduce the number of points in the following paper

• George, Laurent, and Hermant, Jean-François. "Characterization of the space of feasible worst-case execution times for earliest-deadline-first scheduling." Journal of Aerospace Computing, Information, and Communication 6.11 (2009): 604-623.

How to use it

If you are lucky and want to run it first then understand it later, compile the code with the following commands:

• git clone --recurse-submodules git@github.com:ebni/edf_hull.git
• cd edf_hull
• make all

Then run the executable as follows:

• ./edf_hull

The above command will read the task set from the file input_task_set.txt and identify the minimal set of constraints needed to guarantee EDF schedulability.

Want to understand more? Just open the Makefile and go top-down. Or read next.

For more information on the inner workings of the code, go to the How does it work section.

Input

In the code stand out two different modes of use, FILE_MODE (option -i) and RANDOM_MODE (option -s) referring to the way a task set's parameters (period, deadline ,offset) are choosen.

File mode

The user specifies directly all the variables that come to define a particular task set by writing them on the ./input_task_set.txt file, in the following format, one point per line:

• the number of tasks (integer)
• sensitivity of the hyperperiod
• a line for each task with period, deadline, and offset separated by spaces.

Notice that the parameters are read as floating point numbers. Hence, the least common multiple among periods (often called hyperperiod in the literature) is computed with a tolerance specified as second parameter (second line).

Random mode

Additionally a task set can be internally generated by calling the program with the -s flag and specifying the arguments to the mandatory options (see --help for more information).

Mandatory options for the random mode are:

• the random mode flag -s
• one of the two options:
  • --rand-seed to specify the seed of the random task set generator or,
  • --num-repeat to specify the number of times the procedure is executed on a different task set (with these same user settings for randomization)
• --num to specify the number of tasks composing the task set,
• --eps to specify the sensitivity of the hyperperiod
• --period-max and --period-min to specify the range of allowed periods
• --relative-dl-avg and --relative-dl-var to specify the range of allowed relative deadlines
• --phasing provides each task with an offset (absent by default)

The complete list of mandatory options is always available in the help option, together with more usage information.

Example

Running the programm with following command

    ./edf_hull

reads the task set from the file input_task_set.txt that as a default contains the following 2-task system:

$T_i$	$D_i$	$O_i$
3	4	0
4	2	0

with $T_i$ the period, $D_i$ the deadline, and $O_i$ the offset of the $i$-th task.

The program then computes the minimal set of constraints to guarantee EDF schedulability. The result are the two following tables:

Minimal constraints (first format)	Minimal constraints (second format)
eta_1 eta_2 t_1 t_0 -1 0 0 0 0 -1 0 0 0.3333 0.2500 1 0 3.0000 3.0000 10 0 0.0 1.0000 2 0	a_1 a_2 t_1 t_0 -0.3333 0.0000 0 0 0.0000 -0.2500 0 0 1.0000 1.0000 1 0 0.9000 1.2000 10 0 0.0000 2.0000 2 0

How to read the output

The two tables above represent the same set of constraints. They are to be read as follows:

• The table on the left represents each constraint in the following form:

  $\eta_1 * C_1 + \eta_2 * C_2 ... + \eta_n * C_n <= t_1 - t_0$

  where

  • $C_i$ is the execution time of the $i$-th task
  • $[t_0,t_1]$ is the interval where EDF schedulability is checked, and
  • $\eta_i$ is the number of jobs of the $i$-th task with both activation and deadline in the interval $[t_0,t_1]$

  For example, the fourth row represents the constraint $$3C_1 + 3C_2 <= 10$$ because the interval $[0,10]$ contains 3 jobs of both tasks.

  The first row, instead, represents the constraint $$-C_1 &lt;= 0$$ which is equivalent to $C_1 &gt;= 0$.

• The table on the right represents the same information in a normalized format:

  $a_1 * U_1 + a_2 * U_2 + ... + a_n * U_n &lt;= 1$

  where $U_i$ is the utilization of the $i$-th task and $a_i$ is computed to have 1 at the RHS (please refer to the above mentioned paper for details).

The first n rows will always represent the positivity constraints, which guarantee a non-negative execution time for each task i$$ - C_i <= 0$$ while the n+1-th might be the total utilization constraint (unless it's not included among the minimal set of constraint by the procedure).

The last column is zero because there is no offset in this example.

How does it work

This code detects the minimal set of constraints which are needed to guarantee EDF schedulability. This action is made by the following steps:

1. the task set parameters are read (either from a file or internally generated)
2. for each constraint , a vector is created
3. the set of constraints is transformed
4. the convex hull of the constraints is computed
5. the vertices of the convex hull are selected

Useful options

The user can specify the level of verbosity and the destination of the output:

• with the verbose flag that can be set with the ---verbose option and provides a more detailed output on terminal or,
• with the add_constraints_info that can be set with -e flag and provides additional information over the minimal constraints found in a particular configuration. These data is printed on a csv file positioned in the ../datasets/additional_info/ folder.

Additional information on the constraints

This option needs to be used in combination with option --rand-seed and all the other mandatory options The csv file resulting from the -e option referes to a single task set, possibly found while executing the program in random mode with the --num-repeat option.

The output file contains the following information for each constraint:

• the seed Seed used to generate this specific task set, if the task set was generated randomly, otherwise the seed is set to -1
• all the parameters defining each task $i$ (period T_i, deadline D_i, hyperperiod H)
• for each task the ratio Ratio_i = $\frac{D_i}{T_i}$
• the differences diff1, diff2, etc, between the instant t and the last absolute deadline related to the task i
• the absolute deadlinet that will be at the right side of the inequality defining the constraint
• boolean variables task1_gen_t, task2_gen_t, etc. , that signal if the absolute deadline t is a deadline for the task i (1) or not (0)
• the number of constraints m selected by the convex hull procedure
• the command line arguments used to generate this task set Command

The number of minimal constraints m includes the total utilization constraint but excludes positivity constraints.

Creating the constraints

For each absolute deadline, the number of jobs per task within such a deadline are computed, as requested by EDF exact schedulability condition [Baruah et al. 1990]. These numbers of jobs are treated as vectors to be processed.

We identify different types of constraints, depending on the property they are meant to guarantee:

• Positivity constraints for each task i: $$ - C_i <= 0$$
• Total utilization constraint : the sum of the utilization of all the tasks is less than 1 $$\sum_{i=1}^{n} U_i &lt;= 1$$
• Schedulability constraints for each absolute deadline $t \in DlSet$ (see paper for more info): $$\sum_{i =1}^{n} \max {0, \lfloor\frac{t-D_i}{T_i}\rfloor +1} * C_i \leq t$$

Translating the constraints

To achieve the minimal number of constraints, the constraints are translated. A detailed explanation of this phase is given in the paper.

Computing the convex hull

The convex hull of the vectors representing the constraints is computed by the Qhull library, available on github. The constraints are copied into a global data structure used by Qhull to store configuration flags, constants and among other information, arrays of vertexes. The executable qhull will use the input present in the struct qhT for the computation.

The data copied into the structure qhT involves:

1. the size n of the vectors (number of tasks in our case)
2. the number m of vectors
3. m rows of space-separated vectors of size n

Result of the procedure

qhull then writes the set of the vertices of the convex hull in the data structure qhT saving:

1. the number v of vertices of the convex hull
2. the sequence of v indices (one per row) of the vectors which are vertices

Finally, the program displays what is the tightest set of constraints that needs to be checked, by reading the indices stored in the struct qhT, together with the original total number of constraints and the resulting minimal number.