跳转到内容

User:Pdeantihuman/SCHED DEADLINE

维基百科，自由的百科全书
进程调度器在 Linux 内核的简化结构中的位置。

SCHED_DEADLINE是 Linux 内核自 3.14 版以来可用的 CPU调度器[1] [2]基于最早截止时间优先调度 (EDF)和恒定带宽服务器 (CBS) [3]算法，支持资源预留：在此策略下调度的每个任务与预算Q（又名运行时）和周期P 相关联，相当于对内核声明：每P个时间单位，该任务就需要Q个时间单位。这使得SCHED_DEADLINE特别适用于实时应用程序，如多媒体或工业控制，其中 P 对应于该任务的两次激活之间的最短时间间隔，Q 对应于最坏情况下每次激活任务所需的执行时间。

Linux 内核中 CPU 调度器的背景

[编辑]

Linux 内核包含不同的调度器类。 [4]默认情况下，内核使用 2.6.23 版本内核中引入的称为完全公平调度器 (CFS) 的调度器机制。 [5]在内部，这个默认调度器类也称为SCHED_NORMAL ，但内核还包含两个符合 POSIX [6]实时调度类，名为SCHED_FIFO （实时先进先出）和SCHED_RR （实时Round Robin循环制），两者都优先于默认类。 [4] SCHED_DEADLINE调度类在 2014 年 3 月 30 日发布的 Linux 内核主线3.14 版中被添加到 Linux 调度器中[7] [8]并优先于所有其他调度类。

默认调度器 CFS 在处理不同用例方面做得非常好。例如，当混合批处理工作负载（例如长时间运行的代码编译或数字处理）和交互式应用程序（例如桌面应用程序、多媒体或其他应用程序）时，CFS 会动态降低批处理任务的优先级，以支持交互式任务。然而，当一个应用程序需要一个可预测和精确的调度时，通常它必须递归到其他实时调度器之一，SCHED_RR 或 SCHED_FIFO，它们应用固定优先级按优先级调度任务，并且其任务在任何任务之前被调度在 SCHED_NORMAL 类中。

操作

[编辑]

当在同一系统上混合具有异构时序要求的实时工作负载时， SCHED_RR和SCHED_FIFO一个众所周知的问题是，由于它们基于任务优先级，因此运行时间超过预期的高优先级任务可能会任意延迟低优先级任务，以不受控制的方式执行任务。

相反，使用SCHED_DEADLINE ，任务根据每个任务周期所需的每个任务运行时(并且在每个周期开始后的每个任务截止时间内到期)独立声明它们的定时要求，并且内核在可调度性测试后在调度器中接受它们。现在，如果任务试图运行的时间超过其分配的预算，内核将挂起该任务并将其执行推迟到下一个激活周期。调度器的这种非保持工作调度器（英语：Work-conserving scheduler）特性允许它在任务之间提供时间隔离（英语：Temporal isolation）。这导致了一个重要的特性，即在单处理器系统或分区的多处理器系统上（其中任务在可用 CPU 之间进行分区，因此每个任务都固定在特定的 CPU 上并且无法迁移），所有接受的SCHED_DEADLINE任务都是保证在每个时间窗口中安排的总时间等于他们的预算，只要他们的时间段，除非任务本身阻塞并且不需要运行。此外，CBS 算法的一个特殊属性是它在存在任务阻塞和恢复执行的情况下也能保证时间隔离：这是通过将任务调度截止日期重置为一个完整的时间间隔来完成的，只要任务唤醒太晚。在任务在多处理器上自由迁移的一般情况下，由于SCHED_DEADLINE实现了全局 EDF，适用于全局 EDF 的一般延迟限制，详细信息可参考[9]。

为了更好地理解调度器的工作方式，请考虑一组SCHED_DEADLINE任务，这些任务可能具有不同的时间段，但截止日期与时间段相同。对于每个任务，除了配置的运行时间和（相对）周期之外，内核还会跟踪当前运行时间和当前（绝对）截止时间。任务使用全局 EDF 根据当前的截止日期在 CPU 上进行调度。当任务调度策略初始设置为SCHED_DEADLINE ，当前截止时间初始化为当前时间加上配置的时间段，当前预算设置为等于配置的预算。每次任务被安排在任何 CPU 上运行时，内核让它最多运行可用的当前预算，并且每当任务被取消调度时，它的当前预算会减少它已运行的时间量。一旦当前预算变为零，任务将暂停（节流）直到下一个激活周期，当当前预算再次重新填充到配置值时，截止日期前移一个等于任务周期的值。

