Linux 2.6 Completely Fair Scheduler 內(nèi)幕

robbielee

任務(wù)調(diào)度器是任何操作系統(tǒng)的關(guān)鍵部分，Linux 在此領(lǐng)域中不斷發(fā)展和創(chuàng)新。在內(nèi)核 2.6.23 中，推出了 Completely Fair Scheduler (CFS)。這款調(diào)度器不依賴于運行隊列而是使用紅黑樹 (red-black tree) 實現(xiàn)任務(wù)管理。 本文介紹 CFS 的設(shè)計思想、其實現(xiàn)及其與之前的 O(1) 調(diào)度器相比的優(yōu)勢。
Linux 調(diào)度器是一個頗有壓力但很有趣的課題。一方面它涉及應(yīng)用 Linux 的使用模型。盡管 Linux 最初開發(fā)為桌面操作系統(tǒng)環(huán)境，但現(xiàn)在在服務(wù)器、微型嵌入式設(shè)備、主機和超級計算機中都能發(fā)現(xiàn)它。 無疑，這些領(lǐng)域的調(diào)度負(fù)載有很大差異。另一方面，它要考慮平臺方面的技術(shù)進(jìn)步，包括架構(gòu)（多處理、對稱多線程、非一致內(nèi)存訪問 [NUMA] 和虛擬化）。 另外，這里還要考慮交互性（用戶響應(yīng)能力）和整體公平性之間的平衡。從這些方面很容易看出解決 Linux 中的調(diào)度問題有多難。
Linux 調(diào)度器簡史
早期的 Linux 調(diào)度器使用了最低的設(shè)計，它顯然不關(guān)注具有很多處理器的大型架構(gòu)，更不用說是超線程了。1.2 Linux 調(diào)度器使用了環(huán)形隊列用于可運行的任務(wù)管理，使用循環(huán)調(diào)度策略。 此調(diào)度器添加和刪除進(jìn)程效率很高（具有保護(hù)結(jié)構(gòu)的鎖）。簡而言之，該調(diào)度器并不復(fù)雜但是簡單快捷。
Linux 版本 2.2 引入了調(diào)度類的概念，允許針對實時任務(wù)、非搶占式任務(wù)、非實時任務(wù)的調(diào)度策略。 2.2 調(diào)度器還包括對稱多處理 (SMP) 支持。
2.4 內(nèi)核包含了相對簡單的調(diào)度器，按 O(N) 的時間間隔運行（在調(diào)度事件期間它會迭代每個任務(wù)）。2.4 調(diào)度器將時間分割成 epoch，每個 epoch 中，每個任務(wù)允許執(zhí)行到其時間切片用完。如果某個任務(wù)沒有使用其所有的時間切片，那么 剩余時間切片的一半將被添加到新時間切片使其在下個 epoch 中可以執(zhí)行更長時間。 調(diào)度器只是迭代任務(wù)，應(yīng)用 goodness 函數(shù)（指標(biāo)）決定下面執(zhí)行哪個任務(wù)。盡管這種方法比較簡單，但是卻比較低效、缺乏可擴(kuò)展性而且不適合用在實時系統(tǒng)中。它還缺少利用新硬件架構(gòu)（比如多核處理器）的能力。
早期的 2.6 調(diào)度器，叫做 O(1) 調(diào)度器，它旨在解決 2.4 調(diào)度器存在的問題 — 該調(diào)度器不需要迭代整個任務(wù)列表來確定要調(diào)度的下一個任務(wù)（因此得名 O(1)，這意味著它效率更高，擴(kuò)展性更好）。O(1) 調(diào)度器跟蹤運行隊列中可運行的任務(wù)（實際上，每個優(yōu)先級水平有兩個運行隊列 — 一個用于活動任務(wù)，一個用于過期任務(wù)）， 這意味著要確定接下來執(zhí)行的任務(wù)，調(diào)度器只需按優(yōu)先級將下一個任務(wù)從特定活動的運行隊列中取出即可）。 O(1) 調(diào)度器擴(kuò)展性更好而且包含交互性，提供了大量啟示用于確定任務(wù)是受 I/O 限制還是受處理器限制。 但是 O(1) 調(diào)度器在內(nèi)核中很笨拙。需要大量代碼計算啟示，難以管理并且對于純粹主義者而言未能體現(xiàn)算法的本質(zhì)。

進(jìn)程與線程
Linux 通過將進(jìn)程和線程調(diào)度視為一個，同時包含二者。進(jìn)程可以看做是單個線程，但是進(jìn)程可以包含共享一定資源（代碼和/或數(shù)據(jù)）的多個線程。
為了解決 O(1) 調(diào)度器面臨的問題以及應(yīng)對其他外部壓力， 需要改變某些東西。這種改變來自 Con Kolivas 的內(nèi)核補丁，其中包括他的 Rotating Staircase Deadline Scheduler (RSDL)， 這包含了他在 staircase 調(diào)度器方面的早期工作。這些工作的成果就是一個設(shè)計簡單的調(diào)度器，包含了公平性和界限內(nèi)延遲。 Kolivas 的調(diào)度器吸引了很多人（并且很多人呼吁將其包含在目前的 2.6.21 主流內(nèi)核中），很顯然調(diào)度器的變革即將發(fā)生。 Ingo Molnar，O(1) 調(diào)度器的創(chuàng)造者，然后圍繞 Kolivas 的一些思想開發(fā)了基于 CFS 的調(diào)度器。我們來剖析一下 CFS，從較高的層次上看看它是如何運行的。
CFS 概述
CFS 背后的主要想法是維護(hù)為任務(wù)提供處理器時間方面的平衡（公平性）。這意味著應(yīng)給進(jìn)程分配相當(dāng)數(shù)量的處理器。分給某個任務(wù)的時間失去平衡時（意味著一個或多個任務(wù)相對于其他任務(wù)而言未被給予相當(dāng)數(shù)量的時間），應(yīng)給失去平衡的任務(wù)分配時間，讓其執(zhí)行。
要實現(xiàn)平衡，CFS 在叫做虛擬運行時 的地方維持提供給某個任務(wù)的時間量。任務(wù)的虛擬運行時越小， 意味著任務(wù)被允許訪問服務(wù)器的時間越短 — 其對處理器的需求越高。CFS 還包含睡眠公平概念以便確保那些目前沒有運行的 任務(wù)（例如，等待 I/O）在其最終需要時獲得相當(dāng)份額的處理器。
但是與之前的 Linux 調(diào)度器不同，它沒有將任務(wù)維護(hù)在運行隊列中，CFS 維護(hù)了一個以時間為順序的紅黑樹（參見圖 1）。 紅黑樹 是一個樹，具有很多有趣、有用的屬性。首先，它是自平衡的，這意味著樹上沒有路徑比任何其他路徑長兩倍以上。 第二，樹上的運行按 O(log n) 時間發(fā)生（其中 n 是樹中節(jié)點的數(shù)量）。這意味著您可以快速高效地插入或刪除任務(wù)。
圖 1. 紅黑樹示例


任務(wù)存儲在以時間為順序的紅黑樹中（由 sched_entity 對象表示），對處理器需求最多的任務(wù) （最低虛擬運行時）存儲在樹的左側(cè)，處理器需求最少的任務(wù)（最高虛擬運行時）存儲在樹的右側(cè)。 為了公平，調(diào)度器然后選取紅黑樹最左端的節(jié)點調(diào)度為下一個以便保持公平性。任務(wù)通過將其運行時間添加到虛擬運行時， 說明其占用 CPU 的時間，然后如果可運行，再插回到樹中。這樣，樹左側(cè)的任務(wù)就被給予時間運行了，樹的內(nèi)容從右側(cè)遷移到左側(cè)以保持公平。 因此，每個可運行的任務(wù)都會追趕其他任務(wù)以維持整個可運行任務(wù)集合的執(zhí)行平衡。
CFS 內(nèi)部原理
Linux 內(nèi)的所有任務(wù)都由稱為 task_struct 的任務(wù)結(jié)構(gòu)表示。該結(jié)構(gòu)（以及其他相關(guān)內(nèi)容）完整地描述了任務(wù)并包括了任務(wù)的當(dāng)前狀態(tài)、其堆棧、進(jìn)程標(biāo)識、優(yōu)先級（靜態(tài)和動態(tài)）等等。您可以在 ./linux/include/linux/sched.h 中找到這些內(nèi)容以及相關(guān)結(jié)構(gòu)。 但是因為不是所有任務(wù)都是可運行的，您在 task_struct 中不會發(fā)現(xiàn)任何與 CFS 相關(guān)的字段。 相反，會創(chuàng)建一個名為 sched_entity 的新結(jié)構(gòu)來跟蹤調(diào)度信息（參見圖 2）。
圖 2. 任務(wù)和紅黑樹的結(jié)構(gòu)層次


各種結(jié)構(gòu)的關(guān)系如
圖 2
所示。樹的根通過 rb_root 元素通過 cfs_rq 結(jié)構(gòu)（在 ./kernel/sched.c 中）引用。紅黑樹的葉子不包含信息，但是內(nèi)部節(jié)點代表一個或多個可運行的任務(wù)。紅黑樹的每個節(jié)點都由 rb_node 表示，它只包含子引用和父對象的顏色。 rb_node 包含在 sched_entity 結(jié)構(gòu)中，該結(jié)構(gòu)包含 rb_node 引用、負(fù)載權(quán)重以及各種統(tǒng)計數(shù)據(jù)。最重要的是， sched_entity 包含 vruntime（64 位字段），它表示任務(wù)運行的時間量，并作為紅黑樹的索引。 最后，task_struct 位于頂端，它完整地描述任務(wù)并包含 sched_entity 結(jié)構(gòu)。
就 CFS 部分而言，調(diào)度函數(shù)非常簡單。 在 ./kernel/sched.c 中，您會看到通用 schedule() 函數(shù)，它會先搶占當(dāng)前運行任務(wù)（除非它通過 yield() 代碼先搶占自己）。注意 CFS 沒有真正的時間切片概念用于搶占，因為搶占時間是可變的。 當(dāng)前運行任務(wù)（現(xiàn)在被搶占的任務(wù)）通過對 put_prev_task 調(diào)用（通過調(diào)度類）返回到紅黑樹。 當(dāng) schedule 函數(shù)開始確定下一個要調(diào)度的任務(wù)時，它會調(diào)用 pick_next_task 函數(shù)。此函數(shù)也是通用的（在 ./kernel/sched.c 中），但它會通過調(diào)度器類調(diào)用 CFS 調(diào)度器。 CFS 中的 pick_next_task 函數(shù)可以在 ./kernel/sched_fair.c（稱為 pick_next_task_fair()）中找到。 此函數(shù)只是從紅黑樹中獲取最左端的任務(wù)并返回相關(guān) sched_entity。通過此引用，一個簡單的 task_of() 調(diào)用確定返回的 task_struct 引用。通用調(diào)度器最后為此任務(wù)提供處理器。
優(yōu)先級和 CFS
CFS 不直接使用優(yōu)先級而是將其用作允許任務(wù)執(zhí)行的時間的衰減系數(shù)。 低優(yōu)先級任務(wù)具有更高的衰減系數(shù)，而高優(yōu)先級任務(wù)具有較低的衰減系數(shù)。 這意味著與高優(yōu)先級任務(wù)相比，低優(yōu)先級任務(wù)允許任務(wù)執(zhí)行的時間消耗得更快。 這是一個絕妙的解決方案，可以避免維護(hù)按優(yōu)先級調(diào)度的運行隊列。
CFS 組調(diào)度
CFS 另一個有趣的地方是組調(diào)度 概念（在 2.6.24 內(nèi)核中引入）。組調(diào)度是另一種為調(diào)度帶來公平性的方式，尤其是在處理產(chǎn)生很多其他任務(wù)的任務(wù)時。 假設(shè)一個產(chǎn)生了很多任務(wù)的服務(wù)器要并行化進(jìn)入的連接（HTTP 服務(wù)器的典型架構(gòu)）。不是所有任務(wù)都會被統(tǒng)一公平對待， CFS 引入了組來處理這種行為。產(chǎn)生任務(wù)的服務(wù)器進(jìn)程在整個組中（在一個層次結(jié)構(gòu)中）共享它們的虛擬運行時，而單個任務(wù)維持其自己獨立的虛擬運行時。這樣單個任務(wù)會收到與組大致相同的調(diào)度時間。您會發(fā)現(xiàn) /proc 接口用于管理進(jìn)程層次結(jié)構(gòu)，讓您對組的形成方式有完全的控制。使用此配置，您可以跨用戶、跨進(jìn)程或其變體分配公平性。

