Linux的內(nèi)核開發(fā)是一個漫長的過程，自2001年11月開發(fā)出2.5.0以來，Linux內(nèi)核的發(fā)展十分迅速，作了很多重大的改進(jìn)，性能也有了很大的提高。內(nèi)核調(diào)度器的改進(jìn)是最主要的進(jìn)步之一，本文對比研究了Linux2.4和Linux2.6的調(diào)度器，全面剖析了Linux2.6對調(diào)度器的改進(jìn)。
　　一個成功的調(diào)度器的基本要求可以概括為以下三點(diǎn)：
　　(1)減少花在調(diào)度上的時間，以增加花在執(zhí)行程序上的時間；
　　(2)在多處理器" title="多處理器">多處理器系統(tǒng)上，保持處理器的負(fù)載平衡；
　　(3)對交互式應(yīng)用有良好的響應(yīng)速度。
　　但是，一個成功的調(diào)度器是很難設(shè)計(jì)好的， 因?yàn)橐粋€真正投入運(yùn)行的系統(tǒng)受到很多因素的制約。相對于Linux2.6，Linux2.4的調(diào)度器有很多的不足之處， 2.6版本的Linux內(nèi)核使用了新的調(diào)度器算法，稱為O(1)算法，它在高負(fù)載的情況下執(zhí)行得極其出色，并且當(dāng)有很多處理器時也可以很好地擴(kuò)展。
　　O(n)算法，O代表order，括號里的數(shù)字代表最壞情況下算法效率的上限取決于算法涉及到的元素的個數(shù)，O(1)說明是一個常數(shù)，在這種情況下，每次調(diào)度的效率是一樣的，與涉及的元素的多少沒有關(guān)系，O(n)表示算法效率取決于算法涉及元素的個數(shù)。
1 Linux2.4的調(diào)度機(jī)制
　　Linux2.4的調(diào)度機(jī)制可以用下面的" title="面的">面的算法來描述^[3]，示意圖如圖1所示。

