Linux系統中的實時調度器DL調度器的原理是什么？詳細概述

一、概述

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

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

二、Linux系統中的實時調度器

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

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

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

chrt -f 10 video_processing_tool

通過上面的命令，video_processing_tool任務會歸于RT調度器管理，其實時優先級是10，調度策略是FIFO（-f參數）

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

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

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

通過chrt命令我們可以設定deadline調度參數，例如：上面的視頻任務可以這樣設定：

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

--sched-period 16666666 0 video_processing_tool

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

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

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

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

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

三、實時調度概述

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

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

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

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

我們舉一個實際的例子，假設系統中有三個周期性任務，參數如下（deadline等于period）：

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

對于這樣的一組實時任務，EDF調度器的調度行為如下圖所示：

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

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

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

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

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

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

（1）全局類（Global）：即一個調度器就可以管理系統中的所有CPU，任務可以在CPU之間自由遷移。

（2）集群類（Clustered）：系統中的CPU被分成互不相交的幾個cluster，調度器負責調度任務到cluster內的CPU上去。

（3）分區類（Partitioned ）：每個調度器只管自己的那個CPU，系統有多少個CPU就有多少個調度器實體。

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

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

4 * 1000/1000 = 4

調度的結果如下圖所示：

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

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

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

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