[[398959]]

本文轉(zhuǎn)載自微信公眾號(hào)「人人都是極客」，作者布道師Peter。轉(zhuǎn)載本文請(qǐng)聯(lián)系人人都是極客公眾號(hào)。

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

• O(n) 調(diào)度器是在內(nèi)核2.4以及更早期版本采用的算法，其調(diào)度算法非常簡(jiǎn)單和直接，就緒隊(duì)列是個(gè)全局列表，從就緒隊(duì)列中查找下一個(gè)最佳任務(wù)，由于每次在尋找下一個(gè)任務(wù)時(shí)需要遍歷系統(tǒng)中所有的任務(wù)(全局列表)，因此被稱(chēng)為 O(n) 調(diào)度器(時(shí)間復(fù)雜度)。
• 內(nèi)核2.6采用了O(1) 調(diào)度器，讓每個(gè)CPU維護(hù)一個(gè)自己的就緒隊(duì)列，從而減少了鎖的競(jìng)爭(zhēng)。就緒隊(duì)列由兩個(gè)優(yōu)先級(jí)數(shù)組組成，分別是active優(yōu)先級(jí)數(shù)組和expired優(yōu)先級(jí)數(shù)組。每個(gè)優(yōu)先級(jí)數(shù)組包含140個(gè)優(yōu)先級(jí)隊(duì)列，也就是每個(gè)優(yōu)先級(jí)對(duì)應(yīng)一個(gè)隊(duì)列，其中前100個(gè)對(duì)應(yīng)實(shí)時(shí)進(jìn)程，后40個(gè)對(duì)應(yīng)普通進(jìn)程。如下圖所示：

這樣設(shè)計(jì)的好處，調(diào)度器選擇下一個(gè)被調(diào)度任務(wù)就變得高效和簡(jiǎn)單多了，只需要在active優(yōu)先級(jí)數(shù)組中選擇優(yōu)先級(jí)高，并且隊(duì)列中有可運(yùn)行的任務(wù)即可。這里使用位圖來(lái)定義該隊(duì)列中是否有可運(yùn)行的任務(wù)，如果有，則位圖中相應(yīng)的位就會(huì)被置1。這樣選擇下一個(gè)被調(diào)用任務(wù)的時(shí)間就變成了查詢(xún)位圖的操作。

• 但上面的算法有個(gè)問(wèn)題，一個(gè)高優(yōu)先級(jí)多線(xiàn)程的應(yīng)用會(huì)比低優(yōu)先級(jí)單線(xiàn)程的應(yīng)用獲得更多的資源，這就會(huì)導(dǎo)致一個(gè)調(diào)度周期內(nèi)，低優(yōu)先級(jí)的應(yīng)用可能一直無(wú)法響應(yīng)，直到高優(yōu)先級(jí)應(yīng)用結(jié)束。CFS調(diào)度器就是站在一視同仁的角度解決了這個(gè)問(wèn)題，保證在一個(gè)調(diào)度周期內(nèi)每個(gè)任務(wù)都有執(zhí)行的機(jī)會(huì)，執(zhí)行時(shí)間的長(zhǎng)短，取決于任務(wù)的權(quán)重。下面詳細(xì)看下CFS調(diào)度器是如何動(dòng)態(tài)調(diào)整任務(wù)的運(yùn)行時(shí)間，達(dá)到公平調(diào)度的。

實(shí)際運(yùn)行時(shí)間

CFS是Completely Fair Scheduler簡(jiǎn)稱(chēng)，即完全公平調(diào)度器。CFS調(diào)度器和以往的調(diào)度器不同之處在于沒(méi)有時(shí)間片的概念，而是公平分配cpu使用的時(shí)間。例如：2個(gè)相同優(yōu)先級(jí)的進(jìn)程在一個(gè)cpu上運(yùn)行，那么每個(gè)進(jìn)程都將會(huì)分配50%的cpu運(yùn)行時(shí)間。這就是要實(shí)現(xiàn)的公平。

但現(xiàn)實(shí)中，必然是有的進(jìn)程優(yōu)先級(jí)高，有的進(jìn)程優(yōu)先級(jí)低。CFS調(diào)度器引入權(quán)重的概念，用權(quán)重代表進(jìn)程的優(yōu)先級(jí)，各個(gè)進(jìn)程按照權(quán)重的比例分配cpu的時(shí)間。比如：2個(gè)進(jìn)程A和B。A的權(quán)重是1024，B的權(quán)重是2048。那么A獲得cpu的時(shí)間比例是1024/(1024+2048) = 33.3%。B進(jìn)程獲得的cpu時(shí)間比例是2048/(1024+2048)=66.7%。

