一個成功的調(diào)度器的基本要求可以概括為以下三點：

(1)減少花在調(diào)度上的時間，以增加花在執(zhí)行程序上的時間；

(2)在多處理器系統(tǒng)上，保持處理器的負載平衡；

(3)對交互式應(yīng)用有良好的響應(yīng)速度。

但是，一個成功的調(diào)度器是很難設(shè)計好的，因為一個真正投入運行的系統(tǒng)受到很多因素的制約。相對于Linux2.6，Linux2.4的調(diào)度器有很多的不足之處，2.6版本的Linux內(nèi)核使用了新的調(diào)度器算法，稱為0(1)算法，它在高負載的情況下執(zhí)行得極其出色，并且當有很多處理器時也可以很好地擴展。

O(n)算法，O代表order，括號里的數(shù)字代表最壞情況下算法效率的上限取決于算法涉及到的元素的個數(shù)，O(1)說明是一個常數(shù)，在這種情況下，每次調(diào)度的效率是一樣的，與涉及的元素的多少沒有關(guān)系，O(n)表示算法效率取決于算法涉及元素的個數(shù)。

1 Linux2.4的調(diào)度機制

Linux2.4的調(diào)度機制可以用下面的算法來描述，示意圖如圖1所示。

所有的就緒進程都在一個全局的就緒進程隊列中，這個隊列沒有任何有意義的排序；時間片重算算法是在所有的進程都用盡它們的時間片以后才重新計算。整個隊列由一個讀／寫自旋鎖(read／write spinlock)保護著，這樣多個處理器可以并行訪問，但同時提供寫操作的互斥訪問。

由算法可以看出，Linux2.4的調(diào)度算法可以說是一個O(n)算法，因為調(diào)度器挑選執(zhí)行進程的開銷是隨系統(tǒng)中就緒進程 的增長而線性增長的。同時，當系統(tǒng)中有多個處理器時，訪問就緒進程隊列就成了瓶頸，性能也會顯著的下降。因而有很多的缺點：

(1)每次調(diào)度時，調(diào)度器都要線性遍歷這個隊列，以找出最值得運行的進程執(zhí)行：當系統(tǒng)負載很高的時候。可執(zhí)行進程隊列會很長，線性搜索的時間是線性增長的，這個時間會很長，當這個時間足夠長的時候，有可能出現(xiàn)多個處理器選擇了同一個進程的情況，這樣，有些處理器會發(fā)現(xiàn)，他選擇的進程已經(jīng)分配了其他的處理器，而不得不重新選擇，甚至出現(xiàn)選擇運行進程的時間比實際執(zhí)行進程的時間還要長的情況。

(2)當大多數(shù)的就緒進程的時間片都用完而又還投有重新分配時間片的時候，SMP系統(tǒng)中有些處理器處于空閑狀態(tài)，這將影響SMP的效率。

(3)當空閑的處理器開始執(zhí)行那些時間片尚未用盡而處于等待狀態(tài)的進程(如果它們自己的處理器忙)時，會導(dǎo)致進程開始在處理器之間“跳躍”，實時進程或者占用內(nèi)存大的進程在處理器之間跳躍會嚴重影響系統(tǒng)的性能。

(4)在一個有很多處理器的系統(tǒng)中，當進程用完它們的時間片以后需等待重算，以得到新的時間片，從而導(dǎo)致大部分的處理器處于空閑狀態(tài)；這將影響SMP的效率。

因此，不難看出當系統(tǒng)中有大量的可執(zhí)行進程時，選擇一個進程去執(zhí)行可能要花費較長的時間，系統(tǒng)中有多個處理器的時候，難度就更大了，這種調(diào)度，在多處理器或者系統(tǒng)負載比較高的情況下，性能受到影響。

2 Linux2.4調(diào)度器性能低下的原因

從上面的分析可以看出，造成Linux2.4調(diào)度器性能低下的主要原因如下：

(1)系統(tǒng)中調(diào)度算法屬于O(n)，開銷是線性增長的；

(2)只有一個全局的就緒進程隊列，對多處理器的伸縮性支持不好；

(3)處理器的親和性不好，容易導(dǎo)致進程在處理器之間“跳躍”；

(4)時間片的重算循環(huán)制約了多處理器的效率。

Linux2.6做了很大的改進，它采用O(1)算法，它在高負載的情況下執(zhí)行得極其出色，并且當有很多處理器時也可以很好地擴展，不但大大改善了對SMP的支持，同時也兼顧了單CPU或者雙CPU系統(tǒng)的要求。

3 Linux2.6調(diào)度器的改進目標

為了改善Linux2.4的上述不足，Linux2.6的調(diào)度器可以通過提供下列新的特性來改善調(diào)度器的性能：

(1)提供完全的O(1)調(diào)度算法，也就是說，不管系統(tǒng)中進程數(shù)量的多少，調(diào)度器中所有的算法都必須在常數(shù)時間內(nèi)完成。

(2)應(yīng)該對SMP有良好的可伸縮性，理想情況下，每個處理器應(yīng)該有獨立的可執(zhí)行進程隊列和鎖機制。

(3)應(yīng)該提高SMP的處理器親和性，但是同時也應(yīng)該有在負載不平衡的時候在處理器間遷移進程的能力。

4 Linux2.6的調(diào)度機制

