Evidence Srl, in collaboration with ReTiS Lab of Scuola Sant'Anna, has designed and developed a real-time CPU scheduler for Linux.
The project has been carried out within the ACTORS FP7 project.
We submitted the first version of the scheduler on LKML on September 2009. Almost at the same time, we presented the project 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 will be available soon.
The scheduler is now available by default in the official Linux kernel (included 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:
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 it 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 ?
Need further information ?
The source code is open-source and free. However, if you want further information or discover how SCHED_DEADLINE can help you in creating a more reliable system, contact us.
Linux Weekly News (LWN):
Page on the Actors website:
Automotive Grade Linux: