一、概述

實時系統(tǒng)是這樣的一種計算系統(tǒng)：當事件發(fā)生后，它必須在確定的時間范圍內(nèi)做出響應(yīng)。在實時系統(tǒng)中，產(chǎn)生正確的結(jié)果不僅依賴于系統(tǒng)正確的邏輯動作，而且依賴于邏輯動作的時序。換句話說，當系統(tǒng)收到某個請求，會做出相應(yīng)的動作以響應(yīng)該請求，想要保證正確地響應(yīng)該請求，一方面邏輯結(jié)果要正確，更重要的是需要在最后期限（deadline）內(nèi)作出響應(yīng)。如果系統(tǒng)未能在最后期限內(nèi)進行響應(yīng)，那么該系統(tǒng)就會產(chǎn)生錯誤或者缺陷。在多任務(wù)操作系統(tǒng)中（如Linux），實時調(diào)度器（realtime scheduler）負責協(xié)調(diào)實時任務(wù)對CPU的訪問，以確保系統(tǒng)中的所有的實時任務(wù)在其deadline內(nèi)完成。

如果對實時任務(wù)進行抽象，那么它需要三個元素：周期（period），運行時間（runtime）和最后期限（deadline）。Deadline調(diào)度器正是利用了這一點（指對實時任務(wù)完美的抽象），允許用戶來指定該任務(wù)的具體需求，從而使系統(tǒng)能夠做出最好的調(diào)度決策，即使在負載很高的系統(tǒng)中也能保證實時任務(wù)的調(diào)度。

二、Linux系統(tǒng)中的實時調(diào)度器

實時任務(wù)和非實時任務(wù)（或者普通任務(wù)）的區(qū)別是什么？實時任務(wù)有deadline，超過deadline，將不能產(chǎn)生正確的邏輯結(jié)果，非實時任務(wù)則沒有這個限制。為了滿足實時任務(wù)的調(diào)度需求，Linux提供了兩種實時調(diào)度器：POSIX realtime scheduler（后文簡稱RT調(diào)度器）和deadline scheduler（后文簡稱DL調(diào)度器）。

RT調(diào)度器有兩種調(diào)度策略：FIFO（first-in-first-out）和RR（round-robin）。無論FIFO還是RR，RT調(diào)度器都是根據(jù)任務(wù)的實時優(yōu)先級（Linux進程描述符中的rt_priority成員）進行調(diào)度。最高優(yōu)先級的任務(wù)將最先獲得CPU資源。在實時理論中，這種調(diào)度器被歸類為固定優(yōu)先級調(diào)度器（fixed-priority scheduler，即每一個rt任務(wù)都固定分配一個優(yōu)先級）。當實時優(yōu)先級不同的時候，F(xiàn)IFO和RR沒有什么不同，只有在兩個任務(wù)具有相同優(yōu)先級的時候，我們才可以看出FIFO和RR之間的區(qū)別。對于FIFO調(diào)度器，最先進入runnable狀態(tài)的任務(wù)將首先獲取CPU資源，并且一直占用該資源，直到該進程進入睡眠狀態(tài)。而對于RR調(diào)度器，具有相同優(yōu)先級的任務(wù)將以輪流執(zhí)行的方式共享處理器資源。當某個RR任務(wù)開始運行后，如果該任務(wù)不會阻塞，那么它將一直運行，直到分配給該任務(wù)的時間片到期。當時間片用完，調(diào)度器將把該任務(wù)放在任務(wù)鏈表的末端（注意，只有相同優(yōu)先級的任務(wù)才會放到一個鏈表中，不同優(yōu)先級在不同的鏈表中），并從任務(wù)鏈表中選擇下一個任務(wù)去執(zhí)行。

