一些概念
調度程序負責決定哪個進程投入運行，何時運行及運行多長時間。進程調度程序就是在可運行態進程之間分配有限的處理器時間資源的內核子系統。 多任務系統可分為兩類：
非搶占式多任務和
搶占式多任務。Linux提供了搶占式多任務。
I/O消耗型進程就是大部分時間用來提交I/O請求或者是等待I/O請求。 處理器消耗型進程就是把時間大多用在代碼執行上。
調度策略通常就是在兩個矛盾的目標中間尋求平衡：進程迅速響應（響應時間短）、最大系統利用率（高吞吐量）。
進程優先級：Linux中用nice值表示，范圍是從-20到+19，默認為0，越大的nice值代表更低的優先級。 時間片：是進程在被搶占之前所能持續運行的時間。時間片太短會明顯增加進程切換帶來的處理器耗時；時間片太長會導致系統交互表現欠佳。
Linux調度算法
Linux調度器是以模塊方式調度的，這樣做的目的是允許不同類型的進程可以針對性的選擇調度算法。
完全公平調度算法（CFS）是針對普通進程的調度，在Linux中稱為SCHED_NORMAL。算法定義在文件kernel/sched_fair.c。
完全公平調度（CFS）不是直接分配時間片到進程，而是將處理器的使用比劃分給進程，同時nice值（優先級）只是作為進程獲得的處理器運行比的權重（幾何加權）。
Linux調度的實現
CFS調度算法的實現分四個組成部分：時間記賬
進程選擇
調度器入口
睡眠和喚醒
時間記賬：
CFS使用
調度器實體結構（struct_sched_entity）來追蹤進程運行的時間記賬，調度器實體結構是作為se成員變量嵌入在進程描述符struct task_struct內。
虛擬實時vruntime變量存放進程的虛擬運行時間，CFS用vruntime來記錄一個程序到底運行了多長時間以及還要運行多長時間。
進程選擇：
CFS調度算法的核心：選擇最小的vruntime的任務。 CFS使用
紅黑樹來組織可運行的進程隊列，並利用其迅速找到最小vruntime的進程。Linux中紅黑樹成為
rbtree，是一個自平衡二叉搜索樹。紅黑樹是以樹節點的形式存儲數據，每個數據對應一個鍵值。
平衡二叉搜索樹的原則是鍵值小於該節點，則轉向左分支，鍵值大於該節點，則轉向右分支。所以CFS的進程選擇算法可簡單總結為“運行rbtree樹中最左邊葉子節點所代表的進程”。
CFS將進程加入到rbtree中是發生在進程變為可運行狀態或者是通過fork調用第一次創建進程時。添加原則就是鍵值小的走左分支，鍵值大的走又分支。
CFS將進程從rbtree中刪除是發生在進程阻塞或者終止時。
調度器入口
進程調度的主要入口點是
函數schedule()：選擇哪個進程可以運行，何時將其投入運行。函數會調用pick_next_task()，以優先級為序依次檢查每一個調度類，從最高優先級的調度類中選擇最高優先級的進程。
睡眠和喚醒
睡眠：進程把自己標記為休眠狀態，從可執行紅黑樹中移除，放入等待隊列，然後調用schedule()選擇和執行一個其他進程
喚醒：喚醒操作通過wake_up()函數進行，喚醒指定的隊列的所有進程。
搶占和上下文切換
上下文切換就是從一個可執行進程切換到另一個可執行進程，由context_switch()函數負責處理。 用戶搶占：內核即將返回用戶空間的時候，如果need_resched標志被設置，會導致schedule()被調用。用戶搶占發生在以下情況，從系統調用返回用戶空間時；從中斷處理程序返回用戶空間時。
內核搶占：Linux支持完整的內核搶占，只要沒有鎖，內核就可以進行搶占。
內核搶占發生在：
- 中斷處理程序正在執行，且返回內核空間之前
- 內核代碼再一次具有可搶占性的時候
- 內核中的任務顯式的調用schedule
- 如果內核中的任務阻塞
實時調度策略
Linux提供了兩種實時調度策略：
SCHED_FIFO和
SCHED_RR SCHED_FIFO實現的是一種簡單的、先入先出的調度算法，不使用時間片。處於可運行狀態的SCHED_FIFO級進程會比任何SCHED_NORMAL級的進程優先得到調用。它不基於時間片，可以一直執行下去，只有自己收阻塞或者顯式的釋放處理器，或者更高優先級的SCHED_FIFO或SCHED_RR進程搶占。相同優先級的SCHED_FIFO進程會輪流執行，但同樣是在它們願意讓出處理器才行。
SCHED_RR是帶有時間片的SCHED_FIFO，這是一種實時輪流調度算法。
