探祕 Linux 進程調度器：操作系統的核心 “指揮官”

在操作系統的複雜世界裏，進程就如同一個個忙碌的 “小工人”，它們都渴望獲得 CPU 的 “青睞”，以執行自己的任務。而在這背後，有一位默默掌控全局的 “指揮官”，它就是 Linux 進程調度器。想象一下，當你在電腦上同時打開多個應用程序，一邊瀏覽網頁，一邊播放音樂，還在運行着辦公軟件，這些進程看似和諧共處，實則在激烈競爭着有限的 CPU 資源。

那麼，究竟是誰在有條不紊地安排它們的執行順序，讓整個系統能夠高效穩定地運行呢？沒錯，就是 Linux 進程調度器。今天，就讓我們一同走進這個神祕的領域，揭開 Linux 進程調度器的神祕面紗，看看它是如何在幕後指揮着這場進程 “交響樂” 的 。

一、進程調度簡介

進程調度是操作系統最重要的內容之一，也是學習操作系統的重點和難點。關於進程調度，我們首先就會問出一些問題，什麼是進程調度，爲什麼要進程調度，如何進行調度。下面我們用一幅圖把這些問題關聯起來：

這張圖把進程調度的所有問題和知識點都關聯了起來，本文後面所有的內容都是對這張圖的解釋和擴展延伸，下面讓我們來一一講解。

⑴什麼是調度

什麼是調度？調度是 CPU 資源管理器。操作系統的作用之一就是系統資源管理器。CPU 是計算機系統中最重要的資源，當然也要管理。所有進程的運行都需要 CPU，對 CPU 該如何管理呢？對於直接共享型的事物，我們有兩種管理方法：一種是時間分割管理，另一種是空間分割管理。由於 CPU 自身的特性，沒有空間分割相似性，只有時間分割相似性，所以我們只能對 CPU 進行時間分割管理。對 CPU 進行時間分割管理的具體做法就叫做進程調度。

那麼調度的是什麼呢？進程調度，調度的當然是進程啦，也對也不對。我們知道進程是資源分配的單位，線程是執行的單位。早期的時候沒有多線程，進程就是線程，線程就是進程，所以此時進程調度調度的是進程。但是當有了多線程之後，線程變成了執行的單位，進程不再是執行的單位，進程調度調度的就是線程了。不過由於歷史原因，大家都習慣叫進程調度，所以現在這個領域的名稱還是叫進程調度。後文中說到調度進程的地方都是調度的線程，由於習慣問題，我們還說調度進程不說調度線程，請大家要注意。

對線程的調度可以有兩種方式：一種是直接調度線程，不考慮它們所屬的進程，這種方式叫做直接調度或者一級調度；另一種是先調度進程，再在進程內部調度線程，這種方式叫做間接調度或者二級調度。POSIX 規定，操作系統可以選擇這兩種方式中的任何一種都行。Linux 選擇的是一級調度，爲什麼會這麼選擇呢？主要是爲了提高進程的併發性，充分利用多 CPU 多核的優勢。如果使用二級調度的話，看似每個進程之間都公平了，但是有些進程的計算量比較大，就無法通過多開線程提高自己的性能，這樣對系統整體的性能是有害的，也不利用發揮計算機多 CPU 的優勢。一級調度看似對有些進程不公平，但是計算量小的進程少開線程，計算量大的進程多開線程，相對還是很公平的。

就像國家希望每個企業都做大做強，但是同時也會反壟斷一樣。Linux 也推出了 cgroup 組調度機制，來限制某個或者某一類進程對 CPU 資源的過度佔用。本文中不講 cgroup 組調度機制，後文的講解都是假設沒有 cgroup 組調度。

⑵爲什麼要調度

我們知道了什麼是調度，那麼爲什麼要調度呢，沒有調度會怎麼樣呢？最早的計算機是沒有調度的，程序只能一個一個地運行，一個進程死亡之後才能去運行下一個進程。這裏面首先存在的問題就是我們沒法同時運行多個進程。其次就算我們不需要同時運行多個進程，程序在運行的過程中如果要等 IO，CPU 就只能空轉，這也十分浪費 CPU 資源。

於是最早的多任務——協作式多任務誕生了，當程序由於要等 IO 而阻塞時就會去調度執行其它的進程。但是協作式多任務存在着很大的問題，就是每個進程運行的時間片長短是不確定的，而且是很偶然很隨機的。如果一個進程它一直在做運算就是不進行 IO 操作，那麼它就會一直霸佔 CPU。

針對這個問題，當時想出的方法是道德解決方案。內核向進程提供系統調用 sched_yield，它會使進程主動放棄 CPU 讓其它進程來執行。然後要求所有的程序員在程序中合適的地方儘量多地加入 sched_yield 調用。這個方法在當時是管用的，因爲當時計算機的使用者 (同時也是程序員) 僅限於少數科研機構和政府機關的部分人員，一臺電腦的共同使用者都認識，面子上還得過得去。

後來隨着計算機的普及，以及計算機的使用者和程序員這兩個角色的分離，主要靠道德約束的協作式多任務已經行不通了，我們需要強制性多任務，也就是搶佔式多任務。搶佔式多任務使得每個進程都可以相對公平地平分 CPU 時間，如果一個進程運行了過長的時間就會被強制性地調度出去，不管這個進程是否願意。

