Linux2.4與Linux2.6內核調度器的比較研究

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

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

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

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

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

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

1 Linux2.4的調度機制

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

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

由算法可以看出，Linux2.4的調度算法可以說(shuō)是一個(gè)O(n)算法，因為調度器挑選執行進(jìn)程的開(kāi)銷(xiāo)是隨系統中就緒進(jìn)程 的增長(cháng)而線(xiàn)性增長(cháng)的。同時(shí)，當系統中有多個(gè)處理器時(shí)，訪(fǎng)問(wèn)就緒進(jìn)程隊列就成了瓶頸，性能也會(huì )顯著(zhù)的下降。因而有很多的缺點(diǎn)：

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

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

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

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

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

2 Linux2.4調度器性能低下的原因

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

(1)系統中調度算法屬于O(n)，開(kāi)銷(xiāo)是線(xiàn)性增長(cháng)的；

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

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

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

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

3 Linux2.6調度器的改進(jìn)目標

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

(1)提供完全的O(1)調度算法，也就是說(shuō)，不管系統中進(jìn)程數量的多少，調度器中所有的算法都必須在常數時(shí)間內完成。

(2)應該對SMP有良好的可伸縮性，理想情況下，每個(gè)處理器應該有獨立的可執行進(jìn)程隊列和鎖機制。

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

4 Linux2.6的調度機制

新的調度器都實(shí)現了這些目標，具體方法是?；诿總€(gè)CPU來(lái)分布時(shí)間片，并且取消了全局同步和重算循環(huán)。

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

如果一個(gè)進(jìn)程消耗完了它的“時(shí)間片”，就進(jìn)入不活躍就緒進(jìn)程數組的相應隊列的隊尾。當所有的進(jìn)程都“耗盡”了它的“時(shí)間片”后，交換活躍與不活躍就緒進(jìn)程隊列數組的指針就可以了，不需要任何其他的開(kāi)銷(xiāo)。

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

這個(gè)算法有很多的優(yōu)點(diǎn)，簡(jiǎn)述如下：

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

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

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

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

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

從表中可以看出，使用新的調度器，在同樣的時(shí)間內系統能作更多的事情。

5 Linux2.6調度器的不足

新的調度算法在以下幾個(gè)方面有待改進(jìn)。

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

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

其次，仍是進(jìn)程遷移問(wèn)題，因為在處理器間遷移不同進(jìn)程的代價(jià)是不盡相同的，所以在遷移進(jìn)程的時(shí)候，應該適當考慮進(jìn)程的特點(diǎn)。

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

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

6 對Linux2.6調度器的幾點(diǎn)改進(jìn)建議

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

可以在每個(gè)進(jìn)程的就緒進(jìn)程位圖中存儲一些大進(jìn)程的標志信息，跟本處理器中大進(jìn)程占的比重來(lái)遷出或者遷入大進(jìn)程。

設置一個(gè)調節負載平衡的處理器負載閾值load_threshold，在load_balance函數中檢查系統欲調節負載的處理器的實(shí)際負載，沒(méi)有超過(guò)事先給定的threshold，就不對這個(gè)處理器作真正意義上的負載平衡調節。