和RT調(diào)度器不同，DL調(diào)度器是按照任務(wù)的deadline進行調(diào)度的（從名字也看的出來，哈哈）。當產(chǎn)生一個調(diào)度點的時候，DL調(diào)度器總是選擇其Deadline距離當前時間點最近的那個任務(wù)并調(diào)度它執(zhí)行。調(diào)度器總是根據(jù)任務(wù)的配置參數(shù)進行調(diào)度，對于RT調(diào)度器而言，用戶需要配置任務(wù)的調(diào)度策略（FIFO或者RR）和那個固定的實時優(yōu)先級。例如：

chrt -f 10 video_processing_tool

通過上面的命令，video_processing_tool任務(wù)會歸于RT調(diào)度器管理，其實時優(yōu)先級是10，調(diào)度策略是FIFO（-f參數(shù)）

對于DL調(diào)度器，用戶需要設(shè)定三個參數(shù)：周期（period）、運行時間（runtime）和最后期限（deadline）。周期和該實時任務(wù)的工作模式相關(guān)。例如：對于一個視頻處理任務(wù)，它的主要的工作是每秒鐘處理60幀的視頻數(shù)據(jù)，即每16毫秒需要處理每一幀視頻，因此，該任務(wù)的周期就是16ms。

對于實時任務(wù)，一個周期內(nèi)總是有固定的“工作”要做，例如在視頻任務(wù)中，所謂的工作就是對一幀視頻數(shù)據(jù)進行處理，Runtime是完成這些“工作”需要的CPU執(zhí)行時間，即在一個周期中，需要CPU參與運算的時間值。在設(shè)定運行時間參數(shù)的時候我們不能太樂觀，runtime在設(shè)定的時候必須考慮最壞情況下的執(zhí)行時間（worst-case execution time ，WCET）。例如，在視頻處理中，各個幀的情況可能不太一樣（一方面幀間的相關(guān)性不同，另外，即便是針對一幀數(shù)據(jù)，其圖像像素之間的相關(guān)性也不同），有些會耗時長一些，有些會短一些。如果處理時間最長的那幀視頻需要5毫秒來處理，那么它的runtime設(shè)定就是五毫秒。

最后我們來說說Deadline參數(shù)。在一個實時任務(wù)的工作周期內(nèi)，deadline定義了處理完成的結(jié)果必須被交付的最后期限。我們還是以上面的視頻處理任務(wù)為例，在一個視頻幀的處理周期中（16ms），如果該任務(wù)需要在該周期的前10毫秒內(nèi)把處理過的視頻幀傳送給下一個模塊，那么deadline參數(shù)就是10毫秒。為了達到這個要求，顯然在該周期的前10ms就必須完成一幀數(shù)據(jù)的處理，即5ms的runtime必須位于該周期的前10ms時間范圍內(nèi)。

通過chrt命令我們可以設(shè)定deadline調(diào)度參數(shù)，例如：上面的視頻任務(wù)可以這樣設(shè)定：

chrt -d --sched-runtime 5000000 --sched-deadline 10000000 \

--sched-period 16666666 0 video_processing_tool

其中“-d”參數(shù)說明設(shè)定的調(diào)度策略是deadline，“--sched-runtime 5000000”是將運行時間參數(shù)設(shè)定為5ms，“--sched-deadline 10000000”是將deadline設(shè)定為10ms，“--sched-period 16666666”則是設(shè)定周期參數(shù)。命令行中的“0”是優(yōu)先級占位符，DL調(diào)度器并不使用優(yōu)先級參數(shù)。

通過上面的設(shè)定，我們可以確保每16ms的周期內(nèi)，DL調(diào)度器會分配給該任務(wù)5ms的CPU運行時間，而且這個5ms的CPU時間會保證在10ms內(nèi)的deadline之前配備給該任務(wù)，以便該任務(wù)完成處理并交付給下一個任務(wù)或者軟件模塊。

Deadline的參數(shù)看似復雜，其實簡單，因為只要知道了task的行為，就可以推斷出其調(diào)度參數(shù)并進行設(shè)定。也就是說deadline任務(wù)的調(diào)度參數(shù)只和自己相關(guān)，和系統(tǒng)無關(guān)。RT task則不然，它需要綜合整個系統(tǒng)來看，把適合的rt priority配置給系統(tǒng)中的各個rt task，以確保整個系統(tǒng)能正常的運作（即在deadline之前，完成各個rt task的調(diào)度執(zhí)行）。

