Deadline Scheduling for Linux: Status Report
Dario Faggioli, Juri Lelli, Fabio Checconi and Dhaval Giani, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, and Claudio Scordino, Evidence s.r.l., Italy
This paper describes the current development status of SCHED_DEADLINE, the Earliest Deadline First (EDF) based scheduling policy that is being implemented and maintained by Scuola Superiore Sant'Anna (ReTiS Lab) and Evidence s.r.l. The basic ideas and the first drafted implementation have already been presented in the previous edition of this same event. Since then, the project underwent radical restructuring and improvements - thanks to the feedback received from the Linux kernel community through the official Linux Kernel Mailing List (LKML) - and many features have been added to it. For example, bandwidth reclaiming logic has been introduced, so that the scheduler can be forced to be work-conserving on a per-task basis and in three different ways. More important, deadline inheritance, to deal with the well-known problem of "priority" inversion, is now available, while methods to enrich it with bandwidth inheritance capabilities are started being studied and will be discussed in the paper. SCHED_DEADLINE has also been made capable of handling dynamic task migrations; this means all the partitioned (tasks are statically assigned to processors), clustered (tasks can migrate among a subset of the processors) and global (tasks can migrate among all processors) variants of EDF can be now deployed in a Linux system. Furthermore, the code has been fully ported on the PREEMPT-RT branch, thus enabling to combine the benefits of EDF and Resource Reservation based scheduling with the low latencies achieved within this patchset.
Finally, the paper will also discuss the relationship between SCHED_DEADLINE and the other main publicly released work about the introduction of EDF-based scheduling in the Linux kernel, known as "EDF Throttling", and the possibilities of integration of the two projects. Apart from the description of these new features and of the design decisions that led to them, the paper contains some performance evaluations for the scheduling policy, obtained by means of classical tools used by real-time Linux users, application and kernel developers.