Linux 完全公平調(diào)度算法
Linux 進(jìn)程調(diào)度算法經(jīng)歷了以下幾個(gè)版本的發(fā)展：
基于時(shí)間片輪詢調(diào)度算法。(2.6之前的版本)
O(1) 調(diào)度算法。(2.6.23之前的版本)
完全公平調(diào)度算法。(2.6.23以及之后的版本)
之前我寫過一篇分析?O(1)調(diào)度算法?的文章：O(1)調(diào)度算法，而這篇主要分析 Linux 現(xiàn)在所使用的?完全公平調(diào)度算法。
分析?完全公平調(diào)度算法?前，我們先了解下?完全公平調(diào)度算法?的基本原理。
完全公平調(diào)度算法基本原理
完全公平調(diào)度算法?體現(xiàn)在對(duì)待每個(gè)進(jìn)程都是公平的，那么怎么才能做到完全公平呢？有一個(gè)比較簡單的方法就是：讓每個(gè)進(jìn)程都運(yùn)行一段相同的時(shí)間片，這就是?基于時(shí)間片輪詢調(diào)度算法。如下圖所示：
如上圖所示，開始時(shí)進(jìn)程1獲得?time0 ~ time1?的CPU運(yùn)行時(shí)間。當(dāng)進(jìn)程1的時(shí)間片使用完后，進(jìn)程2獲得?time1 ~ time2?的CPU運(yùn)行時(shí)間。而當(dāng)進(jìn)程2的時(shí)間片使用完后，進(jìn)程3獲得?time2 ~ time3?的CPU運(yùn)行時(shí)間。
如此類推，由于每個(gè)時(shí)間片都是相等的，所以理論上每個(gè)進(jìn)程都能獲得相同的CPU運(yùn)行時(shí)間。這個(gè)算法看起來很不錯(cuò)，但存在兩個(gè)問題：
不能按權(quán)重分配不同的運(yùn)行時(shí)間，例如有些進(jìn)程權(quán)重大的應(yīng)該獲得更多的運(yùn)行時(shí)間。
每次調(diào)度時(shí)都需要遍歷運(yùn)行隊(duì)列中的所有進(jìn)程，找到優(yōu)先級(jí)最大的進(jìn)程運(yùn)行，時(shí)間復(fù)雜度為?
O(n)。對(duì)于一個(gè)高性能的操作系統(tǒng)來說，這是不能接受的。
為了解決上面兩個(gè)問題，Linux內(nèi)核的開發(fā)者創(chuàng)造了?完全公平調(diào)度算法。
完全公平調(diào)度的兩個(gè)時(shí)間
為了實(shí)現(xiàn)?完全公平調(diào)度算法，為進(jìn)程定義兩個(gè)時(shí)間:
實(shí)際運(yùn)行時(shí)間：
實(shí)際運(yùn)行時(shí)間 = 調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和
調(diào)度周期：是指所有可進(jìn)程運(yùn)行一遍所需要的時(shí)間。進(jìn)程權(quán)重：依據(jù)進(jìn)程的重要性，分配給每個(gè)進(jìn)程不同的權(quán)重。
例如，調(diào)度周期為 30ms，進(jìn)程A的權(quán)重為 1，而進(jìn)程B的權(quán)重為 2。那么：
進(jìn)程A的實(shí)際運(yùn)行時(shí)間為：30ms * 1 / (1 + 2) = 10ms
進(jìn)程B的實(shí)際運(yùn)行時(shí)間為：30ms * 2 / (1 + 2) = 20ms
虛擬運(yùn)行時(shí)間：
虛擬運(yùn)行時(shí)間 = 實(shí)際運(yùn)行時(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)重
從上面的公式可以看出，在一個(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)核使用?紅黑樹?來保存可運(yùn)行的進(jìn)程，而比較的鍵值就是進(jìn)程的?虛擬運(yùn)行時(shí)間。
如果不了解?紅黑樹?的話，可以把它看成一個(gè)自動(dòng)排序的容器即可。如下圖所示：
如上圖所示，紅黑樹?的左節(jié)點(diǎn)比父節(jié)點(diǎn)小，而右節(jié)點(diǎn)比父節(jié)點(diǎn)大。所以查找最小節(jié)點(diǎn)時(shí)，只需要獲取?紅黑樹?的最左節(jié)點(diǎn)即可，時(shí)間復(fù)雜度為?O(logN)。
完全公平調(diào)度的兩個(gè)對(duì)象
Linux 內(nèi)核為了實(shí)現(xiàn)?完全公平調(diào)度算法，定義兩個(gè)對(duì)象：cfs_rq (可運(yùn)行進(jìn)程隊(duì)列)?和?sched_entity (調(diào)度實(shí)體)。
cfs_rq (可運(yùn)行進(jìn)程隊(duì)列)：使用?紅黑樹?結(jié)構(gòu)來保存內(nèi)核中可以運(yùn)行的進(jìn)程。sched_entity (調(diào)度實(shí)體)：可被內(nèi)核調(diào)度的實(shí)體，如果忽略組調(diào)度（本文也不涉及組調(diào)度），可以把它當(dāng)成是進(jìn)程。
cfs_rq?對(duì)象定義
struct cfs_rq {struct load_weight load;unsigned long nr_running; // 運(yùn)行隊(duì)列中的進(jìn)程數(shù)u64 exec_clock; // 當(dāng)前時(shí)鐘u64 min_vruntime; // 用于修證虛擬運(yùn)行時(shí)間struct rb_root tasks_timeline; // 紅黑樹的根節(jié)點(diǎn)struct rb_node *rb_leftmost; // 緩存紅黑樹最左端節(jié)點(diǎn), 用于快速獲取最小節(jié)點(diǎn)...};
對(duì)于?cfs_rq?對(duì)象，現(xiàn)在主要關(guān)注的是?tasks_timeline?成員，其保存了可運(yùn)行進(jìn)程隊(duì)列的根節(jié)點(diǎn)（紅黑樹的根節(jié)點(diǎn)）。
sched_entity?對(duì)象定義
struct sched_entity {struct load_weight load;??struct?rb_node????run_node;?????????//?用于連接到運(yùn)行隊(duì)列的紅黑樹中struct list_head group_node;??unsigned?int????on_rq;??????????????//?是否已經(jīng)在運(yùn)行隊(duì)列中u64 exec_start; // 開始統(tǒng)計(jì)運(yùn)行時(shí)間的時(shí)間點(diǎn)u64 sum_exec_runtime; // 總共運(yùn)行的實(shí)際時(shí)間u64 vruntime; // 虛擬運(yùn)行時(shí)間(用于紅黑樹的鍵值對(duì)比)u64 prev_sum_exec_runtime; // 總共運(yùn)行的虛擬運(yùn)行時(shí)間u64 last_wakeup;u64 avg_overlap;...};
對(duì)于?sched_entity?對(duì)象，現(xiàn)在主要關(guān)注的是?run_node?成員，其主要用于把調(diào)度實(shí)體連接到可運(yùn)行進(jìn)程的隊(duì)列中。
另外，進(jìn)程描述符?task_struct?對(duì)象中，定義了一個(gè)類型為?sched_entity?的成員變量?se，如下：
struct task_struct {...struct sched_entity se;...}
所以，他們之間的關(guān)系如下圖：
從上圖可以看出，所有?sched_entity?對(duì)象通過其?run_node?成員組成了一顆紅黑樹，這顆紅黑樹的根結(jié)點(diǎn)保存在?cfs_rq?對(duì)象的?task_timeline?成員中。
另外，進(jìn)程描述符?task_sturct?定義了一個(gè)類型為?sched_entity?的成員變量?se，所以通過進(jìn)程描述符的?se?字段就可以把進(jìn)程保存到可運(yùn)行隊(duì)列中。
完全公平調(diào)度算法實(shí)現(xiàn)
有了上面的基礎(chǔ)，現(xiàn)在可以開始分析 Linux 內(nèi)核中怎么實(shí)現(xiàn)?完全公平調(diào)度算法?了。
我們先來看看怎么更新一個(gè)進(jìn)程的虛擬運(yùn)行時(shí)間。
1. 更新進(jìn)程虛擬運(yùn)行時(shí)間
更新一個(gè)進(jìn)程的虛擬運(yùn)行時(shí)間是通過?__update_curr()?函數(shù)完成的，其代碼如下：
/src/kernel/sched_fair.c
static inline void__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,unsigned long delta_exec){unsigned long delta_exec_weighted;curr->sum_exec_runtime += delta_exec; // 增加進(jìn)程總實(shí)際運(yùn)行的時(shí)間delta_exec_weighted = delta_exec; // 初始化進(jìn)程使用的虛擬運(yùn)行時(shí)間// 根據(jù)進(jìn)程的權(quán)重計(jì)算其使用的虛擬運(yùn)行時(shí)間if (unlikely(curr->load.weight != NICE_0_LOAD)) {delta_exec_weighted = calc_delta_fair(delta_exec_weighted, &curr->load);}curr->vruntime += delta_exec_weighted; // 更新進(jìn)程的虛擬運(yùn)行時(shí)間}
__update_curr()?函數(shù)各個(gè)參數(shù)意義如下：
cfs_rq：可運(yùn)行隊(duì)列對(duì)象。curr：當(dāng)前進(jìn)程調(diào)度實(shí)體。delta_exec：實(shí)際運(yùn)行的時(shí)間。
__update_curr()?函數(shù)主要完成以下幾個(gè)工作：
更新進(jìn)程調(diào)度實(shí)體的總實(shí)際運(yùn)行時(shí)間。
根據(jù)進(jìn)程調(diào)度實(shí)體的權(quán)重值，計(jì)算其使用的虛擬運(yùn)行時(shí)間。
把計(jì)算虛擬運(yùn)行時(shí)間的結(jié)果添加到進(jìn)程調(diào)度實(shí)體的?
vruntime?字段。
我們接著分析怎么把進(jìn)程添加到運(yùn)行隊(duì)列中。
2. 把進(jìn)程調(diào)度實(shí)體添加到運(yùn)行隊(duì)列中
要將進(jìn)程調(diào)度實(shí)體添加到運(yùn)行隊(duì)列中，可以調(diào)用?__enqueue_entity()?函數(shù)，其實(shí)現(xiàn)如下：
/src/kernel/sched_fair.c
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se){struct rb_node **link = &cfs_rq->tasks_timeline.rb_node; // 紅黑樹根節(jié)點(diǎn)struct rb_node *parent = NULL;struct sched_entity *entry;s64 key = entity_key(cfs_rq, se); // 當(dāng)前進(jìn)程調(diào)度實(shí)體的虛擬運(yùn)行時(shí)間int leftmost = 1;while (*link) { // 把當(dāng)前調(diào)度實(shí)體插入到運(yùn)行隊(duì)列的紅黑樹中parent = *link;entry = rb_entry(parent, struct sched_entity, run_node);if (key < entity_key(cfs_rq, entry)) { // 比較虛擬運(yùn)行時(shí)間link = &parent->rb_left;} else {link = &parent->rb_right;leftmost = 0;}}if (leftmost) {cfs_rq->rb_leftmost = &se->run_node; // 緩存紅黑樹最左節(jié)點(diǎn)cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, se->vruntime);}// 這里是紅黑樹的平衡過程(參考紅黑樹數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn))rb_link_node(&se->run_node, parent, link);rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);}
__enqueue_entity()?函數(shù)的主要工作如下：
獲取運(yùn)行隊(duì)列紅黑樹的根節(jié)點(diǎn)。
獲取當(dāng)前進(jìn)程調(diào)度實(shí)體的虛擬運(yùn)行時(shí)間。
把當(dāng)前進(jìn)程調(diào)度實(shí)體添加到紅黑樹中（可參考紅黑樹的插入算法）。
緩存紅黑樹最左端節(jié)點(diǎn)。
對(duì)紅黑樹進(jìn)行平衡操作（可參考紅黑樹的平衡算法）。
調(diào)用?__enqueue_entity()?函數(shù)后，就可以把進(jìn)程調(diào)度實(shí)體插入到運(yùn)行隊(duì)列的紅黑樹中。同時(shí)會(huì)把紅黑樹最左端的節(jié)點(diǎn)緩存到運(yùn)行隊(duì)列的?rb_leftmost?字段中，用于快速獲取下一個(gè)可運(yùn)行的進(jìn)程。
3. 從可運(yùn)行隊(duì)列中獲取下一個(gè)可運(yùn)行的進(jìn)程
要獲取運(yùn)行隊(duì)列中下一個(gè)可運(yùn)行的進(jìn)程可以通過調(diào)用?__pick_next_entity()?函數(shù)，其實(shí)現(xiàn)如下：
/src/kernel/sched_fair.c
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq){// 1. 先調(diào)用 first_fair() 獲取紅黑樹最左端節(jié)點(diǎn)// 2. 調(diào)用 rb_entry() 返回節(jié)點(diǎn)對(duì)應(yīng)的調(diào)度實(shí)體return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node);}static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq){return cfs_rq->rb_leftmost; // 獲取紅黑樹最左端節(jié)點(diǎn)}
前面介紹過，紅黑樹的最左端節(jié)點(diǎn)就是虛擬運(yùn)行時(shí)間最少的進(jìn)程，所以?__pick_next_entity()?函數(shù)的流程就非常簡單了，如下：
首先調(diào)用?
first_fair()?獲取紅黑樹最左端節(jié)點(diǎn)。然后再調(diào)用?
rb_entry()?返回節(jié)點(diǎn)對(duì)應(yīng)的調(diào)度實(shí)體。
調(diào)度時(shí)機(jī)
前面介紹了?完全公平調(diào)度算法?怎么向可運(yùn)行隊(duì)列添加調(diào)度的進(jìn)程和怎么從可運(yùn)行隊(duì)列中獲取下一個(gè)可運(yùn)行的進(jìn)程，那么 Linux 內(nèi)核在什么時(shí)候會(huì)進(jìn)行進(jìn)程調(diào)度呢？
答案是由 Linux 內(nèi)核的時(shí)鐘中斷觸發(fā)的。
時(shí)鐘中斷?是什么？如果沒了解過操作系統(tǒng)原理的可能不了解這個(gè)東西，但是沒關(guān)系，不了解可以把他當(dāng)成是定時(shí)器就好了，就是每隔固定一段時(shí)間會(huì)調(diào)用一個(gè)回調(diào)函數(shù)來處理這個(gè)事件。
時(shí)鐘中斷?猶如 Linux 的心臟一樣，每隔一定的時(shí)間就會(huì)觸發(fā)調(diào)用?scheduler_tick()?函數(shù)，其實(shí)現(xiàn)如下：
void scheduler_tick(void){...curr->sched_class->task_tick(rq, curr, 0); // 這里會(huì)調(diào)用 task_tick_fair() 函數(shù)...}
scheduler_tick()?函數(shù)會(huì)調(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ù)實(shí)現(xiàn)如下：
static voidentity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued){// 更新當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間update_curr(cfs_rq);...if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))check_preempt_tick(cfs_rq, curr); // 判斷是否需要進(jìn)行進(jìn)程調(diào)度}
entity_tick()?函數(shù)主要完成以下工作：
調(diào)用?
update_curr()?函數(shù)更新進(jìn)程的虛擬運(yùn)行時(shí)間，這個(gè)前面已經(jīng)介紹過。調(diào)用?
check_preempt_tick()?函數(shù)判斷是否需要進(jìn)行進(jìn)程調(diào)度。
我們接著分析?check_preempt_tick()?函數(shù)的實(shí)現(xiàn)：
static voidcheck_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr){unsigned long ideal_runtime, delta_exec;// 計(jì)算當(dāng)前進(jìn)程可用的時(shí)間片ideal_runtime = sched_slice(cfs_rq, curr);// 進(jìn)程運(yùn)行的實(shí)際時(shí)間delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;// 如果進(jìn)程運(yùn)行的實(shí)際時(shí)間大于其可用時(shí)間片, 那么進(jìn)行調(diào)度if (delta_exec > ideal_runtime)resched_task(rq_of(cfs_rq)->curr);}
check_preempt_tick()?函數(shù)主要完成以下工作：
通過調(diào)用?
sched_slice()?計(jì)算當(dāng)前進(jìn)程可用的時(shí)間片。獲取當(dāng)前進(jìn)程在當(dāng)前調(diào)度周期實(shí)際已運(yùn)行的時(shí)間。
如果進(jìn)程實(shí)際運(yùn)行的時(shí)間大于其可用時(shí)間片, 那么調(diào)用?
resched_task()?函數(shù)進(jìn)行進(jìn)程調(diào)度。
可以看出，在?時(shí)鐘中斷?的處理中，有可能會(huì)進(jìn)行進(jìn)程調(diào)度。除了?時(shí)鐘中斷?外，一些主動(dòng)讓出 CPU 的操作也會(huì)進(jìn)行進(jìn)程調(diào)度（如一些 I/O 操作），這里就不詳細(xì)分析了，有興趣可以自己研究。