一、前言

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

二、細節(jié)

DL調(diào)度器是根據(jù)任務(wù)的deadline來確定調(diào)度的優(yōu)先順序的：deadline最早到來的那個任務(wù)最先調(diào)度執(zhí)行。對于有M個處理器的系統(tǒng)，優(yōu)先級最高的前M個deadline任務(wù)（即deadline最早到來的前M個任務(wù)）將被選擇在對應(yīng)M個處理器上運行。

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

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

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

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

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

三、使用方法

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

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

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

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

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

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

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

四、程序員視角

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

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

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

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

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

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

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

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

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

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

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

五、結(jié)論

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

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

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

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