User Tools

Site Tools


sched_deadline

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
sched_deadline [2013/12/10 13:28]
claudio_scordino
sched_deadline [2014/06/03 05:43] (current)
claudio_scordino
Line 1: Line 1:
  
-===== SCHED_DEADLINE ​ =====+===== Introduction ​ =====
  
  
- +**SCHED_DEADLINE** is the name of a patch proposed to add a resource-reservation ​**real-time CPU scheduler** to the Linux kernel.
-==== Introduction ​ ==== +
- +
- +
-**SCHED_DEADLINE** is the name of a patch proposed to add a resource-reservation real-time CPU scheduler to the Linux kernel.+
  
 The Linux kernel contains different scheduler classes. By default the kernel uses a scheduler mechanism called [[http://​en.wikipedia.org/​wiki/​Completely_Fair_Scheduler|Completely Fair Scheduler]],​ introduced in the 2.6.23 version of the kernel. Internally this default-scheduler class is also known as SCHED_OTHER. The standard Linux kernel also contains two 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. The SCHED_DEADLINE patch adds a new scheduling class to the modular Linux scheduler, and implements the well-known [[http://​en.wikipedia.org/​wiki/​Earliest_deadline_first_scheduling|Earliest Deadline First (EDF) algorithm]]. The Linux kernel contains different scheduler classes. By default the kernel uses a scheduler mechanism called [[http://​en.wikipedia.org/​wiki/​Completely_Fair_Scheduler|Completely Fair Scheduler]],​ introduced in the 2.6.23 version of the kernel. Internally this default-scheduler class is also known as SCHED_OTHER. The standard Linux kernel also contains two 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. The SCHED_DEADLINE patch adds a new scheduling class to the modular Linux scheduler, and implements the well-known [[http://​en.wikipedia.org/​wiki/​Earliest_deadline_first_scheduling|Earliest Deadline First (EDF) algorithm]].
  
-The project was initially financed by the European commission through [[http://​www.actors-project.eu|the ACTORS FP7 project]]. The first version of the patch was called SCHED_EDF and [presented to the Linux kernel community in 2009. With this name was also [[http://​lwn.net/​images/​conf/​rtlws11/​papers/​proc/​p16.pdf|presented to the Real-Time Linux Workshop]] after a few weeks. The name has been then changed to SCHED_DEADLINE after [[https://​lkml.org/​lkml/​2009/​9/​22/​214|the request of the Linux kernel community]]. 
  
-The project is carried out jointly by the [[http://​retis.sssup.it|Real-Time Systems Laboratory of Scuola Superiore Sant'​Anna]] and the [[http://​www.evidence.eu.com|company Evidence Srl]]. +===== Motivation  ​=====
- +
- +
-==== Motivation ​ ====+
  
  
Line 28: Line 20:
   - They cannot provide the guarantees a time-sensitive application may require. ​   - They cannot provide the guarantees a time-sensitive application may require. ​
    
- ​Using ​sched_fair, no concept of timing constraint (e.g., deadline) can be associated to tasks. In fact, although it is possible to assign a share of the processor time to a task (or a group of tasks), there is no way to specify that a task must execute for 20msec within 100msec, unlike using a real-time scheduling algorithm, such as EDF.+ ​Using ​SCHED_OTHER, no concept of timing constraint (e.g., deadline) can be associated to tasks. In fact, although it is possible to assign a share of the processor time to a task (or a group of tasks), there is no way to specify that a task must execute for 20msec within 100msec, unlike using a real-time scheduling algorithm, such as EDF.
  As a proof of concept, we implemented a very simple test to run two tasks that need to execute for 20msec every 50msec. We scheduled them using CFS with the same CPU share, and we observed that even if there is enough spare CPU time (the system is idle), the tasks occasionally experience some deadline miss. The test is available [[http://​www.evidence.eu.com/​download/​scheddead/​test_cfs.tgz|here]] (otherwiise the [[https://​github.com/​gbagnoli/​rt-app|RT-APP application]] can be used for similar tests).  As a proof of concept, we implemented a very simple test to run two tasks that need to execute for 20msec every 50msec. We scheduled them using CFS with the same CPU share, and we observed that even if there is enough spare CPU time (the system is idle), the tasks occasionally experience some deadline miss. The test is available [[http://​www.evidence.eu.com/​download/​scheddead/​test_cfs.tgz|here]] (otherwiise the [[https://​github.com/​gbagnoli/​rt-app|RT-APP application]] can be used for similar tests).
- ​Using ​sched_rt, instead, we can give that kind of guarantee only using a global period, with the constraint that "a subgroup must have a smaller or equal period to its parent"​.+ ​Using ​SCHED_FIFO/​SCHED_RR, instead, we can give that kind of guarantee only using a global period, with the constraint that "a subgroup must have a smaller or equal period to its parent"​.
    
   - The latency experienced by a task (i.e., the time between two consecutive executions of a task) is not deterministic and cannot be bound, since it  highly depends on the number of tasks running in the system at that time.   - The latency experienced by a task (i.e., the time between two consecutive executions of a task) is not deterministic and cannot be bound, since it  highly depends on the number of tasks running in the system at that time.
Line 55: Line 47:
  
  
-==== Releases ​ ====+===== History of the project ​ ====
 + 
 + 
 +The initial idea of a Linux scheduling class based on the Earliest Deadline First (EDF) algorithm is born in the small context of the [[http://​retis.sssup.it|Real-Time Systems (ReTiS) Lab of Scuola Superiore Sant'​Anna]] and its Spin-Off company [[http://​www.evidence.eu.com|Evidence Srl]].  
 +Then, Evidence Srl leveraged the funding of the [[http://​www.actors-project.eu|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 code has been developed by Dario Faggioli (for the first three versions) and Juri Lelli (since the fourth version) with sporadic help from Michael Trimarchi and Fabio Checconi. Claudio Scordino has been in charge of the initial coordination,​ supporting and project advertisement. Johan Eker has been in charge of coordination within ACTORS and supporting from Ericsson. 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 original version of the patch was called SCHED_EDF and [[https://​lkml.org/​lkml/​2009/​9/​22/​186|presented to the Linux kernel community in 2009]]. With this name was also [[http://​lwn.net/​images/​conf/​rtlws11/​papers/​proc/​p16.pdf|presented to the Real-Time Linux Workshop]] after a few weeks. The name has been then changed to SCHED_DEADLINE after [[https://​lkml.org/​lkml/​2009/​9/​22/​214|the request of the Linux kernel community]]. 
 + 
 +The following versions have been released: 
 + 
 +  * The initial version of the scheduler was [[https://​lkml.org/​lkml/​2009/​9/​22/​186|submitted on September 22, 2009]] with the name of SCHED_EDF. 
 +  * The first version of the scheduler after the name changed to SCHED_DEADLINE was [[https://​lkml.org/​lkml/​2009/​10/​16/​161|submitted to LKML on October 16, 2009]]. 
 +  * The second version of the scheduler has been [[https://​lkml.org/​lkml/​2010/​2/​28/​107|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 [[https://​lkml.org/​lkml/​2010/​10/​29/​67|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 [[https://​lkml.org/​lkml/​2012/​4/​6/​39|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 [[http://​lwn.net/​Articles/​498472/​|submitted to LKML on May 23, 2012]]. 
 +  * The sixth version of the scheduler has been [[https://​lwn.net/​Articles/​521091/​|submitted to LKML on October 24, 2012]]. 
 +  * The seventh version of the scheduler has been [[http://​lwn.net/​Articles/​537388/​|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 [[http://​lwn.net/​Articles/​570293/​|submitted to LKML on October 14, 2013]]. 
 +  * The ninth (current) version of the scheduler has been [[http://​lwn.net/​Articles/​573233/​|submitted to LKML on November 7, 2013]]. 
 + 
 +The project has been [[http://​lwn.net/​Articles/​570293/​|already integrated in the Yocto distribution]]. Moreover, there has been some [[https://​groups.google.com/​a/​linaro.org/​forum/#​!topic/​linaro-networking/​IDmDhH6JL8U|interest for inclusion in Linaro]] as well. 
 + 
 +An [[http://​lwn.net/​Articles/​575497/​|article on the popular Linux Weekly News site]] argued that SCHED_DEADLINE may be merged into the mainline kernel in the very next releases.  
 + 
 +The code has been merged into the mainline kernel ([[http://​git.kernel.org/​linus/​a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8|commit number a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8]]) and therefore will be **available from kernel release 3.14**. 
 + 
 + 
 +===== Academic conferences and events ​ ===== 
 + 
 + 
 +The project has been presented through some academic workshops, conferences and journals: 
 + 
 +  * Dario Faggioli, Fabio Checconi, Michael Trimarchi, Claudio Scordino, [[http://​lwn.net/​images/​conf/​rtlws11/​papers/​proc/​p16.pdf|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, [[http://​retis.sssup.it/​~faggioli/​papers/​OSPERT-2010-dlinterrupt.pdf|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, [[http://​retis.sssup.it/​~faggioli/​papers/​OSPERT-2011-gedf.pdf|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, [[http://​ieeexplore.ieee.org/​xpl/​articleDetails.jsp?​tp=&​arnumber=5680892&​contentType=Journals+%26+Magazines&​queryText%3DResource+Management+on+Multicore+Systems%3A+The+ACTORS+Approach|Resource Management on Multicore Systems: The ACTORS Approach]], IEEE Micro, vol. 31, no. 3, pp. 72–81, May/June 2011. 
 +  * Andrea Parri, Juri Lelli, Mauro Marinoni, Giuseppe Lipari, [[https://​www.osadl.org/​Lugano-Manno-2013.rtlws15-lugano-manno-2013.0.html|Design and Implementation of the Multiprocessor Bandwidth Inheritance Protocol on Linux]], 15th Real-Time Linux Workshop (RTLWS), Lugano-Manno,​ Switzerland,​ October 2013. 
 + 
 +The project has been also presented at the [[http://​lwn.net/​Articles/​412745/​|Kernel Summit in 2010]], at the [[http://​www.linuxplumbersconf.org/​2012/​|Linux Plumbers Conference 2012]], and at the [[http://​events.linuxfoundation.org/​events/​archive/​2013/​embedded-linux-conference/​program/​|Embedded Linux Conference 2013]]. 
 + 
 +Recently, [[http://​www.youtube.com/​watch?​v=_APmI6qe9kU|a video has been uploaded on youtube]].  
 + 
 + 
 +===== Web pages  ===== 
 + 
 + 
 +Several websites (e.g., OSNews, Slashdot, Linux Today, Phoronix, etc.) have talked about the project in the course of the years.  
 + 
 +Among the various websites, the best resources are:
  
 +  * Linux Weekly News (LWN):
 +    * [[http://​lwn.net/​Articles/​356576/​|http://​lwn.net/​Articles/​356576/​]]
 +    * [[http://​lwn.net/​Articles/​396634/​|http://​lwn.net/​Articles/​396634/​]]
 +    * [[http://​lwn.net/​Articles/​378044/​|http://​lwn.net/​Articles/​378044/​]]
 +    * [[http://​lwn.net/​Articles/​412745/​|http://​lwn.net/​Articles/​412745/​]]
 +    * [[http://​lwn.net/​Articles/​491722/​|http://​lwn.net/​Articles/​491722/​]]
 +    * [[http://​lwn.net/​Articles/​575497/​|http://​lwn.net/​Articles/​575497/​]]
 +  * [[http://​www.linkedin.com/​groups?​gid=2319046|LinkedIn Group]]
 +  * [[http://​en.wikipedia.org/​wiki/​SCHED_DEADLINE|Page on Wikipedia]]
  
  
-==== Academic conferences ​and events ​ ====+===== Download ​and usage  =====
  
  
 +The project has an [[http://​www.evidence.eu.com/​sched_deadline.html|official page]].
  
-==== Web pages  ====+The code is publicly available on a [[https://​github.com/​jlelli/​sched-deadline|GitHub website]].
  
 +To download a Linux kernel with SCHED_DEADLINE integrated, type
  
 +  git clone git://​github.org/​jlelli/​sched_deadline.git
  
-==== Download and usage  ====+The documentation is available inside the [[https://​github.com/​jlelli/​sched-deadline/​blob/​sched-dl-V9-rebase/​Documentation/​scheduler/​sched-deadline.txt|Documentation/​scheduler/​sched-deadline.txt file]].
  
sched_deadline.1386682086.txt.gz · Last modified: 2013/12/10 13:28 by claudio_scordino