Current real-time embedded systems evolve towards complex systems using new state of the art technologies such as multi-core processors and virtualization techniques. Both technologies requires new real-time scheduling algorithms. For uniprocessor scheduling, utilization-based evaluation methodologies are common and well-established. For multicore systems and virtualization, evaluating and comparing scheduling techniques using the tasks' parameters is more realistic. Evaluating these di erent scheduling techniques requires relevant and standardised task sets. Scheduling algorithms can be evaluated on three evaluation levels: 1) by using the mathematical model of the scheduling algorithm, 2) by simulating the scheduling algorithm and 3) by implementing the algorithm on the target platform. Generating task sets is straightforward in case of the rst two levels; only the parameters of the tasks are required. Evaluating and comparing scheduling algorithms on the target platform itself, however, requires real executable tasks matching the prede ned standardised task sets. Generating those executable tasks is not standardized yet.
Therefore, we developed a task-set generator that generates reproducible, standardised task sets that are suitable at all levels. Beside generating the tasks' parameters, it includes an executable generator methodology that generates executables by combining publicly available benchmarks with know execution times. This paper presents and evaluates this task-set generator. The executables approximate the wanted execution time on the hardware platform.
Current evolutions of mechatronics show an exponential growth in the number of embedded systems used for control due to the shift from mechanical control towards electronic control. This evolution creates new opportunities for even more advanced software based control. On the downside, it introduces new challenges regarding safety and reliability. Both opportunities and challenges will result in more complex software and hence higher computational requirements. These requirements can be tackled by using state of the art technologies on embedded system. Multi-core processors is a common solution to increase the computational power in a single chip. Virtualization techniques is applied to handle the complexity of the software by decomposing the software in to components which can be analysis independent from each other. For real-time systems, most applications are composed of recurring tasks with periods, deadlines and execution times. This collection of tasks is called a task set. The schedulability of task sets is very important. Uniprocessor scheduling algorithms are evaluated and compared using the maximum task set utilization which can be scheduled by the algorithm. For multiprocessor scheduling algorithms, however, the complexity of the analysis methodologies increases dramatically. This is due to the concurrent execution of tasks and the indeterminism of most multi-core architectures. Virtualization introduces a two-level hierarchical scheduling structure where the traditional analysis techniques can not be applied to. The many open issues and the practical importance of these technologies make it a topic of active research.
Parameter-based analysis uses the tasks' parameters during analysis. This results in an one-to-one mapping of taskset and scheduling algorithm; the schedulability can be analysed for a speci c task set using a certain scheduling algorithm. The parameter-based analysis is more realistic for multiprocessor scheduling algorithms, and at this moment the only analysis methodology for the hierarchical scheduling structure in the virtualization technology. The schedulability of a task set is the key criteria for the evaluation and comparison of scheduling algorithms. Other criteria such as the number of pre-emptions, energy consumption, scheduler overhead, cache performance etc. can also be used the evaluate and compare scheduling algorithm. The schedulability and other criteria can be evaluated at an early stage of the design process of the mechatronic system. At this stage the complexity and cost are relatively low compared to later stages of the process. However, at the later stages more evaluation criteria can be evaluated and compared with other scheduling algorithms. The performance of scheduling algorithms can be evaluated on three levels:
Formal proof: at the highest evaluation level, schedulability can be formaly proven by the mathematical model of the scheduling technique.
Simulation-based analysis: at the second evaluation level schedulability is validated based on the simulation model of the scheduling technique. This technique simulates a task set scheduling based on speci c input parameters covering the target hardware (number of cores, ...) and the simulator settings (stepsize, simulation time, ...).
Implementation-based analysis: at the last evaluation level, real-time tasks are deployed on the target platform. To schedule the tasks on the target platform, a scheduler and hence a Real-Time Operating System (RTOS) are required. The scheduler uses the scheduling algorithm to de ne the order of execution of the tasks.
Evaluating scheduling algorithms requires input data. In this case, a set of real-time tasks is needed to evaluate and compare di erent scheduling mechanisms. Depending on the evaluation level the content and format of the tasks and task set di er considerably. In the rst two levels, synthetic task sets are required. This implies that the task model should only include the tasks' parameters (Worst-Case Execution Time (WCET), period and deadline) of the di erent tasks. It is crucial that the generated values of those parameters are not biased against any scheduling algorithm. At the third level, however, the task model is extended with executable code. The code has to match the existing task parameters. The executable tasks should be created taking into account the WCET parameter of the task. The WCET of a task is expressed in time units and will by consequence di er when deployed on di erent target platforms. Therefore the task model should be injected by di erent sets of task code when deployed on di erent platforms. The latter feature is missing in current evaluations of scheduling algorithms making them hard to compare or reproduce across platforms. The goal is to create executable tasks, based on the synthetic task set, for a broad set of di erent architectures and to examine and compare the performance of the scheduling algorithms. The execution time of the tasks will be equal to the WCET of the tasks to test the worst-case scenario for the scheduler.
In this paper we present a task-set generator tool, which not only generates synthetic task sets, but also the executable tasks for a given target platform using publicly available benchmark programs. This tool can be used to generate task sets suitable to evaluate and compare scheduling algorithms at all evaluation levels using standardized, reproducible and transparent task-set generation techniques.
The rest of the paper is organized as follows. The related work on generating synthetic task sets and executable tasks is brie y reviewed in Section 2. The task-set generator tool and its di erent parts are discussed in Section 3. Section 4 describes an experimental evaluation of the tool. We conclude the paper and give on overview of future research in Section 5. 2.
Synthetic task-set generator tools hardly ever exist as
independent tools. They often occur in literature as part
of larger research projects. In [
Research on task-set generation tools that generate
executable tasks is rather limited. TIMES [
In [
Wagemann et al. proposed GenE [
The tool presented in this paper will generate task sets for the evaluation of scheduling algorithms at three levels of abstraction in the design process. For formal and simulation based analysis, synthetic task sets are generated given a global utilization range for the task sets. A task set S consists of a set of n independent real-time tasks f 1; 2; :::; ng. Let i indicate any given task of the task set. Each task has three parameters: the WCET C, the relative deadline D and the period T . The utilization of a task set is de ned as:
n n U t = X Ui = X Ci i=0 i=0 Ti (1) where Ci is the WCET of task i and Ti the period of task i.
For implementation-based analysis, the tasks of the
synthetic task sets are extended with an executable instance.
These executable tasks are created by combining benchmark
programs from the TACLeBench benchmark suite [
The tool is structured into three major parts which can operate independently. The rst part creates the synthetic task sets, the second part selects the combination of benchmark programs for each task and the last part generates the source code and the make le to create the executable tasks. 3.1
To generate task sets to evaluate and compare scheduling
algorithms, the distribution of the utilization of the tasks
must be unbiased towards any scheduling algorithm [
In the second step, the period of each task is de ned and
the execution time is calculated for each task. The period
is randomly selected between the given lower Tl and upper
bound Tu. Based on the generated period T and task
utilization U , the execution time C is calculated. The mininum
di erence between periods of two di erent tasks is de ned
as T . To evaluate the e ect of an input parameter,
pseudorandom generators are used to generate these values. This
implies that, for example, two identical task sets, in terms
of task utilization, can be generated, but with a di erent
lower and upper bound of the period. By keeping all other
parameters xed, all confounding e ects are avoided [
The number of generated task sets (m) depends on the number of utilization steps and the number of task sets per utilization, m = UtmUaxtstUeptmin + 1 k. Another advantage of the pseudorandom generator is its ability to reproduce identical tests. An identical set of task sets can be generated by other parties in the same domain when using the same input parameters. The generated synthetic task sets are used to generated the benchmark program sequence in the second part. 3.2
After the synthetic task sets are generated, a benchmark
program sequence is calculated for every task. The tool
uses the TACLeBench benchmark suite as a source for the
benchmark programs [
The rst function initializes the benchmark program, the
second executes the main functionality and the third
function returns a variable for sanity checks. Furthermore,
almost all benchmarks are platform-independent and can be
compiled to and evaluated on any kind of target platform.
To use the benchmark programs in the task-set generator,
information regarding each benchmark must be accessible for
the tool. This is realized by a complementary description le
for each benchmark. This description le contains all
necessary information of the benchmark (location, execution
time,...). Based on the information in the description le
and the selection criteria given by the user, the tool checks
whether the benchmark program is suitable to be used in
the benchmark program sequence. The rst round of
selection is based on the architecture of the target hardware;
if the description le includes timing information (execution
cycles) of the benchmark program on the given architecture,
the benchmark program is selected. This selection results in
a subset of the benchmark programs which are used to
calculate the benchmark program sequence for each task. By
adding more information about the benchmark programs
in their description le, a more precise selection of
benchmark programs is possible. To prevent non-reproducible
behaviour, each benchmark program should run at least a
minimum number of times in a row; due to cache e ects and
other micro-architectural features, a program's execution
time may vary strongly. Yet, when executed in sequence, the
execution time eventually stabilizes. Hence, we also derive
the minimum number of executions until a stable execution
time occurs. This means that when a benchmark program
is selected, the number of times a benchmark program is
executed lies between its minimum number and in nity. A
minimum number of consecutive executions is necessary to
get a reproducible execution time. For each benchmark
program, the minimum number of executions is di erent and
does not only depends on the code of the benchmark
program, but also on the architecture of the target hardware.
The value of this minimum number of executions, has to
be obtained in a measurement based approach by executing
the benchmark program in a loop and varying the loop size.
This minimum number of executions is included in the
description le of the benchmark program. To calculate the
program sequence for each task, we use an Integer Linear
Programming (ILP) model [
k X(ciyi + eili) i=1 k X(ciyi + eili) i=1 yi = (0 for li = 0
1 for li > 0 li 2 Z 0; yi 2 f0; 1g ;
E; i = 1; :::; k
i = 1; :::; k
i = 1; :::; k
i = 1; :::; k
(2)
where e0; :::; ek is the set of execution times of the subset of
benchmark programs. The number of times a benchmark
program must be executed is represented by l0; :::; lk, and
E represents the targeted execution time of the task. The
initial cost of each benchmark program is represented by
c0; :::; ck. The output of the ILP is for each benchmark
program the value of l; if l is bigger than zero, the minimum
number of executions for that benchmark program is added
to l and the benchmark program is selected. The tool uses
the GNU Linear Programming Kit (GLPK) [
The nal part of the tool-chain generates the source code for each task and a make le for every task set. It uses the task sets from Section 3.2 as input. For each task of a task set the initialization and main function of all selected benchmarks are called from within the code of the task. Afterwards a make le is generated that compiles the tasks for the target platform. Each benchmark program is called within a for-loop statement, where l is the loop bound. After the code of the benchmark programs is appended, additional lines of code are inserted at the beginning and the end of the code, depending on the user requirements. This header and footer code can be added and/or changed in the template le. Listing 1 shows an example of generated source code. Compiling the source code les using the make le, results in a set of executables which can be executed on the target hardware.
Listing 1: Example of generated code of a Task with minimal header and footer code // h e a d e r b e g i n i n t t a s k ( void ) f // h e a d e r e n d i n t i ; f o r ( i = 0 ; i <606; i ++)f b i t o n i c i n i t ( ) ; b i t o n i c m a i n ( ) ; g f o r ( i = 0 ; i <103; i ++)f h 2 6 4 d e c i n i t ( ) ; h264dec main ( ) ; g f o r ( i = 0 ; i <210; i ++)f n d e s i n i t ( ) ; ndes main ( ) ; g f o r ( i = 0 ; i <308; i ++)f b i t c o u n t i n i t ( ) ; b i t c o u n t m a i n ( ) ; g // f o o t e r b e g i n g // f o o t e r e n d
In this section we introduced a task-set generator tool which can be used to generate tasks for the formal proof, analysis by simulation and for the analysis on the implementation level. In the next section, we evaluate the generated executable tasks by executing them on the target platform and compare the measured execution times to the targeted execution times of the tasks.
In this section, we report on the experiments using the task-set generator and the results of these experiments. To compare the performance of the scheduling algorithm on different evaluation levels, the utilization of the generated task sets must be identical on each level. Consequently, the execution time of each task must be equal to the targeted WCET of the task as used in the the rst two evaluation levels, or at least within an acceptable margin. The aim of our experiment is to examine the deviations of the task behaviour at the three evaluation levels: (i) the formal analysis, (ii) the simulation based analysis, and (iii) the analysis at the implementation level.
We have generated a number of synthetic task sets and executables using the task-set generator. To create the executables, we rst need to derive the timing behaviour of the benchmark programs To this end, we have executed and measured 10 benchmark programs to obtain their execution times and their minimum required number of executions. After updating the description les, the task-set generator calculates the benchmark program sequence of each task. 4.1
We have conducted our experiments on a platform with an Intel(R) Xeon(R) CPU E5-2420 v2 processors at 2:20 GHz. Xen 4.5 was patched with the latest version of RT-Xen1. The guest domain was installed with a para-virtualized kernel. Dom0 is booted with two VCPUs, each pinned on a PCPU, and 4GB memory. The remaining ten cores where used to run the guest domain. The scheduling algorithm of the guest OS, patched by LITMUSRT, is a global Earliest Deadline First (EDF) algorithm. In our experiments tasks are generated based on the base task from the LITMUSRT library. For tracing the tasks in the feather-trace tool, included by LITMUSRT, was used. 4.2
We selected 10 benchmark programs from the TACLeBench benchmark suite. Before these programs can be used to create executable tasks, the execution time of the benchmark must be known. To create reproducible task times, a minimum number of executions is required for each benchmark program (Section 3.2). For this, we analyse the execution time of a benchmark program by executing the benchmarks a statistically relevant number of times l. Typically for each benchmark we do l = f10; 50; 100; 500; 1000; 2000g measurements. Besides the execution times, we calculate the mean execution time T . Based on the above measurements a value l0 exists: 8l > l0 : l T Tl with Tl the execution time of running the benchmark l times. This value l0 is de ned as the minimum required executions for the benchmark program. This results in an execution time T and a minimum required executions l0 for each benchmark program. We analysed the execution of each benchmark program, and observed that the execution time has a standard deviation of less than 1% if the benchmark program is executed for at least l0 times. To correct for the uctuation of a task's execution time, an extra safety margin M has to be added to the number of execution cycles of the benchmark programs. We have found that a safety margin M = 2% su ces to ensure that the 1https://sites.google.com/site/realtimexen/ execution time does not exceed the WCET of the task. The calculated execution times and the minimum required executions for the corresponding architecture (in this case x86) are added to the description le of the benchmark program. See Figure 1. 4.3
After updating the description les, we generated the synthetic task sets and the executable tasks. We generated 5 randomized synthetic task sets S1; :::; S5, each with 20 tasks. For each task we executed the ILP program and generated the source code based on the benchmark sequence of the task. For our experiment, we have compiled the tasks as shared libraries to call the task function (Listing 1) in each job of the real-time task in LITMUSRT. Because the focus of the experiment lies on measuring the execution time of tasks, we used one guest with one dedicated core and pinned the virtual cpu to a physical cpu and execute the tasks one by one. The runtime of the experiment per task is 10 seconds and we repeat the experiment 10 times. Since the aim of the experiment is deriving the execution times of the tasks, the period of each task is xed to 1 second, this gives us an equal number of measurements for each task. This results in 100 measurements for every task of the 5 task sets. 4.4
The experiments shows that the calculated WCET of the ILP program of each task has a deviation of less than 0.00001% compared the target WCET generated in the rst part of the task-set generator. Comparing the execution time of the tasks on the target platform to the target WCET demonstrates that the execution time does not exceed the target WCET of the tasks. Secondly, the task with the lowest minimum execution time is task 9 of task set S5, Figure 2, with an execution time of 96:4% of the target WCET. Decreasing the safety margin M would result in an higher lower bound of the execution time. The upper bound of the execution time, however, would exceed the WCET and could result in an overload situation.
This paper presents a next generation task-set generator tool. It generates reproducible task sets for the three evaluation levels to evaluate and compare scheduling algorithms for state of the art technologies. For the rst two levels, synthetic task sets are generated that do not bias against any scheduling algorithm. Pseudorandom generated values make it possible to generate reproducible task sets. For the third level, a new task set generator methodology to create executable tasks for measurement-based analysis has been introduced. Using publicly available benchmark programs, making test sets reproducible and also making this tool open source enables the possibility to standardize the proposed methodology.We have evaluated the task-set generator tool in a number of experiments. They establish that the execution time of the tasks do not exceed the WCET of the task, and has a lower bound of 96:4% of the WCET. The development of the task-set generator tool is a ongoing process. At this moment a rst version of this tool is publicly available under the GPL license. This version of the tool can be used to generate task sets with executable tasks for the x86 architecture using 10 benchmark programs.
As this is the rst version of a task-set generator there is room for many improvements and extensions. We will focus on the two topics with the highest priority:
The concept is that users should be able to tune the input parameters in a sense that the generated task sets support their research goals.
time due to cache e ects. This would result more stable execution times, and would decrease the safety margin M while not exceeding the targeted WCETs of the tasks.
This would gave us and other researchers the possibility to evaluate and compare scheduling algorithms on di erent target platforms using identical synthetic task sets.
Make the selection of the benchmark programs not only based on the architecture of the target platform, but also on other criteria. After preselecting the benchmark programs with support of the chosen architecture, the user will be able to select an adjusted set of benchmarks. Potential selection criteria are the use of oating point units, the size of the benchmarks, or the domain of the benchmarks.