• linux 進(jìn)程調(diào)度算法經(jīng)歷了以下幾個版本的發(fā)展：

1. 基于時間片輪詢調(diào)度算法。(2.6之前的版本)

2. O(1) 調(diào)度算法。(2.6.23之前的版本)

3. 完全公平調(diào)度算法。(2.6.23以及之后的版本)

• 這篇主要分析 Linux 現(xiàn)在所使用的 完全公平調(diào)度算法。

• 分析 完全公平調(diào)度算法 前，我們先了解下 完全公平調(diào)度算法 的基本原理。

完全公平調(diào)度算法基本原理

• 完全公平調(diào)度算法 體現(xiàn)在對待每個進(jìn)程都是公平的，那么怎么才能做到完全公平呢？有一個比較簡單的方法就是：讓每個進(jìn)程都運行一段相同的時間片，這就是 基于時間片輪詢調(diào)度算法。如下圖所示：

• 如上圖所示，開始時進(jìn)程1獲得 time0 ~ time1 的CPU運行時間。當(dāng)進(jìn)程1的時間片使用完后，進(jìn)程2獲得 time1 ~ time2 的CPU運行時間。而當(dāng)進(jìn)程2的時間片使用完后，進(jìn)程3獲得 time2 ~ time3 的CPU運行時間。

• 如此類推，由于每個時間片都是相等的，所以理論上每個進(jìn)程都能獲得相同的CPU運行時間。這個算法看起來很不錯，但存在兩個問題：

1. 不能按權(quán)重分配不同的運行時間，例如有些進(jìn)程權(quán)重大的應(yīng)該獲得更多的運行時間。

2. 每次調(diào)度時都需要遍歷運行隊列中的所有進(jìn)程，找到優(yōu)先級最大的進(jìn)程運行，時間復(fù)雜度為 O(n)。對于一個高性能的操作系統(tǒng)來說，這是不能接受的。

• 為了解決上面兩個問題，Linux內(nèi)核的開發(fā)者創(chuàng)造了 完全公平調(diào)度算法。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。?！前100名進(jìn)群領(lǐng)取，額外贈送一份價值699的內(nèi)核資料包（含視頻教程、電子書、實戰(zhàn)項目及代碼)? ??

完全公平調(diào)度的兩個時間

• 為了實現(xiàn) 完全公平調(diào)度算法，為進(jìn)程定義兩個時間:

1. 實際運行時間：

實際運行時間 = 調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和

• 調(diào)度周期：是指所有可進(jìn)程運行一遍所需要的時間。

• 進(jìn)程權(quán)重：依據(jù)進(jìn)程的重要性，分配給每個進(jìn)程不同的權(quán)重。

例如，調(diào)度周期為 30ms，進(jìn)程A的權(quán)重為 1，而進(jìn)程B的權(quán)重為 2。

那么：進(jìn)程A的實際運行時間為：30ms * 1 / (1 + 2) = 10ms進(jìn)程B的實際運行時間為：30ms * 2 / (1 + 2) = 20ms

2. 虛擬運行時間：

虛擬運行時間 = 實際運行時間?

* 1024 / 進(jìn)程權(quán)重 = (調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和)?

* 1024 / 進(jìn)程權(quán)重 = 調(diào)度周期?

* 1024 / 所有進(jìn)程總權(quán)重

• 從上面的公式可以看出，在一個調(diào)度周期里，所有進(jìn)程的 虛擬運行時間 是相同的。所以在進(jìn)程調(diào)度時，只需要找到 虛擬運行時間 最小的進(jìn)程調(diào)度運行即可。

• 為了能夠快速找到 虛擬運行時間 最小的進(jìn)程，Linux 內(nèi)核使用 紅黑樹 來保存可運行的進(jìn)程，而比較的鍵值就是進(jìn)程的 虛擬運行時間。

• 如果不了解 紅黑樹 的話，可以把它看成一個自動排序的容器即可。如下圖所示：

