ENS de Cachan: comment y aller

Salle des conférences - Bâtiment Pavillon des jardins

**Abstract:** Hard real-time tasks execution on shared memory multiprocessors has been
subjected to a lot of studies. The study of practical algorithm
implementation is less considered, except Brandenburg et al. who
proposed partitioned and Pfair schedulers on LITMUS, an Linux extension
which allows different scheduling algorithms to be linked as plugin
components.

Several overheads have been identified : they affect the effective execution and increase the global task set utilisation. One of these overheads is the context switch when task preemptions or migrations are allowed. Optimal scheduling algorithms are known to produce a lot of context switches contrary to non-optimal ones. However the optimality is an important characteristic, it allows to obtain theoretically a correct schedule whenever the task set is feasible. Moreover, these algorithms are computed on-line and often exhibit a complexity depending on the number of tasks executed which leads to a scalability problem.

In this talk, we focus on optimizing performance for optimal hard real-time schedules in a multicore preemptive context by decreasing task preemptions and migrations. This method allows a better scalability than existing approaches by minimizing two important overheads : the number of context switches (preemptions and migrations) and the on-line scheduler complexity. This is achieved by proceeding in two steps, one off-line to place jobs on intervals and one on-line to schedule them dynamically inside each interval. We propose a new linear programming formulation and a local scheduler which exhibits low complexity and produces few task preemptions and migrations. Simulation results illustrate the competitiveness of our approach using the implicit-deadline periodic task model with respect to task preemptions and migrations.

**Abstract:**Power consumption of real-time embedded systems is a significant
problem. Existing works on power-aware scheduling algorithms tend to
focus only on dynamic consumption. However, it is being overtaken by
static consumption. This paper proposes a new approach to decrease
static consumption for multiprocessor embedded hard real-time
systems. The objective is to make an efficient usage of the low-power
states of each processor. In a low-power state, the processor is not
active and has a reduced consumption. But it takes a transition delay
to come back to an active state. Our approach reduces the number of
idle periods to increase their duration allowing the activation of
deeper low-power states. It also avoids generating idle periods too
small to activate a low-power state. The approach is both off-line and
on-line. Off-line, it divides the hyper-period in intervals. It then
computes using linear programming the portion of each task to be
scheduled during each interval such that the number of idle periods is
reduced. On-line, the algorithm schedules tasks inside intervals. Its
objective is to aggregate idle periods from successive intervals when
tasks do not use all their worst case execution time. Simulations show
that our solution generates more than ten times less idle periods than
existing approaches when tasks use their worst case execution time.