本文將回顧一下 Linux 2.6 的任務(wù)調(diào)度器及其最重要的一些屬性。在深入介紹調(diào)度器的詳細(xì)信息之前，讓我們先來理解一下調(diào)度器的基本目標(biāo)。

什么是調(diào)度器？

通常來說，操作系統(tǒng)是應(yīng)用程序和可用資源之間的媒介。典型的資源有內(nèi)存和物理設(shè)備。但是 CPU 也可以認(rèn)為是一個資源，調(diào)度器可以臨時分配一個任務(wù)在上面執(zhí)行（單位是時間片）。調(diào)度器使得我們同時執(zhí)行多個程序成為可能，因此可以與具有各種需求的用戶共享 CPU。

調(diào)度器的一個重要目標(biāo)是有效地分配 CPU 時間片，同時提供很好的用戶體驗(yàn)。調(diào)度器還需要面對一些互相沖突的目標(biāo)，例如既要為關(guān)鍵實(shí)時任務(wù)最小化響應(yīng)時間，又要最大限度地提高 CPU 的總體利用率。下面我們來看一下 Linux 2.6 調(diào)度程序是如何實(shí)現(xiàn)這些目標(biāo)的，并與以前的調(diào)度器進(jìn)行比較。

回頁首

早期 Linux 調(diào)度器的問題

在 2.6 版本的內(nèi)核之前，當(dāng)很多任務(wù)都處于活動狀態(tài)時，調(diào)度器有很明顯的限制。這是由于調(diào)度器是使用一個復(fù)雜度為 O(n) 的算法實(shí)現(xiàn)的。在這種調(diào)度器中，調(diào)度任務(wù)所花費(fèi)的時間是一個系統(tǒng)中任務(wù)個數(shù)的函數(shù)。換而言之，活動的任務(wù)越多，調(diào)度任務(wù)所花費(fèi)的時間越長。在任務(wù)負(fù)載非常重時，處理器會因調(diào)度消耗掉大量的時間，用于任務(wù)本身的時間就非常少了。因此，這個算法缺乏可伸縮性。

在對稱多處理系統(tǒng)（SMP）中，2.6 版本之前的調(diào)度器對所有的處理器都使用一個運(yùn)行隊(duì)列。這意味著一個任務(wù)可以在任何處理器上進(jìn)行調(diào)度 —— 這對于負(fù)載均衡來說是好事，但是對于內(nèi)存緩存來說卻是個災(zāi)難。例如，假設(shè)一個任務(wù)正在 CPU-1 上執(zhí)行，其數(shù)據(jù)在這個處理器的緩存中。如果這個任務(wù)被調(diào)度到 CPU-2 上執(zhí)行，那么數(shù)據(jù)就需要先在 CPU-1 使其無效，并將其放到 CPU-2 的緩存中。

以前的調(diào)度器還使用了一個運(yùn)行隊(duì)列鎖；因此在 SMP 系統(tǒng)中，選擇一個任務(wù)執(zhí)行就會阻礙其他處理器操作這個運(yùn)行隊(duì)列。結(jié)果是空閑處理器只能等待這個處理器釋放出運(yùn)行隊(duì)列鎖，這樣會造成效率的降低。

最后，在早期的內(nèi)核中，搶占是不可能的；這意味著如果有一個低優(yōu)先級的任務(wù)在執(zhí)行，高優(yōu)先級的任務(wù)只能等待它完成。

回頁首

Linux 2.6 調(diào)度器簡介

2.6 版本的調(diào)度器是由 Ingo Molnar 設(shè)計并實(shí)現(xiàn)的。Ingo 從 1995 年開始就一直參與 Linux 內(nèi)核的開發(fā)。他編寫這個新調(diào)度器的動機(jī)是為喚醒、上下文切換和定時器中斷開銷建立一個完全 O(1) 的調(diào)度器。觸發(fā)對新調(diào)度器的需求的一個問題是 Java? 虛擬機(jī)（JVM）的使用。Java 編程模型使用了很多執(zhí)行線程，在 O(n) 調(diào)度器中這會產(chǎn)生很多調(diào)度負(fù)載。O(1) 調(diào)度器在這種高負(fù)載的情況下并不會受到太多影響，因此 JVM 可以有效地執(zhí)行。

