在當(dāng)今數(shù)字化時(shí)代，操作系統(tǒng)如同復(fù)雜交響樂的指揮家，高效協(xié)調(diào)著計(jì)算機(jī)系統(tǒng)的各項(xiàng)資源。而多任務(wù)處理，無疑是這場(chǎng)交響樂中最激昂的樂章。想象一下，你的電腦在同一時(shí)刻流暢運(yùn)行著辦公軟件、瀏覽器、音樂播放器等多個(gè)程序，這背后便是多任務(wù)處理的神奇魔力。

在 Linux 操作系統(tǒng)的內(nèi)核中，有一位默默奉獻(xiàn)的 “幕后英雄”——CFS 調(diào)度器。它宛如一位精明的管家，精心管理著 CPU 時(shí)間這一寶貴資源，將其合理分配給各個(gè)運(yùn)行的進(jìn)程。從誕生之初，CFS 調(diào)度器便承載著實(shí)現(xiàn)公平、高效多任務(wù)調(diào)度的使命，在 Linux 內(nèi)核的發(fā)展歷程中留下了濃墨重彩的一筆。接下來，讓我們一同揭開 Linux 內(nèi)核 CFS 調(diào)度器的神秘面紗，探尋它在多任務(wù)處理中創(chuàng)造奇跡的奧秘。

一、CFS調(diào)度器簡(jiǎn)介

1. 什么是CFS調(diào)度器

在 Linux 內(nèi)核的龐大體系中，CFS 調(diào)度器(Completely Fair Scheduler，完全公平調(diào)度器)占據(jù)著舉足輕重的地位，是 Linux 默認(rèn)的調(diào)度類 ，負(fù)責(zé)普通用戶任務(wù)(SCHED_OTHER 和 SCHED_BATCH)的調(diào)度，自 Linux 2.6.23 版本引入以來，一直是 Linux 內(nèi)核中的默認(rèn)調(diào)度器。

CFS 調(diào)度器的核心使命是為所有運(yùn)行的任務(wù)提供公平的 CPU 時(shí)間分配，它就像是一位公正無私的 “時(shí)間管家”，精心管理著系統(tǒng)中各個(gè)任務(wù)對(duì) CPU 時(shí)間的使用。在多任務(wù)處理的場(chǎng)景下，不同的任務(wù)都在競(jìng)爭(zhēng) CPU 資源，而 CFS 調(diào)度器的存在，確保了每個(gè)任務(wù)都能在這場(chǎng)資源競(jìng)爭(zhēng)中獲得合理的時(shí)間份額，不會(huì)出現(xiàn)某些任務(wù)長(zhǎng)時(shí)間霸占 CPU，而其他任務(wù)卻苦苦等待的不公平現(xiàn)象。

2. CFS調(diào)度器誕生背景

在 CFS 調(diào)度器出現(xiàn)之前，Linux 內(nèi)核使用的調(diào)度器在多任務(wù)處理方面存在一些明顯的不足。早期的調(diào)度器往往難以在不同類型的任務(wù)之間實(shí)現(xiàn)精準(zhǔn)的平衡，比如在面對(duì)交互式任務(wù)和計(jì)算密集型任務(wù)時(shí)，就容易顧此失彼。對(duì)于交互式任務(wù)而言，它們對(duì)響應(yīng)時(shí)間極為敏感，用戶期望在進(jìn)行操作后能立即得到系統(tǒng)反饋，像我們?nèi)粘Ｊ褂玫膱D形界面應(yīng)用程序，每一次鼠標(biāo)點(diǎn)擊、鍵盤輸入都希望能即時(shí)在屏幕上呈現(xiàn)出結(jié)果。而計(jì)算密集型任務(wù)則更側(cè)重于長(zhǎng)時(shí)間占用 CPU 資源，以高效完成復(fù)雜的計(jì)算任務(wù)，例如科學(xué)計(jì)算程序、大數(shù)據(jù)分析任務(wù)等 。

在早期調(diào)度器的管理下，計(jì)算密集型任務(wù)可能會(huì)憑借其對(duì) CPU 資源的持續(xù)需求，長(zhǎng)時(shí)間霸占 CPU，使得交互式任務(wù)的響應(yīng)時(shí)間大幅增加，用戶在操作時(shí)會(huì)明顯感覺到卡頓、延遲，極大地影響了使用體驗(yàn)。這種資源分配的不公平性，就像一場(chǎng)比賽中，有的選手被過度偏袒，而有的選手則被嚴(yán)重忽視，整個(gè)比賽失去了公平競(jìng)爭(zhēng)的基礎(chǔ)。

為了解決這些問題，CFS 調(diào)度器應(yīng)運(yùn)而生。它的出現(xiàn)，就像是為多任務(wù)處理的賽場(chǎng)引入了一位公正的裁判，致力于打破資源分配的不公平局面，為每個(gè)任務(wù)提供公平競(jìng)爭(zhēng) CPU 資源的機(jī)會(huì)，確保系統(tǒng)在各種任務(wù)混合的場(chǎng)景下，都能高效、穩(wěn)定地運(yùn)行，滿足不同類型任務(wù)的需求，提升整個(gè)系統(tǒng)的性能和用戶體驗(yàn)。

二、CFS調(diào)度器實(shí)現(xiàn)方式

1. 虛擬運(yùn)行時(shí)間(vruntime)：公平的基石

