Linux內核的DL調度器的細節和怎么樣使用DL調度器？

一、前言

Linux內核的DL調度器是一個全局EDF調度器，它主要針對有deadline限制的sporadic任務。注意：這些術語已經在本系列文章的第一部分中說明了，這里不再贅述。在這本文中，我們將一起來看看Linux DL調度器的細節以及如何使用它。另外，本文對應的英文原文是https://lwn.net/Articles/743946/，感謝lwn和Daniel Bristot de Oliveira的分享。

二、細節

DL調度器是根據任務的deadline來確定調度的優先順序的：deadline最早到來的那個任務最先調度執行。對于有M個處理器的系統，優先級最高的前M個deadline任務（即deadline最早到來的前M個任務）將被選擇在對應M個處理器上運行。

Linux DL調度器還實現了constant bandwidth server（CBS）算法，該算法是一種CPU資源預留協議。CBS可以保證每個任務在每個period內都能收到完整的runtime時間。在一個周期內，DL進程的“活”來的時候，CBS會重新補充該任務的運行時間。在處理“活”的時候，runtime時間會不斷的消耗；如果runtime使用完畢，該任務會被DL調度器調度出局。在這種情況下，該任務無法再次占有CPU資源，只能等到下一次周期到來的時候，runtime重新補充之后才能運行。因此，CBS一方面可以用來保證每個任務的CPU時間按照其定義的runtime參數來分配，另外一方面，CBS也保證任務不會占有超過其runtime的CPU資源，從而防止了DL任務之間的互相影響。

為了避免DL任務造成系統超負荷運行，DL調度器有一個準入機制，在任務配置好了period、runtime和deadline參數之后并準備加入到系統的時候，DL調度器會對該任務進行評估。這個準入機制保證了DL任務將不會使用超過系統的CPU時間的最大值。這個最大值在kernel.sched_rt_runtime_us和kernel.sched_rt_period_us sysctl參數中指定。默認值是950000和1000000，表示在1s的周期內，CPU用于執行實時任務（DL任務和RT任務）的最大時間值是950000μs。對于單個核心系統，這個測試既是必要的，也是充分的。這意味著：既然接受了該DL任務，那么CPU有信心可以保證其在截止日期之前能夠分配給它需要的runtime長度的CPU時間。

然而，值得注意的是，準入測試對于多處理器系統的全局調度算法是必要的，但不是充分的。Dhall效應（在Deadline調度器之原理部分描述）說明了全局deadline調度器即便是接受了該任務，但是在每個CPU利用率未達100％的情況下（有可分配的CPU資源），也不能保證能該DL任務的deadline的需求得到滿足。因此，在多處理器系統中，準入測試并不保證一旦接受，任務將能夠在截止日期之前分配并使用其指定的運行時間。對于被接受的DL任務而言，調度器最多能做到的是“有界延遲“，對于軟實時系統而言，這已經是一個不錯的保證了。如果用戶希望保證所有任務都能滿足他們的最后期限，用戶就必須使用分區方法（即使用partitioned scheduler），或者使用下面的準入測試（是必要且充分的）：

把上面的公式用一句話表示就是：每個任務的（運行時間/周期）的總和應該小于或等于處理器的數目M，減去最大的利用率Umax乘以（M-1）。Umax是所有DL任務中，（運行時間/周期）值最大的那個（即對CPU資源需求最大）。事實證明，在低負荷情況下（即Umax比較?。?，系統容易進行調度處理。

對于那些cpu利用率很高的任務而言，一個很好的策略是將系統進行區域劃分。即將一些高負載任務隔離開來，從而使“小活”（cpu使用率不高）和“大活”各自在一組不同的CPU上進行調度。目前，DL調度器不允許用戶設置一個線程的親和性，不過可以使用control group cpusets來對系統進行分區。

三、使用方法

例如，考慮一個有八個CPU的系統。一個“大活”的CPU利用率接近90%（單核場景下），而組內其他任務的利用率都較低。在這種場景下，一個推薦的設置是這樣的：CPU0運行CPU利用率高的那個“大活”任務，讓其他任務運行在其余的CPU上。要想實現這樣的系統配置，用戶可以執行以下步驟：

首先進入cpuset目錄，創建兩個cpuset，然后執行下面的命令：

上面的操作在root cpuset中disable了負載均衡，從而讓新創建的cluster和partition這兩個cpuset變成root domain。下面我們將對cluster進行配置，具體操作如下：

上面的操作設定了cluster中的任務可以使用1～7這些系統中的CPU，cpuset.mems那一行操作和memory node相關（即設定該cpuset可以使用的memory node），如果系統不是NUMA的話，echo 0就OK了。cpuset.cpu_exclusive 是配置cpuset.cpus中的cpu們是否是該cpuset獨占的cpu。在這個場景中，CPU 1~7只是分配給cluster這個cpu set，因此是獨占的。OK，現在需要把各個task加入到該cluster這個cpu set中了，具體操作如下：

