跳至內容

使用者: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://wiki.tuftech.org/w/index.php?title=User:Pdeantihuman/SCHED_DEADLINE&oldid=66735878」