調(diào)度類和域
與 CFS 一起引入的是調(diào)度類概念（可以回顧
圖 2
）。每個任務(wù)都屬于一個調(diào)度類，這決定了任務(wù)將如何調(diào)度。 調(diào)度類定義一個通用函數(shù)集（通過 sched_class），函數(shù)集定義調(diào)度器的行為。例如，每個調(diào)度器提供一種方式， 添加要調(diào)度的任務(wù)、調(diào)出要運行的下一個任務(wù)、提供給調(diào)度器等等。每個調(diào)度器類都在一對一連接的列表中彼此相連，使類可以迭代（例如， 要啟用給定處理器的禁用）。一般結(jié)構(gòu)如圖 3 所示。注意，將任務(wù)函數(shù)加入隊列或脫離隊列只需從特定調(diào)度結(jié)構(gòu)中加入或移除任務(wù)。 函數(shù) pick_next_task 選擇要執(zhí)行的下一個任務(wù)（取決于調(diào)度類的具體策略）。
圖 3. 調(diào)度類圖形視圖


但是不要忘了調(diào)度類是任務(wù)結(jié)構(gòu)本身的一部分（參見
圖 2
）。這一點簡化了任務(wù)的操作，無論其調(diào)度類如何。例如， 以下函數(shù)用 ./kernel/sched.c 中的新任務(wù)搶占當(dāng)前運行任務(wù)（其中 curr 定義了當(dāng)前運行任務(wù)， rq 代表 CFS 紅黑樹而 p 是下一個要調(diào)度的任務(wù)）：
static inline void check_preempt( struct rq *rq, struct task_struct *p )
{
  rq->curr->sched_class->check_preempt_curr( rq, p );
}
如果此任務(wù)正使用公平調(diào)度類，則 check_preempt_curr() 將解析為 check_preempt_wakeup()。 您可以在 ./kernel/sched_rt.c, ./kernel/sched_fair.c 和 ./kernel/sched_idle.c 中查看這些關(guān)系。
調(diào)度類是調(diào)度發(fā)生變化的另一個有趣的地方，但是隨著調(diào)度域的增加，功能也在增加。 這些域允許您出于負(fù)載平衡和隔離的目的將一個或多個處理器按層次關(guān)系分組。 一個或多個處理器能夠共享調(diào)度策略（并在其之間保持負(fù)載平衡）或?qū)崿F(xiàn)獨立的調(diào)度策略從而故意隔離任務(wù)。

其他調(diào)度器
繼續(xù)研究調(diào)度，您將發(fā)現(xiàn)正在開發(fā)中的調(diào)度器將會突破性能和擴(kuò)展性的界限。Con Kolivas 沒有被他的 Linux 經(jīng)驗羈絆，他開發(fā)出了另一個 Linux 調(diào)度器，其縮寫為：BFS。該調(diào)度器據(jù)說在 NUMA 系統(tǒng)以及移動設(shè)備上具有更好的性能， 并且被引入了 Android 操作系統(tǒng)的一款衍生產(chǎn)品中。

展望
對于 Linux 技術(shù)而言，惟一不變的就是永恒的變化。今天，CFS 是 2.6 Linux 調(diào)度器； 明天可能就會是另一個新的調(diào)度器或一套可以被靜態(tài)或動態(tài)調(diào)用的調(diào)度器。 CFS、RSDL 以及內(nèi)核背后的進(jìn)程中還有很多秘密，但是多虧了 Kolivas 和 Molnar 的工作，我們在 2.6 任務(wù)調(diào)度方面達(dá)到了更高層次的公平。

參考資料
學(xué)習(xí)

• 
  紅黑樹
  （平衡二叉樹）是自平衡二叉樹，由 Rudolf Bayer 發(fā)明。它是一種非常有用的樹表示法， 能以時間復(fù)雜度進(jìn)行插入、搜索和刪除等操作。您可以在各種應(yīng)用程序中發(fā)現(xiàn)紅黑樹，包括關(guān)聯(lián)數(shù)組的構(gòu)建。
  