在引入權(quán)重之后，分配給進(jìn)程的時(shí)間計(jì)算公式如下：

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

CFS調(diào)度器用nice值表示優(yōu)先級(jí)，取值范圍是[-20, 19]，nice和權(quán)重是一一對(duì)應(yīng)的關(guān)系。數(shù)值越小代表優(yōu)先級(jí)越大，同時(shí)也意味著權(quán)重值越大，nice值和權(quán)重之間的轉(zhuǎn)換關(guān)系：

const int sched_prio_to_weight[40] = { 
 /* -20 */     88761,     71755,     56483,     46273,     36291, 
 /* -15 */     29154,     23254,     18705,     14949,     11916, 
 /* -10 */      9548,      7620,      6100,      4904,      3906, 
 /*  -5 */      3121,      2501,      1991,      1586,      1277, 
 /*   0 */      1024,       820,       655,       526,       423, 
 /*   5 */       335,       272,       215,       172,       137, 
 /*  10 */       110,        87,        70,        56,        45, 
 /*  15 */        36,        29,        23,        18,        15, 
};  

數(shù)組值計(jì)算公式是：weight = 1024 / 1.25nice。

公式中的1.25取值依據(jù)是：進(jìn)程每降低一個(gè)nice值，將多獲得10% cpu的時(shí)間。公式中以1024權(quán)重為基準(zhǔn)值計(jì)算得來(lái)，1024權(quán)重對(duì)應(yīng)nice值為0，其權(quán)重被稱(chēng)為NICE_0_LOAD。默認(rèn)情況下，大部分進(jìn)程的權(quán)重基本都是NICE_0_LOAD。

虛擬運(yùn)行時(shí)間

根據(jù)上面的理解，這里看個(gè)例子。假如一個(gè)CPU的調(diào)度周期是6ms，進(jìn)程A和B的權(quán)重分別是1024和820(nice值分別是0和1)，那么進(jìn)程A獲得的運(yùn)行時(shí)間是6x1024/(1024+820)=3.3ms，進(jìn)程B獲得的執(zhí)行時(shí)間是6x820/(1024+820)=2.7ms。進(jìn)程A的cpu使用比例是3.3/6x100%=55%，進(jìn)程B的cpu使用比例是2.7/6x100%=45%。(符合上面說(shuō)的“進(jìn)程每降低一個(gè)nice值，將多獲得10% CPU的時(shí)間”)

很明顯，2個(gè)進(jìn)程的實(shí)際執(zhí)行時(shí)間是不相等的，但是CFS想保證每個(gè)進(jìn)程運(yùn)行時(shí)間相等。因此CFS引入了虛擬時(shí)間的概念，也就是說(shuō)上面的2.7ms和3.3ms經(jīng)過(guò)一個(gè)公式的轉(zhuǎn)換可以得到一樣的值，這個(gè)轉(zhuǎn)換后的值稱(chēng)作虛擬時(shí)間。這樣的話(huà)，CFS只需要保證每個(gè)進(jìn)程運(yùn)行的虛擬時(shí)間是相等的即可。虛擬時(shí)間vriture_runtime和實(shí)際時(shí)間(wall time)轉(zhuǎn)換公式如下：

虛擬運(yùn)行時(shí)間 = 實(shí)際運(yùn)行時(shí)間 * NICE_0_LOAD / 進(jìn)程權(quán)重 = (調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和) * NICE_0_LOAD / 進(jìn)程權(quán)重 = 調(diào)度周期 * 1024 / 所有進(jìn)程總權(quán)重

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

為了能夠快速找到虛擬運(yùn)行時(shí)間最小的進(jìn)程，Linux 內(nèi)核使用紅黑樹(shù)來(lái)保存可運(yùn)行的進(jìn)程。CFS跟蹤調(diào)度實(shí)體sched_entity的虛擬運(yùn)行時(shí)間vruntime，將sched_entity通過(guò)enqueue_entity()和dequeue_entity()來(lái)進(jìn)行紅黑樹(shù)的出隊(duì)入隊(duì)，vruntime少的調(diào)度實(shí)體sched_entity排列到紅黑樹(shù)的左邊。