　　for(each runnable process on the system) {
　　　　find worthiness of this process
　　　　if(this is the worthiest process yet) remember it
　　}
　　if(the worthiest process′timeslice is zero) recalculate timeslice
　　else run the most worthy process
　　所有的就緒進(jìn)程都在一個全局的就緒進(jìn)程隊(duì)列中，這個隊(duì)列沒有任何有意義的排序；時間片重算算法是在所有的進(jìn)程都用盡它們的時間片以后才重新計(jì)算。整個隊(duì)列由一個讀/寫自旋鎖(read/write spinlock)保護(hù)著，這樣多個處理器可以并行訪問，但同時提供寫操作的互斥訪問。
　　由算法可以看出，Linux2.4的調(diào)度算法可以說是一個O(n)算法，因?yàn)檎{(diào)度器挑選執(zhí)行進(jìn)程的開銷是隨系統(tǒng)中就緒進(jìn)程的增長而線性增長的^[1]。同時，當(dāng)系統(tǒng)中有多個處理器時，訪問就緒進(jìn)程隊(duì)列就成了瓶頸，性能也會顯著的下降。因而有很多的缺點(diǎn)：
　　(1)每次調(diào)度時，調(diào)度器都要線性遍歷" title="遍歷">遍歷這個隊(duì)列，以找出最值得運(yùn)行的進(jìn)程執(zhí)行：當(dāng)系統(tǒng)負(fù)載很高的時候，可執(zhí)行進(jìn)程隊(duì)列會很長，線性搜索的時間是線性增長的，這個時間會很長，當(dāng)這個時間足夠長的時候，有可能出現(xiàn)多個處理器選擇了同一個進(jìn)程的情況，這樣，有些處理器會發(fā)現(xiàn)，他選擇的進(jìn)程已經(jīng)分配了其他的處理器，而不得不重新選擇，甚至出現(xiàn)選擇運(yùn)行進(jìn)程的時間比實(shí)際執(zhí)行進(jìn)程的時間還要長的情況。
　　(2)當(dāng)大多數(shù)的就緒進(jìn)程的時間片都用完而又還沒有重新分配時間片的時候，SMP系統(tǒng)中有些處理器處于空閑狀態(tài)，這將影響SMP的效率。
　　(3)當(dāng)空閑的處理器開始執(zhí)行那些時間片尚未用盡而處于等待狀態(tài)的進(jìn)程(如果它們自己的處理器忙)時，會導(dǎo)致進(jìn)程開始在處理器之間“跳躍”，實(shí)時進(jìn)程或者占用內(nèi)存大的進(jìn)程在處理器之間跳躍會嚴(yán)重影響系統(tǒng)的性能。
　　(4)在一個有很多處理器的系統(tǒng)中，當(dāng)進(jìn)程用完它們的時間片以后需等待重算，以得到新的時間片，從而導(dǎo)致大部分的處理器處于空閑狀態(tài)；這將影響SMP的效率。
　　因此，不難看出當(dāng)系統(tǒng)中有大量的可執(zhí)行進(jìn)程時，選擇一個進(jìn)程去執(zhí)行可能要花費(fèi)較長的時間，系統(tǒng)中有多個處理器的時候，難度就更大了，這種調(diào)度，在多處理器或者系統(tǒng)負(fù)載比較高的情況下，性能受到影響。
2 Linux2.4調(diào)度器性能低下的原因
　　從上面的分析可以看出，造成Linux2.4調(diào)度器性能低下的主要原因如下：
　　(1)系統(tǒng)中調(diào)度算法屬于O(n)，開銷是線性增長的；
　　(2)只有一個全局的就緒進(jìn)程隊(duì)列，對多處理器的伸縮性支持不好；
　　(3)處理器的親和性不好，容易導(dǎo)致進(jìn)程在處理器之間“跳躍”；
　　(4)時間片的重算循環(huán)制約了多處理器的效率。
　　Linux2.6做了很大的改進(jìn)，它采用O(1)算法，它在高負(fù)載的情況下執(zhí)行得極其出色，并且當(dāng)有很多處理器時也可以很好地擴(kuò)展，不但大大改善了對SMP的支持，同時也兼顧了單CPU或者雙CPU系統(tǒng)的要求。
3 Linux2.6調(diào)度器的改進(jìn)目標(biāo)
　　為了改善Linux2.4的上述不足，linux2.6的調(diào)度器可以通過提供下列新的特性來改善調(diào)度器的性能：
　　(1)提供完全的O(1)調(diào)度算法，也就是說，不管系統(tǒng)中進(jìn)程數(shù)量的多少，調(diào)度器中所有的算法都必須在常數(shù)時間內(nèi)完成。
　　(2)應(yīng)該對SMP有良好的可伸縮性，理想情況下,每個處理器應(yīng)該有獨(dú)立的可執(zhí)行進(jìn)程隊(duì)列和鎖機(jī)制。
　　(3)應(yīng)該提高SMP 的處理器親和性，但是同時也應(yīng)該有在負(fù)載不平衡" title="不平衡">不平衡的時候在處理器間遷移進(jìn)程的能力。
4 Linux2.6的調(diào)度機(jī)制
　　新的調(diào)度器都實(shí)現(xiàn)了這些目標(biāo)，具體方法是，基于每個 CPU 來分布時間片，并且取消了全局同步和重算循環(huán)^[2]。
　　每個進(jìn)程有兩個數(shù)組，活動就緒進(jìn)程隊(duì)列數(shù)組和不活躍就緒進(jìn)程隊(duì)列數(shù)組。每個數(shù)組中有140個就緒進(jìn)程隊(duì)列(runqueue)，每個隊(duì)列對應(yīng)于140個優(yōu)先級的某一個。由一個位圖來指示哪些隊(duì)列是空的，哪些不是空的，每個隊(duì)列都是先進(jìn)先出的(FIFO)。這樣，在挑選進(jìn)程的時候，只要通過find_first_bit找到第一個不為空的隊(duì)列，并取隊(duì)首的進(jìn)程就可以了。
　　如果一個進(jìn)程消耗完了它的“時間片”，就進(jìn)入不活躍就緒進(jìn)程數(shù)組的相應(yīng)隊(duì)列的隊(duì)尾。當(dāng)所有的進(jìn)程都“耗盡”了它的“時間片”后，交換活躍與不活躍就緒進(jìn)程隊(duì)列數(shù)組的指針就可以了，不需要任何其他的開銷。
　　這樣，不管隊(duì)列中有多少個就緒進(jìn)程，挑選就緒程的速度是一定的，所以稱為O(1)算法，該算法可描述如下，示意圖如圖2所示。

　　get the highest priority level that has processes
　　get first process in the list at that priority level
　　run this process
　　這個算法有很多的優(yōu)點(diǎn)，簡述如下：
　　(1)每個處理器都有獨(dú)立的就緒進(jìn)程隊(duì)列，各個處理器可以并行地運(yùn)行Scheduler程序來挑選進(jìn)程運(yùn)行，不同處理器上的進(jìn)程可以完全并行地休眠、喚醒和上下文切換。
　　(2)進(jìn)程只映射到一個處理器的就緒進(jìn)程隊(duì)列中，不會被其他的處理器選中，因而也就不會在不同的處理器之間跳躍。
　　當(dāng)然，處理器有時確實(shí)需要在處理器之間遷移進(jìn)程，例如負(fù)載不平衡的時候，每個處理器每200ms檢查一次其他的處理器是不是處在負(fù)載不平衡的狀況下，就緒進(jìn)程隊(duì)列為空的處理器會每1ms檢查一次。
　　但是這種情況并不是頻繁的發(fā)生，所以處理器的親和性基本能得到保證。
　　新的調(diào)度器的性能確實(shí)有很大提高，一個服務(wù)器在多個處理器間傳送大量的消息的測試結(jié)果如表1所示。從表中可以看出，使用新的調(diào)度器，在同樣的時間內(nèi)系統(tǒng)能作更多的事情。