在 CFS 調(diào)度器的公平調(diào)度體系中，虛擬運(yùn)行時(shí)間(vruntime)是最為核心的概念，它就像是一把精準(zhǔn)的 “公平標(biāo)尺”，用來衡量每個(gè)任務(wù)在 CPU 資源競(jìng)爭(zhēng)中的 “進(jìn)度”。

CFS 調(diào)度器的設(shè)計(jì)目標(biāo)是模擬一個(gè)理想的多任務(wù) CPU 環(huán)境，在這個(gè)環(huán)境中，所有任務(wù)都能以相同的速率并行運(yùn)行。但在現(xiàn)實(shí)中，CPU 資源是有限的，多個(gè)任務(wù)必須分時(shí)復(fù)用 CPU。為了實(shí)現(xiàn)這種理想的公平狀態(tài)，CFS 引入了 vruntime 。它并不是真實(shí)的物理時(shí)間，而是一個(gè)抽象的虛擬時(shí)間概念。當(dāng)一個(gè)任務(wù)開始執(zhí)行時(shí)，它的 vruntime 會(huì)隨著實(shí)際執(zhí)行時(shí)間的增加而增長(zhǎng)，增長(zhǎng)的速度與任務(wù)的權(quán)重相關(guān)。

例如，系統(tǒng)中有兩個(gè)任務(wù) A 和 B，任務(wù) A 的權(quán)重較高，任務(wù) B 的權(quán)重較低。假設(shè)任務(wù) A 的權(quán)重是任務(wù) B 的兩倍，那么在相同的實(shí)際執(zhí)行時(shí)間內(nèi)，任務(wù) B 的 vruntime 增長(zhǎng)速度將是任務(wù) A 的兩倍。這意味著，即使任務(wù) A 和 B 在不同的時(shí)間段內(nèi)執(zhí)行，但只要它們獲得的 CPU 時(shí)間與各自的權(quán)重成正比，它們的 vruntime 增長(zhǎng)就會(huì)保持一種相對(duì)的公平性。

當(dāng)任務(wù)執(zhí)行完畢或者被搶占時(shí)，它的 vruntime 就會(huì)保持不變，等待下一次被調(diào)度執(zhí)行。在調(diào)度決策時(shí)，CFS 調(diào)度器會(huì)從所有就緒任務(wù)中，挑選出 vruntime 最小的任務(wù)來運(yùn)行，因?yàn)檫@個(gè)任務(wù)的 vruntime 最小，說明它之前獲得的 CPU 時(shí)間相對(duì)較少，受到了 “不公平” 對(duì)待，理應(yīng)在下一輪調(diào)度中優(yōu)先獲得 CPU 資源 。通過這種方式，CFS 調(diào)度器不斷地讓各個(gè)任務(wù)的 vruntime 相互追趕，從而實(shí)現(xiàn)了 CPU 時(shí)間在不同任務(wù)之間的公平分配，確保每個(gè)任務(wù)都能在合理的時(shí)間內(nèi)得到執(zhí)行。

在CFS調(diào)度器中，虛擬運(yùn)行時(shí)間(virtual runtime)通過每個(gè)任務(wù)的p->se.vruntime(以納秒單位)來表示和跟蹤，這樣，就可以準(zhǔn)確地標(biāo)記時(shí)間戳并測(cè)量任務(wù)應(yīng)該獲得的預(yù)期 CPU 時(shí)間。其中，p指向一個(gè)struct task_struct結(jié)構(gòu)體。

/* include/linux/sched.h */

struct sched_entity {
	...
	/*
	 * 進(jìn)程的虛擬運(yùn)行時(shí)間 = 進(jìn)程的實(shí)際運(yùn)行時(shí)間 / 相對(duì)權(quán)重
	 *
	 * 進(jìn)程的 實(shí)際運(yùn)行時(shí)間 是一段一段的，所以進(jìn)程的 虛擬運(yùn)行時(shí)間 也是一段一段增長(zhǎng)的。
	 *
	 * 進(jìn)程的 虛擬運(yùn)行時(shí)間 還會(huì)在 進(jìn)程入隊(duì)時(shí) 與 運(yùn)行隊(duì)列中的最小虛擬時(shí)間 相比較，如
	 * 果更小的話會(huì)直接進(jìn)行增加，并不對(duì)應(yīng) 實(shí)際的運(yùn)行時(shí)間。為什么要這么做呢？因?yàn)橛械?	 * 進(jìn)程可能會(huì)因長(zhǎng)時(shí)間睡眠，導(dǎo)致其 虛擬運(yùn)行時(shí)間 小于運(yùn)行隊(duì)列中所有進(jìn)程中的 最小虛
	 * 擬運(yùn)行時(shí)間，這樣的進(jìn)程一旦運(yùn)行起來，會(huì)因?yàn)槠?虛擬運(yùn)行時(shí)間 小，占據(jù) CPU 的時(shí)間
	 * 就會(huì)長(zhǎng)，對(duì)其它進(jìn)程就不公平了。
	 */
	u64				vruntime;
	...
};

struct task_struct {
	...
	const struct sched_class	*sched_class; /* 如果任務(wù)使用 CFS 調(diào)度，則為 &fair_sched_class */
	struct sched_entity		se; /* CFS 類進(jìn)程調(diào)度參數(shù) */
	...
};

