|
本文將回顧一下 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)為是一個(gè)資源，調(diào)度器可以臨時(shí)分配一個(gè)任務(wù)在上面執(zhí)行（單位是時(shí)間片）。調(diào)度器使得我們同時(shí)執(zhí)行多個(gè)程序成為可能，因此可以與具有各種需求的用戶共享 CPU。 調(diào)度器的一個(gè)重要目標(biāo)是有效地分配 CPU 時(shí)間片，同時(shí)提供很好的用戶體驗(yàn)。調(diào)度器還需要面對一些互相沖突的目標(biāo)，例如既要為關(guān)鍵實(shí)時(shí)任務(wù)最小化響應(yīng)時(shí)間，又要最大限度地提高 CPU 的總體利用率。下面我們來看一下 Linux 2.6 調(diào)度程序是如何實(shí)現(xiàn)這些目標(biāo)的，并與以前的調(diào)度器進(jìn)行比較。 早期 Linux 調(diào)度器的問題O-notation 的重要性O-notation 可以告訴我們一個(gè)算法會占用多少時(shí)間。一個(gè) O(n) 算法所需要的時(shí)間依賴于輸入的多少（與 n 是線性關(guān)系），而 O(n^2) 則是輸入數(shù)量的平方。O(1) 與輸入無關(guān)，可以在固定的時(shí)間內(nèi)完成操作。 在 2.6 版本的內(nèi)核之前，當(dāng)很多任務(wù)都處于活動狀態(tài)時(shí)，調(diào)度器有很明顯的限制。這是由于調(diào)度器是使用一個(gè)復(fù)雜度為 O(n) 的算法實(shí)現(xiàn)的。在這種調(diào)度器中，調(diào)度任務(wù)所花費(fèi)的時(shí)間是一個(gè)系統(tǒng)中任務(wù)個(gè)數(shù)的函數(shù)。換而言之，活動的任務(wù)越多，調(diào)度任務(wù)所花費(fèi)的時(shí)間越長。在任務(wù)負(fù)載非常重時(shí)，處理器會因調(diào)度消耗掉大量的時(shí)間，用于任務(wù)本身的時(shí)間就非常少了。因此，這個(gè)算法缺乏可伸縮性。 在對稱多處理系統(tǒng)（SMP）中，2.6 版本之前的調(diào)度器對所有的處理器都使用一個(gè)運(yùn)行隊(duì)列。這意味著一個(gè)任務(wù)可以在任何處理器上進(jìn)行調(diào)度 —— 這對于負(fù)載均衡來說是好事，但是對于內(nèi)存緩存來說卻是個(gè)災(zāi)難。例如，假設(shè)一個(gè)任務(wù)正在 CPU-1 上執(zhí)行，其數(shù)據(jù)在這個(gè)處理器的緩存中。如果這個(gè)任務(wù)被調(diào)度到 CPU-2 上執(zhí)行，那么數(shù)據(jù)就需要先在 CPU-1 使其無效，并將其放到 CPU-2 的緩存中。 以前的調(diào)度器還使用了一個(gè)運(yùn)行隊(duì)列鎖；因此在 SMP 系統(tǒng)中，選擇一個(gè)任務(wù)執(zhí)行就會阻礙其他處理器操作這個(gè)運(yùn)行隊(duì)列。結(jié)果是空閑處理器只能等待這個(gè)處理器釋放出運(yùn)行隊(duì)列鎖，這樣會造成效率的降低。 最后，在早期的內(nèi)核中，搶占是不可能的；這意味著如果有一個(gè)低優(yōu)先級的任務(wù)在執(zhí)行，高優(yōu)先級的任務(wù)只能等待它完成。 Linux 2.6 調(diào)度器簡介2.6 版本的調(diào)度器是由 Ingo Molnar 設(shè)計(jì)并實(shí)現(xiàn)的。Ingo 從 1995 年開始就一直參與 Linux 內(nèi)核的開發(fā)。他編寫這個(gè)新調(diào)度器的動機(jī)是為喚醒、上下文切換和定時(shí)器中斷開銷建立一個(gè)完全 O(1) 的調(diào)度器。觸發(fā)對新調(diào)度器的需求的一個(gè)問題是 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 個(gè)主要問題（O(n) 和 SMP 可伸縮性的問題），還解決了其他一些問題?，F(xiàn)在我們將開始探索一下 2.6 版本的調(diào)度器的基本設(shè)計(jì)。 主要的調(diào)度結(jié)構(gòu)首先我們來回顧一下 2.6 版本的調(diào)度器結(jié)構(gòu)。每個(gè) CPU 都有一個(gè)運(yùn)行隊(duì)列，其中包含了 140 個(gè)優(yōu)先級列表，它們是按照先進(jìn)先出的順序進(jìn)行服務(wù)的。被調(diào)度執(zhí)行的任務(wù)都會被添加到各自運(yùn)行隊(duì)列優(yōu)先級列表的末尾。每個(gè)任務(wù)都有一個(gè)時(shí)間片，這取決于系統(tǒng)允許執(zhí)行這個(gè)任務(wù)多長時(shí)間。運(yùn)行隊(duì)列的前 100 個(gè)優(yōu)先級列表保留給實(shí)時(shí)任務(wù)使用，后 40 個(gè)用于用戶任務(wù)（參見圖 1）。我們稍后將來看一下為什么這種區(qū)別非常重要。 圖 1. Linux 2.6 調(diào)度器的運(yùn)行隊(duì)列結(jié)構(gòu) 除了 CPU 的運(yùn)行隊(duì)列（稱為活動運(yùn)行隊(duì)列（active runqueue））之外，還有一個(gè)過期運(yùn)行隊(duì)列。當(dāng)活動運(yùn)行隊(duì)列中的一個(gè)任務(wù)用光自己的時(shí)間片之后，它就被移動到過期運(yùn)行隊(duì)列（expired runqueue） 中。在移動過程中，會對其時(shí)間片重新進(jìn)行計(jì)算（因此會體現(xiàn)其優(yōu)先級的作用；稍后會更詳細(xì)地介紹）。如果活動運(yùn)行隊(duì)列中已經(jīng)沒有某個(gè)給定優(yōu)先級的任務(wù)了，那么指向活動運(yùn)行隊(duì)列和過期運(yùn)行隊(duì)列的指針就會交換，這樣就可以讓過期優(yōu)先級列表變成活動優(yōu)先級的列表。 調(diào)度器的工作非常簡單：它在優(yōu)先級最高的隊(duì)列中選擇一個(gè)任務(wù)來執(zhí)行。為了使這個(gè)過程的效率更高，內(nèi)核使用了一個(gè)位圖來定義給定優(yōu)先級列表上何時(shí)存在任務(wù)。因此，在大部分體系架構(gòu)上，會使用一條 更好地支持 SMP 系統(tǒng)那么什么是 SMP 呢？SMP 是一種體系架構(gòu)，其中多個(gè) CPU 可以用來同時(shí)執(zhí)行各個(gè)任務(wù)，它與傳統(tǒng)的非對稱處理系統(tǒng)不同，后者使用一個(gè) CPU 來執(zhí)行所有的任務(wù)。SMP 體系架構(gòu)對多線程的應(yīng)用程序非常有益。 盡管優(yōu)先級調(diào)度在 SMP 系統(tǒng)上也可以工作，但是它這種大鎖體系架構(gòu)意味著當(dāng)一個(gè) CPU 選擇一個(gè)任務(wù)進(jìn)行分發(fā)調(diào)度時(shí)，運(yùn)行隊(duì)列會被這個(gè) CPU 加鎖，其他 CPU 只能等待。2.6 版本的調(diào)度器不是使用一個(gè)鎖進(jìn)行調(diào)度；相反，它對每個(gè)運(yùn)行隊(duì)列都有一個(gè)鎖。這樣允許所有的 CPU 都可以對任務(wù)進(jìn)行調(diào)度，而不會與其他 CPU 產(chǎn)生競爭。 另外，由于每個(gè)處理器都有一個(gè)運(yùn)行隊(duì)列，因此任務(wù)通常都是與 CPU 密切相關(guān)的，可以更好地利用 CPU 的熱緩存。 任務(wù)搶占Linux 2.6 版本調(diào)度器的另外一個(gè)優(yōu)點(diǎn)是它允許搶占。這意味著當(dāng)高優(yōu)先級的任務(wù)準(zhǔn)備運(yùn)行時(shí)低優(yōu)先級的任務(wù)就不能執(zhí)行了。調(diào)度器會搶占低優(yōu)先級的進(jìn)程，并將這個(gè)進(jìn)程放回其優(yōu)先級列表中，然后重新進(jìn)行調(diào)度。 但是請等一下，還有更多功能呢！似乎 2.6 版本調(diào)度器的 O(1) 特性和搶占特性還不夠，這個(gè)調(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 的訪問能力。 用戶響應(yīng)能力更好與用戶進(jìn)行通信的任務(wù)都是交互型的，因此其響應(yīng)能力應(yīng)該比非交互式任務(wù)更好。由于與用戶的通信（不管是向標(biāo)準(zhǔn)輸出上發(fā)送數(shù)據(jù)，還是通過標(biāo)準(zhǔn)輸入等待輸入數(shù)據(jù)）都是 I/O 綁定型的，因此提高這些任務(wù)的優(yōu)先級可以獲得更好的交互式響應(yīng)能力。 由于 I/O 綁定型的任務(wù)對于 CPU 訪問來說是無私的，因此其優(yōu)先級減少（獎勵）最多 5 個(gè)優(yōu)先級。CPU 綁定的任務(wù)會通過將其優(yōu)先級增加最多 5 個(gè)優(yōu)先級進(jìn)行懲罰。 任務(wù)到底是 I/O 綁定的還是 CPU 綁定的，這是根據(jù)交互性 原則確定的。任務(wù)的交互性指標(biāo)是根據(jù)任務(wù)執(zhí)行所花費(fèi)的時(shí)間與睡眠所花費(fèi)的時(shí)間的對比程度進(jìn)行計(jì)算的。注意，由于 I/O 任務(wù)先對 I/O 進(jìn)行調(diào)度，然后再進(jìn)行睡眠，因此 I/O 綁定的任務(wù)會在睡眠和等待 I/O 操作完成上面花費(fèi)更多的時(shí)間。這會提高其交互性指標(biāo)。 有一點(diǎn)值得注意，優(yōu)先級的調(diào)整只會對用戶任務(wù)進(jìn)行，對于實(shí)時(shí)任務(wù)來說并不會對其優(yōu)先級進(jìn)行調(diào)整。 SMP 負(fù)載均衡在 SMP 系統(tǒng)中創(chuàng)建任務(wù)時(shí)，這些任務(wù)都被放到一個(gè)給定的 CPU 運(yùn)行隊(duì)列中。通常來說，我們無法知道一個(gè)任務(wù)何時(shí)是短期存在的，何時(shí)需要長期運(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ù)均衡操作。 這個(gè)過程的一點(diǎn)負(fù)面影響是新 CPU 的緩存對于遷移過來的任務(wù)來說是冷的（需要將數(shù)據(jù)讀入緩存中）。 記住 CPU 緩存是一個(gè)本地（片上）內(nèi)存，提供了比系統(tǒng)內(nèi)存更快的訪問能力。如果一個(gè)任務(wù)是在某個(gè) CPU 上執(zhí)行的，與這個(gè)任務(wù)有關(guān)的數(shù)據(jù)都會被放到這個(gè) CPU 的本地緩存中，這就稱為熱的。如果對于某個(gè)任務(wù)來說，CPU 的本地緩存中沒有任何數(shù)據(jù)，那么這個(gè)緩存就稱為冷的。 不幸的是，保持 CPU 繁忙會出現(xiàn) CPU 緩存對于遷移過來的任務(wù)為冷的情況。 挖掘更多潛能2.6 版本調(diào)度器的源代碼都很好地封裝到了 /usr/src/linux/kernel/sched.c 文件中。我們在表 1 中對在這個(gè)文件中可以找到的一些有用的函數(shù)進(jìn)行了總結(jié)。
運(yùn)行隊(duì)列的結(jié)構(gòu)也可以在 /usr/src/linux/kernel/sched.c 文件中找到。2.6 版本的調(diào)度器還可以提供一些統(tǒng)計(jì)信息（如果啟用了 展望Linux 2.6 調(diào)度器從早先的 Linux 調(diào)度器已經(jīng)跨越了一大步。它極大地改善了最大化利用 CPU 的能力，同時(shí)還為用戶提供了很好的響應(yīng)體驗(yàn)。搶占和對多處理器體系架構(gòu)的更好支持使整個(gè)系統(tǒng)更接近于多桌面和實(shí)時(shí)系統(tǒng)都非常有用的操作系統(tǒng)。Linux 2.8 版本的內(nèi)核現(xiàn)在談?wù)撨€為時(shí)尚早，但是從 2.6 版本的變化中，我們可以期望會有更多的好東西。 參考資料學(xué)習(xí)
獲得產(chǎn)品和技術(shù)
討論
|
|
|
