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

一、前言

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

二、細節(jié)

DL調度器是根據任務的deadline來確定調度的優(yōu)先順序的：deadline最早到來的那個任務最先調度執(zhí)行。對于有M個處理器的系統(tǒng)，優(yōu)先級最高的前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任務造成系統(tǒng)超負荷運行，DL調度器有一個準入機制，在任務配置好了period、runtime和deadline參數之后并準備加入到系統(tǒng)的時候，DL調度器會對該任務進行評估。這個準入機制保證了DL任務將不會使用超過系統(tǒng)的CPU時間的最大值。這個最大值在kernel.sched_rt_runtime_us和kernel.sched_rt_period_us sysctl參數中指定。默認值是950000和1000000，表示在1s的周期內，CPU用于執(zhí)行實時任務（DL任務和RT任務）的最大時間值是950000μs。對于單個核心系統(tǒng)，這個測試既是必要的，也是充分的。這意味著：既然接受了該DL任務，那么CPU有信心可以保證其在截止日期之前能夠分配給它需要的runtime長度的CPU時間。

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

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

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

三、使用方法

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

首先進入cpuset目錄，創(chuàng)建兩個cpuset，然后執(zhí)行下面的命令：

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

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

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

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

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

四、程序員視角

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

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

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

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

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

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

在非周期性（aperiodic ）的情況下，任務不需要知道周期何時開始，它只管運行就好了，反正在該任務消耗完指定的運行時間之后，DL調度器會對其進行節(jié)流（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參數是一樣的）：

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

五、結論

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

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

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

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