• 如上圖所示，紅黑樹 的左節(jié)點比父節(jié)點小，而右節(jié)點比父節(jié)點大。所以查找最小節(jié)點時，只需要獲取 紅黑樹 的最左節(jié)點即可，時間復(fù)雜度為 O(logN)。

完全公平調(diào)度的兩個對象

• Linux 內(nèi)核為了實現(xiàn) 完全公平調(diào)度算法，定義兩個對象：cfs_rq (可運行進(jìn)程隊列) 和 sched_entity (調(diào)度實體)。

1. cfs_rq (可運行進(jìn)程隊列)：使用 紅黑樹 結(jié)構(gòu)來保存內(nèi)核中可以運行的進(jìn)程。

2. sched_entity (調(diào)度實體)：可被內(nèi)核調(diào)度的實體，如果忽略組調(diào)度（本文也不涉及組調(diào)度），可以把它當(dāng)成是進(jìn)程。

• cfs_rq 對象定義

• 對于 cfs_rq 對象，現(xiàn)在主要關(guān)注的是 tasks_timeline 成員，其保存了可運行進(jìn)程隊列的根節(jié)點（紅黑樹的根節(jié)點）。

• sched_entity 對象定義

• 對于 sched_entity 對象，現(xiàn)在主要關(guān)注的是 run_node 成員，其主要用于把調(diào)度實體連接到可運行進(jìn)程的隊列中。

• 另外，進(jìn)程描述符 task_struct 對象中，定義了一個類型為 sched_entity 的成員變量 se，如下：

struct task_struct { ? ?... ? ?struct sched_entity se; ? ?... }

• 所以，他們之間的關(guān)系如下圖：

• 從上圖可以看出，所有 sched_entity 對象通過其 run_node 成員組成了一顆紅黑樹，這顆紅黑樹的根結(jié)點保存在 cfs_rq 對象的 task_timeline 成員中。

• 另外，進(jìn)程描述符 task_sturct 定義了一個類型為 sched_entity 的成員變量 se，所以通過進(jìn)程描述符的 se 字段就可以把進(jìn)程保存到可運行隊列中。

完全公平調(diào)度算法實現(xiàn)

• 有了上面的基礎(chǔ)，現(xiàn)在可以開始分析 Linux 內(nèi)核中怎么實現(xiàn) 完全公平調(diào)度算法 了。

• 我們先來看看怎么更新一個進(jìn)程的虛擬運行時間。

1. 更新進(jìn)程虛擬運行時間

• 更新一個進(jìn)程的虛擬運行時間是通過 __update_curr() 函數(shù)完成的，其代碼如下：

/src/kernel/sched_fair.c

• __update_curr() 函數(shù)各個參數(shù)意義如下：

1. cfs_rq：可運行隊列對象。

2. curr：當(dāng)前進(jìn)程調(diào)度實體。

3. delta_exec：實際運行的時間。

• __update_curr() 函數(shù)主要完成以下幾個工作：

1. 更新進(jìn)程調(diào)度實體的總實際運行時間。

2. 根據(jù)進(jìn)程調(diào)度實體的權(quán)重值，計算其使用的虛擬運行時間。

3. 把計算虛擬運行時間的結(jié)果添加到進(jìn)程調(diào)度實體的 vruntime 字段。

• 我們接著分析怎么把進(jìn)程添加到運行隊列中。

2. 把進(jìn)程調(diào)度實體添加到運行隊列中

• 要將進(jìn)程調(diào)度實體添加到運行隊列中，可以調(diào)用 __enqueue_entity() 函數(shù)，其實現(xiàn)如下：

/src/kernel/sched_fair.c

• __enqueue_entity() 函數(shù)的主要工作如下：

1. 獲取運行隊列紅黑樹的根節(jié)點。

2. 獲取當(dāng)前進(jìn)程調(diào)度實體的虛擬運行時間。