2.6 版本的調(diào)度器解決了以前調(diào)度器中發(fā)現(xiàn)的 3 個主要問題（O(n) 和 SMP 可伸縮性的問題），還解決了其他一些問題?，F(xiàn)在我們將開始探索一下 2.6 版本的調(diào)度器的基本設(shè)計。

主要的調(diào)度結(jié)構(gòu)

首先我們來回顧一下 2.6 版本的調(diào)度器結(jié)構(gòu)。每個 CPU 都有一個運(yùn)行隊(duì)列，其中包含了 140 個優(yōu)先級列表，它們是按照先進(jìn)先出的順序進(jìn)行服務(wù)的。被調(diào)度執(zhí)行的任務(wù)都會被添加到各自運(yùn)行隊(duì)列優(yōu)先級列表的末尾。每個任務(wù)都有一個時間片，這取決于系統(tǒng)允許執(zhí)行這個任務(wù)多長時間。運(yùn)行隊(duì)列的前 100 個優(yōu)先級列表保留給實(shí)時任務(wù)使用，后 40 個用于用戶任務(wù)（參見圖 1）。我們稍后將來看一下為什么這種區(qū)別非常重要。

圖 1. Linux 2.6 調(diào)度器的運(yùn)行隊(duì)列結(jié)構(gòu)

除了 CPU 的運(yùn)行隊(duì)列（稱為活動運(yùn)行隊(duì)列（active runqueue））之外，還有一個過期運(yùn)行隊(duì)列。當(dāng)活動運(yùn)行隊(duì)列中的一個任務(wù)用光自己的時間片之后，它就被移動到過期運(yùn)行隊(duì)列（expired runqueue） 中。在移動過程中，會對其時間片重新進(jìn)行計算（因此會體現(xiàn)其優(yōu)先級的作用；稍后會更詳細(xì)地介紹）。如果活動運(yùn)行隊(duì)列中已經(jīng)沒有某個給定優(yōu)先級的任務(wù)了，那么指向活動運(yùn)行隊(duì)列和過期運(yùn)行隊(duì)列的指針就會交換，這樣就可以讓過期優(yōu)先級列表變成活動優(yōu)先級的列表。

