Linux操作系統(tǒng)作為一個開源且廣泛應(yīng)用的操作系統(tǒng)，其內(nèi)核設(shè)計包含了許多核心功能，而進程調(diào)度器（Scheduler）就是其中一個至關(guān)重要的模塊。進程調(diào)度器負責(zé)決定在任何給定的時刻哪個進程可以運行，以及其運行的順序。這篇文章將詳細探討Linux進程調(diào)度器的工作原理、主要算法、調(diào)度策略以及其在實際操作中的應(yīng)用。

進程調(diào)度是指操作系統(tǒng)決定在多道程序環(huán)境下如何分配CPU時間給多個進程或線程的過程。在一個現(xiàn)代操作系統(tǒng)中，通常有多個進程或線程需要執(zhí)行，但是CPU的核心數(shù)量有限，因此需要通過調(diào)度來合理分配這些有限的計算資源。Linux進程調(diào)度的目標(biāo)包括以下幾個方面：

響應(yīng)時間：保證交互式進程有良好的響應(yīng)時間。
吞吐量：盡可能多地完成任務(wù)，提高系統(tǒng)的整體吞吐量。
公平性：確保所有進程都有機會獲得CPU時間，避免饑餓現(xiàn)象。
實時性：對于實時系統(tǒng)，調(diào)度器應(yīng)能確保實時任務(wù)在其時間約束內(nèi)完成。

為達到以上目標(biāo)，Linux按照調(diào)度的優(yōu)先級，分別實現(xiàn)了DEADLINE調(diào)度策略、實時（RT）調(diào)度策略、完全公平調(diào)度策略等。

圖1 Linux調(diào)度策略的優(yōu)先次序

如圖1所示[1]，Linux在調(diào)度過程中首先嘗試在最高級別的策略模塊中尋找調(diào)度實體（即進程），如果沒找到，則到下一級的策略模塊中尋找，如果都沒找到，則進入idle狀態(tài)。例如，Linux內(nèi)核如果在DEADLINE策略模塊中找到了調(diào)度實體，就會在處理器上調(diào)度運行該實體，而不會繼續(xù)到RT調(diào)度策略模塊中尋找。接下來分節(jié)介紹Linux中最常用的DEADLINE、RT以及完全公平調(diào)度策略模塊，又稱調(diào)度器。

DEADLINE調(diào)度器

Linux內(nèi)核中的DEADLINE調(diào)度器是一種實時調(diào)度策略，旨在滿足具有嚴(yán)格時間要求的實時任務(wù)的需求。它在設(shè)計上結(jié)合了EDF（Earliest Deadline First）和CBS（Constant Bandwidth Server）兩種經(jīng)典的實時調(diào)度算法，為實時應(yīng)用程序提供了更可靠和可預(yù)測的執(zhí)行環(huán)境。

Linux DEADLINE調(diào)度器是Linux內(nèi)核自3.14版本以來引入的調(diào)度策略，其目的是為實時任務(wù)提供精確的時間控制和調(diào)度保證。DEADLINE調(diào)度器通過為每個任務(wù)分配三個關(guān)鍵參數(shù)——開始時間（Start Time）、截止時間（Deadline）和運行時間（Runtime），來確定任務(wù)的執(zhí)行順序和調(diào)度行為。

調(diào)度器的目標(biāo)是在任務(wù)的截止時間到達之前，完成所有具有時間約束的任務(wù)。如果任務(wù)沒有在截止時間前完成，通常會被視為任務(wù)失敗或延遲，這在硬實時系統(tǒng)中是不可接受的。

DEADLINE調(diào)度器基于EDF（Earliest Deadline First）的思想，即在系統(tǒng)中，優(yōu)先選擇截止時間最早的任務(wù)執(zhí)行。此外，結(jié)合CBS（Constant Bandwidth Server）機制，DEADLINE調(diào)度器還能控制任務(wù)的CPU時間消耗，防止任務(wù)因超出分配的時間片而影響系統(tǒng)的整體實時性能。