有了搶佔式多任務，我們在宏觀上不僅可以同時運行多個進程，而且它們會一起齊頭並進地往前運行，不會出現某個進程被餓死的情況，這樣我們使用電腦的體驗就非常完美了。搶佔式多任務和協作式多任務不是對立的，它們是相互獨立的，可以同時存在於系統中。

搶佔又分爲用戶搶佔和內核搶佔。由於搶佔對進程來說是異步的，進程被搶佔時不一定運行在什麼地方，有可能運行在用戶空間，也有可能運行在內核空間 (進程通過系統調用進入內核空間)。如果搶佔點是在用戶空間，那麼搶佔就是安全的，如果在內核空間就不一定安全，這是爲什麼呢？因爲對於用戶空間來說，如果搶佔會導致線程同步問題，那麼用戶空間有責任使用線程同步機制來保護臨界區，只要用戶空間做好同步就不會出問題。

如果內核也做好了同步措施，內核搶佔也不會出問題，但是內核最初的設計就沒有考慮內核搶佔問題，所以剛開始的時候內核是不能搶佔的。後來內核開發者對內核進行了完善，把內核所有的臨界區都加上了同步措施，然後內核就是可搶佔的了。內核能搶佔了不代表內核一定會搶佔，內核會不會搶佔由 config 選項控制，可以開啓也可以關閉，因爲內核搶佔還會影響系統的響應性和性能。

開啓內核搶佔會提高系統的響應性但是會降低一點性能，關閉內核搶佔會降低系統的響應性但是會提高一點性能。因此把內核搶佔做成配置項，可以讓大家靈活配置。服務器系統一般不需要與用戶交互，所以會關閉內核搶佔來提高性能，桌面系統會開啓內核搶佔來提高系統的響應性，來增加用戶體驗。

現在我們再來看一下爲什麼要調度。因爲如果沒有調度的話，就不能實現多任務，一次就只能運行一個程序，我們使用電腦的體驗就會大大降低。有了調度就有了多任務，我們就能同時在電腦上做很多事情，使用體驗就會非常好。

⑶爲什麼能調度

我們再來看看爲什麼能調度呢。我們把協作式多任務叫做主動調度，搶佔式多任務叫做被動調度。爲什麼能調度分爲兩部分：爲什麼能觸發調度和爲什麼能執行調度。對於主動調度，調度是進程主動觸發的，這個是肯定能的。對於被動調度，在圖靈機模型中是做不到的，因爲圖靈機是一條線性一直往前走的，進程在執行時，進程要是不主動，是不可能跳到其它進程來執行的。

被動調度能做到的原因關鍵就在於中斷機制，因爲中斷是強行在正常的執行流中插入了一段代碼，它能改變後續代碼的走向。有了中斷機制，我們就可以創建一個定時器中斷，以固定的時間間隔比如每 10ms 來觸發中斷，檢測進程是否運行時間過長，如果過長就觸發調度。這樣任何進程都不可能霸佔 CPU，所以進程都能公平地共享 CPU 時間。

可以看到在純圖靈機模型中，進程如果不主動進行調度，是沒有外力強迫進程進行調度的，進程就能一直霸佔 CPU。有了中斷機制之後，在中斷的處理中可以觸發調度，在中斷返回的點可以執行調度，這樣就可以避免進程霸佔 CPU 了。

前面說的是爲何能觸發進程調度，主動調度是進程自己觸發的，被動調度是在中斷中觸發的。現在來看看爲何能執行調度，執行調度包括兩部分：選擇進程和切換進程。選擇進程是純軟件的，肯定能實現。切換進程是怎麼切換呢？一個進程執行得好好的，怎麼就切換了呢，需不需要硬件的支持呢？進程切換主要是切換執行棧和用戶空間，這兩個都需要用到 CPU 特定的指令。

⑷何時調度

我們前面已經講了主動調度 (協作式多任務) 和被動調度(搶佔式多任務)。

對於主動調度，觸發調度和執行調度是同步的、一體的，觸發即執行。主動調度發生的時機有 IO 等待、加鎖失敗等各種阻塞操作以及用戶空間主動調用 sched_yield。

對於被動調度，觸發調度和執行調度是異步的、分離的，觸發調度並不會立馬執行調度，而是做個需要調度的標記，然後在之後的某個合適的地方會檢測這個標記，如果被設置就進行調度。觸發調度的點有：在定時器中斷中發現當前進程超時了，在喚醒進程時發現新進程需要搶佔當前進程，在遷移進程時發現新進程需要搶佔當前進程，在改變進程優先級時發現新進程需要搶佔當前進程。

其中第一個觸發點是當前進程需要被搶佔，它是用來保證公平調度，防止進程霸佔 CPU 的，後三個觸發點是新進程需要搶佔當前進程，它是用來提高系統響應性的。執行調度的點有：系統調用完成之後即將返回用戶空間，中斷完成之後即將返回用戶空間，如果開啓了內核搶佔的話則還有, 中斷完成之後即將返回內核, 如果中斷髮生在禁止搶佔臨界區中，那麼中斷完成之後返回內核是不會執行調度的，而是會在臨界區結束的時候執行調度。

