SCHED_DEADLINE in mainline

Most RTOSs provide Fixed Priority scheduling as the only available scheduling policy. This is because FP is effective, and easy to be implemented efficiently. Also, FP is in the POSIX standard, so all UNIX-based systems implement it. Different flavours of FP are also available in Windows and Mac OS.

At the RETIS lab, we have based much of our research on an alternative scheduler, Earliest Deadline First (EDF), known to be a theoretically optimal scheduler. As part of these research efforts, the group at RETIS Lab of Scuola Superiore Sant'Anna, together with the people at Evidence, implemented some time ago the SCHED_DEADLINE scheduler, while working on the ACTORS EU project. The scheduler has been continuously improved and maintained by our group over the years, and it is now being used in the JUNIPER project.

The SCHED_DEADLINE patch implements the EDF with the Constant Bandwidth Server (CBS) algorithm. According to this policy, each thread is assigned a budget Q and a period P. The thread is then guaranteed to receive Q units of execution time every P. Therefore, this policy combines real-time behavior (thanks to the EDF real-time policy) and temporal isolation (thanks to the budgeting policy). In particular, a thread cannot "disturb" the execution of the other threads in the system, because it cannot execute more than its assigned share of CPU Q/P. The scheduler is ready for multicore systems and it can support global as well as clustered and partitioned scheduling.

A few weeks ago, the scheduler went into the mainline Linux kernel. Here is one announcement. Many thanks first of all to Peter Zjilstra who has always supported this idea; and to Thomas Gleixner for his initial help and support all along the way. Also, many thanks to all the people that have contributed to its development: Michael Trimarchi, Claudio Scordino, Fabio Checconi, Luca Abeni, Dario Faggioli and Juri Lelli.

If you are interested, here are two recent papers on this scheduler.

  • Juri Lelli, Giuseppe Lipari, Dario Faggioli, Tommaso Cucinotta, An efficient and scalable implementation of global EDF in Linux In proceedings of the 7th Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Porto (Portugal), July 2011. (pdf)
  • A. Parri, J. Lelli, M. Marinoni and G. Lipari. An implementation of the Bandwidth Inheritance Protocol in the Linux Kernel. In RTLWS'13. 2013. (pdf)
Tags: