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.