系統調用完成之後即將返回用戶空間和中斷完成之後即將返回用戶空間，是非常好的執行進行調度的點，也就是此圖中的三個箭頭的地方。CPU 異常在意義上不是系統調用，但是在形式上和邏輯上相當於是系統調用。

中斷髮生在內核空間的場景，如果開啓了內核搶佔，如果被搶佔的內核代碼不是在禁用搶佔臨界區，中斷返回時是執行調度的點。如果被搶佔的內核代碼在禁用搶佔臨界區中，在執行調度的點被推遲到了臨界區的出口處。

⑸如何調度

現在到了執行調度的時刻了。執行調度分爲兩步：一是選擇下一個要執行的進程，二是切換進程。選擇下一個要執行的進程，這就是調度算法了。首先調度算法只能從 Runnable 的進程中進行選擇，不能選擇 Blocked 進程，因爲選擇了也沒有意義。其次算法還要區分進程類型，比如普通進程與實時進程，肯定要優先選擇實時進程，在同一類型的進程中還要有具體的算法來決定到底選擇哪個進程。在 Linux 中一共把進程分爲了 5 類，每一類都有一個具體的算法。類之間的關係是優先選擇高類的進程，只有當高類沒有 Runnable 進程時纔會去選擇低類進程。

進程選擇好了之後就要切換進程了。切換進程分兩步：第一步是切換用戶空間，第二步是切換執行棧 (線程棧)。如果要切換的兩個線程屬於同一個進程就不需要切換用戶空間了。切換用戶空間是一個 CPU 架構相關的事情，在 x86 CPU 上是給 CR3 寄存器賦值新進程的頁表樹的根指針。

此時切換的執行棧是線程的內核棧，執行棧代表的是當前線程的執行情況，切換執行棧就是切換線程。線程的用戶棧信息都在內核棧裏保存着。切換完內核棧之後，線程繼續執行就會返回用戶空間，由於此時用戶空間已經切換完成，內核棧上也保存着用戶棧的信息，所以線程能返回到正確的用戶空間線程上去。下面我們畫個圖來看一下：

對於一個 CPU 來說，永遠只有一個當前進程在運行，當執行進程調度時，需要從其它進程中選擇一個進程，把它旋轉到最下方作爲當前進程，它就開始運行了。

⑹調度均衡

前面所說的都是針對一個 CPU 的情況，對於多個 CPU 來說，每個 CPU 也是這樣的邏輯。但是有一點不同的是，如果一個系統上的多個 CPU 忙的忙死閒的閒死，顯然不太好，因此多個 CPU 之間會進行調度均衡。調度均衡可以分爲個體均衡和總體均衡。個體均衡是從進程的角度出發選擇到一個相對清閒的 CPU 上去運行。總體均衡是從 CPU 的角度出發如何從別的 CPU 上拉取一些進程到自己這來執行，使得所有 CPU 的工作量儘量平均。

個體均衡的觸發點有三個：一是新進程剛創建時，二是進程要執行新程序時，三是進程被喚醒時，在這三個點進程都可以選擇去哪個 CPU 的運行隊列上去等待執行。在個體均衡下，每個進程都儘量選擇相對清閒的 CPU，所以所有 CPU 的負載應該還是會比較均衡的。但是時間長了可能還是會出現負載不均衡的情況，此時就要進行總體均衡了。總體均衡的觸發點有三個：一是 CPU 即將 idle 前會去找到最忙的 CPU 然後拉取一些任務過來；二是定時器中斷的週期性檢測，會檢查是否所有的 CPU 都一樣忙，如果忙閒差別太大就會進行進程遷移，使得所有 CPU 忙閒程度接近；三是在 idle 進程中如果 CPU 發現自己太忙而有的 CPU 在 idle 就會喚醒那個 CPU 進行負載均衡。

二、基礎概念解析

2.1 進程的定義與分類

在計算機系統中，進程堪稱最基礎且重要的概念之一。從本質上講，進程是程序在計算機中的一次動態執行過程。打個比方，當你在 Linux 系統中啓動一個應用程序，如文本編輯器，系統便會爲該程序創建一個進程，這個進程涵蓋了程序運行所需的各種資源，包括代碼、數據、打開的文件以及分配的內存空間等。

進程可以依據不同的標準進行分類。常見的分類方式有：按照對資源的需求特性，可分爲 I/O 受限型進程和 CPU 受限型進程 。I/O 受限型進程，正如其名，這類進程的執行過程中，大部分時間都在等待 I/O 操作的完成，例如讀取文件、網絡請求等，像瀏覽器在加載網頁時，就需要頻繁地進行網絡 I/O 操作，此時它就是一個典型的 I/O 受限型進程。而 CPU 受限型進程則主要將時間花費在 CPU 的計算上，像一些科學計算程序、加密算法程序等，它們需要大量的 CPU 計算資源來完成複雜的運算任務。