这不足以保证时间隔离（英语：Temporal isolation）。一个任务在其激活后不久暂停，然后在接近当前截止日期或什至超过它时唤醒，它会以几乎所有配置的预算唤醒，但当前截止日期非常接近到期，甚至在过去的。在这种情况下，该任务将在任何其他任务之前被调度，并且在单处理器系统上，它可以将任何其他截止时间任务的执行延迟到其预算内。为了避免这个问题， SCHED_DEADLINE采用了CBS算法中定义的唤醒调度规则。当一个任务被唤醒时，如果自该任务被阻塞以来已经过去了相对较短的时间，那么该任务之前的当前期限和预算保持不变。但是，如果时间过长，则内核将当前截止时间重置为当前时间加上预留时间，并将当前预算重置为分配的预留预算。有关示例的详细说明，请参阅。 [9]

在多处理器或多核系统上， SCHED_DEADLINE实现全局 EDF，因此任务能够跨可用 CPU 迁移。在这种情况下，配置的预算是允许任务在每个时间段内在任何 CPU 上运行的总累积时间量。但是，调度器也尊重任务的亲和掩码，因此可以轻松创建分区调度方案，将任务划分为每个组仅限于特定 CPU 的组，或集群调度方案，通过对 CPU 进行分区并固定每个任务分区来获得到特定的 CPU 分区。

SCHED_DEADLINE技术详细信息，请参阅内核源代码树中的可用文档。 [9]有关 CBS 及其如何启用时间隔离的更多详细信息，请参阅原始 CBS 论文[3][10]有关 CBS 的部分出现在 lwn.net。

历史

[编辑]

基于最早截止日期优先 (EDF) 算法的 Linux 调度类的最初想法诞生于Scuola Superiore Sant'Anna [11]的实时系统 (ReTiS) 实验室及其衍生公司 Evidence先生。 [12]然后，Evidence Srl 利用由欧盟委员会[13] [14]的资金，为补丁的第一个版本的开发提供资金和促进。原始版本由 Dario Faggioli（与 Evidence Srl 签订前三个版本的开发合同）和 Juri Lelli（从第四个版本开始） [15]并得到 Michael Trimarchi 和 Fabio Checconi 的零星帮助。 Johan Eker 一直负责 ACTORS 内部的协调和爱立信的支持。 Juri Lelli、Luca Abeni 和 Claudio Scordino 合作开发了回收（即GRUB [16] ）和频率缩放（即GRUB-PA [17] ) 特性。

该补丁已通过 Linux 内核邮件列表(LKML) 定期发布给内核社区。每个版本都将代码与内核的最新版本保持一致，并考虑了上次提交时收到的评论。随着调度器的普及，越来越多的内核开发人员开始提供他们的反馈和贡献。

该项目最初名为SCHED_EDF并于 2009 年提交给 Linux 内核社区。 [18]几周后，这个名字也出现在实时 Linux 研讨会上。 [19]应 Linux 内核社区的要求，该名称已更改为 SCHED_DEADLINE。 [20]

多年来，发布了以下版本：

  • 调度器的第一个版本于 2009 年 9 月 22 日提交，名称为SCHED_EDF 。 [18]
  • 2009 年 10 月 16 日向 LKML 提交SCHED_DEADLINE后的第一个版本的调度器[21]
  • 调度器的第二个版本已于 2010 年 2 月 28 日提交给 LKML，并首次实现了 Deadline Inheritance 协议。 [22]
  • 调度器的第三个版本已于 2010 年 10 月 29 日提交给 LKML，它通过动态任务迁移增加了对全局/集群多处理器调度的支持。 [23]
  • 第四版调度器已于2012年4月6日提交给LKML，更好地处理动态任务迁移的rq选择，更好地与PREEMPT_RT集成。 [24]
  • 调度器第五版已于2012年5月23日提交给LKML。 [25]
  • 调度器第六版已于2012年10月24日提交给LKML。 [26]
  • 调度器第七版已于2013年2月11日提交给LKML。 [27]内部数学已被限制为微秒分辨率（以避免溢出）并且 RFC 标签已被删除。
  • 调度器第八版已于2013年10月14日提交给LKML。 [28]
  • 第九版调度器已于2013年11月7日提交给LKML。 [29]
  • 最后一个版本被合并到主线 Linux 内核中（提交号 a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8 [30] ），从那时起成为它的常规部分。

