在當今數字化時代，操作系統如同復雜交響樂的指揮家，高效協調著計算機系統的各項資源。而多任務處理，無疑是這場交響樂中最激昂的樂章。想象一下，你的電腦在同一時刻流暢運行著辦公軟件、瀏覽器、音樂播放器等多個程序，這背后便是多任務處理的神奇魔力。

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

一、CFS調度器簡介

1. 什么是CFS調度器

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

CFS 調度器的核心使命是為所有運行的任務提供公平的 CPU 時間分配，它就像是一位公正無私的 “時間管家”，精心管理著系統中各個任務對 CPU 時間的使用。在多任務處理的場景下，不同的任務都在競爭 CPU 資源，而 CFS 調度器的存在，確保了每個任務都能在這場資源競爭中獲得合理的時間份額，不會出現某些任務長時間霸占 CPU，而其他任務卻苦苦等待的不公平現象。

2. CFS調度器誕生背景

在 CFS 調度器出現之前，Linux 內核使用的調度器在多任務處理方面存在一些明顯的不足。早期的調度器往往難以在不同類型的任務之間實現精準的平衡，比如在面對交互式任務和計算密集型任務時，就容易顧此失彼。對于交互式任務而言，它們對響應時間極為敏感，用戶期望在進行操作后能立即得到系統反饋，像我們日常使用的圖形界面應用程序，每一次鼠標點擊、鍵盤輸入都希望能即時在屏幕上呈現出結果。而計算密集型任務則更側重于長時間占用 CPU 資源，以高效完成復雜的計算任務，例如科學計算程序、大數據分析任務等 。

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

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

二、CFS調度器實現方式

1. 虛擬運行時間(vruntime)：公平的基石

在 CFS 調度器的公平調度體系中，虛擬運行時間(vruntime)是最為核心的概念，它就像是一把精準的 “公平標尺”，用來衡量每個任務在 CPU 資源競爭中的 “進度”。

CFS 調度器的設計目標是模擬一個理想的多任務 CPU 環境，在這個環境中，所有任務都能以相同的速率并行運行。但在現實中，CPU 資源是有限的，多個任務必須分時復用 CPU。為了實現這種理想的公平狀態，CFS 引入了 vruntime 。它并不是真實的物理時間，而是一個抽象的虛擬時間概念。當一個任務開始執行時，它的 vruntime 會隨著實際執行時間的增加而增長，增長的速度與任務的權重相關。

例如，系統中有兩個任務 A 和 B，任務 A 的權重較高，任務 B 的權重較低。假設任務 A 的權重是任務 B 的兩倍，那么在相同的實際執行時間內，任務 B 的 vruntime 增長速度將是任務 A 的兩倍。這意味著，即使任務 A 和 B 在不同的時間段內執行，但只要它們獲得的 CPU 時間與各自的權重成正比，它們的 vruntime 增長就會保持一種相對的公平性。

當任務執行完畢或者被搶占時，它的 vruntime 就會保持不變，等待下一次被調度執行。在調度決策時，CFS 調度器會從所有就緒任務中，挑選出 vruntime 最小的任務來運行，因為這個任務的 vruntime 最小，說明它之前獲得的 CPU 時間相對較少，受到了 “不公平” 對待，理應在下一輪調度中優先獲得 CPU 資源 。通過這種方式，CFS 調度器不斷地讓各個任務的 vruntime 相互追趕，從而實現了 CPU 時間在不同任務之間的公平分配，確保每個任務都能在合理的時間內得到執行。

在CFS調度器中，虛擬運行時間(virtual runtime)通過每個任務的p->se.vruntime(以納秒單位)來表示和跟蹤，這樣，就可以準確地標記時間戳并測量任務應該獲得的預期 CPU 時間。其中，p指向一個struct task_struct結構體。

/* include/linux/sched.h */