依據進程的實時性要求，進程又可分爲實時進程和普通進程 。實時進程對響應時間有着極高的要求，必須在規定的時間內完成任務，否則可能會導致嚴重的後果。以工業控制系統中的實時監控進程爲例，它需要實時採集傳感器的數據，並及時做出響應，以確保生產過程的安全和穩定。如果這個進程不能在規定時間內完成數據採集和處理，就可能引發生產事故。相比之下，普通進程對響應時間的要求相對寬鬆，它們可以在系統資源允許的情況下，逐步完成任務，如我們日常使用的文本編輯、文件下載等操作對應的進程。

2.2 進程狀態詳解

Linux 進程有多種狀態，常見的狀態包括：

進程狀態之間可以相互轉換。一般來說，進程可能從可執行狀態（R）進入睡眠狀態（S 或 D），當等待的事件發生時，又從睡眠狀態轉換回可執行狀態。如果進程收到暫停信號，會從可執行狀態轉換爲暫停狀態（T），收到繼續執行的信號後再轉換回可執行狀態。當進程完成任務後，會從可執行狀態轉換爲退出狀態（Z 或 X）。

三、常見調度策略

3.1 實時調度策略

實時調度策略對於那些對時間極爲敏感的任務而言，無疑是至關重要的保障。在 Linux 系統中，實時調度策略主要包含 DEADLINE、SCHED_FIFO 以及 SCHED_RR 這幾種類型 。

DEADLINE 調度策略，猶如一位精準的時間管家，它主要依據任務的截止時間來進行調度決策。每個任務在創建之初，都會被分配運行時（Runtime）、週期（Period）以及最後期限（Deadline）這三個關鍵參數。調度器會如同嚴格的監工，時刻緊盯任務的最後期限，優先調度那些截止時間最早的任務。舉例來說，在工業自動化生產線上，傳感器數據的實時採集與處理任務就對時間有着嚴苛的要求，DEADLINE 調度策略能夠確保這些任務在規定的時間內完成，從而保障生產線的穩定、高效運行。

Linux 實時進程採用 SCHED_FIFO 和 SCHED_RR 調度算法：

①SCHED_FIFO

特點：實現了一種簡單的、先入先出的調度算法，不使用時間片。處於可運行狀態的 SCHED_FIFO 級的進程會比任何 SCHED_NORMAL 級的進程都先得到調用。一旦一個 SCHED_FIFO 級進程處於可執行狀態，就會一直執行，直到它自己受阻塞或顯式地釋放處理器爲止。只有更高優先級的 SCHED_FIFO 或者 SCHED_RR 任務才能搶佔 SCHED_FIFO 任務。如果有兩個或者更多的同優先級的 SCHED_FIFO 級進程，它們會輪流執行，但是依然只有在它們願意讓出處理器時纔會退出。只要有 SCHED_FIFO 級進程在執行，其他級別較低的進程就只能等待它變爲不可運行態後纔有機會執行。

實時優先級的靜態特性影響：實時優先級只有靜態優先級，不會調整優先級，默認優先級爲 0 - 99（MAX_RT_PRIO = 100）。這意味着一旦確定了實時進程的優先級，在整個運行過程中它不會因爲其他因素而改變，保證了高優先級的實時進程能夠在需要時儘快得到執行。

②SCHED_RR

特點：與 SCHED_FIFO 大體相同，只是 SCHED_RR 級的進程在耗盡事先分配給它的時間後就不能再繼續執行了。也就是說，SCHED_RR 是帶有時間片的 SCHED_FIFO，是一種實時輪流調度算法。當 SCHED_RR 任務耗盡它的時間片時，在同一優先級的其他實時進程被輪流調度。時間片只用來重新調度同一優先級的進程。對於 SCHED_FIFO 進程，優先級總是立即搶佔低優先級，但低優先級進程決不能搶佔 SCHED_RR 任務，即使它的時間片耗盡。

實時優先級的靜態特性影響：同樣，由於實時優先級是靜態的，SCHED_RR 進程在確定了優先級後，其執行順序和時間片的分配都是基於這個固定的優先級。這使得系統在處理實時任務時能夠有明確的調度規則，確保關鍵任務能夠在規定的時間內得到執行。

3.2 完全公平調度策略（CFS）

完全公平調度策略（CFS）是 Linux 進程調度器的核心組成部分，其設計理念精妙絕倫，旨在爲系統中的每個進程都提供公平的 CPU 時間分配。

CFS 的核心思想建立在虛擬運行時間（vruntime）這一創新概念之上。簡單來講，虛擬運行時間是一個相對值，它用於衡量每個進程在 CPU 上的執行時間份額。每個進程都擁有一個屬於自己的 vruntime，其數值會隨着進程的運行而不斷增加。不過，這裏存在一個關鍵的區別，那就是不同優先級的進程，其 vruntime 的增加速度並不相同。具體而言，高優先級的進程，其 vruntime 的增長速度相對較慢；而低優先級的進程，vruntime 的增長速度則會更快。這就好比在一場比賽中，高優先級的選手被賦予了較慢的前進速度，而低優先級的選手則以較快的速度前進，這樣一來，最終的結果是所有選手在虛擬的時間賽道上能夠相對公平地競爭。