• 任務(wù)調(diào)度是操作系統(tǒng)設(shè)計的一個重要方面，從桌面操作系統(tǒng)調(diào)度器到實時調(diào)度器和嵌入式操作系統(tǒng)調(diào)度器。來自
  Martin C. Rinard 操作系統(tǒng)講座
  的文章提供了關(guān)于處理器調(diào)度話題的要點總結(jié)。
  
• 
  大O符號
  是用于描述函數(shù)漸近行為的數(shù)學(xué)符號。此維基百科條目包含了一些重要信息以及函數(shù)類的有用列表。
  
• 您可以在 “
  Linux 調(diào)度器內(nèi)幕
  ” （developerWorks，2006 年 6 月）中了解 Linux O(1) 調(diào)度器的更多信息。
  
• Con Kolivas 從事新的實驗性的 Linux 調(diào)度器研究有一段時間了。您可以了解關(guān)于其調(diào)度器的更多信息， 包括
  Staircase Process Scheduler
  和
  Rotating Staircase Deadline Scheduler
  ，這些調(diào)度器最終證明公平共享調(diào)度是可以實現(xiàn)的。
  
• Avinesh Kumar 對 CFS 及其他新增功能進(jìn)行了介紹。了解其文章 “
  使用完全公平調(diào)度程序（CFS）進(jìn)行多任務(wù)處理
  ” （developerWorks，2008 年 1 月）。
  
• 沒有戲劇生活將會怎樣？要了解幕后故事，請參閱
  CFS 的開發(fā)
  ，查看此 Linux 內(nèi)核郵件列表結(jié)合，其中包括 Con Kolivas（他引入了 RSDL 補丁、實現(xiàn)了 CFS 的核心思想）和 Ingo Molnar（調(diào)度器代碼看門人，在最初拒絕該思想后，他稍后推出了自己的調(diào)度器版本）。真相總是介于兩者之間，但是來自
  Kerneltrap
  的這篇有趣的文章揭示了開源開發(fā)的另一面。
  
• 在
  developerWorks Linux 專區(qū)
  尋找為 Linux 開發(fā)人員（包括
  Linux 新手入門
  ）準(zhǔn)備的更多參考資料，查閱我們
  最受歡迎的文章和教程
  。
  
• 在 developerWorks 上查閱所有
  Linux 技巧
  和
  Linux 教程
  。
  
• 隨時關(guān)注 developerWorks
  技術(shù)活動
  和
  網(wǎng)絡(luò)廣播
  。
  

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

• Con Kolivas 推出的另一款調(diào)度器，
  BFS 調(diào)度器
  已經(jīng)作為 Linux 桌面系統(tǒng)以及小型移動設(shè)備的補丁提供了。 Kolivas 選擇了這個縮寫名（其名稱無法拼讀），因為他希望提醒大家注意一個事實：讓調(diào)度器支持大量任務(wù)固然很好，但是也應(yīng)該考慮構(gòu)建在較低配置硬件上的桌面調(diào)度器。
  
• 使用可以直接從 developerWorks 下載的
  IBM 產(chǎn)品評估試用版軟件
  ，在 Linux 上構(gòu)建您的下一個項目。
  

討論

• 加入
  My developerWorks 社區(qū)
  ；您可以通過個人檔案和定制主頁獲得符合自己的興趣的 developerWorks 文章，并與其他 developerWorks 用戶進(jìn)行交流。

關(guān)于作者







M. Tim Jones 是一名嵌入式固件架構(gòu)師，他是 Artificial Intelligence: A Systems Approach, GNU/Linux Application Programming（現(xiàn)在已經(jīng)是第 2 版）、AI Application Programming（第 2 版）和 BSD Sockets Programming from a Multilanguage Perspective 等書的作者。他的工程背景非常廣泛，從同步宇宙飛船的內(nèi)核開發(fā)到嵌入式系統(tǒng)架構(gòu)設(shè)計，再到網(wǎng)絡(luò)協(xié)議的開發(fā)。Tim 是位于科羅拉多州 Longmont 的 Emulex Corp. 的一名顧問工程師。


本文來自ChinaUnix博客，如果查看原文請點：http://blog.chinaunix.net/u/23353/showart_2162660.html