Linux Weekly News [31]和Phoronix（英语：Phoronix Test Suite） [32]网站上的文章认为SCHED_DEADLINE可能会在下一个版本中合并到主线内核中。最终，经过四年多的时间和九个版本的提交，补丁被接受并合并到了 Linux 内核 3.14 中。 [7] [8]

在 SCHED_DEADLINE 问世之前，Sant'Anna School of Advanced Studies（英语：Sant'Anna School of Advanced Studies）的实时系统 (ReTiS) 实验室[11]在其他欧洲研究项目（包括 OCERA）的背景下，提供了各种其他的 CBS 开源实现及其在 Linux 内核中的变体, [33] FRESCOR 项目中的AQuoSA（英语：AQuoSA）[34]和 IRMOS。 [35]然而，这些先前的努力始于学术方法，其主要目的是为研究项目收集实验结果，而不是提供适合在主线内核中集成的实现。通过 IRMOS，该实验室与 Linux 内核开发人员进行了第一次认真的接触。 [10]

自内核 4.13 起，SCHED_DEADLINE 使用未使用带宽的贪婪回收 (GRUB) 算法[36] [37]该支持由 ReTiS 实验室与 Evidence Srl 合作开发。

自内核 4.16 起，SCHED_DEADLINE 进一步发展以通过实现 GRUB-PA 算法来降低 ARM 平台上的能耗。 [17]这项工作由 ARM Ltd. 与 Evidence Srl 和 Scuola Superiore Sant'Anna 合作完成。 [38]

学术背景

[编辑]

SCHED_DEADLINE已通过一些学术研讨会、会议和期刊发表：

  • 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.
  • 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.
  • 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.[39]
  • 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.[40]
  • 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.[41]

该项目还在 2010 年的内核峰会、2012 年 Linux Plumbers会议[42] [43] [44] [45]和 2013 年嵌入式 Linux 会议上发表。 [46]

其他信息

[编辑]

该项目有一个官方页面。 [47]在主线集成之前，该代码曾经在 GitHub 网站上公开提供， [48]取代了之前在 Gitorious 上的存储库。 [49]由于主线集成，官方代码包含在 Linux 内核源代码树中。

Linux Weekly News 、 [1] [50] Slashdot 、 [51] OSNews [2] [52]和 LinuxToday 上发表了多篇文章。 [53] [54]上也上传了一个视频。

在集成到主线内核之前， SCHED_DEADLINE已经集成到Yocto 项目中。 [28]并且也有人对加入Linaro项目感兴趣。 [55]

参考文献