Linux DEADLINE調(diào)度器的主要應(yīng)用場景是硬實時系統(tǒng)，如工業(yè)控制系統(tǒng)、機器人控制、航空航天等領(lǐng)域，這些系統(tǒng)對任務(wù)的時間精度要求非常高，任務(wù)的延遲或未按時完成會導(dǎo)致嚴(yán)重的后果。通過DEADLINE調(diào)度器，系統(tǒng)可以確保任務(wù)在其指定的截止時間內(nèi)完成。多媒體應(yīng)用，如音頻和視頻流處理，要求任務(wù)以固定的周期執(zhí)行，并在特定時間內(nèi)完成，以保證輸出的連續(xù)性和質(zhì)量。DEADLINE調(diào)度器可以幫助這些任務(wù)獲得所需的CPU時間，從而避免丟幀或音視頻不同步的問題。以及高精度定時任務(wù)，如在金融交易系統(tǒng)、科學(xué)計算、醫(yī)療設(shè)備等場景中，高精度的定時任務(wù)非常重要。DEADLINE調(diào)度器能夠確保這些任務(wù)按預(yù)定時間精確執(zhí)行，滿足系統(tǒng)的嚴(yán)格要求。

DEADLINE調(diào)度器的缺點是相比于普通調(diào)度器，DEADLINE調(diào)度器的配置參數(shù)較多，需要用戶對任務(wù)的時間需求有詳細了解，這對應(yīng)用開發(fā)者提出了更高的要求。另外，DEADLINE調(diào)度器需要系統(tǒng)有足夠的資源來滿足實時任務(wù)的要求，當(dāng)任務(wù)過多或系統(tǒng)資源有限時，可能會出現(xiàn)任務(wù)調(diào)度失敗的情況。最后，DEADLINE調(diào)度器缺乏彈性，在負載非常動態(tài)的系統(tǒng)中，DEADLINE調(diào)度器可能不如CFS等調(diào)度器靈活，因為它嚴(yán)格依賴于預(yù)先設(shè)定的時間參數(shù)。

RT調(diào)度器

RT調(diào)度器是Linux內(nèi)核中專門為實時任務(wù)設(shè)計的調(diào)度器，它為那些對延遲敏感的任務(wù)提供了更高的調(diào)度優(yōu)先級，以確保它們能夠在預(yù)定時間內(nèi)執(zhí)行。Linux中主要有兩種RT調(diào)度策略：SCHED_FIFO 和 SCHED_RR，它們都是基于優(yōu)先級的調(diào)度策略，與普通調(diào)度策略相比，RT調(diào)度策略提供了更嚴(yán)格的時間保證。

SCHED_FIFO（First In, First Out）：這是一個簡單的實時調(diào)度策略，任務(wù)按優(yōu)先級排序，優(yōu)先級相同的任務(wù)按到達順序執(zhí)行。SCHED_FIFO任務(wù)一旦獲得CPU資源，將持續(xù)運行，直到任務(wù)主動讓出CPU或被更高優(yōu)先級的任務(wù)搶占。沒有時間片的概念，這意味著低優(yōu)先級的任務(wù)可能會被高優(yōu)先級任務(wù)“餓死”。

SCHED_RR（Round-Robin）：SCHED_RR與SCHED_FIFO類似，但它在相同優(yōu)先級的任務(wù)之間實現(xiàn)了時間片輪轉(zhuǎn)。每個任務(wù)在獲得CPU時會運行一個時間片（默認(rèn)100ms），然后讓位給同一優(yōu)先級的下一個任務(wù)。這樣可以防止同一優(yōu)先級的任務(wù)發(fā)生饑餓現(xiàn)象。

RT調(diào)度器具有嚴(yán)格的優(yōu)先級控制，RT調(diào)度策略減少了調(diào)度延遲，保證了任務(wù)在規(guī)定時間內(nèi)獲得CPU資源。在需要高可靠性和時間精度的場景中，RT調(diào)度器提供了比普通調(diào)度器更高的穩(wěn)定性和可預(yù)測性。

RT調(diào)度器的缺點是高優(yōu)先級的RT任務(wù)可能長期占用CPU，導(dǎo)致低優(yōu)先級任務(wù)得不到執(zhí)行，甚至可能導(dǎo)致系統(tǒng)不響應(yīng)（例如，一個SCHED_FIFO任務(wù)如果沒有主動釋放CPU，系統(tǒng)將無法響應(yīng)其他任務(wù)）。另外RT調(diào)度器配置復(fù)雜，配置復(fù)雜：合理配置RT調(diào)度器的優(yōu)先級和時間片需要深入了解任務(wù)的時間需求，配置不當(dāng)可能導(dǎo)致系統(tǒng)不穩(wěn)定或性能下降。RT調(diào)度器對資源的占用較為剛性，在動態(tài)負載環(huán)境下可能表現(xiàn)不佳。

完全公平調(diào)度器

Linux內(nèi)核的完全公平調(diào)度器（Completely Fair Scheduler, CFS）是目前Linux系統(tǒng)中默認(rèn)的進程調(diào)度器，它旨在提供一個公平、可擴展且高效的調(diào)度機制。CFS調(diào)度器的設(shè)計理念是盡量公平地分配CPU時間，使得每個任務(wù)都能獲得與其優(yōu)先級相符的CPU時間份額。

在CFS中，公平的概念體現(xiàn)在所有任務(wù)都應(yīng)該在相同優(yōu)先級的情況下，獲得相等的CPU時間份額。CFS通過維護每個任務(wù)的“虛擬運行時間”來實現(xiàn)這一點。任務(wù)的虛擬運行時間越少，意味著它獲得的CPU時間越少，因此CFS會優(yōu)先調(diào)度虛擬運行時間較少的任務(wù)，以實現(xiàn)CPU時間的公平分配。

CFS使用紅黑樹（Red-Black Tree）數(shù)據(jù)結(jié)構(gòu)來管理所有可運行的任務(wù)。紅黑樹是一種自平衡二叉搜索樹，能夠在O(log N)時間內(nèi)插入、刪除和查找元素。CFS將所有任務(wù)按其虛擬運行時間排序存儲在紅黑樹中，每次調(diào)度時，選擇樹中最左邊（虛擬運行時間最少）的任務(wù)來運行。

最后，CFS調(diào)度器與cgroups（Control Groups）緊密結(jié)合，允許管理員對任務(wù)組設(shè)置CPU資源的配額。通過cgroups，系統(tǒng)管理員可以將進程劃分為不同的組，并為每個組分配CPU時間份額，從而實現(xiàn)更精細的資源控制。

圖2 Linux完全公平調(diào)度策略與Cgroup的進程組的結(jié)合

如圖2所示，與Cgroup結(jié)合后，Linux完全公平調(diào)度的實體，按照調(diào)度任務(wù)組形成了一個樹狀結(jié)構(gòu)。在進行調(diào)度實體選擇時，調(diào)度器首先從樹的根結(jié)點（與處理器直接對應(yīng)的調(diào)度組），逐層選取最佳調(diào)度實體，一直到葉子結(jié)點（與具體進程對應(yīng)）。

望獲自適應(yīng)調(diào)度器

最后簡單介紹一下，國科環(huán)宇在研的望獲自適應(yīng)調(diào)度器。該調(diào)度器針對Linux實時調(diào)度器配置和運行不夠靈活的缺點，對進程的行為進行在線分析，并利用機器學(xué)習(xí)的方法對進程的調(diào)度進行配置，以做到實時性和靈活性的兼顧。

?可點擊進入望獲實時Linux官網(wǎng)試用：

https://www.onewos.com/

參考文獻

[1] Digging into the Linux scheduler

http:// https://deepdives.medium.com/digging-into-linux-scheduler-47a32ad5a0a8

審核編輯 黃宇