點(diǎn)擊「閱讀原文」查看良許原創(chuàng)精品視頻。

本文就看下內(nèi)核態(tài)是如何對(duì) task 進(jìn)行調(diào)度的。

調(diào)度的發(fā)展歷史

O(n)算法雖然歷史有點(diǎn)悠久，但很有必要研究，是后續(xù)O(1)等算法理解的基礎(chǔ)。由于O(n)不是本文重點(diǎn)，建議先去網(wǎng)上了解相關(guān)知識(shí)點(diǎn)。

O(1) 調(diào)度器:

O(1) 調(diào)度器中引入了per-CPU runqueue的概念。系統(tǒng)中所有的可運(yùn)行狀態(tài)的進(jìn)程首先經(jīng)過(guò)負(fù)載均衡模塊掛入各個(gè)CPU的runqueue，每隔 200ms，處理器都會(huì)檢查 CPU 的負(fù)載是否不均衡，如果不均衡，處理器就會(huì)在 CPU 之間進(jìn)行一次任務(wù)均衡操作。然后由主調(diào)度器和tick調(diào)度器驅(qū)動(dòng)該CPU上的調(diào)度行為。每一個(gè)優(yōu)先級(jí)的進(jìn)程被掛入不同鏈表中。

上圖說(shuō)明了 task 與負(fù)載均衡和 runqueue 以及對(duì)應(yīng)調(diào)度器之間的關(guān)系。每個(gè) runqueue 里又會(huì)分為active和expired隊(duì)列，每個(gè)隊(duì)列中掛載著140個(gè)優(yōu)先級(jí)不同的 task 。關(guān)于調(diào)度器在 runqueue 里的算法實(shí)現(xiàn)我們看下面一張圖：

來(lái)自網(wǎng)絡(luò)

可以看出2.6 kernel 里有 140 種優(yōu)先級(jí)，所以我們就用長(zhǎng)度為 140 的 array 去記錄優(yōu)先級(jí)。每個(gè)優(yōu)先級(jí)下面用一個(gè) FIFO queue 管理這個(gè)優(yōu)先級(jí)下的 process。

那么，我們?cè)趺凑业疆?dāng)前最高優(yōu)先級(jí)下面的可執(zhí)行的 process 呢？如果從 0 開(kāi)始一直遍歷下去，算法雖然不是 O(N)，但是是跟優(yōu)先級(jí)多少相關(guān)的 O(M)，也不能算作 O(1)。在 2.6 scheduler 里，采用 bitarray。它為每種優(yōu)先級(jí)分配一個(gè) bit，如果這個(gè)優(yōu)先級(jí)隊(duì)列下面有 process，那么就對(duì)相應(yīng)的 bit 染色，置為 1，否則置為 0。問(wèn)題就簡(jiǎn)化成尋找一個(gè) bitarray 里面最高位是 1 的 bit（left-most bit），這基本上是一條 CPU 指令的事（fls）

大致的思路齊備，我們來(lái)整理下步驟：

在 active bitarray 里，尋找 left-most bit 的位置 x。
在 active priority array（APA）中，找到對(duì)應(yīng)隊(duì)列 APA[x]。
從 APA[x] 中 dequeue 一個(gè) process，dequeue 后，如果 APA[x] 的 queue 為空，那么將 active bitarray 里第 x bit置為 0。
對(duì)于當(dāng)前執(zhí)行完的 process，重新計(jì)算其 priority，然后 enqueue 到 expired priority array（EPA）相應(yīng)的隊(duì)里 EPA[priority]。
如果 priority 在 expired bitarray 里對(duì)應(yīng)的 bit 為 0，將其置 1。
如果 active bitarray 全為零，將 active bitarray 和 expired bitarray 交換一下。

CFS 調(diào)度器:

虛擬時(shí)間：

比如，調(diào)度周期是12ms，2個(gè)相同優(yōu)先級(jí)的進(jìn)程A和B，那么每個(gè)進(jìn)程的運(yùn)行時(shí)間各為6ms。倘若進(jìn)程A,B的優(yōu)先級(jí)nice分別為0和1，那么權(quán)重分別是1024和820。它們的關(guān)系如下：

權(quán)重 = 1024 / 1.25nice(次方)

那么進(jìn)程A獲取的運(yùn)行時(shí)間是12x1024/(1024+820)=6.66ms，進(jìn)程B獲取的運(yùn)行時(shí)間是12x820/(1024+820)=5.34ms。進(jìn)程A的cpu使用比例是6.66/10=66.6%，進(jìn)程B的cpu使用比例是5.34/10=53.4%。這里我們看到2個(gè)進(jìn)程的執(zhí)行時(shí)間分別是6.66ms和5.34ms，是不一樣的。但是CFS是想讓每個(gè)進(jìn)程完全公平調(diào)度，這里就引入一個(gè)概念——虛擬時(shí)間，CFS也是通過(guò)虛擬時(shí)間相等來(lái)保證調(diào)度公平的。虛擬時(shí)間vriture_runtime和實(shí)際時(shí)間wall time轉(zhuǎn)換公式如下：

虛擬時(shí)間 = 實(shí)際時(shí)間 * (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)重

可以看出雖然進(jìn)程的權(quán)重不同，但是它們的 vruntime增長(zhǎng)速度應(yīng)該是一樣的，與權(quán)重?zé)o關(guān)。（進(jìn)程A的虛擬時(shí)間=6.66 *（1024/1024）= 6.66ms，進(jìn)程B的虛擬時(shí)間=5.34 *（1024/820）= 6.66ms。這里我們看出雖然進(jìn)程的優(yōu)先級(jí)不同，但最終的虛擬時(shí)間一樣。）

總結(jié)：誰(shuí)的vruntime值較小就說(shuō)明它當(dāng)前占用cpu的時(shí)間較短，受到了“不公平”對(duì)待，因此下一個(gè)運(yùn)行進(jìn)程就是它。這樣既能公平選擇進(jìn)程，又能保證高優(yōu)先級(jí)進(jìn)程獲得較多的運(yùn)行時(shí)間。這就是CFS的主要思想了。

就緒隊(duì)列（runqueue）:

CFS維護(hù)了一個(gè)按照虛擬時(shí)間排序的紅黑樹(shù)：

任務(wù)存儲(chǔ)在以時(shí)間為順序的紅黑樹(shù)中（由 sched_entity 對(duì)象表示），對(duì)處理器需求最多的任務(wù) （最低虛擬運(yùn)行時(shí)）存儲(chǔ)在樹(shù)的左側(cè)，處理器需求最少的任務(wù)（最高虛擬運(yùn)行時(shí)）存儲(chǔ)在樹(shù)的右側(cè)。為了公平，調(diào)度器然后選取紅黑樹(shù)最左端的節(jié)點(diǎn)調(diào)度為下一個(gè)以便保持公平性。任務(wù)通過(guò)將其運(yùn)行時(shí)間添加到虛擬運(yùn)行時(shí)，說(shuō)明其占用 CPU 的時(shí)間，然后如果可運(yùn)行，再插回到樹(shù)中。這樣，樹(shù)左側(cè)的任務(wù)就被給予時(shí)間運(yùn)行了，樹(shù)的內(nèi)容從右側(cè)遷移到左側(cè)以保持公平。因此，每個(gè)可運(yùn)行的任務(wù)都會(huì)追趕其他任務(wù)以維持整個(gè)可運(yùn)行任務(wù)集合的執(zhí)行平衡。

良許個(gè)人微信

添加良許個(gè)人微信即送3套程序員必讀資料

→ 精選技術(shù)資料共享

→ 高手如云交流社群

本公眾號(hào)全部博文已整理成一個(gè)目錄，請(qǐng)?jiān)诠娞?hào)里回復(fù)「m」獲取！

Linux 是如何調(diào)度進(jìn)程的？

點(diǎn)擊「閱讀原文」查看良許原創(chuàng)精品視頻。