struct sched_entity {
	...
	/*
	 * 進程的虛擬運行時間 = 進程的實際運行時間 / 相對權重
	 *
	 * 進程的 實際運行時間 是一段一段的，所以進程的 虛擬運行時間 也是一段一段增長的。
	 *
	 * 進程的 虛擬運行時間 還會在 進程入隊時 與 運行隊列中的最小虛擬時間 相比較，如
	 * 果更小的話會直接進行增加，并不對應 實際的運行時間。為什么要這么做呢？因為有的
	 * 進程可能會因長時間睡眠，導致其 虛擬運行時間 小于運行隊列中所有進程中的 最小虛
	 * 擬運行時間，這樣的進程一旦運行起來，會因為其 虛擬運行時間 小，占據 CPU 的時間
	 * 就會長，對其它進程就不公平了。
	 */
	u64				vruntime;
	...
};

struct task_struct {
	...
	const struct sched_class	*sched_class; /* 如果任務使用 CFS 調度，則為 &fair_sched_class */
	struct sched_entity		se; /* CFS 類進程調度參數 */
	...
};

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

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

2. 權重(Weight)：優先級的體現

在 CFS 調度器中，任務的權重是決定其優先級的關鍵因素，而權重又與任務的 nice 值緊密相關。nice 值是 Linux 系統中用于調整進程優先級的一個參數，它的取值范圍通常是 -20 到 19 ，數值越小，表示任務的優先級越高 。通過 nice 值與權重的映射關系，CFS 調度器能夠為不同優先級的任務分配不同的權重。

具體來說，低 nice 值的任務具有較高的優先級，相應地，它們也會被賦予較大的權重。這就好比一場比賽中，實力更強(優先級更高)的選手會得到更多的資源支持(更大的權重)。當一個任務具有較大的權重時，在相同的實際執行時間內，它的 vruntime 增長速度會相對較慢。例如，有任務 C 和任務 D，任務 C 的 nice 值較低，權重較大，任務 D 的 nice 值較高，權重較小。在同樣運行 10 毫秒的情況下，任務 D 的 vruntime 增加量會大于任務 C，這使得任務 C 在調度競爭中更具優勢，能夠獲得更多的 CPU 執行時間。

這種通過權重調整 vruntime 增長速度的機制，不僅保證了高優先級任務能夠優先獲得 CPU 資源，同時也兼顧了低優先級任務的執行機會，避免了低優先級任務長時間得不到調度而 “餓死” 的情況。CFS 調度器就像一位經驗豐富的資源分配者，在高優先級任務和低優先級任務之間找到了一個平衡點，讓系統中的所有任務都能在這個公平的調度框架下有序運行。

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

為了高效地管理就緒隊列中的任務，CFS 調度器采用了紅黑樹這種數據結構。紅黑樹是一種自平衡的二叉查找樹，它具有高效的插入、刪除和查找操作特性，這使得 CFS 調度器能夠快速地對任務進行管理和調度決策。

在 CFS 調度器中，紅黑樹的每個節點都對應一個任務，節點中的關鍵值就是任務的 vruntime 。當一個新任務進入就緒隊列時，它會根據自己的 vruntime 被插入到紅黑樹的合適位置;當任務執行完畢或者被搶占時，它會從紅黑樹中刪除。紅黑樹的自平衡特性保證了樹的高度始終保持在一個較低的水平，從而確保了插入、刪除和查找操作的時間復雜度始終保持在 O (log n)，這里的 n 是紅黑樹中節點的數量 。

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

CFS 需要高效的數據結構來跟蹤任務信息，需要高性能的代碼來產生調度。讓我們從調度中的一個中心術語開始，即運行隊列(runqueue)。運行隊列(runqueue)是一個數據結構，表示被調度任務的時間線。盡管有這個名字，但運行隊列不需要以傳統方式實現，如實現為一個 FIFO 列表。CFS 打破了傳統，它不使用運行隊列以往的舊數據結構，而是使用按時間排序的紅黑樹(red-black tree)作為可運行任務隊列，來構建未來任務執行的時間線。