<p data-pid="qy7bviVo">在理想的 虛擬 CPU 上，在任何時(shí)刻，所有任務(wù) 虛擬運(yùn)行時(shí)間值 p->se.vruntime 都保持相同的值；CFS 調(diào)度器，其任務(wù)選擇邏輯基于 p->se.vruntime 值：CFS 始終嘗試運(yùn)行具有最小 p->se.vruntime 值的任務(wù)（即到目前為止虛擬執(zhí)行時(shí)間(virtual runtime)最小的任務(wù)）。

CFS 始終嘗試在可運(yùn)行任務(wù)之間平均分配 虛擬 CPU時(shí)間 ，盡可能接近理想的多任務(wù) 虛擬 CPU。CFS 設(shè)計(jì)的其余部分大部分都脫離了這個(gè)非常簡(jiǎn)單的概念，有一些其它附加修飾，如任務(wù)的 nice 值，各種識(shí)別睡眠任務(wù)的算法等等。

2. 權(quán)重(Weight)：優(yōu)先級(jí)的體現(xiàn)

在 CFS 調(diào)度器中，任務(wù)的權(quán)重是決定其優(yōu)先級(jí)的關(guān)鍵因素，而權(quán)重又與任務(wù)的 nice 值緊密相關(guān)。nice 值是 Linux 系統(tǒng)中用于調(diào)整進(jìn)程優(yōu)先級(jí)的一個(gè)參數(shù)，它的取值范圍通常是 -20 到 19 ，數(shù)值越小，表示任務(wù)的優(yōu)先級(jí)越高 。通過 nice 值與權(quán)重的映射關(guān)系，CFS 調(diào)度器能夠?yàn)椴煌瑑?yōu)先級(jí)的任務(wù)分配不同的權(quán)重。

具體來說，低 nice 值的任務(wù)具有較高的優(yōu)先級(jí)，相應(yīng)地，它們也會(huì)被賦予較大的權(quán)重。這就好比一場(chǎng)比賽中，實(shí)力更強(qiáng)(優(yōu)先級(jí)更高)的選手會(huì)得到更多的資源支持(更大的權(quán)重)。當(dāng)一個(gè)任務(wù)具有較大的權(quán)重時(shí)，在相同的實(shí)際執(zhí)行時(shí)間內(nèi)，它的 vruntime 增長(zhǎng)速度會(huì)相對(duì)較慢。例如，有任務(wù) C 和任務(wù) D，任務(wù) C 的 nice 值較低，權(quán)重較大，任務(wù) D 的 nice 值較高，權(quán)重較小。在同樣運(yùn)行 10 毫秒的情況下，任務(wù) D 的 vruntime 增加量會(huì)大于任務(wù) C，這使得任務(wù) C 在調(diào)度競(jìng)爭(zhēng)中更具優(yōu)勢(shì)，能夠獲得更多的 CPU 執(zhí)行時(shí)間。

這種通過權(quán)重調(diào)整 vruntime 增長(zhǎng)速度的機(jī)制，不僅保證了高優(yōu)先級(jí)任務(wù)能夠優(yōu)先獲得 CPU 資源，同時(shí)也兼顧了低優(yōu)先級(jí)任務(wù)的執(zhí)行機(jī)會(huì)，避免了低優(yōu)先級(jí)任務(wù)長(zhǎng)時(shí)間得不到調(diào)度而 “餓死” 的情況。CFS 調(diào)度器就像一位經(jīng)驗(yàn)豐富的資源分配者，在高優(yōu)先級(jí)任務(wù)和低優(yōu)先級(jí)任務(wù)之間找到了一個(gè)平衡點(diǎn)，讓系統(tǒng)中的所有任務(wù)都能在這個(gè)公平的調(diào)度框架下有序運(yùn)行。

3. 紅黑樹(Red - Black Tree)：高效的任務(wù)管理

為了高效地管理就緒隊(duì)列中的任務(wù)，CFS 調(diào)度器采用了紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。紅黑樹是一種自平衡的二叉查找樹，它具有高效的插入、刪除和查找操作特性，這使得 CFS 調(diào)度器能夠快速地對(duì)任務(wù)進(jìn)行管理和調(diào)度決策。

在 CFS 調(diào)度器中，紅黑樹的每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)任務(wù)，節(jié)點(diǎn)中的關(guān)鍵值就是任務(wù)的 vruntime 。當(dāng)一個(gè)新任務(wù)進(jìn)入就緒隊(duì)列時(shí)，它會(huì)根據(jù)自己的 vruntime 被插入到紅黑樹的合適位置;當(dāng)任務(wù)執(zhí)行完畢或者被搶占時(shí)，它會(huì)從紅黑樹中刪除。紅黑樹的自平衡特性保證了樹的高度始終保持在一個(gè)較低的水平，從而確保了插入、刪除和查找操作的時(shí)間復(fù)雜度始終保持在 O (log n)，這里的 n 是紅黑樹中節(jié)點(diǎn)的數(shù)量 。

由于紅黑樹是按照 vruntime 從小到大的順序排列節(jié)點(diǎn)的，CFS 調(diào)度器可以通過簡(jiǎn)單地訪問紅黑樹的最左節(jié)點(diǎn)(即 vruntime 最小的節(jié)點(diǎn))，快速地找到下一個(gè)應(yīng)該執(zhí)行的任務(wù)。這種高效的查找方式，使得 CFS 調(diào)度器能夠在眾多就緒任務(wù)中迅速做出調(diào)度決策，大大提高了調(diào)度效率。與傳統(tǒng)的線性鏈表結(jié)構(gòu)相比，紅黑樹在處理大量任務(wù)時(shí)的優(yōu)勢(shì)更加明顯，它能夠顯著減少查找下一個(gè)執(zhí)行任務(wù)所需的時(shí)間，從而提升整個(gè)系統(tǒng)的多任務(wù)處理能力。