爲了更直觀地理解，我們不妨假設系統中有兩個進程 A 和 B，進程 A 的優先級較高，進程 B 的優先級較低。在開始時，它們的 vruntime 都爲 0。隨着時間的推移，進程 A 和 B 都開始運行。由於進程 A 的優先級高，它的 vruntime 增長速度較慢，假設在一段時間內，進程 A 的 vruntime 只增加了 1；而進程 B 由於優先級低，其 vruntime 增長速度較快，在相同的時間內，進程 B 的 vruntime 增加了 3。此時，調度器在進行調度決策時，會優先選擇 vruntime 值最小的進程，也就是進程 A。這樣，高優先級的進程 A 就能夠得到更多的 CPU 運行時間，同時，低優先級的進程 B 也不會被完全忽視，依然有機會在合適的時候運行。

在 CFS 的實現過程中，使用了紅黑樹這種高效的數據結構來管理所有進程。紅黑樹以 vruntime 作爲鍵值，將所有可運行的進程按照 vruntime 的大小進行排序。這樣，在每次進行調度時，調度器只需要從紅黑樹的最左端選取 vruntime 值最小的進程，即可實現高效、公平的調度。這種方式不僅保證了進程間的公平性，還能夠有效減少調度的開銷，提高系統的整體性能。

完全公平調度算法依賴於虛擬時鐘，用以度量等待進程在完全公平系統中所能得到的 CPU 時間。但數據結構中並沒有虛擬時鐘的表示，這是因爲虛擬時鐘可以通過實際時鐘，以及與每個進程相關的負荷權重計算出來；所有和虛擬時鐘相關的計算都在 update_curr 中進行的，該函數在系統中各個不同的地方調用。

 336 static void update_curr(struct cfs_rq *cfs_rq)
 337 {
 338     struct sched_entity *curr = cfs_rq->curr;
 339     u64 now = rq_of(cfs_rq)->clock;
 340     unsigned long delta_exec;
 341 
 342     if (unlikely(!curr))
 343         return;
 344 
 345     /*
 346      * Get the amount of time the current task was running
 347      * since the last time we changed load (this cannot
 348      * overflow on 32 bits):
 349      */
 350     delta_exec = (unsigned long)(now - curr->exec_start);
 351 
 352     __update_curr(cfs_rq, curr, delta_exec);
 353     curr->exec_start = now;
 354 
 355     if (entity_is_task(curr)) {
 356         struct task_struct *curtask = task_of(curr);
 357 
 358         cpuacct_charge(curtask, delta_exec);
 359     }
 360 }

339 rq_of(cfs_rq)->clock 用於實現就緒隊列自身的時鐘，每次調用週期性調度器時，都會更新 clock 的值。

350 curr->exec_start 保存了上次更改 load 時的時間，注意並不是進程的上一次運行時間。當前進程在一次運行過程中，可能會發生多次 update_curr。

__update_curr

 304 static inline void
 305 __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
 306           unsigned long delta_exec)
 307 {
 308     unsigned long delta_exec_weighted;
 309     u64 vruntime;
 310 
 311     schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
 312 
 313     curr->sum_exec_runtime += delta_exec;
 314     schedstat_add(cfs_rq, exec_clock, delta_exec);
 315     delta_exec_weighted = delta_exec;
 316     if (unlikely(curr->load.weight != NICE_0_LOAD)) {
 317         delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
 318                             &curr->load);
 319     }
 320     curr->vruntime += delta_exec_weighted;
 321 
 322     /*
 323      * maintain cfs_rq->min_vruntime to be a monotonic increasing
 324      * value tracking the leftmost vruntime in the tree.
 325      */
 326     if (first_fair(cfs_rq)) {
 327         vruntime = min_vruntime(curr->vruntime,
 328                 __pick_next_entity(cfs_rq)->vruntime);
 329     } else
 330         vruntime = curr->vruntime;
 331 
 332     cfs_rq->min_vruntime =
 333         max_vruntime(cfs_rq->min_vruntime, vruntime);
 334 }

在運行過程中，進程調度實體的 vruntime 是單調增加的，優先級越高的進程，增加的速度越慢，因此他們向右移動的速度也就越慢。這樣被調度的機會就越大。

延遲跟蹤：內核有一個固有的概念，稱之爲調度延遲，保證每個進程至少被運行一次的時間間隔。

sysctl_sched_latency：參數用來控制這個行爲，缺省定義爲 20ms，可以通過 / proc/sys/kernel/sched_latency_ns 來控制。

sched_nr_latency：控制在一個延遲週期內處理的最大活動數目。如果活動進程的數據超過了該上限，則延遲週期也成比例的線性擴展。

__sched_period：延遲週期的長度，通常就是 sysctl_sched_latency，但是如果有更多的進程正在運行，那麼其值要通過如下公式計算：

__sched_period = sysctl_sched_latency * nr_running / sched_nr_latency

在一個延遲週期內，通過考慮各個進程的權重，將延遲週期的時間在活動進程之間進行分配。對於有某個調度實體表示的給定進程，分配到的時間如下計算：

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running);
 
    slice *= se->load.weight;
    do_div(slice, cfs_rq->load.weight);
 
    return slice;
}

四、調度器的工作機制

4.1 進程優先級的確定