調(diào)度器的工作非常簡單：它在優(yōu)先級最高的隊(duì)列中選擇一個任務(wù)來執(zhí)行。為了使這個過程的效率更高，內(nèi)核使用了一個位圖來定義給定優(yōu)先級列表上何時存在任務(wù)。因此，在大部分體系架構(gòu)上，會使用一條 find-first-bit-set 指令在 5 個 32 位的字（140 個優(yōu)先級）中哪一位的優(yōu)先級最高。查找一個任務(wù)來執(zhí)行所需要的時間并不依賴于活動任務(wù)的個數(shù)，而是依賴于優(yōu)先級的數(shù)量。這使得 2.6 版本的調(diào)度器成為一個復(fù)雜度為 O(1) 的過程，因?yàn)檎{(diào)度時間既是固定的，而且也不會受到活動任務(wù)個數(shù)的影響。

更好地支持 SMP 系統(tǒng)

那么什么是 SMP 呢？SMP 是一種體系架構(gòu)，其中多個 CPU 可以用來同時執(zhí)行各個任務(wù)，它與傳統(tǒng)的非對稱處理系統(tǒng)不同，后者使用一個 CPU 來執(zhí)行所有的任務(wù)。SMP 體系架構(gòu)對多線程的應(yīng)用程序非常有益。

盡管優(yōu)先級調(diào)度在 SMP 系統(tǒng)上也可以工作，但是它這種大鎖體系架構(gòu)意味著當(dāng)一個 CPU 選擇一個任務(wù)進(jìn)行分發(fā)調(diào)度時，運(yùn)行隊(duì)列會被這個 CPU 加鎖，其他 CPU 只能等待。2.6 版本的調(diào)度器不是使用一個鎖進(jìn)行調(diào)度；相反，它對每個運(yùn)行隊(duì)列都有一個鎖。這樣允許所有的 CPU 都可以對任務(wù)進(jìn)行調(diào)度，而不會與其他 CPU 產(chǎn)生競爭。

另外，由于每個處理器都有一個運(yùn)行隊(duì)列，因此任務(wù)通常都是與 CPU 密切相關(guān)的，可以更好地利用 CPU 的熱緩存。

任務(wù)搶占

Linux 2.6 版本調(diào)度器的另外一個優(yōu)點(diǎn)是它允許搶占。這意味著當(dāng)高優(yōu)先級的任務(wù)準(zhǔn)備運(yùn)行時低優(yōu)先級的任務(wù)就不能執(zhí)行了。調(diào)度器會搶占低優(yōu)先級的進(jìn)程，并將這個進(jìn)程放回其優(yōu)先級列表中，然后重新進(jìn)行調(diào)度。

回頁首

但是請等一下，還有更多功能呢！

似乎 2.6 版本調(diào)度器的 O(1) 特性和搶占特性還不夠，這個調(diào)度器還提供了動態(tài)任務(wù)優(yōu)先級和 SMP 負(fù)載均衡功能。下面就讓我們來討論一下這些功能都是什么，以及它們分別提供了哪些優(yōu)點(diǎn)。

動態(tài)任務(wù)優(yōu)先級

為了防止任務(wù)獨(dú)占 CPU 從而會餓死其他需要訪問 CPU 的任務(wù)，Linux 2.6 版本的調(diào)度器可以動態(tài)修改任務(wù)的優(yōu)先級。這是通過懲罰 CPU 綁定的任務(wù)而獎勵 I/O 綁定的任務(wù)實(shí)現(xiàn)的。I/O 綁定的任務(wù)通常使用 CPU 來設(shè)置 I/O，然后就睡眠等待 I/O 操作完成。這種行為為其他任務(wù)提供了 CPU 的訪問能力。

由于 I/O 綁定型的任務(wù)對于 CPU 訪問來說是無私的，因此其優(yōu)先級減少（獎勵）最多 5 個優(yōu)先級。CPU 綁定的任務(wù)會通過將其優(yōu)先級增加最多 5 個優(yōu)先級進(jìn)行懲罰。

任務(wù)到底是 I/O 綁定的還是 CPU 綁定的，這是根據(jù)交互性 原則確定的。任務(wù)的交互性指標(biāo)是根據(jù)任務(wù)執(zhí)行所花費(fèi)的時間與睡眠所花費(fèi)的時間的對比程度進(jìn)行計算的。注意，由于 I/O 任務(wù)先對 I/O 進(jìn)行調(diào)度，然后再進(jìn)行睡眠，因此 I/O 綁定的任務(wù)會在睡眠和等待 I/O 操作完成上面花費(fèi)更多的時間。這會提高其交互性指標(biāo)。

有一點(diǎn)值得注意，優(yōu)先級的調(diào)整只會對用戶任務(wù)進(jìn)行，對于實(shí)時任務(wù)來說并不會對其優(yōu)先級進(jìn)行調(diào)整。

SMP 負(fù)載均衡

在 SMP 系統(tǒng)中創(chuàng)建任務(wù)時，這些任務(wù)都被放到一個給定的 CPU 運(yùn)行隊(duì)列中。通常來說，我們無法知道一個任務(wù)何時是短期存在的，何時需要長期運(yùn)行。因此，最初任務(wù)到 CPU 的分配可能并不理想。

為了在 CPU 之間維護(hù)任務(wù)負(fù)載的均衡，任務(wù)可以重新進(jìn)行分發(fā)：將任務(wù)從負(fù)載重的 CPU 上移動到負(fù)載輕的 CPU 上。Linux 2.6 版本的調(diào)度器使用負(fù)載均衡（load balancing） 提供了這種功能。每隔 200ms，處理器都會檢查 CPU 的負(fù)載是否不均衡；如果不均衡，處理器就會在 CPU 之間進(jìn)行一次任務(wù)均衡操作。

這個過程的一點(diǎn)負(fù)面影響是新 CPU 的緩存對于遷移過來的任務(wù)來說是冷的（需要將數(shù)據(jù)讀入緩存中）。

記住 CPU 緩存是一個本地（片上）內(nèi)存，提供了比系統(tǒng)內(nèi)存更快的訪問能力。如果一個任務(wù)是在某個 CPU 上執(zhí)行的，與這個任務(wù)有關(guān)的數(shù)據(jù)都會被放到這個 CPU 的本地緩存中，這就稱為熱的。如果對于某個任務(wù)來說，CPU 的本地緩存中沒有任何數(shù)據(jù)，那么這個緩存就稱為冷的。

不幸的是，保持 CPU 繁忙會出現(xiàn) CPU 緩存對于遷移過來的任務(wù)為冷的情況。

回頁首

挖掘更多潛能

2.6 版本調(diào)度器的源代碼都很好地封裝到了 /usr/src/linux/kernel/sched.c 文件中。我們在表 1 中對在這個文件中可以找到的一些有用的函數(shù)進(jìn)行了總結(jié)。

運(yùn)行隊(duì)列的結(jié)構(gòu)也可以在 /usr/src/linux/kernel/sched.c 文件中找到。2.6 版本的調(diào)度器還可以提供一些統(tǒng)計信息（如果啟用了 CONFIG_SCHEDSTATS）。這些統(tǒng)計信息可以從 /proc 文件系統(tǒng)中的 /proc/schedstat 看到，它為系統(tǒng)中的每個 CPU 都提供了很多數(shù)據(jù)，包括負(fù)載均衡和進(jìn)程遷移的統(tǒng)計信息。

回頁首

展望

Linux 2.6 調(diào)度器從早先的 Linux 調(diào)度器已經(jīng)跨越了一大步。它極大地改善了最大化利用 CPU 的能力，同時還為用戶提供了很好的響應(yīng)體驗(yàn)。搶占和對多處理器體系架構(gòu)的更好支持使整個系統(tǒng)更接近于多桌面和實(shí)時系統(tǒng)都非常有用的操作系統(tǒng)。Linux 2.8 版本的內(nèi)核現(xiàn)在談?wù)撨€為時尚早，但是從 2.6 版本的變化中，我們可以期望會有更多的好東西。