CFS 需要高效的數(shù)據(jù)結(jié)構(gòu)來跟蹤任務(wù)信息，需要高性能的代碼來產(chǎn)生調(diào)度。讓我們從調(diào)度中的一個(gè)中心術(shù)語開始，即運(yùn)行隊(duì)列(runqueue)。運(yùn)行隊(duì)列(runqueue)是一個(gè)數(shù)據(jù)結(jié)構(gòu)，表示被調(diào)度任務(wù)的時(shí)間線。盡管有這個(gè)名字，但運(yùn)行隊(duì)列不需要以傳統(tǒng)方式實(shí)現(xiàn)，如實(shí)現(xiàn)為一個(gè) FIFO 列表。CFS 打破了傳統(tǒng)，它不使用運(yùn)行隊(duì)列以往的舊數(shù)據(jù)結(jié)構(gòu)，而是使用按時(shí)間排序的紅黑樹(red-black tree)作為可運(yùn)行任務(wù)隊(duì)列，來構(gòu)建未來任務(wù)執(zhí)行的時(shí)間線。

紅黑樹非常適合這項(xiàng)工作，因?yàn)樗且粋€(gè)自平衡的二叉搜索樹，具有高效的插入和刪除操作，在 O(log N) 時(shí)間內(nèi)執(zhí)行，其中 N 是樹中的節(jié)點(diǎn)數(shù)。此外，樹是一種出色的數(shù)據(jù)結(jié)構(gòu)，用于根據(jù)特定屬性(在 CFS 中為 vruntime)將實(shí)體組織到層次結(jié)構(gòu)中。

在 CFS 中，樹的內(nèi)部節(jié)點(diǎn)表示要調(diào)度的任務(wù)，而樹作為一個(gè)整體(與任何運(yùn)行隊(duì)列一樣)表示任務(wù)執(zhí)行的時(shí)間線。紅黑樹被廣泛使用，還用于任務(wù)調(diào)度之外，例如，Java 使用此數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)其樹狀圖。

在 CFS 下，每個(gè)處理器都有一個(gè)自己特定的任務(wù)運(yùn)行隊(duì)列，同一任務(wù)某一時(shí)刻只會(huì)位于某個(gè)運(yùn)行隊(duì)列中。每個(gè)運(yùn)行隊(duì)列都是一棵紅黑樹。樹的內(nèi)部節(jié)點(diǎn)表示任務(wù)或任務(wù)組，這些節(jié)點(diǎn)按其 vruntime 值索引，因此(在整個(gè)樹或任何子樹中)左側(cè)內(nèi)部節(jié)點(diǎn)的 vruntime 值低于右側(cè)節(jié)點(diǎn)：

    25     ## 25 is a task vruntime
    /\
  17  29   ## 17 roots the left subtree, 29 the right one
  /\  ...
 5  19     ## and so on
...  \
     nil   ## leaf nodes are nil

總之，具有最低 vruntime 的任務(wù)(因此對(duì)處理器的需求最大)位于左側(cè)子樹的某個(gè)位置;具有相對(duì)較高的 vruntimes 的任務(wù)聚集在右側(cè)子樹中。搶占的任務(wù)將進(jìn)入右側(cè)子樹，從而使其他任務(wù)有機(jī)會(huì)在樹中向左移動(dòng)。具有最小 vruntime 的任務(wù)最終出現(xiàn)在樹的最左側(cè)(內(nèi)部)節(jié)點(diǎn)中，因此該節(jié)點(diǎn)位于運(yùn)行隊(duì)列的前面。

/* kernel/sched/sched.h */

/* CFS-related fields in a runqueue */
struct cfs_rq {
	...
	u64 min_vruntime; /* CFS 調(diào)度算法 運(yùn)行隊(duì)列中 進(jìn)程 的 最小 虛擬運(yùn)行時(shí)間 */
	...
	/*
	 * CFS 進(jìn)程 運(yùn)行隊(duì)列 紅黑樹 根節(jié)點(diǎn): 
	 * 按進(jìn)程的 vruntime 為鍵值進(jìn)行排序。 
	 */
	struct rb_root_cached tasks_timeline;
	...
};

/*
 * This is the main, per-CPU runqueue data structure.
 *
 * Locking rule: those places that want to lock multiple runqueues
 * (such as the load balancing or the thread migration code), lock
 * acquire operations must be ordered by ascending &runqueue.
 */
struct rq {
	...
	struct cfs_rq cfs;
	...
};

DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); /* 每 CPU 的運(yùn)行隊(duì)列 */

紅黑樹的每個(gè)內(nèi)部節(jié)點(diǎn)都有指向父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)的指針，葉節(jié)點(diǎn)的值為NULL：

struct rb_node {
	unsigned long  __rb_parent_color; /* 父節(jié)點(diǎn)顏色: 紅 或 黑 */
	struct rb_node *rb_right;
	struct rb_node *rb_left;
/* The alignment might seem pointless, but allegedly CRIS needs it */
} __attribute__((aligned(sizeof(long))));

struct rb_root { /* 紅黑樹 的 根 */
	struct rb_node *rb_node;
};