在 Linux 進程調度的複雜體系中，進程優先級的確定猶如精密儀器的校準，是保障系統高效、穩定運行的關鍵環節。這一過程並非簡單隨意，而是受到諸多因素的綜合影響，其中，Nice 值和 Priority 權重值起着核心作用。

Nice 值，作爲用戶可以對進程優先級進行調整的重要手段，其取值範圍在 - 20 到 19 之間 。這裏需要明確的是，數值越小，代表進程的優先級越高。例如，當一個進程的 Nice 值被設置爲 - 10 時，相較於 Nice 值爲 5 的進程，它在 CPU 資源競爭中會更具優勢，更有可能優先獲得 CPU 的執行時間。

通常情況下，普通用戶僅能將 Nice 值設置在 0 到 19 的區間內，這意味着普通用戶只能降低自己進程的優先級，以避免對系統中其他重要進程造成資源搶佔。而超級用戶則擁有更大的權限，能夠在 - 20 到 19 的全範圍內進行調整，從而根據系統的實際需求，靈活地爲特定進程賦予更高或更低的優先級。比如，在進行系統維護任務時，超級用戶可以將相關維護進程的 Nice 值設置爲較低數值，以確保這些任務能夠優先且高效地執行。

Priority 權重值，並非孤立存在，它與 Nice 值緊密關聯，共同影響着進程的優先級 。系統會依據一系列複雜的算法，結合 Nice 值以及其他諸如進程的資源使用情況、運行歷史等因素，來精確計算出每個進程的 Priority 權重值。這個權重值就如同進程在 CPU 資源分配 “賽場” 上的實力評估指標，權重值越高，進程在競爭 CPU 資源時的地位就越有利，能夠獲得的 CPU 時間份額也就越多。

例如，對於一個長時間運行且對系統性能至關重要的後臺服務進程，系統可能會根據其穩定的資源使用情況和重要性，爲其分配較高的 Priority 權重值，從而保證它在多進程環境中能夠持續、穩定地獲得足夠的 CPU 資源，以維持服務的高效運行。

Linux 提供兩種優先級：普通進程優先級和實時進程優先級。

⑴實時進程優先級：

實時優先級採用兩種調度算法：SCHED_FIFO（先入先出調度算法）和 SCHED_RR（時間片輪詢調度算法）。

實時優先級只有靜態優先級，不會調整優先級，默認優先級爲 0 - 99（MAX_RT_PRIO = 100）。nice 值隻影響 100 ~ 100 + 40 的進程優先級。

對於 SCHED_FIFO 算法，只有當進程執行完畢才能輪到其他進程執行；對於 SCHED_RR 算法，一旦時間片消耗完，則將該進程放到隊列末端，其他進程才能執行。

⑵普通進程優先級

普通優先級採用的調度算法是 SCHED_NORMAL（CFS 調度器實現）。

普通優先級根據動態優先級調度，動態優先級由靜態優先級調整而來。靜態優先級由內核隱藏，但可以由 nice 值計算得到：static_prio = MAX_RT_PRIO（默認 100）+ nice + 20。nice 取值範圍是 -20 ~ 19，所以靜態優先級爲 100 ~ 139。

進程時間片也是由靜態優先級得到。如果靜態優先級小於 120，時間片爲 (140 - static_prio) * 20；如果靜態優先級大於等於 120，時間片爲 (140 - static_prio) * 5。

動態優先級主要考慮靜態優先級和進程平均運行時間 bouns 值，計算公式爲：dynamic_prio = max (100, min (static_prio - bouns + 5, 139))。當 bouns 值大於 5 表示優先級提高，小於 5 時優先級變低。Linux 內核會根據進程的平均運行時間動態改變進程的動態優先級。一般來說，交互式進程的平均運行時間比較長，因此 Linux 內核會獎勵從而增加 bouns 的值。

4.2 調度的時機與觸發

進程調度的時機與觸發，就像是一場精心編排的交響樂演出中的節奏轉換，在 Linux 系統運行的每一刻都發揮着關鍵作用。瞭解這一過程，能夠讓我們深入洞悉系統是如何在不同場景下，巧妙地進行進程切換，以實現資源的最優配置。

當進程的狀態發生變化時，調度器會敏銳地捕捉到這一信號，並適時地介入調度 。比如，當一個進程從運行狀態轉變爲等待狀態時，這通常意味着它需要等待某種外部資源的就緒，如等待磁盤 I/O 操作完成、等待網絡數據的接收等。以一個正在讀取大型文件的進程爲例，當它發出讀取文件的請求後，由於磁盤讀寫速度相對較慢，它不得不進入等待狀態，此時調度器會感知到這一狀態變化，將 CPU 資源從該進程轉移到其他處於就緒狀態的進程上，以避免 CPU 資源的閒置浪費。同樣，當進程從等待狀態轉變爲就緒狀態時，例如等待的網絡數據已經接收完畢，調度器會將其重新納入可調度的進程隊列中，參與 CPU 資源的競爭。