參考資料

學(xué)習(xí)

• 您可以參閱本文在 developerWorks 全球站點(diǎn)上的 英文原文 。
• “改善 Linux 內(nèi)核性能和可伸縮性”（developerWorks，2003 年 1 月）解釋了如何確定 Linux 內(nèi)核系統(tǒng)的性能，這樣我們就可以對系統(tǒng)進(jìn)行評測和調(diào)優(yōu)（包括調(diào)度器調(diào)優(yōu)）。
• Open Source Development Labs 上的 Linux Process Scheduler Improvements in Version 2.6.0 文章給出了 2.6 版本的調(diào)度器對 2.4 版本的調(diào)度器在各種多處理器系統(tǒng)配置上的改進(jìn)。
• “Linux Kernel 2.6: the Future of Embedded Computing”（Linux Journal，2004 年 3 月）簡要介紹了 2.6 版本內(nèi)核的一些重要特性，包括調(diào)度器及其在嵌入式系統(tǒng)中的影響。
• “內(nèi)核比較: 從 2.4 到 2.6 內(nèi)核開發(fā)中的改進(jìn)”（developerWorks，2004 年 2 月）對讓 2.6 版本更好的工具、測試和技術(shù)進(jìn)行了介紹。
• IBM 紅皮書 An Application Centric Performance Evaluation of the Linux 2.6 Operating System（2004 年 7 月）重點(diǎn)介紹了圍繞著實(shí)際應(yīng)用程序和 Linux 2.6 框架周圍的與可伸縮性和性能有關(guān)的問題。
• “在 iSeries 和 pSeries 上將 Linux 內(nèi)核從 2.4 遷移到 2.6”（developerWorks，2004 年 7 月）重點(diǎn)介紹了 2.4 版本和 2.6 版本的 Linux 內(nèi)核在 POWER 架構(gòu)上的區(qū)別。
• “Linux 2.6 for Embedded Systems -- Closing in on Real Time”（RTC Magazine，2003 年 11 月）討論了具有實(shí)時屬性的嵌入式系統(tǒng)如何從 2.6 版本的調(diào)度器中獲得最多優(yōu)勢。
• 在 What's New in Linux 2.6（Ulrich Weigand 博士的一篇演示文稿），我們可以看到 Linux 2.6 是如何幫助 IBM zSeries 開發(fā)的。
• 在 developerWorks Linux 專區(qū) 可以找到為 Linux 開發(fā)人員準(zhǔn)備的更多資源。
• 隨時關(guān)注 developerWorks 技術(shù)事件和網(wǎng)絡(luò)廣播。

獲得產(chǎn)品和技術(shù)

• 在 Linux Kernel Archives 上，查找最新的 Linux 內(nèi)核。
• 在您的下一個開發(fā)項(xiàng)目中采用 IBM 試用軟件，這可以從 developerWorks 上直接下載。

討論

• 通過參與 developerWorks blogs 加入 developerWorks 社區(qū)。