Sites Inria

Version française

Séminaire des équipes de recherche

Towards the design of optimal and efficient real-time scheduling algorithms

George Lima is an Associate Professor at Federal University of Bahia (UFBA) in Brazil, and holds a Ph.D. degree in Computer Science from the from The University of York, UK (2003). At UFBA, George has taken several relevant administrative positions, among which Head of Department and Head of the Ph.D. Program in Computer Science. His main research interests are in the area of real-time systems, covering topics such as scheduling, fault tolerance, operating systems, communication networks, and distributed systems.

  • Date : 27/06/2017
  • Place : Inria Paris - Bâtiment C, JJ Lions - 10h00
  • Guest(s) : George Lima (UFBA)

This talk addresses some of the key principles behind the design of efficient and optimal scheduling algorithms for multiprocessor real-time systems. Those are low overhead algorithms capable of generating a schedule for a set of tasks on M processors according to which no task misses its deadlines whenever such a kind of schedule exists. If M = 1, it is well known that the greedy Earliest Deadline First (EDF) algorithm achieves both optimality and efficiency. Unfortunately, EDF is not optimal when M > 1. Indeed, after executing the earliest deadline tasks on the M processors, there may not be enough time left for meeting the deadline fo some tasks awaiting their execution. That is, greediness should be jointly implemented with some kind of execution control so as to avoid that tasks wait too much for being scheduled. 

Most execution control mechanisms implemented in optimal scheduling algorithms are based on similar reasoning. Time is divided into scheduling windows and processor shares are assigned to tasks within each window proportionally to their needs. This approach produces Fairness-oriented schedules and ensures necessary execution control. The fairness principle has indeed established a paradigm in the design of optimal real-time scheduling algorithms for many years since its formulation in the nineties. Unfortunately, Fairness-based algorithms can impose high overheads. As scheduling windows can be small, chopping tasks' execution into those windows may compromise efficiency.

Recently, it has been shown that fairness, and hence its overhead side-effects, is indeed not necessary for obtaining optimality in multiprocessor real-time scheduling. Two of these algorithms, named Reduction to Uniprocessor (RUN) and Quasi-Partitioning Scheduling (QPS), will be discussed in this talk. Their underline principles will be intuitively described and their differences and similarities will be highlighted.

Keywords: Algorithme Séminaire Aoste2 Real Time Scheduling Design