如上圖所示，紅黑樹(shù)的左節(jié)點(diǎn)比父節(jié)點(diǎn)小，而右節(jié)點(diǎn)比父節(jié)點(diǎn)大。所以查找最小節(jié)點(diǎn)時(shí)，只需要獲取紅黑樹(shù)的最左節(jié)點(diǎn)即可。

相關(guān)步驟如下：

• 每個(gè)sched_latency周期內(nèi)，根據(jù)各個(gè)任務(wù)的權(quán)重值，可以計(jì)算出運(yùn)行時(shí)間runtime;
• 運(yùn)行時(shí)間runtime可以轉(zhuǎn)換成虛擬運(yùn)行時(shí)間vruntime;
• 根據(jù)虛擬運(yùn)行時(shí)間的大小，插入到CFS紅黑樹(shù)中，虛擬運(yùn)行時(shí)間少的調(diào)度實(shí)體放置到左邊;
• 在下一次任務(wù)調(diào)度的時(shí)候，選擇虛擬運(yùn)行時(shí)間少的調(diào)度實(shí)體來(lái)運(yùn)行(pick_next_task從就緒隊(duì)列中選擇最適合運(yùn)行的調(diào)度實(shí)體，即虛擬時(shí)間最小的調(diào)度實(shí)體);

CFS 數(shù)據(jù)結(jié)構(gòu)

task_struct: 任務(wù)描述符，包含很多進(jìn)程相關(guān)的信息，例如，優(yōu)先級(jí)、進(jìn)程狀態(tài)以及調(diào)度實(shí)體等。

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

cfs_rq：跟蹤就緒隊(duì)列信息以及管理就緒態(tài)調(diào)度實(shí)體，并維護(hù)一棵按照虛擬時(shí)間排序的紅黑樹(shù)。tasks_timeline->rb_root是紅黑樹(shù)的根，tasks_timeline->rb_leftmost指向紅黑樹(shù)中最左邊的調(diào)度實(shí)體，即虛擬時(shí)間最小的調(diào)度實(shí)體。

struct cfs_rq { 
  ... 
  struct rb_root_cached tasks_timeline 
  ... 
}; 

sched_entity：可被內(nèi)核調(diào)度的實(shí)體。每個(gè)就緒態(tài)的調(diào)度實(shí)體sched_entity包含插入紅黑樹(shù)中使用的節(jié)點(diǎn)rb_node，同時(shí)vruntime成員記錄已經(jīng)運(yùn)行的虛擬時(shí)間。

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

這些數(shù)據(jù)結(jié)構(gòu)的關(guān)系如下圖所示：

CFS 算法實(shí)現(xiàn)

1.時(shí)鐘中斷 scheduler_tick 更新虛擬運(yùn)行時(shí)間，檢查是否需要搶占。

更新運(yùn)行時(shí)的各類(lèi)統(tǒng)計(jì)信息，比如vruntime， 運(yùn)行時(shí)間、負(fù)載值、權(quán)重值等。

檢查是否需要搶占，主要是比較運(yùn)行時(shí)間是否耗盡，以及vruntime的差值是否大于運(yùn)行時(shí)間等。

2.任務(wù)出隊(duì)入隊(duì)

當(dāng)任務(wù)進(jìn)入可運(yùn)行狀態(tài)時(shí)，用 enqueue_task_fair 將調(diào)度實(shí)體放入到紅黑樹(shù)中，完成入隊(duì)操作;當(dāng)任務(wù)退出可運(yùn)行狀態(tài)時(shí)，用 dequeue_task_fair 將調(diào)度實(shí)體從紅黑樹(shù)中移除，完成出隊(duì)操作;隊(duì)操作。

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

從 cfs_rq 中獲取下一個(gè)可運(yùn)行的任務(wù)

每當(dāng)進(jìn)程任務(wù)切換的時(shí)候，也就是schedule函數(shù)執(zhí)行時(shí)，調(diào)度器都需要選擇下一個(gè)將要執(zhí)行的任務(wù)。在CFS調(diào)度器中，是通過(guò) pick_next_task_fair 函數(shù)完成的，其本質(zhì)是從就緒隊(duì)列中選擇最適合運(yùn)行的調(diào)度實(shí)體(虛擬時(shí)間最小的調(diào)度實(shí)體)。