上面的命令把系統中所有的LWP加入到cluster cpuset中。下面我們開始配置partition cpuset：

這里的配置過程和配置cluster的過程是一樣的，這里就不再具體解釋了?，F在我們需要把shell移到partition這個cpuset中，操作命令如下：

完成上面的準備工作之后，最后一步就是在shell中啟動deadline任務。

四、程序員視角

我們在這一章討論使用DL調度器的場景。我們提供了三個例子：

（1）固定占有CPU資源的服務器程序

（2）按照固定的周期重新分配CPU資源的任務

（3）等待外部事件的服務器程序（外部事件可以周期性的，也可以使sporadic形態的）

周期是DL調度中最基本的參數，它定義了一個任務是以什么樣子的頻繁程度被激活。當一個任務沒有固定的激活模式時，也可以使用DL調度器，但是這時候往往是僅僅使用其CBS特性。

我們首先舉一個僅僅使用DL調度器CBS特性的例子。假設一個task，沒有固定pattern，但是我們不想讓它占用太多的CPU資源，僅僅是想讓它最多占有20％的CPU資源。這時候，我們可以設定周期為1S，runtime是200ms，sched_setattr() 接口函數可以用來設定DL調度參數，具體的實現可以參考下面的代碼：

在非周期性（aperiodic ）的情況下，任務不需要知道周期何時開始，它只管運行就好了，反正在該任務消耗完指定的運行時間之后，DL調度器會對其進行節流（throttle ）。這種場景下，應用程序沒有deadline的需求（deadline等于period），僅僅使用CBS特性。

我們再來一個DL調度器應用場景的例子：這次是一個有固定激活模式的任務，即該任務會在固定的時間間隔上醒來，進行事務處理，而該任務處理完之后就睡眠，直到下一個周期到來。這時候在新的周期中，runtime會重新恢復，該任務會再次被DL調度器調度，然后周而復始。具體的代碼和上一段代碼類似，只是具體計算部分的代碼如下：

具體的調度參數和上一個代碼示例是一樣的（即事件到來的周期是1S），雖然給出了200ms的runtime設定，但是實際上的處理不會超過200ms，一旦處理完事件，程序會調用sched_yield告知DL調度器：我已經處理完事件了，到下一個周期再給我分配資源吧，我沒有什么事情需要處理了。順便說一句，處理時間超過200ms是沒有意義的，這時候CBS會throttle該任務。還有一個比較有意思的知識點就是DL調度器對yield的處理和CFS調度器不一樣，DL task yield之后會阻塞該進程，直到下一個調度周期到來。

上面的例子有點類似定時任務，即每個固定的時間間隔就起來處理一些日常性事務，不過真實的實時進程往往是外部事件驅動的具體代碼如下（DL參數是一樣的）：

在這個場景下，該任務是阻塞在系統調用中。當外部事件發生的時候，該任務被喚醒。外部事件并不是以嚴格的周期來喚醒該任務，但是會有一個最小的周期，也就是說這是一個sporadic task。一旦任務被激活，它將執行計算并提供響應，當該任務完成計算，提供了輸出，它將由于等待下一個事件而進入休眠狀態。

五、結論

deadline調度器是僅僅根據實時任務的時序約束進行調度的，從而保證實時任務正確的邏輯行為。雖然在多核系統中，全局deadline調度器會面臨Dhall效應，不過我們仍然可以對系統進行分區來解決這個問題。具體的做法是采用cpusets的方法把CPU利用率高的任務放置到指定的cpuset上。開發人員也可以受益于deadline調度器：他們可以通過設計其應用程序與DL調度器交互，從而簡化任務的時序控制行為。

在linux中，DL任務比實時任務（RR和FIFO）具有更高的優先級。這意味著即使是最高優先級的實時任務也會被DL任務延遲執行。因此，DL任務不需要考慮來自實時任務的干擾，但實時任務必須考慮DL任務的干擾。

DL調度器和PREEMPT_RT補丁在改善Linux實時性方面發揮著不同的作用。DL調度器讓任務的調度以一種更可預測的方式進行，而PREEMPT_RT補丁集的目標是減少和限制較低優先級的任務對實時任務的調度延遲。具體的做法是通過減少下列內核中的不可搶占時間來完成的：（1）關閉搶占（2）disable IRQ（3）低優先級任務持鎖。

例如，當一個實時任務運行在非實時內核上的時候，從該任務被喚醒到真正調度執行可能會有高達5ms的調度延遲。在這樣的系統中，內核是無法處理deadline小于5ms的任務。相反，在實時內核的情況下，調度延遲可能不會超過150μs。這時候，那些更短的deadline的任務（例如小于5ms）也能被輕松處理。