[编辑]

  [[Category:有未审阅翻译的页面]]

  1. ^ 1.0 1.1 [1] Linux Weekly News, Deadline scheduling for Linux
  2. ^ 2.0 2.1 [2] OSNews, Deadline Scheduling in the Linux Kernel
  3. ^ 3.0 3.1 [3] 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
  4. ^ 4.0 4.1 Bar, Moshe. The Linux Scheduler. Linux Journal. [2012-04-14]. 
  5. ^ Molnár, Ingo. [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]. linux-kernel (邮件列表). 2007-04-13. 
  6. ^ [4] IEEE Standard for Information Technology – Portable Operating System Interface, POSIX.1b, Real-time extensions (IEEE Std 1003.1b-1993)
  7. ^ 7.0 7.1 Linux kernel 3.14, Section 1.1. Deadline scheduling class for better real-time scheduling. kernelnewbies.org. 2014-03-30 [2014-04-02]. 
  8. ^ 8.0 8.1 [5] Phoronix, The Linux 3.14 Kernel Already Has Many Exciting Features
  9. ^ 9.0 9.1 9.2 Deadline Task Scheduling
  10. ^ 10.0 10.1 T. Cucinotta and F. Checconi, "The IRMOS realtime scheduler", section "The CBS: EDF-based Scheduling and Temporal Isolation"
  11. ^ 11.0 11.1 [6] ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, Italy
  12. ^ [7] Evidence Srl, press release for SCHED_DEADLINE v6
  13. ^ [8] ACTORS FP7 project
  14. ^ [9] 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.
  15. ^ [10] History of SCHED_DEADLINE project
  16. ^ CPU reclaiming for SCHED_DEADLINE [LWN.net]. lwn.net. [2018-10-24]. 
  17. ^ 17.0 17.1 GRUB-PA. git.kernel.org. [2018-10-24] （英语）. 
  18. ^ 18.0 18.1 [11] First submission of SCHED_DEADLINE (still called SCHED_EDF)
  19. ^ [12] 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.
  20. ^ [13] Request to change the name from SCHED_EDF to SCHED_DEADLINE
  21. ^ [14] First version of SCHED_DEADLINE
  22. ^ [15] Second version of SCHED_DEADLINE
  23. ^ [16] Third version of SCHED_DEADLINE
  24. ^ [17] Fourth version of SCHED_DEADLINE
  25. ^ [18] Fifth version of SCHED_DEADLINE
  26. ^ [19] Sixth version of SCHED_DEADLINE
  27. ^ [20] Seventh version of SCHED_DEADLINE
  28. ^ 28.0 28.1 [21] Eighth version of SCHED_DEADLINE
  29. ^ [22] Ninth version of SCHED_DEADLINE
  30. ^ [23] Commit merging SCHED_DEADLINE in the mainline kernel
  31. ^ Deadline scheduling: coming soon?. lwn.net. 
  32. ^ [24] Phoronix, SCHED_DEADLINE To Be Added To Linux 3.14
  33. ^ [25] OCERA European research project on CORDIS
  34. ^ [26] FRESCOR European research project on CORDIS
  35. ^ [27] IRMOS European research project on CORDIS
  36. ^ kernel/git/torvalds/linux.git - Linux kernel source tree. git.kernel.org. [2017-09-05] （英语）. 
  37. ^ [28] Greedy Reclamation of Unused Bandwidth (GRUB) algorithm
  38. ^ kernel/git/torvalds/linux.git - Linux kernel source tree. git.kernel.org. [2019-01-04]. 
  39. ^ Lelli, Juri. Deadline scheduling in the Linux kernel. Software: Practice and Experience. 2015, 46 (6): 821–839. doi:10.1002/spe.2335. 
  40. ^ Scordino, Claudio; Abeni, Luca; Lelli, Juri. Energy-aware real-time scheduling in the linux kernel. ACM. 2018-04-09: 601–608. ISBN 9781450351911. doi:10.1145/3167132.3167198. 
  41. ^ ACM SIGAPP Applied Computing Review (ACR) Vol. 18 No. 4, 2018. (PDF). 
  42. ^ [29] SCHED_DEADLINE at Kernel Summit 2010 (KS2010)
  43. ^ [30] ReTiS Lab, SCHED_DEADLINE presented at kernel Summit 2010
  44. ^ [31] Linux Plumbers Conference 2012
  45. ^ [32] SOOS project, SCHED_DEADLINE at the Linux Plumbers Conference 2012
  46. ^ [33] Embedded Linux Conference, San Francisco, 2013. Deadline Miss Detection with SCHED_DEADLINE, Yoshitake Kobayashi, TOSHIBA Corporation
  47. ^ [34] Official webpage of SCHED_DEADLINE project
  48. ^ [35] New GitHub public repository
  49. ^ Archived copy. [2011-01-11]. （原始内容存档于2010-12-27）.  Previous Gitorious repository
  50. ^ [36] Linux Weekly News, Adding periods to SCHED_DEADLINE
  51. ^ [37] Slashdot, Deadline Scheduling Proposed For the Linux Kernel
  52. ^ [38] OSNews, New Version of SCHED_DEADLINE for Linux Available
  53. ^ [39] LinuxToday, Adding periods to SCHED_DEADLINE
  54. ^ [40] SCHED_DEADLINE video on YouTube
  55. ^ [41] SCHED_DEADLINE on Linaro
检索自“https://zh.wikipedia.org/w/index.php?title=User:Pdeantihuman/SCHED_DEADLINE&oldid=66735878”