從1991年Linux的第1版到後來的2.4內核系列，Linux的調度程式都相當簡陋，設計近乎原始，見0.11版內核進程調度。當然它很容易理解，但是它在眾多可運行進程或者多處理器的環境下都難以勝任。 正因為如此，在Linux2.5開發系列的內核中，調度程式做了大手術。開始採用了一種叫做O(1)調度程 ...
從1991年Linux的第1版到後來的2.4內核系列，Linux的調度程式都相當簡陋，設計近乎原始，見0.11版內核進程調度。當然它很容易理解，但是它在眾多可運行進程或者多處理器的環境下都難以勝任。
正因為如此，在Linux2.5開發系列的內核中，調度程式做了大手術。開始採用了一種叫做O(1)調度程式的新調度程式——它是因為其演算法的行為而得名的。它解決了先前版本Linux調度程式的許多不足，引入了許多強大的新特性和性能特征。O(1)調度程式雖然對於大伺服器的工作負載很理想，但是在有很多交互程式要運行的桌面系統上則表現不佳，因為其缺少交互進程。
自2.6內核系統開發初期，開發人員為了提高對交互程式的調度性能引入了新的進程調度演算法。其中最為著名的是“反轉樓梯最後期限調度演算法”（RSDL），該演算法吸取了隊列理論，將公平調度的概念引入了Linux調度程式。並且最終在2.6.23內核版本中替代了O(1)調度演算法，它此刻被稱為“完全公平調度演算法”，或者簡稱CFS。
1.策略
策略決定調度程式在何時讓什麼進程運行。調度器的策略往往就決定系統的整體印象，並且，還要負責優化使用處理器時間。無論從哪個方面來看，它都是至關重要的。
進程可以被分為I/O消耗型和處理器消耗型。
1.1.進程優先順序
調度演算法中最基本的一類就是基於優先順序的調度。Linux採用了2種不同的優先順序範圍。第一種是用nice值，它的範圍是從-20到+19，預設值為0，越大的nice值意味著更低的優先順序；第二種範圍是實時優先順序，其值是可配置的，預設情況下它的變化範圍是從0到99（包括0和99），與nice值意義相反，越高的實時優先順序數值意味著進程優先順序越高。
1.2.時間片
時間片是一個數值，它表明進程在被搶占前所能持續運行的時間。I/O消耗型不需要長的時間片，而處理器消耗型的進程則希望越長越好（比如這樣可以讓它們的高速緩存命中率更高）。Linux的CFS調度器並沒有直接分配時間片到進程，它是將處理器的使用比劃分給了進程。這樣一來，進程所獲得的處理器時間其實是和系統負載密切相關的。
在多數操作系統中，是否要將一個進程立刻投入運行（也就是搶占當前進程），是完全由進程優先順序和是否有時間片決定的。而在Linux中使用新的CFS調度器，其搶占時機取決於新的可運行程式消耗了多少處理器使用比。如果消耗的使用比比當前進程小，則新進程立刻投入運行，搶占當前進程。否則，將推遲其運行。
2.Linux調度演算法
在前面內容中，我們抽象地討論了進程調度原理。
2.1.調度器類
Linux調度器是以模塊方式提供的，這樣做的目的是允許不同類型的進程可以有針對性地選擇調度演算法。
這種模塊化結構被稱為調度器類，它允許多種不同的可動態添加的調度演算法並存，調度屬於自己範疇的進程。每個調度器都有一個優先順序，基礎的調度器代碼定義在kernel/sched.c文件中，它會按照優先順序順序遍歷調度類，擁有一個可執行進程的最高優先順序的調度器類勝出，去選擇下麵要執行的那一個程式。
完全公平調度（CFS）是一個針對普通進程的調度類。CFS採用的方法是對時間片分配方式進行根本性的重新設計（就進程調度器而言）：完全摒棄時間片而是分配給進程一個處理器使用比重。通過這種方式，CFS確保了進程調度中能有恆定的公平性，而將切換頻率置於不斷變動中。
2.2.公平調度
CFS的做法是允許每個進程運行一段時間、迴圈輪轉、選擇運行最少的進程作為下一個運行進程，而不再採用分配給每個進程時間片的做法了，CFS在所有可運行進程總數基礎上計算出一個進程應該運行多久，而不是依靠nice值來計算時間片。
nice值在CFS中被作為進程獲得的處理器運行比的權重：越高的nice值（越低的優先順序）進程獲得更低的處理器使用權重，這是相對預設nice值進程的進程而言的；相反，更低的nice值（越高的優先順序）的進程獲得更高的處理器使用權重。
絕對的nice值不再影響調度決策：只有相對值才會影響處理器時間的分配比例。
總結一下，任何進程所獲得的處理器時間是由它自己和其他所有可運行進程nice值的相對差值決定的。nice值對時間片的作用不再是算數加權，而是幾何加權。任何nice值對應的絕對時間不再是一個絕對值，而是處理器的使用比。CFS稱為公平調度器是因為它確保給每個進程公平的處理器使用比。CFS不是完美的公平，它只是近乎完美的多任務。
3.Linux調度的實現
● 時間記賬
● 進程選擇
● 調度器入口
● 睡眠和喚醒
3.1.時間記賬
CFS不再有時間片的概念，但是它也必須維護每個進程運行的時間記賬，因為它需要確保每個進程只在公平分配給它的處理器時間內運行。CFS使用調度器實體結構（<linux/sched.h>的struct_sched_entiry中）來追蹤進程運行記賬。
vruntime變數存放進程的虛擬運行時間，該運行時間（花在運行上的時間和）的計算是經過了所有可運行進程總數的標準化（或者說是被加權的）。虛擬時間是以ns為單位的，所以vruntime和定時器節拍不再相關。CFS使用vruntime變數來記錄一個程式到底運行了多長時間以及它還應該再運行多久。
3.2.進程選擇
在前面談到若存在一個完美的多任務處理器，所有可運行進程的vruntime值將一致。但事實上我們沒有找到完美的多任務處理器，因此CFS試圖利用一個簡單的規則去均衡進程的虛擬運行時間：當CFS需要選擇下一個運行進程時，它會挑一個具有最小vruntime的進程。這其實就是CFS調度演算法的核心：選擇具有最小vruntime的任務。
CFS使用紅黑樹來組織可運行進程隊列，並利用其迅速找到最小vruntime值的進程。
我們先假設，有那麼一個紅黑樹存儲了系統中所有的可運行進程，其中節點的鍵值便是可運行進程的虛擬運行時間。CFS調度器選取待運行的下一個進程，是所有進程中vruntime最小的那個，它對應的便是樹中最左側的葉子節點。CFS的進程選擇演算法可簡單總結為“運行rbtree樹中最左邊葉子節點所代表的那個進程”。實現這一過程的函數是_pick_next_entity()，它定義在kernel/sched_fair.c中。
3.3.調度器入口
進程調度的主要入口點是函數schedule()，定在kernel/sched.c中。該函數中唯一重要的事情是，它會調用pick_next_task()，被調用的這個函數會以優先順序為序，從高到低，依次檢查每一個調度類，並且從最高優先順序的調度類中，選擇最高優先順序的進程。
3.4.睡眠和喚醒
休眠的進程處於一個特殊的不可執行狀態。這點非常重要，如果沒有這種特殊狀態的話，調度程式就可能選出一個本不願意被執行的進程。休眠的一個常見原因就是文件I/O。
無論哪種情況，內核的操作都相同：進程把自己標記成休眠狀態，從可執行紅黑樹中移出，放入等待隊列，然後調用schedule()選擇和執行一個其他進程。喚醒的過程剛好相反：進程被設置為可執行狀態，然後再從等待隊列中移到可執行紅黑樹中。
4.搶占和上下文切換
上下文切換，也就是從一個可執行進程切換到另一個可執行進程，由定義在kernel/sched.c中的context_switch()函數負責處理。每當一個新的進程被選出來準備投入運行的時候，schedule()就會調用該函數。它完成了兩項基本的工作：
● 調用聲明在<asm/mmu_context.h>中的switch_mm()，該函數負責把虛擬記憶體從上一個進程映射切換到新進程中。
● 調用聲明在<asm/system.h>中的switch_to()，該函數負責從上一個進程的處理器狀態切換到新進程的處理器狀態等。
4.1.用戶搶占
內核即將返回用戶空間的時候，如果need_resched標誌被設置，會導致schedule()被調用，此時就會發生用戶搶占。用戶搶占在以下情況時產生：
● 從系統調用返回用戶空間時。
● 從中斷處理程式返回用戶空間時。
4.2.內核搶占
與其他大部分的Unix變體和其他大部分的操作系統不同，Linux完整地支持內核搶占。在不支持內核搶占的內核中，內核代碼可以一直執行，到它完成為止。也就是說，調度程式沒有辦法在一個內核級的任務正在執行的時候重新調度。
如果沒有持有鎖，正在執行的代碼就是可重新導入的，也就是可以搶占的。
每個進程的thread_info引入preempt_count計數器，初始值為0，每當使用鎖的時候數值加1，釋放鎖的時候數值減1.當數值為0的時候，內核就可執行搶占。從中斷返回內核空間的時候，內核會檢查need_resched和preempt_count的值。如果need_resched被設置，並且preempt_count為0的話，這說明有一個更為重要的任務需要執行並且可以安全地搶占，此時，調度程式就會被調用。如果preempt_count不為0，說明當前任務持有鎖，所以搶占是不安全的。這時，內核就會像通常那樣直接從中斷返回當前執行進程。