CFS 調(diào)度器用 task_struct 來描述一個(gè)任務(wù)，task_struct 用于跟蹤有關(guān)要調(diào)度的每個(gè)任務(wù)的詳細(xì)信息。此結(jié)構(gòu)嵌入了一個(gè) sched_entity 結(jié)構(gòu)，該結(jié)構(gòu)又具有特定于調(diào)度的信息，特別是每個(gè)任務(wù)或任務(wù)組的 vruntime，即 rq->cfs.min_vruntime 值，該值是一個(gè)單調(diào)遞增值，用于跟蹤運(yùn)行隊(duì)列中所有任務(wù)中的最小 vruntime。該值用于盡可能將新激活的調(diào)度實(shí)體(struct sched_entity，即任務(wù))放置在紅黑樹的左側(cè)。由于該值一直使用 min_vruntime 單調(diào)遞增累加，所以也可用來跟蹤系統(tǒng)完成的工作總量。

/* include/linux/sched.h */

struct sched_entity {
	...
	u64	vruntime;
	...
};

struct task_struct {
	...
	struct sched_entity se;  /* vruntime, etc. */
	...
};

運(yùn)行隊(duì)列的權(quán)重通過rq->cfs.load值進(jìn)行統(tǒng)計(jì)，該值是運(yùn)行隊(duì)列上排隊(duì)的任務(wù)權(quán)重的總和：

/* kernel/sched/sched.h */

/* CFS-related fields in a runqueue */
struct cfs_rq {
	/*
	 * 運(yùn)行隊(duì)列的權(quán)重, 等于其上所有進(jìn)程的權(quán)重之和。
	 * 進(jìn)程在入隊(duì)出隊(duì)時(shí)，也會(huì)相應(yīng)地從運(yùn)行隊(duì)列中加上減去其自身的權(quán)重。
	 */
	struct load_weight load;
	...
};

CFS 維護(hù)一個(gè)按時(shí)間排序的 紅黑樹(rbtree)，即所有可運(yùn)行的任務(wù)都按 p->se.vruntime 鍵排序，然后CFS 從這棵樹中挑選最左邊(即 p->se.vruntime 最小)的任務(wù)執(zhí)行。隨著時(shí)間往后推移，執(zhí)行的任務(wù)越來越多地被放入樹中，執(zhí)行時(shí)間更少的任務(wù)逐漸往紅黑樹左邊移動(dòng)，執(zhí)行時(shí)間更多的任務(wù)往紅黑樹右邊移動(dòng)，如此循環(huán)往復(fù)。

創(chuàng)建新任務(wù)時(shí)，將它們插入紅黑樹，初始 vruntime 值賦為 min_vruntime，使得它們盡可能快的得到執(zhí)行：vruntime 越小，越快得到執(zhí)行。

使用紅黑樹還有一個(gè)優(yōu)點(diǎn)，那就是如果一個(gè)進(jìn)程是 I/O 密集型的，那么它的虛擬時(shí)間將非常少，并且它顯示為紅黑樹中最左邊的節(jié)點(diǎn)，因此首先執(zhí)行。因此，CFS 很容易找出哪些是 I/O 密集型的進(jìn)程，哪些是 CPU 密集型的進(jìn)程，并且它讓 I/O 密集型的進(jìn)程具有更高的優(yōu)先級(jí)，從而避免了饑餓。

4. 負(fù)載均衡(Load Balancing)：資源的合理分配

在多核處理器系統(tǒng)中，為了充分發(fā)揮多核的性能優(yōu)勢(shì)，CFS 調(diào)度器需要進(jìn)行負(fù)載均衡操作，確保任務(wù)能夠在各個(gè) CPU 核心之間均勻分布，避免出現(xiàn)某些 CPU 核心負(fù)載過重，而其他 CPU 核心閑置的情況。CFS 調(diào)度器通過調(diào)度域(scheduling domains)和調(diào)度組(sched_groups)來實(shí)現(xiàn)負(fù)載均衡。

調(diào)度域是一種層次結(jié)構(gòu)，它將相關(guān)的 CPU 核心組合在一起，形成一個(gè)調(diào)度范圍。調(diào)度域可以嵌套，形成多層的樹狀結(jié)構(gòu)，最頂層的是根域(Root Domain)，代表整個(gè)系統(tǒng)的所有任務(wù);最底層的是葉域(Leaf Domains)，直接包含具體的任務(wù)。調(diào)度組則是調(diào)度域的一部分，它將 CPU 核心進(jìn)一步分組，以便在組內(nèi)進(jìn)行更精細(xì)的任務(wù)調(diào)度。例如，在一個(gè)具有多個(gè) CPU 核心的服務(wù)器系統(tǒng)中，可能會(huì)根據(jù) CPU 的物理位置、性能特點(diǎn)等因素，將不同的 CPU 核心劃分到不同的調(diào)度組中。

CFS 調(diào)度器會(huì)周期性地執(zhí)行負(fù)載均衡操作，監(jiān)控各個(gè)調(diào)度組和 CPU 核心的負(fù)載情況。當(dāng)發(fā)現(xiàn)某個(gè)調(diào)度組或 CPU 核心的負(fù)載過高時(shí)，調(diào)度器會(huì)將部分任務(wù)從高負(fù)載的調(diào)度組或 CPU 核心遷移到低負(fù)載的調(diào)度組或 CPU 核心上，實(shí)現(xiàn)負(fù)載的均衡分布。在進(jìn)行任務(wù)遷移時(shí)，CFS 調(diào)度器還會(huì)考慮任務(wù)的 CPU 親和性(CPU Affinity)，盡量將任務(wù)分配到它們偏好的 CPU 核心上，同時(shí)仍然保持整體的負(fù)載均衡。

