SCHED_DEADLINE

From Wikipedia, the free encyclopedia
Jump to: navigation, search

SCHED_DEADLINE is a scheduling class for resource-reservation real-time CPU scheduler in the Linux kernel.[1][2]

The Linux kernel contains different scheduler classes.[3] By default, the kernel uses a scheduler mechanism called the Completely Fair Scheduler introduced in the 2.6.23 version of the kernel.[4] Internally, this default scheduler class is also known as SCHED_NORMAL, but the 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.[3]

The SCHED_DEADLINE scheduling class, implementing the earliest deadline first algorithm (EDF), was added to the Linux scheduler in version 3.14 of the Linux kernel mainline, released on 30 March 2014.[5][6]

History[edit]

The initial idea of a Linux scheduling class based on the Earliest Deadline First (EDF) algorithm is born in the small context of the Real-Time Systems (ReTiS) Lab of Scuola Superiore Sant'Anna[7] and its Spin-Off company Evidence Srl.[8] Then, Evidence Srl leveraged the funding of the ACTORS project,[9][10] 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) [11] with sporadic help from Michael Trimarchi and Fabio Checconi. Claudio Scordino has been in charge of 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 project was originally called SCHED_EDF and presented to the Linux kernel community in 2009.[12] With this name was also presented to the Real-Time Linux Workshop after a few weeks.[13] The name has been then changed to SCHED_DEADLINE after the request of the Linux kernel community.[14]

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.[12]
  • The first version of the scheduler after the name changed to SCHED_DEADLINE was submitted to LKML on October 16, 2009.[15]
  • 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.[16]
  • 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.[17]
  • 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.[18]
  • The fifth version of the scheduler has been submitted to LKML on May 23, 2012.[19]
  • The sixth version of the scheduler has been submitted to LKML on October 24, 2012.[20]
  • The seventh version of the scheduler has been submitted to LKML on February 11, 2013.[21] 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.[22]
  • The ninth version of the scheduler has been submitted to LKML on November 7, 2013.[23]
  • The last version was merged into the mainline Linux kernel (commit number a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8[24]), and is since then a regular part of it.

Articles on Linux Weekly News[25] and Phoronix[26] 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.[5][6]

Academic background[edit]

The project 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[13][27]
  • 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[28][29]
  • 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.[30][31]
  • 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.[10]
  • 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.[32]

The project has been also presented at the Kernel Summit in 2010,[33][34] at the Linux Plumbers Conference 2012,[35][36] and at the Embedded Linux Conference 2013.[37]

Other information[edit]

The project has an official page.[38] The code is publicly available on a GitHub website,[39] which replaced the previous repository on Gitorious.[40]

Several articles have appeared on Linux Weekly News,[1][41] Slashdot,[42] OSNews[2][43] and LinuxToday.[44] A video has been uploaded on YouTube[45] as well.

SCHED_DEADLINE has already been integrated into the Yocto Project.[22] There has also been some interest for inclusion in Linaro.[46]

References[edit]

  1. ^ a b [1] Linux Weekly News, Deadline scheduling for Linux
  2. ^ a b [2] OSNews, Deadline Scheduling in the Linux Kernel
  3. ^ a b Bar, Moshe. "The Linux Scheduler". Linux Journal. Retrieved 2012-04-14. 
  4. ^ Molnár, Ingo (2007-04-13). "[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]". linux-kernel mailing list. http://lwn.net/Articles/230501/.
  5. ^ a b "1.1. Deadline scheduling class for better real-time scheduling". Linux kernel 3.14. kernelnewbies.org. 2014-03-30. Retrieved 2014-04-02. 
  6. ^ a b [3] Phoronix, The Linux 3.14 Kernel Already Has Many Exciting Features
  7. ^ [4] ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, Italy
  8. ^ [5] Evidence Srl, press release for SCHED_DEADLINE v6
  9. ^ [6] ACTORS FP7 project
  10. ^ a b [7] 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.
  11. ^ [8] History of SCHED_DEADLINE project
  12. ^ a b [9] First submission of SCHED_DEADLINE (still called SCHED_EDF)
  13. ^ a b [10] 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.
  14. ^ [11] Request to change the name from SCHED_EDF to SCHED_DEADLINE
  15. ^ [12] First version of SCHED_DEADLINE
  16. ^ [13] Second version of SCHED_DEADLINE
  17. ^ [14] Third version of SCHED_DEADLINE
  18. ^ [15] Fourth version of SCHED_DEADLINE
  19. ^ [16] Fifth version of SCHED_DEADLINE
  20. ^ [17] Sixth version of SCHED_DEADLINE
  21. ^ [18] Seventh version of SCHED_DEADLINE
  22. ^ a b [19] Eighth version of SCHED_DEADLINE
  23. ^ [20] Ninth version of SCHED_DEADLINE
  24. ^ [21] Commit merging SCHED_DEADLINE in the mainline kernel
  25. ^ J. Corbet, Deadline scheduling: coming soon?, Linux Weekly News
  26. ^ [22] Phoronix, SCHED_DEADLINE To Be Added To Linux 3.14
  27. ^ [23] Real-Time Linux Workshop (RTLWS) 2009
  28. ^ [24] 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
  29. ^ [25] ACTORS international publications
  30. ^ [26] 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.
  31. ^ [27] International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Porto (Portugal), July 2011
  32. ^ [28] Real-Time Linux Workshop (RTLWS) 2013
  33. ^ [29] SCHED_DEADLINE at Kernel Summit 2010 (KS2010)
  34. ^ [30] ReTiS Lab, SCHED_DEADLINE presented at kernel Summit 2010
  35. ^ [31] Linux Plumbers Conference 2012
  36. ^ [32] SOOS project, SCHED_DEADLINE at the Linux Plumbers Conference 2012
  37. ^ [33] Embedded Linux Conference, San Francisco, 2013. Deadline Miss Detection with SCHED_DEADLINE, Yoshitake Kobayashi, TOSHIBA Corporation
  38. ^ [34] Official webpage of SCHED_DEADLINE project
  39. ^ [35] New GitHub public repository
  40. ^ [36] Previous Gitorious repository
  41. ^ [37] Linux Weekly News, Adding periods to SCHED_DEADLINE
  42. ^ [38] Slashdot, Deadline Scheduling Proposed For the Linux Kernel
  43. ^ [39] OSNews, New Version of SCHED_DEADLINE for Linux Available
  44. ^ [40] LinuxToday, Adding periods to SCHED_DEADLINE
  45. ^ [41] SCHED_DEADLINE video on YouTube
  46. ^ [42] SCHED_DEADLINE on Linaro