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.
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.
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.
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).
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.
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:
3 | 4 | 0 |
4 | 2 | 0 |
with
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) | ||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
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 <= 0$$ which is equivalent to$C_1 >= 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 <= 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.
This code detects the minimal set of constraints which are needed to guarantee EDF schedulability. This action is made by the following steps:
- the task set parameters are read (either from a file or internally generated)
- for each constraint , a vector is created
- the set of constraints is transformed
- the convex hull of the constraints is computed
- the vertices of the convex hull are selected
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.
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$ (periodT_i
, deadlineD_i
, hyperperiodH
) - for each task the ratio
Ratio_i
=$\frac{D_i}{T_i}$ - the differences
diff1
,diff2
, etc, between the instantt
and the last absolute deadline related to the taski
- the absolute deadline
t
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 deadlinet
is a deadline for the taski
(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.
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 <= 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$$
To achieve the minimal number of constraints, the constraints are translated. A detailed explanation of this phase is given in the paper.
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:
- the size n of the vectors (number of tasks in our case)
- the number m of vectors
- m rows of space-separated vectors of size n
qhull
then writes the set of the vertices of the convex hull in the data structure qhT
saving:
- the number v of vertices of the convex hull
- 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.