時間片用完也是引發調度的重要時機 。在 Linux 系統中，每個進程在被調度執行時，都會被分配一個特定的時間片，這就好比運動員在比賽中被分配的一段特定比賽時間。當進程的時間片耗盡時，即使該進程尚未完成當前任務，系統也會強制暫停它的運行，並將 CPU 資源分配給其他就緒進程。這樣做的目的在於確保系統中的各個進程都能有機會公平地使用 CPU 資源，避免某個進程長時間獨佔 CPU，導致其他進程飢餓。例如，在一個多用戶的服務器環境中，如果某個進程長時間佔用大量 CPU 時間，會使得其他用戶的進程響應遲緩，而通過時間片輪轉機制，能夠保證每個用戶的進程都能在合理的時間內得到執行，提高系統的整體公平性和響應性能。

此外，當系統中出現中斷事件時，調度也可能會發生 。中斷是指計算機在運行過程中，由於外部設備或內部事件的觸發，暫時停止當前正在執行的程序，轉而執行相應的中斷處理程序的過程。例如，當用戶按下鍵盤上的某個按鍵時，會產生一個鍵盤中斷信號，通知系統有新的輸入事件發生。在處理中斷的過程中，系統可能會根據當前的進程狀態和資源需求，決定是否進行進程調度。如果在中斷處理完成後，發現有更適合運行的進程，調度器會及時進行切換，以確保系統能夠快速響應各種外部事件，保持高效的運行狀態。

4.3 進程調度器特點

Linux 進程調度器對於 CPU 進程調度，採用時間分片的方式，特點如下：

每個進程近似相等的 CPU 使用權：每一個進程有近乎相等的執行時間，對於邏輯 CPU 而言，進程調度使用輪詢的方式執行，當輪詢完成則回到第一個進程反覆。進程數量消耗時間和進程量成正比，雖然這種方式可能導致一些重要任務延遲，但使得系統最爲穩定。

進程狀態與調度：對於大部分進程來說，不使用時多數處於睡眠狀態。除了睡眠狀態之外，進程還有運行狀態、僵死狀態、就緒狀態等。當進程處於睡眠狀態時，不佔用 CPU 時間，只有在某些條件觸發時纔會獲得 CPU 調度分配，如外部存儲器訪問、用戶鍵入或者鼠標操作觸發事件、等待指定時間等。

吞吐量和延遲：吞吐量是處理完成的進程數量與耗費時間的比值。如果進程多過邏輯 CPU 的數量，則再增加進程無法增加吞吐量。延遲是結束處理時間與開始處理時間的差值，多個進程執行會獲得近似平均的延遲，進程越多延遲越高。在實際系統中，可能出現空閒進程、進程運行態但未就緒、進程運行態且都就緒等情況，不同情況會對延遲和吞吐量產生不同影響。

五、Linux 調度器的演變歷程

Linux 調度器的發展歷程，猶如一部不斷演進的科技史詩，見證了操作系統爲滿足日益複雜的計算需求而進行的持續創新與優化 。

早期的 Linux 系統採用了相對簡單的調度算法，如 O (n) 調度器。這種調度器的工作方式較爲直觀，它會在一個全局的任務隊列中，依次遍歷所有進程，從中挑選出優先級最高的進程來執行。不難想象，當系統中的進程數量較少時，這種調度方式能夠較爲有效地工作。然而，隨着計算機技術的飛速發展，系統中同時運行的進程數量大幅增加，O (n) 調度器的弊端便逐漸暴露出來。由於每次調度都需要遍歷整個任務隊列，其時間複雜度與進程數量成正比，這就導致在高負載情況下，調度的效率急劇下降，系統性能受到嚴重影響。

爲了應對 O (n) 調度器的性能瓶頸，O (1) 調度器應運而生。它的出現，猶如爲 Linux 系統注入了一劑強心針，帶來了顯著的性能提升。O (1) 調度器的核心創新在於，爲每個 CPU 都配備了獨立的運行隊列，並且通過精妙的算法，實現了在常數時間內完成調度決策。這意味着，無論系統中存在多少進程，調度器都能以幾乎相同的速度進行調度，極大地提高了調度效率。具體來說，O (1) 調度器將進程按照優先級分爲不同的隊列，通過維護活動隊列和過期隊列，以及使用位圖等數據結構，快速地找到下一個需要執行的進程。這種設計使得 O (1) 調度器在多處理器系統中表現出色，能夠更好地平衡負載，提高系統的整體性能。

然而，技術的發展永無止境，O (1) 調度器在使用過程中也逐漸暴露出一些問題。例如，它在處理 I/O 密集型任務時，識別準確率有待提高；而且，在進行活動隊列和過期隊列的交換以及重新評估優先級時，會耗費一定的時間，這在一定程度上影響了系統的性能。爲了解決這些問題，Completely Fair Scheduler（CFS）調度器橫空出世 。CFS 調度器的設計理念獨樹一幟，它摒棄了傳統的固定時間片概念，引入了虛擬運行時間（vruntime）的創新概念。每個進程都擁有自己的 vruntime，這個值會隨着進程的運行而不斷變化。CFS 調度器通過紅黑樹數據結構，對所有進程的 vruntime 進行排序，每次調度時，選擇 vruntime 最小的進程運行，從而確保了每個進程都能公平地獲得 CPU 時間。這種公平性的設計，使得 CFS 調度器在多任務環境下表現卓越，能夠爲各種類型的進程提供高效、公平的調度服務。

近年來，隨着硬件技術的不斷進步，如多核處理器、超線程技術的廣泛應用，以及用戶對系統性能和響應性要求的日益提高，Linux 調度器也在持續進化。一些新的調度器，如 SCHED_DEADLINE、BORE（Burst-Oriented Response Enhancer）等應運而生 。SCHED_DEADLINE 調度器專門針對具有嚴格時間限制的任務，能夠確保這些任務在截止日期前完成，在實時性要求極高的場景，如工業自動化控制、航空航天等領域，發揮着重要作用。BORE 調度器則通過引入 “突發性” 這一概念，對任務的權重和延遲進行動態調整，能夠更好地適應不同類型的系統負載，在多任務環境中，爲用戶提供更流暢、高效的使用體驗。

回顧 Linux 調度器的演變歷程，從簡單的 O (n) 調度器到高效的 O (1) 調度器，再到公平的 CFS 調度器以及不斷湧現的新型調度器，每一次的變革都緊密圍繞着硬件的發展和用戶的需求展開。這些演進不僅提升了 Linux 系統的性能和穩定性，還爲用戶帶來了更加出色的使用體驗，使得 Linux 操作系統在各種領域中都能保持強大的競爭力。

六、案例分析

在實際的應用場景中，Linux 進程調度器的作用得到了淋漓盡致的體現。以服務器端的 Web 應用爲例，在高併發的訪問情況下，大量的 HTTP 請求如潮水般湧來，每個請求都對應着一個進程或線程。此時，Linux 進程調度器憑藉其高效的調度策略，能夠迅速且合理地爲這些進程分配 CPU 資源，確保每個請求都能得到及時的處理。比如，當一個用戶在瀏覽器中快速點擊多個鏈接，發起一系列的頁面請求時，調度器會快速響應，優先處理那些對響應時間要求較高的交互式請求，讓用戶感受到流暢的瀏覽體驗，避免出現長時間等待或頁面卡頓的情況。

在實時控制系統中，Linux 進程調度器同樣發揮着關鍵作用。以自動駕駛汽車的控制系統爲例，車輛在行駛過程中，需要實時採集各種傳感器的數據，如攝像頭圖像數據、雷達距離數據等，並對這些數據進行快速處理，以做出準確的駕駛決策，如加速、剎車、轉向等。Linux 進程調度器能夠確保這些實時任務在嚴格的時間限制內完成，保證車輛的行駛安全。在工業自動化生產線中，各種設備的控制和數據採集任務也對實時性要求極高，調度器能夠根據任務的優先級和時間要求，精確地調度各個進程，確保生產線的高效、穩定運行。

在移動設備領域，Linux 系統也被廣泛應用。以智能手機爲例，當用戶同時運行多個應用程序，如微信、音樂播放器、瀏覽器等時，Linux 進程調度器會根據各個應用的優先級和資源需求，合理分配 CPU 時間。對於正在前臺運行的應用，調度器會給予較高的優先級，確保其能夠流暢運行，爲用戶提供良好的交互體驗；而對於後臺運行的應用，調度器會適當降低其優先級，在保證系統整體性能的前提下，讓它們在空閒時間進行數據更新等操作。這樣，用戶在使用手機時，就能夠感受到多個應用的同時運行，而不會出現明顯的卡頓或延遲現象。

七、全文總結

Linux 進程調度器作爲操作系統的核心組件，歷經多年的發展與演進，已經成爲一個功能強大、高度優化的資源管理系統。從早期簡單的調度算法到如今複雜而精妙的調度策略，每一次的變革都緊密貼合着硬件技術的發展以及用戶不斷增長的需求。它不僅確保了系統的高效運行，還爲各種應用場景提供了堅實的支持。

實時調度策略爲對時間要求極高的任務提供了精準的保障，使得諸如工業自動化、航空航天等關鍵領域的系統能夠穩定、可靠地運行。而完全公平調度策略（CFS）則秉持着公平的理念，爲系統中的每個進程都分配了合理的 CPU 時間，有效避免了進程飢餓現象的發生，極大地提升了系統的整體性能和用戶體驗。

展望未來，隨着科技的飛速發展，Linux 進程調度器有望迎來更多令人矚目的創新與突破。隨着人工智能和機器學習技術的蓬勃興起，將這些先進技術融入到調度器的設計中，實現更加智能化的調度決策，是一個極具潛力的發展方向。通過對系統運行狀態的實時監測和深度分析，調度器能夠精準預測進程的資源需求，並據此動態調整調度策略，從而進一步提升系統的資源利用率和響應速度。

此外，隨着硬件技術的不斷革新，如新型處理器架構的不斷湧現，Linux 進程調度器也需要持續優化，以充分發揮這些硬件的強大性能。在面對未來複雜多變的應用場景和用戶需求時，相信 Linux 進程調度器將憑藉其強大的適應性和創新性，不斷髮展壯大，爲 Linux 操作系統的持續領先地位奠定堅實的基礎。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/y5YNZAFBeqEbwAvL6envuQ

猜你喜歡