SCHED DEADLINE

The Linux kernel contains different scheduler classes. By default, the kernel uses a scheduler mechanism called the Completely Fair Scheduler (CFS) introduced in the 2.6.23 version of the kernel. Internally, this default scheduler class is also known as , and the kernel also contains two POSIX-compliant real-time scheduling classes named (realtime first-in-first-out) and (realtime round-robin) both of which take precedence over the default class. and takes precedence over all the other scheduling classes. The default scheduler, CFS, makes a very good job in coping with different use cases. For example, when mixing batch workloads such as long-running code compilations or number crunching, and interactive applications such as desktop applications, multi-media or others, the CFS dynamically de-prioritizes batch tasks in favour of interactive ones. However, when an application needs a predictable and precise schedule, normally it has to recur to one of the other real-time schedulers, or , which apply fixed-priority to schedule tasks by priorities, and whose tasks are scheduled before any task in the class. ==Operation==

When mixing real-time workloads with heterogeneous timing requirements on the same system, a well-known problem of and is that, as these are based on tasks priorities, higher-priority tasks running for longer than expected may arbitrarily delay lower-priority tasks in an uncontrolled way. With , instead, tasks declare independently their timing requirements, in terms of a per-task runtime needed every per-task period (and due within a per-task deadline since each period start), and the kernel accepts them in the scheduler after a schedulability test. Now, if a task tries to run for longer than its assigned budget, the kernel will suspend that task and defer its execution to its next activation period. This non-work conserving property of the scheduler allows it to provide temporal isolation among the tasks. This results in the important property that, on single-processor systems, or on partitioned multi-processor systems (where tasks are partitioned among available CPUs, so each task is pinned down on a specific CPU and cannot migrate), all accepted tasks are guaranteed to be scheduled for an overall time equal to their budget in every time window as long as their period, unless the task itself blocks and doesn't need to run. Also, a peculiar property of the CBS algorithm is that it guarantees temporal isolation also in presence of tasks blocking and resuming execution: this is done by resetting a task scheduling deadline to a whole period apart, whenever a task wakes up too late. In the general case of tasks free to migrate on a multi-processor, as implements global EDF, the general tardiness bound for global EDF applies, as explained in. For further details on the CBS and how it enables temporal isolation, refer to the original CBS paper, appeared on lwn.net. == History ==

The initial idea of a Linux scheduling class based on the Earliest Deadline First (EDF) algorithm was born in the small context of the Real-Time Systems (ReTiS) Lab of Scuola Superiore Sant'Anna and its Spin-Off company Evidence Srl. Then, Evidence Srl leveraged the funding of the ACTORS project, supported by the European Commission through the FP7 framework programme, for financing and promoting the development of the first versions of the patch. The original version has been developed by Dario Faggioli (contract by Evidence Srl for the development of the first three versions) and Juri Lelli (since the fourth version) with sporadic help from Michael Trimarchi and Fabio Checconi. Johan Eker has been in charge of coordination within ACTORS and supporting from Ericsson. Juri Lelli, Luca Abeni and Claudio Scordino have collaborated to the development of the reclaiming (i.e. GRUB) and frequency-scaling (i.e. GRUB-PA) features. The patch has been periodically released to the kernel community through the Linux kernel mailing list (LKML). Each release aligned the code to the latest version of the kernel and took into account comments received at the previous submission. As the popularity of the scheduler increased, a higher number of kernel developers started providing their feedback and their contribution. The project was originally called and presented to the Linux kernel community in 2009. With this name was also presented to the Real-Time Linux Workshop after a few weeks. The name has been then changed to after the request of the Linux kernel community. In the course of the years, the following versions have been released: • The first version of the scheduler was submitted on September 22, 2009, with the name of . • The second version of the scheduler has been submitted to LKML on February 28, 2010, and had a first implementation of the Deadline Inheritance protocol. • The third version of the scheduler has been submitted to LKML on October 29, 2010, and it added support for global/clustered multiprocessor scheduling through dynamic task migrations. • The fourth version of the scheduler has been submitted to LKML on April 6, 2012, and has better handling of rq selection for dynamic task migration and better integration with PREEMPT_RT. • The fifth version of the scheduler has been submitted to LKML on May 23, 2012. • The sixth version of the scheduler has been submitted to LKML on October 24, 2012. • The seventh version of the scheduler has been submitted to LKML on February 11, 2013. Internal math has been restricted to microseconds resolution (to avoid overflows) and the RFC tag has been removed. • The eighth version of the scheduler has been submitted to LKML on October 14, 2013. • The ninth version of the scheduler has been submitted to LKML on November 7, 2013. • The last version was merged into the mainline Linux kernel (commit number a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8), and is since then a regular part of it. Articles on Linux Weekly News and Phoronix websites argued that may be merged into the mainline kernel in the very next releases. Finally, after more than four years and the submission of nine releases, the patch has been accepted and merged into the Linux kernel 3.14. the AQuoSA architecture within the FRESCOR project, and IRMOS. However, these prior efforts started with an academic approach where the main aim was to gather experimental results for research projects, rather than providing an implementation suitable for integration within the mainline kernel. With IRMOS, the lab had a first serious contact with Linux kernel developers. CBS with the Greedy Reclamation of Unused Bandwidth (GRUB) algorithm. The support has been developed by ReTiS Lab with the collaboration of Evidence Srl. Since kernel 4.16, has been further evolved to reduce energy consumption on ARM platforms by implementing the GRUB-PA algorithm. == Academic background ==

