Research Topics of Real-Time and Embedded Systems team

We consider the scheduling problem for non-independent task systems with firm deadlines. We are interested in off-line scheduling techniques: a valid schedule is computed before run-time, which is then stored within a table used by the dispatcher. These techniques are mainly model-oriented. They have two major advantages.

• On the one hand, the processor overload due to scheduling is at most as possible reduced since no scheduling algorithm has to run.
• On the other hand, these techniques are most often based on exhaustive exploration of the solution space (the set of all possible schedules) and thus, if one valid schedule exists, they will find it. These methods are thus more powerful than on-line strategies (which are mainly based on a priority-driven algorithm executed at run-time) since they make their decisions according to the global knowledge of the application, not only on the instantaneous state of the application.

We considerer model oriented approaches based on:

• Petri nets,
• discrete geometry,
• markovian technique based models.

The problems that we address are:

• taking explicitly conditional statements into account during scheduling: scheduling tree, strong scheduling;
• using semantic properties for scheduling,
• considering scalability properties of real-time applications such as task adjunction (either periodic or aperiodic), or processor failure,
• geometrical characterization of fair behaviours,
• measures of fairness for either the extraction of as fair as possible schedules or for a fair distribution of idle time units,
• analysis of cyclicity properties in multiprocessor environment,
• analysis of quality of scheduling processes.

Real-time operating systems define recurring tasks. Real-time tasks are often periodically released. Basically, a periodic task gets its input data from sensors and commands the controlled process by sending data to actuators. Every execution of a task is called a job that must complete by its deadline. Most of real-time kernels implement a priority-driven schedule. The schedule is defined at run-line by choosing the highest priority task to run among available tasks. At any time, the task having the highest priority is executed. According to the on-line scheduling literature, real-time scheduling can be viewed as a on-line scheduling paradigm having only one parameter that is provided on-line: the exact execution requirements of tasks is know when they complete. Furthermore, the execution requirement of a task varies from one job to another. Thus, only an upper limit of execution requirements is known for every task– called the worst-case execution time -Wcet). A on-line real-line scheduling algorithm is optimal if the algorithm finds a feasible schedule for the considered task set, if any.

Two main problems are studied for any on-line scheduling problems: the feasibility analysis that to define a scheduling algorithm so that tasks meet their deadlines at run-time and the schedulability analysis that proves if a given scheduling algorithm will guarantee that no deadline failures will occur at run-time. Both problems highly depend on the task models, sharing resource protocols, task synchronization/communication mechanism and execution platforms characteristics. Feasibility/Schedulability analyses are highly combinatorial decision problems. For number of these problems, only sufficient feasibility/schedulablity conditions are known in order to prove that deadlines will be met at run-time.

The topics studied in our team are:

• new schedulability analysis for transaction of tasks or dependent task,
• approximation algorithms for response time analysis,
• analysis of tasks allowed to self-suspend for performing Input/Ouput operations,
• analysis and configuration of real-time distributed systems.