紅黑樹非常適合這項工作，因為它是一個自平衡的二叉搜索樹，具有高效的插入和刪除操作，在 O(log N) 時間內執行，其中 N 是樹中的節點數。此外，樹是一種出色的數據結構，用于根據特定屬性(在 CFS 中為 vruntime)將實體組織到層次結構中。

在 CFS 中，樹的內部節點表示要調度的任務，而樹作為一個整體(與任何運行隊列一樣)表示任務執行的時間線。紅黑樹被廣泛使用，還用于任務調度之外，例如，Java 使用此數據結構來實現其樹狀圖。

在 CFS 下，每個處理器都有一個自己特定的任務運行隊列，同一任務某一時刻只會位于某個運行隊列中。每個運行隊列都是一棵紅黑樹。樹的內部節點表示任務或任務組，這些節點按其 vruntime 值索引，因此(在整個樹或任何子樹中)左側內部節點的 vruntime 值低于右側節點：

    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 的任務(因此對處理器的需求最大)位于左側子樹的某個位置;具有相對較高的 vruntimes 的任務聚集在右側子樹中。搶占的任務將進入右側子樹，從而使其他任務有機會在樹中向左移動。具有最小 vruntime 的任務最終出現在樹的最左側(內部)節點中，因此該節點位于運行隊列的前面。

/* kernel/sched/sched.h */

/* CFS-related fields in a runqueue */
struct cfs_rq {
	...
	u64 min_vruntime; /* CFS 調度算法 運行隊列中 進程 的 最小 虛擬運行時間 */
	...
	/*
	 * CFS 進程 運行隊列 紅黑樹 根節點: 
	 * 按進程的 vruntime 為鍵值進行排序。 
	 */
	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 的運行隊列 */

紅黑樹的每個內部節點都有指向父節點和兩個子節點的指針，葉節點的值為NULL：

struct rb_node {
	unsigned long  __rb_parent_color; /* 父節點顏色: 紅 或 黑 */
	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 調度器用 task_struct 來描述一個任務，task_struct 用于跟蹤有關要調度的每個任務的詳細信息。此結構嵌入了一個 sched_entity 結構，該結構又具有特定于調度的信息，特別是每個任務或任務組的 vruntime，即 rq->cfs.min_vruntime 值，該值是一個單調遞增值，用于跟蹤運行隊列中所有任務中的最小 vruntime。該值用于盡可能將新激活的調度實體(struct sched_entity，即任務)放置在紅黑樹的左側。由于該值一直使用 min_vruntime 單調遞增累加，所以也可用來跟蹤系統完成的工作總量。

/* include/linux/sched.h */

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

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

運行隊列的權重通過rq->cfs.load值進行統計，該值是運行隊列上排隊的任務權重的總和：

/* kernel/sched/sched.h */

/* CFS-related fields in a runqueue */
struct cfs_rq {
	/*
	 * 運行隊列的權重, 等于其上所有進程的權重之和。
	 * 進程在入隊出隊時，也會相應地從運行隊列中加上減去其自身的權重。
	 */
	struct load_weight load;
	...
};

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

創建新任務時，將它們插入紅黑樹，初始 vruntime 值賦為 min_vruntime，使得它們盡可能快的得到執行：vruntime 越小，越快得到執行。

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

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

在多核處理器系統中，為了充分發揮多核的性能優勢，CFS 調度器需要進行負載均衡操作，確保任務能夠在各個 CPU 核心之間均勻分布，避免出現某些 CPU 核心負載過重，而其他 CPU 核心閑置的情況。CFS 調度器通過調度域(scheduling domains)和調度組(sched_groups)來實現負載均衡。

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

CFS 調度器會周期性地執行負載均衡操作，監控各個調度組和 CPU 核心的負載情況。當發現某個調度組或 CPU 核心的負載過高時，調度器會將部分任務從高負載的調度組或 CPU 核心遷移到低負載的調度組或 CPU 核心上，實現負載的均衡分布。在進行任務遷移時，CFS 調度器還會考慮任務的 CPU 親和性(CPU Affinity)，盡量將任務分配到它們偏好的 CPU 核心上，同時仍然保持整體的負載均衡。

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

三、CFS調度器的調度策略

CFS 調度器針對不同類型的任務，提供了多種調度策略，以滿足多樣化的系統需求。這些調度策略就像是為不同類型的 “選手” 量身定制的比賽規則，確保每個任務都能在最合適的規則下參與 CPU 資源的競爭。

1. SCHED_NORMAL(SCHED_OTHER)

SCHED_NORMAL，也被稱為 SCHED_OTHER ，是 CFS 調度器中最為常用的調度策略，適用于大多數普通的用戶級交互式任務 。像我們日常使用的圖形界面應用程序、辦公軟件、瀏覽器等，這些需要與用戶頻繁交互的任務，都采用了這種調度策略。

在 SCHED_NORMAL 策略下，任務的執行優先級主要由其 nice 值決定。nice 值的取值范圍是 -20 到 19 ，數值越小，任務的優先級越高。系統會根據任務的 nice 值，為其分配相應的 CPU 時間份額。例如，當我們在電腦上同時打開瀏覽器瀏覽網頁，又運行一個文本編輯軟件進行文字處理時，由于這兩個任務都屬于交互式任務，它們的 nice 值默認可能都是 0 。在這種情況下，CFS 調度器會按照公平的原則，為它們分配大致相等的 CPU 時間，使得我們在操作瀏覽器切換頁面時，不會感覺到文本編輯軟件的響應受到明顯影響，反之亦然，從而保證了用戶在使用這些交互式應用時，能夠獲得流暢、及時的體驗 。

2. SCHED_BATCH

SCHED_BATCH 調度策略主要適用于那些非交互式的批處理任務 ，這類任務通常不需要與用戶進行實時交互，它們更注重任務的整體運行效率，而不是對用戶輸入的即時響應。比如一些長時間運行的計算任務，如大數據分析、科學計算程序等。這些任務往往需要大量的 CPU 計算資源，如果它們與交互式任務采用相同的調度策略，可能會因為頻繁的上下文切換，導致 CPU 緩存命中率降低，從而影響整體的計算效率。

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

3. SCHED_IDLE

SCHED_IDLE 是 CFS 調度器中優先級最低的調度策略，它僅在系統處于空閑狀態時才會運行 。這類任務通常是一些對系統性能影響極小，且不需要及時執行的后臺服務，比如系統的一些定期清理任務、日志統計任務等。這些任務的特點是即使延遲執行，也不會對系統的正常運行和用戶體驗產生明顯的影響。

SCHED_IDLE 任務的權重非常低，這使得它們在與其他任務競爭 CPU 資源時，幾乎沒有優勢。當系統中存在其他優先級較高的任務時，SCHED_IDLE 任務會被調度器 “冷落”，幾乎得不到 CPU 的執行時間。只有當系統中所有其他任務都處于等待狀態，CPU 資源完全空閑時，SCHED_IDLE 任務才會有機會被調度執行 。例如，當我們的電腦在一段時間內沒有任何用戶操作，系統處于空閑狀態時，那些采用 SCHED_IDLE 調度策略的后臺清理任務就會開始運行，對系統中的臨時文件、緩存數據等進行清理，為系統的下一次高效運行做好準備，而在系統忙碌時，這些任務則會自動 “讓路”，避免占用寶貴的 CPU 資源，確保其他重要任務的順利執行。

四、CFS調度器常見問題

問題一：請簡述對進程調度器的理解，早起Linux內核調度器(包括O(N)和O(1))調度器是如何工作的?

調度器是按一定的方式對進程進行調度的一種機制，需要為各個普通進程盡可能公平地共享CPU時間。

O(N)調度器發布與1992年，從就緒隊列中比較所有進程的優先級，然后選擇一個最高優先級的進程作為下一個調度進程。每一個進程有一個固定時間片，當進程時間片使用完之后，調度器會選擇下一個調度進程，當所有進程都運行一遍后再重新分配時間片。這個調度器選擇下一個調度進程前需要遍歷整個就緒隊列，花費O(N)時間。

O(1)調度器用于Linux2.6.23內核之前，它為每個CPU維護一組進程優先級隊列，每個優先級一個隊列，這樣在選擇下一個進程時，只要查詢優先級隊列相應的位圖即可知道哪個隊列中有就緒進程，查詢時間常數為O(1)。

問題二：請簡述進程優先級、nice和權重之間的關系。

內核使用0~139的數值表示進程的優先級，數值越低優先級越高。優先級0~99給實時進程使用，100~139給普通進程使用。在用戶空間由一個傳統的變量nice值映射到普通進程的優先級(100~139)。

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

權重信息即為調度實體的權重，為了計算方便，內核約定nice值為0的權重值為1024，其他的nice值對應相應的權重值可以通過查表的方式來獲取，表即為prio_to_weight。

問題三：請簡述CFS調度器是如何工作的。

CFS調度器拋棄以前固定時間片和固定調度周期的算法，采用進程權重值的比重來量化和計算實際運行時間。引入虛擬時鐘的概念，每個進程的虛擬時間是實際運行時間相對nice值為0的權重的比例值。進程按照各自不同的速率比在物理時鐘節拍內前進。nice值小的進程，優先級高且權重大，其虛擬時鐘比真實時鐘跑得慢，但是可以獲得比較多的運行時間;

反之，nice值大的進程，優先級低，權重也低，其虛擬時鐘比真實時鐘跑得快，獲得比較少的運行時間。CFS調度器總是選擇虛擬時鐘跑得慢的進程，類似一個多級變速箱，nice值為0的進程是基準齒輪，其他各個進程在不同變速比下相互追趕，從而達到公正公平。

問題四：CFS調度器中的vruntime是如何計算的?

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

問題五：vruntime是何時更新的?

創建新進程，加入就緒隊列，調度tick等都會更新當前vruntime值。

問題六：CFS調度器中的min_vruntime有什么作用?

min_vruntime在CFS就緒隊列數據結構中，單步遞增，用于跟蹤該就緒隊列紅黑樹中最小的vruntime。

問題七：CFS調度器對新創建的進程和剛喚醒的進程有何關照?

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

對于新創建的進程，需要加上一個調度周期的虛擬是時間(sched_vslice())。首先在task_fork_fair()函數中，place_entity()增加了調度周期的虛擬時間，相當于懲罰，se->vruntime=sched_vslice()。

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

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

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

問題九：內核代碼中定義了若干個表，請分別說出它們的含義，比如prio_to_weight、prio_to_wmult、runnable_avg_yN_inv、runnable_avg_yN_sum。

• prio_to_weight表記錄的是nice值對應的權重值。
• prio_to_wmult表記錄的是nice值對應的權重值倒轉后的值inv_weight=2^32/weight。
• runnable_avg_yN_inv表是為了避免CPU做浮點計算，提前計算了公式2^32*實際衰減因子(第32ms約為0.5)的值，有32個下標，對應過去0~32ms的負載貢獻的衰減因子。
• runnable_avg_yN_sum表為1024*(y+y^2+…+y^n)，y為實際衰減因子，n取1~32。

問題十：如果一個普通進程在就緒隊列里等待了很長時間才被調度，那么它的平均負載該如何計算?

一個進程等待很長時間之后(過了很多個period)，原來的runnable_avg_sum和runable_ave_period值衰減后可能變成0，相當于之前的統計值被清0。