由于deadline任務(wù)明確的告知了調(diào)度器自己對CPU資源的需求，因此，當一個新的deadline task被創(chuàng)建，進入系統(tǒng)的時候，DL調(diào)度器可以知道CPU是否可以承擔這個新創(chuàng)建的DL task。如果系統(tǒng)比較空閑（DL任務(wù)不多），那么可以該task進入調(diào)度，如果系統(tǒng)DL任務(wù)已經(jīng)很多，新加入的DL任務(wù)已經(jīng)導致CPU利用率超過100％，那么DL調(diào)度器會將其拒之門外。一旦DL任務(wù)被接納，那么DL調(diào)度器則可以確保該DL task可以按照其調(diào)度參數(shù)的要求正確的執(zhí)行。

為了進一步討論DL調(diào)度器的好處，我們有必要后退一步，看看實時調(diào)度的藍圖。因此，下一節(jié)我們將描述一些實時調(diào)度的理論知識。

三、實時調(diào)度概述

在調(diào)度理論中，怎么來評估實時調(diào)度器的性能呢？具體的方法就是創(chuàng)建一組實時任務(wù)（后文稱之實時任務(wù)集）讓調(diào)度器來調(diào)度執(zhí)行，看看是否能夠完美的調(diào)度任務(wù)集中的所有任務(wù)，即所有實時任務(wù)的時間要求（deadline）都可以得到滿足。為了能夠在確定的時間內(nèi)響應(yīng)請求，實時任務(wù)必須在確定的時間點內(nèi)完成某些動作。為此，我們需要對實時任務(wù)進行抽象，總結(jié)出其任務(wù)模型來描述這些動作確定性的時序。

每個實時任務(wù)都有N個不斷重復的“工作”（job）組成，如果一個rt task所進行的工作總是在固定的時間間隔內(nèi)到來，那么我們成該任務(wù)是周期性的（Periodic）。例如一個音頻處理程序每隔20ms就會對一幀音頻數(shù)據(jù)進行壓縮。任務(wù)也可以是零散到來的（sporadic），sporadic task類似periodic task，只不過對周期要求沒有那么嚴格。對于sporadic task而言，它只定義了一個最小的時間間隔。假如這個最小時間間隔是20ms，那么job可能在距離上一次20ms后到來，也可能30ms到來，但是不會小于20ms。最后一種是非周期任務(wù)，沒有任何固定的模式。

上一段總結(jié)了實時任務(wù)的工作模式，下面我們看看deadline的分類。一個實時任務(wù)的Deadline有三種：第一種是隱含性的deadline（implicit deadline），即并不明確的定義deadline，其值等于period參數(shù)。這一種實時任務(wù)對時間要求相對比較低，只要在該周期內(nèi)分配了runtime的CPU資源即可。第二種是受限型deadline（constrained deadline），即deadline小于（或者等于）period參數(shù)，這種實時任務(wù)對時間的要求高一些，需要在周期結(jié)束之前的某個時間范圍內(nèi)分配CPU資源。最后一種是arbitrary deadline：即deadline和周期沒有關(guān)系。

根據(jù)抽象出來的任務(wù)模式，實時研究人員已經(jīng)開發(fā)出一種評估調(diào)度算法優(yōu)劣的方法：首先給定一組任務(wù)（包括了各種各樣前面描述的實時任務(wù)類型），讓被測試的調(diào)度器去調(diào)度這一組任務(wù)，以此來評估該調(diào)度器的調(diào)度能力。結(jié)果表明，在單處理器系統(tǒng)中，采用Early Deadline First（EDF）算法的調(diào)度器被認為是最佳的。之所以說它是最好的，言外之意就是當該調(diào)度器無法完成某個任務(wù)集調(diào)度的時候，其他調(diào)度器也無能為力。當在單處理器系統(tǒng)上調(diào)度periodic 和sporadic任務(wù)，并且deadline總是小于或等于周期參數(shù)（也就是constrained deadline）的時候，基于deadline參數(shù)進行調(diào)度的調(diào)度器性能優(yōu)異，表現(xiàn)最佳。實際上，對于那些deadline等于period參數(shù)（即implicit deadline）的periodic或者sporadic tasks，只要被調(diào)度的那組任務(wù)不使用超過100%的CPU時間，那么EDF調(diào)度器都可以正常的完成調(diào)度，滿足每一個rt task的deadline要求。Linux DL調(diào)度器實現(xiàn)了EDF算法。