這就好比在一個(gè)工廠中，管理人員會(huì)根據(jù)各個(gè)生產(chǎn)線的工作量，合理地調(diào)配工人(任務(wù))，讓每個(gè)生產(chǎn)線(CPU 核心)都能高效地運(yùn)轉(zhuǎn)，同時(shí)又考慮到每個(gè)工人(任務(wù))對(duì)不同生產(chǎn)線(CPU 核心)的熟悉程度(CPU 親和性)，從而提高整個(gè)工廠(系統(tǒng))的生產(chǎn)效率 。通過這種負(fù)載均衡機(jī)制，CFS 調(diào)度器能夠充分利用多核處理器的資源，提高系統(tǒng)的整體性能和響應(yīng)速度，讓多任務(wù)處理在多核環(huán)境下更加高效、穩(wěn)定地運(yùn)行。

三、CFS調(diào)度器的調(diào)度策略

CFS 調(diào)度器針對(duì)不同類型的任務(wù)，提供了多種調(diào)度策略，以滿足多樣化的系統(tǒng)需求。這些調(diào)度策略就像是為不同類型的 “選手” 量身定制的比賽規(guī)則，確保每個(gè)任務(wù)都能在最合適的規(guī)則下參與 CPU 資源的競(jìng)爭(zhēng)。

1. SCHED_NORMAL(SCHED_OTHER)

SCHED_NORMAL，也被稱為 SCHED_OTHER ，是 CFS 調(diào)度器中最為常用的調(diào)度策略，適用于大多數(shù)普通的用戶級(jí)交互式任務(wù) 。像我們?nèi)粘Ｊ褂玫膱D形界面應(yīng)用程序、辦公軟件、瀏覽器等，這些需要與用戶頻繁交互的任務(wù)，都采用了這種調(diào)度策略。

在 SCHED_NORMAL 策略下，任務(wù)的執(zhí)行優(yōu)先級(jí)主要由其 nice 值決定。nice 值的取值范圍是 -20 到 19 ，數(shù)值越小，任務(wù)的優(yōu)先級(jí)越高。系統(tǒng)會(huì)根據(jù)任務(wù)的 nice 值，為其分配相應(yīng)的 CPU 時(shí)間份額。例如，當(dāng)我們?cè)陔娔X上同時(shí)打開瀏覽器瀏覽網(wǎng)頁，又運(yùn)行一個(gè)文本編輯軟件進(jìn)行文字處理時(shí)，由于這兩個(gè)任務(wù)都屬于交互式任務(wù)，它們的 nice 值默認(rèn)可能都是 0 。在這種情況下，CFS 調(diào)度器會(huì)按照公平的原則，為它們分配大致相等的 CPU 時(shí)間，使得我們?cè)诓僮鳛g覽器切換頁面時(shí)，不會(huì)感覺到文本編輯軟件的響應(yīng)受到明顯影響，反之亦然，從而保證了用戶在使用這些交互式應(yīng)用時(shí)，能夠獲得流暢、及時(shí)的體驗(yàn) 。

2. SCHED_BATCH

SCHED_BATCH 調(diào)度策略主要適用于那些非交互式的批處理任務(wù) ，這類任務(wù)通常不需要與用戶進(jìn)行實(shí)時(shí)交互，它們更注重任務(wù)的整體運(yùn)行效率，而不是對(duì)用戶輸入的即時(shí)響應(yīng)。比如一些長(zhǎng)時(shí)間運(yùn)行的計(jì)算任務(wù)，如大數(shù)據(jù)分析、科學(xué)計(jì)算程序等。這些任務(wù)往往需要大量的 CPU 計(jì)算資源，如果它們與交互式任務(wù)采用相同的調(diào)度策略，可能會(huì)因?yàn)轭l繁的上下文切換，導(dǎo)致 CPU 緩存命中率降低，從而影響整體的計(jì)算效率。

在 SCHED_BATCH 策略下，任務(wù)會(huì)被調(diào)度器安排在系統(tǒng)資源相對(duì)空閑的時(shí)候執(zhí)行，并且盡量減少任務(wù)的上下文切換次數(shù)。這就好比工廠里的大型生產(chǎn)設(shè)備，在原材料準(zhǔn)備充足、其他輔助工作都安排妥當(dāng)后，集中一段時(shí)間進(jìn)行高效生產(chǎn)，避免頻繁地啟動(dòng)和停止設(shè)備，以提高生產(chǎn)效率。由于批處理任務(wù)不需要像交互式任務(wù)那樣對(duì)用戶操作做出即時(shí)響應(yīng)，它們可以在后臺(tái)默默地運(yùn)行，充分利用 CPU 的空閑時(shí)間，同時(shí)又不會(huì)對(duì)前臺(tái)的交互式任務(wù)造成干擾，確保系統(tǒng)在處理批處理任務(wù)的，用戶仍然能夠正常、流暢地使用其他交互式應(yīng)用。

3. SCHED_IDLE

SCHED_IDLE 是 CFS 調(diào)度器中優(yōu)先級(jí)最低的調(diào)度策略，它僅在系統(tǒng)處于空閑狀態(tài)時(shí)才會(huì)運(yùn)行 。這類任務(wù)通常是一些對(duì)系統(tǒng)性能影響極小，且不需要及時(shí)執(zhí)行的后臺(tái)服務(wù)，比如系統(tǒng)的一些定期清理任務(wù)、日志統(tǒng)計(jì)任務(wù)等。這些任務(wù)的特點(diǎn)是即使延遲執(zhí)行，也不會(huì)對(duì)系統(tǒng)的正常運(yùn)行和用戶體驗(yàn)產(chǎn)生明顯的影響。

