SCHED_DEADLINE: An EDF Scheduler for the Linux Kernel

Evidence Srl and the ReTiS Lab have collaborated in the design and development of a real-time CPU scheduler for Linux.
The project has been carried out within the ACTORS FP7 project. 

The first version of the scheduler was submitted on LKML on September 2009. Almost at the same time, the project was presented through the following paper:

Dario Faggioli, Fabio Checconi, Michael Trimarchi, Claudio Scordino, An EDF scheduling class for the Linux kernel, 11th Real-Time Linux Workshop (RTLWS), Dresden, Germany, September 2009.

The two major developers have been Dario Faggioli and Jury Lelli. The whole history of the project has been described in the following paper

Juri Lelli, Claudio Scordino, Luca Abeni, Dario Faggioli, Deadline scheduling in the Linux kernel, Software: Practice and Experience 2015.

The scheduler is available by default in the official Linux kernel since release 3.14.

Why SCHED_DEADLINE  ?

With previous Linux scheduling policies, no concept of timing constraint (e.g., deadline) could be associated to tasks. For example, it was not possible to specify that a task should be given the CPU for e.g. 20msec every 100msec. For this reason, time-sensitive applications experienced delays, and system developers had to oversize CPUs to meet timing constraints of running applications.  Even worse, the delay experienced by a task depended by the behavior of the other running tasks, making the system undeterministic and unreliable. Without a real-time scheduler, in fact, it was not possible to make any feasibility study of the system under development, and developers could not be sure that the timing requirements would be met under any circumstance. These issues prevented the usage of Linux in industrial contexts.

SCHED_DEADLINE, instead, is a real-time CPU scheduler that:

  • allows to specify the timing constraints of each task;
  • is built around the concept of Resource Reservation, which allows to provide isolation among running tasks;
  • is based on well-known scheduling algorithms (i.e., CBS – Constant Bandwidth Server) , so that latencies are bounded and timing constraints are guaranteed;
  • it does not make any restrictive assumption about the characteristics of the tasks, which can be either periodic, sporadic or aperiodic.

With SCHED_DEADLINE, the temporal behavior of each task (i.e., its ability to meet its deadlines) is not affected by the behavior of any other task in the system. In other words, even if a task misbehaves, it is not able to exploit larger execution times than the amount it has been allocated.

Each task is characterized by a “budget” sched_runtime and a “period” sched_period. The scheduler ensures that the task will be given the CPU for an exact amount of budget every period. This means that the task is guaranteed a share of processor time equal to sched_runtime/sched_period every sched_period. If a task tries to execute more than its budget, it is stopped until the time instant of its next period.
Of course, the sum of sched_runtime/sched_period of all tasks cannot be higher than the total throughput available on the system (i.e., 100% on uniprocessor systems), otherwise, the system is overloaded and task deadlines cannot be guaranteed. 

What is SCHED_DEADLINE useful for  ?

The scheduling policy of a user-level task can be set to SCHED_DEADLINE for achieving two different results:

  • Timing guarantees: the task is guaranteed a certain share of CPU time, regardless of the behavior of the other tasks running on the system; these guarantees are important for time-sensitive applications (e.g., real-time control) that need to execute a certain amount of work within a timing constraint.
  • Timing confinement: the task is forced to use no more than its assigned CPU share; this is useful to limit the amount of CPU used by high-priority tasks which, in case of bug or intensive computation, may starve the rest of the system. It is also useful in virtualization environments, for a fair allocation of the CPU among several virtual machines.

In both cases, the property of temporal isolation is leveraged. In the former case, it is an isolation from the other tasks, for the benefit of the task itself. In the latter case, instead, it is an isolation for the benefit of the other tasks. We have created a video on youtube to show you some examples of usage.  

References

OSNews:

Slashdot:

Linux Weekly News (LWN):

Freshmeat:

Page on the Actors website:

LinkedIn:

Linux Today:

Wikipedia:

Youtube:

Code: