深入探討Linux的進(jìn)程調(diào)度器

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

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

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

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

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

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

DEADLINE調(diào)度器

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

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

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

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

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

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

RT調(diào)度器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

?可點(diǎn)擊進(jìn)入望獲實(shí)時(shí)Linux官網(wǎng)試用：

https://www.onewos.com/

參考文獻(xiàn)

[1] Digging into the Linux scheduler

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

審核編輯 黃宇