SCHED_IDLE 任務(wù)的權(quán)重非常低，這使得它們?cè)谂c其他任務(wù)競(jìng)爭(zhēng) CPU 資源時(shí)，幾乎沒有優(yōu)勢(shì)。當(dāng)系統(tǒng)中存在其他優(yōu)先級(jí)較高的任務(wù)時(shí)，SCHED_IDLE 任務(wù)會(huì)被調(diào)度器 “冷落”，幾乎得不到 CPU 的執(zhí)行時(shí)間。只有當(dāng)系統(tǒng)中所有其他任務(wù)都處于等待狀態(tài)，CPU 資源完全空閑時(shí)，SCHED_IDLE 任務(wù)才會(huì)有機(jī)會(huì)被調(diào)度執(zhí)行 。例如，當(dāng)我們的電腦在一段時(shí)間內(nèi)沒有任何用戶操作，系統(tǒng)處于空閑狀態(tài)時(shí)，那些采用 SCHED_IDLE 調(diào)度策略的后臺(tái)清理任務(wù)就會(huì)開始運(yùn)行，對(duì)系統(tǒng)中的臨時(shí)文件、緩存數(shù)據(jù)等進(jìn)行清理，為系統(tǒng)的下一次高效運(yùn)行做好準(zhǔn)備，而在系統(tǒng)忙碌時(shí)，這些任務(wù)則會(huì)自動(dòng) “讓路”，避免占用寶貴的 CPU 資源，確保其他重要任務(wù)的順利執(zhí)行。

四、CFS調(diào)度器常見問題

問題一：請(qǐng)簡(jiǎn)述對(duì)進(jìn)程調(diào)度器的理解，早起Linux內(nèi)核調(diào)度器(包括O(N)和O(1))調(diào)度器是如何工作的?

調(diào)度器是按一定的方式對(duì)進(jìn)程進(jìn)行調(diào)度的一種機(jī)制，需要為各個(gè)普通進(jìn)程盡可能公平地共享CPU時(shí)間。

O(N)調(diào)度器發(fā)布與1992年，從就緒隊(duì)列中比較所有進(jìn)程的優(yōu)先級(jí)，然后選擇一個(gè)最高優(yōu)先級(jí)的進(jìn)程作為下一個(gè)調(diào)度進(jìn)程。每一個(gè)進(jìn)程有一個(gè)固定時(shí)間片，當(dāng)進(jìn)程時(shí)間片使用完之后，調(diào)度器會(huì)選擇下一個(gè)調(diào)度進(jìn)程，當(dāng)所有進(jìn)程都運(yùn)行一遍后再重新分配時(shí)間片。這個(gè)調(diào)度器選擇下一個(gè)調(diào)度進(jìn)程前需要遍歷整個(gè)就緒隊(duì)列，花費(fèi)O(N)時(shí)間。

O(1)調(diào)度器用于Linux2.6.23內(nèi)核之前，它為每個(gè)CPU維護(hù)一組進(jìn)程優(yōu)先級(jí)隊(duì)列，每個(gè)優(yōu)先級(jí)一個(gè)隊(duì)列，這樣在選擇下一個(gè)進(jìn)程時(shí)，只要查詢優(yōu)先級(jí)隊(duì)列相應(yīng)的位圖即可知道哪個(gè)隊(duì)列中有就緒進(jìn)程，查詢時(shí)間常數(shù)為O(1)。

問題二：請(qǐng)簡(jiǎn)述進(jìn)程優(yōu)先級(jí)、nice和權(quán)重之間的關(guān)系。

內(nèi)核使用0~139的數(shù)值表示進(jìn)程的優(yōu)先級(jí)，數(shù)值越低優(yōu)先級(jí)越高。優(yōu)先級(jí)0~99給實(shí)時(shí)進(jìn)程使用，100~139給普通進(jìn)程使用。在用戶空間由一個(gè)傳統(tǒng)的變量nice值映射到普通進(jìn)程的優(yōu)先級(jí)(100~139)。

nice值從-20~19，進(jìn)程默認(rèn)的nice值為0。這可以理解為40個(gè)等級(jí)，nice值越高，則優(yōu)先級(jí)越低，反之亦然。(nice每變化1，則相應(yīng)的進(jìn)程獲得CPU的時(shí)間就改變10%)。

權(quán)重信息即為調(diào)度實(shí)體的權(quán)重，為了計(jì)算方便，內(nèi)核約定nice值為0的權(quán)重值為1024，其他的nice值對(duì)應(yīng)相應(yīng)的權(quán)重值可以通過查表的方式來獲取，表即為prio_to_weight。

問題三：請(qǐng)簡(jiǎn)述CFS調(diào)度器是如何工作的。

CFS調(diào)度器拋棄以前固定時(shí)間片和固定調(diào)度周期的算法，采用進(jìn)程權(quán)重值的比重來量化和計(jì)算實(shí)際運(yùn)行時(shí)間。引入虛擬時(shí)鐘的概念，每個(gè)進(jìn)程的虛擬時(shí)間是實(shí)際運(yùn)行時(shí)間相對(duì)nice值為0的權(quán)重的比例值。進(jìn)程按照各自不同的速率比在物理時(shí)鐘節(jié)拍內(nèi)前進(jìn)。nice值小的進(jìn)程，優(yōu)先級(jí)高且權(quán)重大，其虛擬時(shí)鐘比真實(shí)時(shí)鐘跑得慢，但是可以獲得比較多的運(yùn)行時(shí)間;