has been presented through some academic workshops, conferences and journals: • 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 • Nicola Manica, Luca Abeni, Luigi Palopoli, Dario Faggioli, Claudio Scordino, Schedulable Device Drivers: Implementation and Experimental Results, International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Brussels, Belgium, July 2010 • Juri Lelli, Giuseppe Lipari, Dario Faggioli, Tommaso Cucinotta, An efficient and scalable implementation of global EDF in Linux, International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Porto (Portugal), July 2011. • Enrico Bini, Giorgio Buttazzo, Johan Eker, Stefan Schorr, Raphael Guerra, Gerhard Fohler, Karl-Erik Arzen, Vanessa Romero Segovia, Claudio Scordino, Resource Management on Multicore Systems: The ACTORS Approach, IEEE Micro, vol. 31, no. 3, pp. 72–81, May/June 2011. • Luca Abeni, Juri Lelli, Claudio Scordino, Luigi Paolopoli, Greedy CPU reclaiming for SCHED_DEADLINE, Proceedings of 16th Real-Time Linux Workshop (RTLWS), Düsseldorf, Germany, October 2014. • Juri Lelli, Claudio Scordino, Luca Abeni, Dario Faggioli, Deadline scheduling in the Linux kernel, Software: Practice and Experience, 46(6): 821–839, June 2016. • Claudio Scordino, Luca Abeni, Juri Lelli, Energy-Aware Real-Time Scheduling in the Linux Kernel, 33rd ACM/SIGAPP Symposium On Applied Computing (SAC 2018), Pau, France, April 2018. • Claudio Scordino, Luca Abeni, Juri Lelli, Real-time and Energy Efficiency in Linux: Theory and Practice, ACM SIGAPP Applied Computing Review (ACR) Vol. 18 No. 4, 2018. The project has been also presented at the Kernel Summit in 2010, at the Linux Plumbers Conference 2012, and at the Embedded Linux Conference 2013. == Other information ==

The project has an official page. Before mainline integration, the code used to be publicly available on a GitHub website, which replaced the previous repository on Gitorious. Since mainline integration, the official code is included in the Linux kernel source tree. Several articles have appeared on Linux Weekly News, Slashdot, OSNews and LinuxToday. A video has been uploaded on YouTube as well. Before integration in the mainline kernel, was already integrated into the Yocto Project. ==See also==