一、前言

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

二、細(xì)節(jié)

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

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

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

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

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

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

三、使用方法

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

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

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

上面的操作設(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獨(dú)占的cpu。在這個(gè)場景中，CPU 1~7只是分配給cluster這個(gè)cpu set，因此是獨(dú)占的。OK，現(xiàn)在需要把各個(gè)task加入到該cluster這個(gè)cpu set中了，具體操作如下：

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

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

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

四、程序員視角

我們?cè)谶@一章討論使用DL調(diào)度器的場景。我們提供了三個(gè)例子：

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

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

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

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

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

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

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

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

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

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

五、結(jié)論

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

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

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

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