反之，nice值大的進(jìn)程，優(yōu)先級(jí)低，權(quán)重也低，其虛擬時(shí)鐘比真實(shí)時(shí)鐘跑得快，獲得比較少的運(yùn)行時(shí)間。CFS調(diào)度器總是選擇虛擬時(shí)鐘跑得慢的進(jìn)程，類似一個(gè)多級(jí)變速箱，nice值為0的進(jìn)程是基準(zhǔn)齒輪，其他各個(gè)進(jìn)程在不同變速比下相互追趕，從而達(dá)到公正公平。

問題四：CFS調(diào)度器中的vruntime是如何計(jì)算的?

vruntime=(delta_exec*nice_0_weight)/weight。其中，delta_exec為實(shí)際運(yùn)行時(shí)間，nice_0_weight為nice為0的權(quán)重值，weight表示該進(jìn)程的權(quán)重值。在update_curr()函數(shù)中，完成了該值的計(jì)算，此時(shí)，為了計(jì)算高效，將計(jì)算方式變成了乘法和移位vruntime=(delta_exec*nice_0_weight*inv_weight)>>shift，其中inv_weight=2^32/weight，是預(yù)先計(jì)算好存放在prio_to_wmult中的。

問題五：vruntime是何時(shí)更新的?

創(chuàng)建新進(jìn)程，加入就緒隊(duì)列，調(diào)度tick等都會(huì)更新當(dāng)前vruntime值。

問題六：CFS調(diào)度器中的min_vruntime有什么作用?

min_vruntime在CFS就緒隊(duì)列數(shù)據(jù)結(jié)構(gòu)中，單步遞增，用于跟蹤該就緒隊(duì)列紅黑樹中最小的vruntime。

問題七：CFS調(diào)度器對(duì)新創(chuàng)建的進(jìn)程和剛喚醒的進(jìn)程有何關(guān)照?

對(duì)于睡眠進(jìn)程，其vruntime在睡眠期間不增長(zhǎng)，在喚醒后如果還用原來的vruntime值，會(huì)進(jìn)行報(bào)復(fù)性滿載運(yùn)行，所以要修正vruntime，具體在enqueue_entity()函數(shù)中，計(jì)算公式為vruntime+=min_vruntime，vruntime=MAX(vruntime, min_vruntime-sysctl_sched_lantency/2)。

對(duì)于新創(chuàng)建的進(jìn)程，需要加上一個(gè)調(diào)度周期的虛擬是時(shí)間(sched_vslice())。首先在task_fork_fair()函數(shù)中，place_entity()增加了調(diào)度周期的虛擬時(shí)間，相當(dāng)于懲罰，se->vruntime=sched_vslice()。

接著新進(jìn)程在添加到就緒隊(duì)列時(shí)，wake_up_new_task()->activate_task()->enqueue_entity()函數(shù)里，se->vruntime+=cfs_rq->min_vruntime。

問題八：如何計(jì)算普通進(jìn)程的平均負(fù)載load_avg_contrib?runnable_avg_sum和runnable_avg_period分別表示了什么含義?

• load_avg_contrib=runnable_avg_sum*weight/runnable_avg_period。
• runnable_avg_sum為調(diào)度實(shí)體的可運(yùn)行狀態(tài)下總衰減累加時(shí)間。
• runnable_avg_period記錄的是上一次更新時(shí)的總周期數(shù)(一個(gè)周期是1024us)，即調(diào)度實(shí)體在調(diào)度器中的總衰減累加時(shí)間。
• runnable_avg_sum越接近runnable_avg_period，則平均負(fù)載越大，表示該調(diào)度實(shí)體一直在占用CPU。

問題九：內(nèi)核代碼中定義了若干個(gè)表，請(qǐng)分別說出它們的含義，比如prio_to_weight、prio_to_wmult、runnable_avg_yN_inv、runnable_avg_yN_sum。

• prio_to_weight表記錄的是nice值對(duì)應(yīng)的權(quán)重值。
• prio_to_wmult表記錄的是nice值對(duì)應(yīng)的權(quán)重值倒轉(zhuǎn)后的值inv_weight=2^32/weight。
• runnable_avg_yN_inv表是為了避免CPU做浮點(diǎn)計(jì)算，提前計(jì)算了公式2^32*實(shí)際衰減因子(第32ms約為0.5)的值，有32個(gè)下標(biāo)，對(duì)應(yīng)過去0~32ms的負(fù)載貢獻(xiàn)的衰減因子。
• runnable_avg_yN_sum表為1024*(y+y^2+…+y^n)，y為實(shí)際衰減因子，n取1~32。

問題十：如果一個(gè)普通進(jìn)程在就緒隊(duì)列里等待了很長(zhǎng)時(shí)間才被調(diào)度，那么它的平均負(fù)載該如何計(jì)算?

一個(gè)進(jìn)程等待很長(zhǎng)時(shí)間之后(過了很多個(gè)period)，原來的runnable_avg_sum和runable_ave_period值衰減后可能變成0，相當(dāng)于之前的統(tǒng)計(jì)值被清0。