新的調(diào)度器都實現(xiàn)了這些目標，具體方法是。基于每個CPU來分布時間片，并且取消了全局同步和重算循環(huán)。

每個進程有兩個數(shù)組，活動就緒進程隊列數(shù)組和不活躍就緒進程隊列數(shù)組。每個數(shù)組中有140個就緒進程隊列(runqueue)，每個隊列對應(yīng)于140個優(yōu)先級的某一個。由一個位圖來指示哪些隊列是空的，哪些不是空的，每個隊列都是先進先出的(FIFO)。這樣，在挑選進程的時候，只要通過find_first_bit找到第一個不為空的隊列，并取隊首的進程就可以了。

如果一個進程消耗完了它的“時間片”，就進入不活躍就緒進程數(shù)組的相應(yīng)隊列的隊尾。當所有的進程都“耗盡”了它的“時間片”后，交換活躍與不活躍就緒進程隊列數(shù)組的指針就可以了，不需要任何其他的開銷。

這樣，不管隊列中有多少個就緒進程，挑選就緒程的速度是一定的，所以稱為0(1)算法，該算法可描述如下，示意圖如圖2所示。

這個算法有很多的優(yōu)點，簡述如下：

(1)每個處理器都有獨立的就緒進程隊列，各個處理器可以并行地運行Scheduler程序來挑選進程運行，不同處理器上的進程可以完全并行地休眠、喚醒和上下文切換。

(2)進程只映射到一個處理器的就緒進程隊列中，不會被其他的處理器選中，因而也就不會在不同的處理器之間跳躍。

當然，處理器有時確實需要在處理器之間遷移進程，例如負載不平衡的時候，每個處理器每200ms檢查一次其他的處理器是不是處在負載不平衡的狀況下，就緒進程隊列為空的處理器會每lms檢查一次。

但是這種情況并不是頻繁的發(fā)生，所以處理器的親和性基本能得到保證。

新的調(diào)度器的性能確實有很大提高，一個服務(wù)器在多個處理器間傳送大量的消息的測試結(jié)果如表1所示。

從表中可以看出，使用新的調(diào)度器，在同樣的時間內(nèi)系統(tǒng)能作更多的事情。

5 Linux2.6調(diào)度器的不足

新的調(diào)度算法在以下幾個方面有待改進。

首先，盡管處理器的速度在很快的發(fā)展，但是存儲體系的速度發(fā)展卻是相對比較緩慢，對存儲器的操作時間往往形成瓶頸。

調(diào)度器給處理器分配進程的時候應(yīng)該考慮進程的相關(guān)性。考慮這樣的一種情況：兩個進程頻繁的通過管道或者共享內(nèi)存通信，測試表明，它們在同一個處理器上工作會更好，因為不用涉及到把數(shù)據(jù)從一個處理器的caehe里拷貝到另一個處理器的cache里。而目前的調(diào)度器不能保證將這樣有著密切聯(lián)系的進程分配到同一個處理器上。同樣的問題也存在于設(shè)備的相關(guān)性。

其次，仍是進程遷移問題，因為在處理器間遷移不同進程的代價是不盡相同的，所以在遷移進程的時候，應(yīng)該適當考慮進程的特點。

遷移進程的時應(yīng)考慮進程的大小(這里是指占有內(nèi)存資源的大小)，遷移進程的時候，并設(shè)有考慮到進程占用內(nèi)存的大小，遷移大的進程到其他的處理器會較嚴重的影響系統(tǒng)的性能。試想出現(xiàn)這樣情況：處理器A把它惟一的大進程遷移到了處理器B，而處理器B上的所有進程都是大進程，存儲資源原本就緊張，這樣一來，處理器A上的進程存儲資源就很豐富。而處理器B則更加槽糕。目前，Linux2.6調(diào)度器在遷移進程的時候還沒有考慮進程的大小。

最后，當系統(tǒng)檢測到需要遷移進程以平衡負載的時候，是不是真的非平衡負載不可呢?當系統(tǒng)的負載不平衡且很輕微的時候，是不一定需要平衡負載的。假設(shè)有這樣情況：有六個進程要求同時執(zhí)行完畢，但是系統(tǒng)中只有四個處理器。這樣，總有兩個處理器有兩個進程，而其他兩個處理器只有一個進程。這就出現(xiàn)問題，因為系統(tǒng)總是不平衡的，導(dǎo)致總有進程在同處理器間遷移，這也就形成了跳躍。

6 對Linux2.6調(diào)度器的幾點改進建議

同一個任務(wù)隊列的進程和同一家族的進程盡量映射到同一個處理器上，因為這些進程之間需要頻繁通信的可能性是最大的；還可以動態(tài)地調(diào)整進程與處理器的映射，當監(jiān)測出兩個處在不同的處理器上的進程頻繁通信的時候，就利用每200ms檢查負載平衡的計劃將它們調(diào)整到同一個處理器上。

可以在每個進程的就緒進程位圖中存儲一些大進程的標志信息，跟本處理器中大進程占的比重來遷出或者遷入大進程。

設(shè)置一個調(diào)節(jié)負載平衡的處理器負載閾值load_threshold，在load_balance函數(shù)中檢查系統(tǒng)欲調(diào)節(jié)負載的處理器的實際負載，沒有超過事先給定的threshold，就不對這個處理器作真正意義上的負載平衡調(diào)節(jié)。