3. 把當(dāng)前進(jìn)程調(diào)度實體添加到紅黑樹中（可參考紅黑樹的插入算法）。

4. 緩存紅黑樹最左端節(jié)點。

5. 對紅黑樹進(jìn)行平衡操作（可參考紅黑樹的平衡算法）。

• 調(diào)用 __enqueue_entity() 函數(shù)后，就可以把進(jìn)程調(diào)度實體插入到運行隊列的紅黑樹中。同時會把紅黑樹最左端的節(jié)點緩存到運行隊列的 rb_leftmost 字段中，用于快速獲取下一個可運行的進(jìn)程。

3. 從可運行隊列中獲取下一個可運行的進(jìn)程

• 要獲取運行隊列中下一個可運行的進(jìn)程可以通過調(diào)用 __pick_next_entity() 函數(shù)，其實現(xiàn)如下：

/src/kernel/sched_fair.c

• 前面介紹過，紅黑樹的最左端節(jié)點就是虛擬運行時間最少的進(jìn)程，所以 __pick_next_entity() 函數(shù)的流程就非常簡單了，如下：

1. 首先調(diào)用 first_fair() 獲取紅黑樹最左端節(jié)點。

2. 然后再調(diào)用 rb_entry() 返回節(jié)點對應(yīng)的調(diào)度實體。

調(diào)度時機

• 前面介紹了 完全公平調(diào)度算法 怎么向可運行隊列添加調(diào)度的進(jìn)程和怎么從可運行隊列中獲取下一個可運行的進(jìn)程，那么 Linux 內(nèi)核在什么時候會進(jìn)行進(jìn)程調(diào)度呢？

答案是由 Linux 內(nèi)核的時鐘中斷觸發(fā)的。

• 時鐘中斷 是什么？如果沒了解過操作系統(tǒng)原理的可能不了解這個東西，但是沒關(guān)系，不了解可以把他當(dāng)成是定時器就好了，就是每隔固定一段時間會調(diào)用一個回調(diào)函數(shù)來處理這個事件。

• 時鐘中斷 猶如 Linux 的心臟一樣，每隔一定的時間就會觸發(fā)調(diào)用 scheduler_tick() 函數(shù)，其實現(xiàn)如下：

• scheduler_tick() 函數(shù)會調(diào)用 task_tick_fair() 函數(shù)處理調(diào)度相關(guān)的工作，而 task_tick_fair() 主要通過調(diào)用 entity_tick() 來完成調(diào)度工作的，調(diào)用鏈如下：

scheduler_tick() -> task_tick_fair() -> entity_tick()

• entity_tick() 函數(shù)實現(xiàn)如下：

• entity_tick() 函數(shù)主要完成以下工作：

1. 調(diào)用 update_curr() 函數(shù)更新進(jìn)程的虛擬運行時間，這個前面已經(jīng)介紹過。

2. 調(diào)用 check_preempt_tick() 函數(shù)判斷是否需要進(jìn)行進(jìn)程調(diào)度。

• 我們接著分析 check_preempt_tick() 函數(shù)的實現(xiàn)：

• check_preempt_tick() 函數(shù)主要完成以下工作：

1. 通過調(diào)用 sched_slice() 計算當(dāng)前進(jìn)程可用的時間片。

2. 獲取當(dāng)前進(jìn)程在當(dāng)前調(diào)度周期實際已運行的時間。

3. 如果進(jìn)程實際運行的時間大于其可用時間片, 那么調(diào)用 resched_task() 函數(shù)進(jìn)行進(jìn)程調(diào)度。

• 可以看出，在 時鐘中斷 的處理中，有可能會進(jìn)行進(jìn)程調(diào)度。除了 時鐘中斷 外，一些主動讓出 CPU 的操作也會進(jìn)行進(jìn)程調(diào)度（如一些 I/O 操作），這里就不詳細(xì)分析了，有興趣可以自己研究。