我們舉一個實際的例子，假設(shè)系統(tǒng)中有三個周期性任務(wù)，參數(shù)如下（deadline等于period）：

這三個任務(wù)對 CPU時間的利用率還沒有達到100％：CPU利用率 = 1/4 + 2/6 + 3/8 = 23/24

對于這樣的一組實時任務(wù)，EDF調(diào)度器的調(diào)度行為如下圖所示：

通過上圖可知3個rt任務(wù)都很好的被調(diào)度，滿足了各自的deadline需求。如果使用固定優(yōu)先級的調(diào)度器（例如Linux內(nèi)核中的FIFO）會怎樣呢？其實不管如何調(diào)整各個rt task的優(yōu)先級，都不能很好的滿足每個任務(wù)的deadline要求，總會有一個任務(wù)的Job會在deadline之后完成，具體參考下面的圖片：

基于deadline的調(diào)度算法最大的好處是：一旦知道了一個實時任務(wù)集中每個任務(wù)的調(diào)度參數(shù)，其實根本不需要分析其他任務(wù)，你也能知道該實時任務(wù)集是否能在deadline之前完成。在單處理器系統(tǒng)，基于deadline進行調(diào)度所產(chǎn)生的上下文切換次數(shù)往往會比較少。此外，在保證每個任務(wù)都滿足其deadline需求的條件下，基于deadline的調(diào)度算法可以調(diào)度的任務(wù)數(shù)目比固定優(yōu)先級的調(diào)度算法要多。當然，基于deadline參數(shù)進行調(diào)度的調(diào)度器（后面簡稱deadline調(diào)度器）也有一些缺點。

deadline調(diào)度器雖然可以保證每個RT任務(wù)在deadline之前完成，但是并不能保證每一個任務(wù)的最小響應(yīng)時間。對于那些基于固定優(yōu)先級的進行調(diào)度的調(diào)度器（后文簡稱priority調(diào)度器），高優(yōu)先級的任務(wù)總是有最小的響應(yīng)延遲時間。EDF調(diào)度算法的priority調(diào)度算法要復雜一些。priority調(diào)度算法的復雜度可以是O（1）（例如Linux中的RT調(diào)度器），相比之下，deadline調(diào)度器的復雜度是O（log（n））（例如Linux中的DL調(diào)度器）。不過priority調(diào)度器需要為每一個task選擇一個最適合的優(yōu)先級，這個最優(yōu)優(yōu)先級的計算過程可能是離線的，這個算法的復雜度是O（N！）。

如果系統(tǒng)出于某種原因發(fā)生過載，例如由于新任務(wù)添加或錯誤的估計了WCET，這時候，deadline調(diào)度有可能會有一個多米諾效應(yīng)：當一個任務(wù)出現(xiàn)問題，影響的并非僅僅是該任務(wù)，這個問題會擴散到系統(tǒng)中的其他任務(wù)上去。我們考慮這樣的場景，由于運行時間超過了其runtime參數(shù)指定的時間，調(diào)度器在deadline之后才完成job，并交付給其他任務(wù)，這個issue很影響系統(tǒng)中所有其他的任務(wù)，從而導致其他任務(wù)也可能會錯過deadline，如紅下面的區(qū)域所示：

