一、概述

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

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

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

實(shí)時(shí)任務(wù)和非實(shí)時(shí)任務(wù)（或者普通任務(wù)）的區(qū)別是什么？實(shí)時(shí)任務(wù)有deadline，超過deadline，將不能產(chǎn)生正確的邏輯結(jié)果，非實(shí)時(shí)任務(wù)則沒有這個(gè)限制。為了滿足實(shí)時(shí)任務(wù)的調(diào)度需求，Linux提供了兩種實(shí)時(shí)調(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ù)的實(shí)時(shí)優(yōu)先級(jí)（Linux進(jìn)程描述符中的rt_priority成員）進(jìn)行調(diào)度。最高優(yōu)先級(jí)的任務(wù)將最先獲得CPU資源。在實(shí)時(shí)理論中，這種調(diào)度器被歸類為固定優(yōu)先級(jí)調(diào)度器（fixed-priority scheduler，即每一個(gè)rt任務(wù)都固定分配一個(gè)優(yōu)先級(jí)）。當(dāng)實(shí)時(shí)優(yōu)先級(jí)不同的時(shí)候，F(xiàn)IFO和RR沒有什么不同，只有在兩個(gè)任務(wù)具有相同優(yōu)先級(jí)的時(shí)候，我們才可以看出FIFO和RR之間的區(qū)別。對(duì)于FIFO調(diào)度器，最先進(jìn)入runnable狀態(tài)的任務(wù)將首先獲取CPU資源，并且一直占用該資源，直到該進(jìn)程進(jìn)入睡眠狀態(tài)。而對(duì)于RR調(diào)度器，具有相同優(yōu)先級(jí)的任務(wù)將以輪流執(zhí)行的方式共享處理器資源。當(dāng)某個(gè)RR任務(wù)開始運(yùn)行后，如果該任務(wù)不會(huì)阻塞，那么它將一直運(yùn)行，直到分配給該任務(wù)的時(shí)間片到期。當(dāng)時(shí)間片用完，調(diào)度器將把該任務(wù)放在任務(wù)鏈表的末端（注意，只有相同優(yōu)先級(jí)的任務(wù)才會(huì)放到一個(gè)鏈表中，不同優(yōu)先級(jí)在不同的鏈表中），并從任務(wù)鏈表中選擇下一個(gè)任務(wù)去執(zhí)行。

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

chrt -f 10 video_processing_tool

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

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

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

最后我們來說說Deadline參數(shù)。在一個(gè)實(shí)時(shí)任務(wù)的工作周期內(nèi)，deadline定義了處理完成的結(jié)果必須被交付的最后期限。我們還是以上面的視頻處理任務(wù)為例，在一個(gè)視頻幀的處理周期中（16ms），如果該任務(wù)需要在該周期的前10毫秒內(nèi)把處理過的視頻幀傳送給下一個(gè)模塊，那么deadline參數(shù)就是10毫秒。為了達(dá)到這個(gè)要求，顯然在該周期的前10ms就必須完成一幀數(shù)據(jù)的處理，即5ms的runtime必須位于該周期的前10ms時(shí)間范圍內(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”是將運(yùn)行時(shí)間參數(shù)設(shè)定為5ms，“--sched-deadline 10000000”是將deadline設(shè)定為10ms，“--sched-period 16666666”則是設(shè)定周期參數(shù)。命令行中的“0”是優(yōu)先級(jí)占位符，DL調(diào)度器并不使用優(yōu)先級(jí)參數(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 * 1000/1000 = 4

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

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

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

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

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