Location of the process scheduler in a simplified structure of the Linux kernel.
SCHED_DEADLINE is a CPU scheduler available in the Linux kernel since version 3.14,[1][2] based on the earliest deadline first (EDF) and constant bandwidth server (CBS)[3] algorithms, supporting resource reservations: each task scheduled under such policy is associated with a budget Q (aka runtime), and a period P, corresponding to a declaration to the kernel that Q time units are required by that task every P time units, on any processor. This makes SCHED_DEADLINE particularly suitable for real-time applications, like multimedia or industrial control, where P corresponds to the minimum time elapsing between subsequent activations of the task, and Q corresponds to the worst-case execution time needed by each activation of the task.
The Linux kernel contains different scheduler classes.[4] By default, the kernel uses a scheduler mechanism called the Completely Fair Scheduler (CFS) introduced in the 2.6.23 version of the kernel.[5] Internally, this default scheduler class is also known as SCHED_NORMAL, and the kernel also contains two POSIX-compliant[6] real-time scheduling classes named SCHED_FIFO (realtime first-in-first-out) and SCHED_RR (realtime round-robin) both of which take precedence over the default class.[4] The SCHED_DEADLINE scheduling class was added to the Linux scheduler in version 3.14 of the Linux kernel mainline, released on 30 March 2014,[7][8] 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, SCHED_RR or SCHED_FIFO, which apply fixed-priority to schedule tasks by priorities, and whose tasks are scheduled before any task in the SCHED_NORMAL class.
Operation
When mixing real-time workloads with heterogeneous timing requirements on the same system, a well-known problem of SCHED_RR and SCHED_FIFO 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 SCHED_DEADLINE, 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 SCHED_DEADLINE 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 SCHED_DEADLINE implements global EDF, the general tardiness bound for global EDF applies, as explained in.[9]
In order to better understand how the scheduler works, consider a set of SCHED_DEADLINE tasks with potentially different periods, having the deadline equal to the period. For each task, in addition to the configured runtime and (relative) period, the kernel keeps track of a current runtime and a current (absolute) deadline. Tasks are scheduled on CPUs based on their current deadlines, using global EDF. When a task scheduling policy is initially set to SCHED_DEADLINE, the current deadline is initialized to the current time plus the configured period, and the current budget is set equal to the configured budget. Each time a task is scheduled to run on any CPU, the kernel lets it run for at most the available current budget, and whenever the task is descheduled its current budget is decreased by the amount of time it has been run. Once the current budget goes to zero, the task is suspended (throttled) till the next activation period, when the current budget is refilled again to the configured value, and the deadline is moved forward by a value equal to the task period.
This is not sufficient to guarantee temporal isolation. A task suspending itself shortly after its activation, and then waking up close to its current deadline or even beyond, would wake up with nearly the whole of its configured budget, with a current deadline that is very close to expire, or even in the past. In such condition, that task would be scheduled before any other one, and on a single-processor system it would be able to delay execution of any other deadline task for as long as its budget. In order to avoid this problem, SCHED_DEADLINE adopts the wake-up scheduling rule defined in the CBS algorithm. When a task wakes up, if a relatively small time has elapsed since the task blocked, then the previous current deadline and budget are kept unchanged for the task. However, if an excessive amount of time has elapsed, then the kernel resets the current deadline to the current time plus the reservation period, and the current budget to the allocated reservation budget. For a longer explanation with examples, see.[9]
On a multi-processor or multi-core system, SCHED_DEADLINE implements global EDF, so tasks are able to migrate across available CPUs. In such a case, the configured budget is the total cumulative amount of time the task is allowed to run on any CPU during each period. However, the scheduler also respects tasks' affinity masks, so one can easily create partitioned scheduling scenarios, partitioning tasks in groups where each group is restricted to a specific CPU, or clustered scheduling scenarios, obtained by also partitioning CPUs and each tasks partition is pinned down to a specific CPUs partition.
For technical details about SCHED_DEADLINE, refer to the documentation available within the kernel source tree.[9] For further details on the CBS and how it enables temporal isolation, refer to the original CBS paper,[3] or the section about the CBS in this article [10] 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[11] and its Spin-Off company Evidence Srl.[12] Then, Evidence Srl leveraged the funding of the ACTORS project,[13][14] 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) [15] 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[16]) and frequency-scaling (i.e. GRUB-PA[17]) 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 SCHED_EDF and presented to the Linux kernel community in 2009.[18] With this name was also presented to the Real-Time Linux Workshop after a few weeks.[19] The name has been then changed to SCHED_DEADLINE after the request of the Linux kernel community.[20]
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 SCHED_EDF.[18]
The first version of the scheduler after the name changed to SCHED_DEADLINE was submitted to LKML on October 16, 2009.[21]
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.[22]
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.[23]
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.[24]
The fifth version of the scheduler has been submitted to LKML on May 23, 2012.[25]
The sixth version of the scheduler has been submitted to LKML on October 24, 2012.[26]
The seventh version of the scheduler has been submitted to LKML on February 11, 2013.[27] 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.[28]
The ninth version of the scheduler has been submitted to LKML on November 7, 2013.[29]
The last version was merged into the mainline Linux kernel (commit number a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8[30]), and is since then a regular part of it.
Articles on Linux Weekly News[31] and Phoronix[32] websites argued that SCHED_DEADLINE 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.[7][8]
Before SCHED_DEADLINE, the Real-Time Systems (ReTiS) Lab[11] of Scuola Superiore Sant'Anna had provided various other open-source implementations of CBS and its variants within the Linux kernel, in the context of other European research projects, including OCERA,[33] the AQuoSA architecture within the FRESCOR project,[34] and IRMOS.[35] 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.[10]
Since kernel 4.13, SCHED_DEADLINE completed[36] CBS with the Greedy Reclamation of Unused Bandwidth (GRUB) algorithm.[37] The support has been developed by ReTiS Lab with the collaboration of Evidence Srl.
Since kernel 4.16, SCHED_DEADLINE has been further evolved to reduce energy consumption on ARM platforms by implementing the GRUB-PA algorithm.[17] The work has been done by ARM Ltd. in collaboration with Evidence Srl and Scuola Superiore Sant'Anna.[38]
Academic background
SCHED_DEADLINE 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[19][39]
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[40][41]
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.[42][43]
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.[14]
Andrea Parri, Juri Lelli, Mauro Marinoni, Giuseppe Lipari, Design and Implementation of the Multiprocessor Bandwidth Inheritance Protocol on Linux, 15th Real-Time Linux Workshop (RTLWS), Lugano-Manno, Switzerland, October 2013.[44]
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.[45]
Juri Lelli, Claudio Scordino, Luca Abeni, Dario Faggioli, Deadline scheduling in the Linux kernel, Software: Practice and Experience, 46(6): 821–839, June 2016.[46]
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.[47]
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.[48]
The project has been also presented at the Kernel Summit in 2010,[49][50] at the Linux Plumbers Conference 2012,[51][52] and at the Embedded Linux Conference 2013.[53]
Other information
The project has an official page.[54] Before mainline integration, the code used to be publicly available on a GitHub website,[55] which replaced the previous repository on Gitorious.[56] Since mainline integration, the official code is included in the Linux kernel source tree.
Several articles have appeared on Linux Weekly News,[1][57]Slashdot,[58] OSNews[2][59] and LinuxToday.[60] A video has been uploaded on YouTube[61] as well.
Before integration in the mainline kernel, SCHED_DEADLINE was already integrated into the Yocto Project.[28] and there had also been some interest for inclusion in Linaro projects.[62]
In computing, scheduling is the action of assigning resources to perform tasks. The resources may be processors, network links or expansion cards. The tasks may be threads, processes or data flows.
μClinux is a variation of the Linux kernel, previously maintained as a fork, that targets microcontrollers without a memory management unit (MMU). It was integrated into the mainline kernel as of 2.5.46; the project continues to develop patches and tools for microcontrollers. The homepage lists Linux kernel releases for 2.0, 2.4 and 2.6.
An O(1) scheduler is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the operating system. This is an improvement over previously used O(n) schedulers, which schedule processes in an amount of time that scales linearly based on the amounts of inputs.
The Linux kernel provides multiple interfaces to user-space and kernel-mode code that are used for varying purposes and that have varying properties by design. There are two types of application programming interface (API) in the Linux kernel:
the "kernel–user space" API; and
the "kernel internal" API.
AQuoSA is an open architecture for the provisioning of adaptive Quality of Service functionality into the Linux kernel. The project features a flexible, portable, lightweight and open architecture for supporting QoS related services on the top of a general-purpose operating system as Linux. The architecture is well founded on formal scheduling analysis and control theoretical results.
The Completely Fair Scheduler (CFS) is a process scheduler that was merged into the 2.6.23 release of the Linux kernel and is the default scheduler of the tasks of the SCHED_NORMAL class. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance.
Con Kolivas is a Greek-Australian anaesthetist. He has worked as a computer programmer on the Linux kernel and on the development of the cryptographic currency mining software CGMiner. His Linux contributions include patches for the kernel to improve its desktop performance, particularly reducing I/O impact.
The Linux kernel is a free and open-source, monolithic, modular, multitasking, Unix-like operating system kernel. It was originally written in 1991 by Linus Torvalds for his i386-based PC, and it was soon adopted as the kernel for the GNU operating system, which was written to be a free (libre) replacement for Unix.
Tomoyo Linux is a Linux kernel security module which implements mandatory access control (MAC).
The Brain Fuck Scheduler (BFS) is a process scheduler designed for the Linux kernel in August 2009 based on earliest eligible virtual deadline first scheduling (EEVDF), as an alternative to the Completely Fair Scheduler (CFS) and the O(1) scheduler. BFS was created by an experienced kernel programmer Con Kolivas.
Temporal isolation or performance isolation among virtual machine (VMs) refers to the capability of isolating the temporal behavior of multiple VMs among each other, despite them running on the same physical host and sharing a set of physical resources such as processors, memory, and disks.
cgroups is a Linux kernel feature that limits, accounts for, and isolates the resource usage of a collection of processes.
Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution.
perf is a performance analyzing tool in Linux, available from Linux kernel version 2.6.31 in 2009. Userspace controlling utility, named perf, is accessed from the command line and provides a number of subcommands; it is capable of statistical profiling of the entire system.
zswap is a Linux kernel feature that provides a compressed write-back cache for swapped pages, as a form of virtual memory compression. Instead of moving memory pages to a swap device when they are to be swapped out, zswap performs their compression and then stores them into a memory pool dynamically allocated in the system RAM. Later writeback to the actual swap device is deferred or even completely avoided, resulting in a significantly reduced I/O for Linux systems that require swapping; the tradeoff is the need for additional CPU cycles to perform the compression.
kpatch is a feature of the Linux kernel that implements live patching of a running kernel, which allows kernel patches to be applied while the kernel is still running. By avoiding the need for rebooting the system with a new kernel that contains the desired patches, kpatch aims to maximize the system uptime and availability. At the same time, kpatch allows kernel-related security updates to be applied without deferring them to scheduled downtimes. Internally, kpatch allows entire functions in a running kernel to be replaced with their patched versions, doing that safely by stopping all running processes while the live patching is performed.
RPMsg is a protocol enabling inter-processor communication inside multi-core processors.
Bcachefs is a copy-on-write (COW) file system for Linux-based operating systems. Its primary developer, Kent Overstreet, first announced it in 2015, and it was added to the Linux kernel beginning with 6.7. It is intended to compete with the modern features of ZFS or Btrfs, and the speed and performance of ext4 or XFS. It self-describes as "stable", as of December 2022.
This article documents the version history of the Linux kernel. The Linux kernel is a free and open-source, monolithic, Unix-like operating system kernel. It was conceived and created in 1991 by Linus Torvalds.
Earliest eligible virtual deadline first (EEVDF) is a dynamic priority proportional share scheduling algorithm for soft real-time systems.
References
1 2 Linux Weekly News, Deadline scheduling for Linux
1 2 OSNews, Deadline Scheduling in the Linux Kernel
1 2 L. Abeni and G. Buttazzo, "Integrating multimedia applications in hard real-time systems," Proc. of the 19th IEEE Real-Time Systems Symposium, Madrid, 1998, pp.4-13
1 2 First submission of SCHED_DEADLINE (still called SCHED_EDF)
1 2 Dario Faggioli, Fabio Checconi, Michael Trimarchi, Claudio Scordino, An EDF scheduling class for the Linux kernel, 11th Real-Time Linux Workshop (RTLW), Dresden, Germany, September 2009.
↑ Request to change the name from SCHED_EDF to SCHED_DEADLINE
↑ 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.
↑ International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Porto (Portugal), July 2011
↑ Lelli, Juri (2015). "Deadline scheduling in the Linux kernel". Software: Practice and Experience. 46 (6): 821–839. doi:10.1002/spe.2335. S2CID5527688.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