而對于那些基于固定優(yōu)先級的調(diào)度算法則相反，當一個任務(wù)出問題的時候，受影響的只是那個優(yōu)先級最低的task。（順便說一句：在linux中，DL調(diào)度器中實現(xiàn)了CBS，從而解決了多米諾效應(yīng)，下一篇文檔會詳述。）

在單核系統(tǒng)中，調(diào)度器只需要考慮任務(wù)執(zhí)行先后順序的問題，在多核系統(tǒng)中，除了任務(wù)先后問題，調(diào)度器還需要考慮CPU分配問題。也就是說，在多核系統(tǒng)中，調(diào)度器還需要決定任務(wù)在那個CPU上運行。一般來說，調(diào)度器可以被劃分為以下幾類：

（1）全局類（Global）：即一個調(diào)度器就可以管理系統(tǒng)中的所有CPU，任務(wù)可以在CPU之間自由遷移。

（2）集群類（Clustered）：系統(tǒng)中的CPU被分成互不相交的幾個cluster，調(diào)度器負責調(diào)度任務(wù)到cluster內(nèi)的CPU上去。

（3）分區(qū)類（Partitioned ）：每個調(diào)度器只管自己的那個CPU，系統(tǒng)有多少個CPU就有多少個調(diào)度器實體。

（4）任意類（Arbitrary ）：每一個任務(wù)都可以運行在任何一個CPU集合上。

對于partitioned deadline調(diào)度器而言，多核系統(tǒng)中的調(diào)度其實就被嚴格分解成一個個的單核deadline調(diào)度過程。也就是說，partitioned deadline調(diào)度器的性能是最優(yōu)的。不過，多核系統(tǒng)中的global、clustered和arbitrary deadline調(diào)度器并非最優(yōu)。例如，在一個有M個處理器的系統(tǒng)中，如果有M個runtime等于period參數(shù)的實時任務(wù)需要調(diào)度，調(diào)度器很容易處理，每個CPU處理一個任務(wù)即可。我們可以進一步具體化，假設(shè)有四個“大活”，runtime和period都是1000ms，一個擁有四個處理器的系統(tǒng)可以分別執(zhí)行這四個“大活”，在這樣的場景下，CPU利用率是400％：

4 * 1000/1000 = 4

調(diào)度的結(jié)果如下圖所示：

在這么重的負載下，調(diào)度器都能工作起來，每個“大活”的deadline都得到滿足。當系統(tǒng)的負載比較輕的情況下，我們直覺就認為調(diào)度器也應(yīng)該能hold住場面。下面我們構(gòu)造一個輕負載：調(diào)度器要面對的是4個“小活”和一個“大活”，“小活”的runtime是1ms，周期是999ms，“大活”同上。在這種場景下，系統(tǒng)的CPU利用率是100.4％：

4 * （1/999） + 1000/1000 = 1.004

1.004是遠遠小于4的，因此，我們直觀上感覺調(diào)度器是可以很好的調(diào)度這個“4小一大”的調(diào)度場景的。然而實時并非如此，單核上表現(xiàn)最優(yōu)的EDF調(diào)度器，在多核系統(tǒng)中會出現(xiàn)問題（指Global EDF調(diào)度器）。具體原因是這樣的：如果所有任務(wù)同時釋放，4個小活（deadline比較早）將會被調(diào)度在4個CPU上，這時候，“大活”只能在“小活”運行完畢之后才開始執(zhí)行，因此“大活”的deadline不能得到滿足。如下圖所示。這就是眾所周知的Dhall效應(yīng)（Dhall‘s effect）。

把若干個任務(wù)分配給若干個處理器執(zhí)行其實是一個NP-hard問題（本質(zhì)上是一個裝箱問題），由于各種異常場景，很難說一個調(diào)度算法會優(yōu)于任何其他的算法。有了這樣的背景知識，我們就可以進一步解析Linux內(nèi)核中的DL調(diào)度器的細節(jié)，看看它是如何避免潛在的問題，發(fā)揮其強大的調(diào)度能力的。欲知詳情，且聽下回分解。