一、完全公平調度演算法 完全公平調度 CFS 的出發點基於一個簡單的理念：進程調度的效果應該如同系統具備一個理想中的完美多任務處理器。在這種系統中，每個進程能夠獲得 1/n 的處理器時間（n 為可運行進程數）。同時，我們可以調度給它們無限小的時間周期，所以，在任何可測量周期內，我們給予 n 個進程中每 ...
一、完全公平調度演算法
完全公平調度 CFS 的出發點基於一個簡單的理念：進程調度的效果應該如同系統具備一個理想中的完美多任務處理器。在這種系統中，每個進程能夠獲得 1/n 的處理器時間（n 為可運行進程數）。同時，我們可以調度給它們無限小的時間周期，所以，在任何可測量周期內，我們給予 n 個進程中每個進程同樣多的運行時間。
但是，上述模型並不現實，因為我們無法再一個處理器上真的同時運行多個進程。而且，如果每個進程運行無限小的時間周期也並不高效（調度時的進程搶占會帶來一定的代價）。因此，雖然我們希望所有的進程能只運行一個非常短的周期（這樣會帶來較好的交互性），但是 CFS 充分考慮了這樣將帶來的額外消耗，實現中首先要確保系統性能不受損失。 CFS 的做法是允許每個進程運行一段時間、迴圈輪轉、選擇運行最少的進程作為下一個運行進程，而不再採用分配時間片的方式。 CFS 在所有可運行進程總數基礎上計算出一個進程應該運行多久，而不是依靠 nice 值來計算時間片。 nice 值在 CFS 中被作為進程獲得的處理器運行比的權重，越高的 nice 值將獲得更低的處理器使用比。
接下來，我們將在上述思想下，討論 CFS 是如何實現的。
二、時間記賬
所有的調度器都必須對進程運行時間做記賬。多數 Unix 系統通過給進程分配時間片的方式來進行時間記賬，每當系統時鐘發生變化時，時間片都會被減少一個節拍周期。當一個進程的時間片被減到 0 時，它就會被另一個時間片尚未減到 0 的可運行進程搶占。
我們已經知道，CFS不再有時間片的概念。儘管如此，我們依然需要對每個進程運行的時間記賬，以保證每個進程只在公平分配給它的處理器時間內運行。CFS 使用調度器實體結構（sched_entity）來追蹤進程運行記賬，其定義在 include/linux/sched.h 中：
/* * CFS stats for a schedulable entity (task, task-group etc) * * Current field usage histogram: * * 4 se->block_start * 4 se->run_node * 4 se->sleep_start * 6 se->load.weight */ struct sched_entity { struct load_weight load; // 權重，與優先順序有關 struct rb_node run_node; // 紅黑樹的結點 struct list_head group_node; // 所在進程組 unsigned int on_rq; // 標記是否處於紅黑樹運行隊列中 u64 exec_start; // 進程開始執行的時間 u64 sum_exec_runtime; // 進程運行總時間 u64 vruntime; // 虛擬運行時間 u64 prev_sum_exec_runtime; // 上個調度周期中進程運行的總時間 u64 last_wakeup; u64 avg_overlap; u64 nr_migrations; u64 start_runtime; u64 avg_wakeup; ... ... #ifdef CONFIG_FAIR_GROUP_SCHED struct sched_entity *parent; /* rq on which this entity is (to be) queued: */ struct cfs_rq *cfs_rq; /* rq "owned" by this entity/group: */ struct cfs_rq *my_q; #endif };
調度器實體結構作為一個名為 se 的成員變數，嵌入在進程描述符 task_struct 內。實際上，在 task_struct 結構中，還定義了一個調度器實體結構 sched_rt_entity，這是實時調度的調度器實體。如下：
struct task_struct{ ...... struct sched_entity se; struct sched_rt_entity rt; ...... }
回到 sched_entity 結構。註意到該結構裡面有一個元素 vruntime（虛擬運行時間），調度器實體結構就是用這個來對進程運行時間進行記賬的。使用 vruntime 進行時間記賬的步驟如下：
1）調用 update_curr() 函數，計算當前進程的執行時間，並將結果存放在變數 delta_exec 中；
2）將 delta_exec 作為參數傳遞給 _update_curr() 函數，該函數將根據當前可運行的進程總數對運行時間進行加權運算；
3）將權值與當前運行進程的 vruntime 相加得到新的 vruntime 值。
update_curr() 函數是由系統定時器周期性調用的，無論進程是處於可運行狀態，還是被堵塞處於不可運行狀態。根據這種方式，vruntime 可以準確地測量給定進程的運行時間，而且可知道誰應該是下一個被運行的進程。
三、進程選擇
當 CFS 需要選擇下一個運行進程時，它會挑一個具有最小 vruntime 的進程。CFS 演算法的核心就是選擇具有最小 vruntime 的任務。CFS 使用紅黑樹來組織可運行進程隊列，並利用其迅速找到最小 vruntime 值（紅黑樹最左葉子結點）的進程。
CFS 通過調用 _pick_next_entity() 函數來尋找紅黑樹最左葉子結點，即最小 vruntime 值，如下：
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) { struct rb_node *left = cfs_rq->rb_leftmost; // rb_leftmost 欄位中緩存著紅黑樹最左葉子結點的值 if (!left) return NULL; return rb_entry(left, struct sched_entity, run_node); }
_pick_next_entity() 函數本身並不會遍歷整個紅黑樹來尋找最左葉子結點，最左葉子結點的值已經緩存到了 rb_leftmost 欄位中，直接調用就行，這樣可以節省時間。當沒有最左葉子結點（也即沒有任何結點）的時候，函數返回值為 NULL，表明沒有可運行的進程，此時 CFS 調度器將選擇 idle 任務運行。
四、調度器入口
進程調度的主要入口點是函數 schedule()，其定義在 kernel/sched.c 中。它正式內核其他部分用於調度進程調度器的入口：選擇哪個進程可以運行，何時將其投入運行。 schedule() 通常都需要和一個具體的調度類相關聯，也就是說，它會找到一個最高優先順序的調度類（這個調度類需要有自己的可運行隊列），然後向這個調度類詢問下一個該運行的進程是哪個。
系統通過 schedule() 函數進入進程調度器，然後schedule() 函數調用 pick_next_task() 函數來選擇下一個將要執行的進程：
/* * Pick up the highest-prio task: */ static inline struct task_struct * pick_next_task(struct rq *rq) { const struct sched_class *class; struct task_struct *p; /* * Optimization: we know that if all tasks are in * the fair class we can call that function directly: */ if (likely(rq->nr_running == rq->cfs.nr_running)) { p = fair_sched_class.pick_next_task(rq); if (likely(p)) return p; } class = sched_class_highest; for ( ; ; ) { p = class->pick_next_task(rq); // 每個調度類都實現了 pick_next_task()函數，它會返回指向下一個可運行進程的指針，若沒有，則返回 NULL
// 從第一個返回非 NULL 值的類中選擇下一個可運行進程
if (p) return p; /* * Will never be NULL as the idle class always * returns a non-NULL p: */ class = class->next; } }
picke_next_task() 函數會以優先順序為順序，從高到低，依次檢查每一個調度類，並且從最高優先順序的調度類中，選擇最高優先順序的進程。
五、睡眠和喚醒
休眠（被阻塞）的進程處於一個特殊的不可執行狀態。如果沒有這種狀態的話，調度程式就可能選出一個本不願意被執行的進程，因此，休眠狀態是很重要的。進程休眠有多種原因，但肯定都是為了等待一些事件。進程有兩種休眠相關的狀態：TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE。其中，TASK_INTERRUPTIBLE 在接收到一個信號時，可以被提前喚醒並響應該信號，而後者則會忽略該信號。
當進程把自己標記成休眠狀態時，從可執行紅黑樹中移除，放入等待隊列，然後調用 schedule() 選擇和執行一個其他進程；喚醒過程剛好相反，進程被設置為執行狀態，然後再從等待隊列中移到可執行紅黑樹中。
5.1、等待隊列
休眠通過等待隊列進行處理。等待隊列是由等待某些事件發生的進程組成的簡單鏈表。內核用 wake_queue_head_t 來代表等待隊列。等待隊列可以通過 DECLARE_WAITQUEUE() 靜態創建，也可以由 init_waitqueue_head() 動態創建。進程把自己放入等待隊列中並設置為不可執行狀態。當與等待隊列相關的事件發生時，隊列上的進程會被喚醒。進程通過以下幾個步驟將自己加入到一個等待隊列中：
1）調用巨集 DEFINE_WAIT() 創建一個等待隊列的項；
2）調用 add_wait_queue() 把自己加入到隊列中。該隊列會在進程等待的條件滿足時喚醒它，通過在事件發生時對等待隊列執行 wake_up() 操作；
3）調用 prepare_to_wait() 方法將進程的狀態變更為 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE 。如果有必要的話，會將進程加入到等待隊列；
4）若進程被設置為 TASK_INTERRUPTIBLE ，則信號喚醒進程。這就是所謂的偽喚醒（喚醒並不是因為事件的發生），因此檢查並處理信號；
5）當進程被喚醒時，它會再次檢查條件是否為真。如果為真，則退出迴圈；否則，再次調用 schedule() 並重覆這一步；
6）當條件滿足後，進程將自己設置為 TASK_RUNNING 並調用 finish_wait() 方法把自己移除等待隊列。
5.2 喚醒
喚醒操作通過函數 wake_up() 進行，它會喚醒指定的等待隊列上的所有進程。它調用函數 try_to_wake_up() ，該函數負責將進程設置為 TASK_RUNNING 狀態，然後調用 enqueue_task() 將此進程放入紅黑樹中，如果被喚醒的進程優先順序比當前正在執行的進程的優先順序高，還要設置 need_resched 標誌。另外，關於休眠，存在虛假的喚醒。有時候進程被喚醒並不是因為他所等待的條件達成了，因此需要用一個迴圈處理來保證等待的條件真正達成（上文中的第5步）。
筆者註：Linux 進程調度很複雜，對於初學的筆者來說，很多地方仍然不明白，只能摸清個大致框架，思路也比較混亂，因此寫出來的東西也很亂，大多數是從書上摘錄的。雖是摘錄，卻也比僅僅是看一遍更能加深印象。本著堅持一周一篇博客的想法，雖然寫的差，但還是決定發出去。後續將不斷補充進程調度相關的內容，不斷學習。
參考書籍：Linux內核設計與實現（第三版）
