引言

進(jìn)程調(diào)度是操作系統(tǒng)的核心功能。調(diào)度器只是是調(diào)度過程中的一部分，進(jìn)程調(diào)度是非常復(fù)雜的過程，需要多個(gè)系統(tǒng)協(xié)同工作完成。本文所關(guān)注的僅為調(diào)度器，它的主要工作是在所有 RUNNING 進(jìn)程中選擇最合適的一個(gè)。作為一個(gè)通用操作系統(tǒng)，Linux 調(diào)度器將進(jìn)程分為三類：

交互式進(jìn)程

此類進(jìn)程有大量的人機(jī)交互，因此進(jìn)程不斷地處于睡眠狀態(tài)，等待用戶輸入。典型的應(yīng)用比如編輯器 vi。此類進(jìn)程對系統(tǒng)響應(yīng)時(shí)間要求比較高，否則用戶會(huì)感覺系統(tǒng)反應(yīng)遲緩。

批處理進(jìn)程

此類進(jìn)程不需要人機(jī)交互，在后臺運(yùn)行，需要占用大量的系統(tǒng)資源。但是能夠忍受響應(yīng)延遲。比如編譯器。

實(shí)時(shí)進(jìn)程

實(shí)時(shí)對調(diào)度延遲的要求最高，這些進(jìn)程往往執(zhí)行非常重要的操作，要求立即響應(yīng)并執(zhí)行。比如視頻播放軟件或飛機(jī)飛行控制系統(tǒng)，很明顯這類程序不能容忍長時(shí)間的調(diào)度延遲，輕則影響電影放映效果，重則機(jī)毀人亡。

根據(jù)進(jìn)程的不同分類 Linux 采用不同的調(diào)度策略。對于實(shí)時(shí)進(jìn)程，采用 FIFO 或者 Round Robin 的調(diào)度策略。對于普通進(jìn)程，則需要區(qū)分交互式和批處理式的不同。傳統(tǒng) Linux 調(diào)度器提高交互式應(yīng)用的優(yōu)先級，使得它們能更快地被調(diào)度。而 CFS 和 RSDL 等新的調(diào)度器的核心思想是“完全公平”。這個(gè)設(shè)計(jì)理念不僅大大簡化了調(diào)度器的代碼復(fù)雜度，還對各種調(diào)度需求的提供了更完美的支持。

在探討CFS和RSDL之前，我們首先回顧一下Linux2.4和Linux2.6.0中所使用的調(diào)度器。

回頁首

內(nèi)核調(diào)度器的簡單歷史

2.1 Linux2.4 的調(diào)度器

Linux2.4.18 中使用的調(diào)度器采用基于優(yōu)先級的設(shè)計(jì)，這個(gè)調(diào)度器和 Linus 在 1992 年發(fā)布的調(diào)度器沒有大的區(qū)別。該調(diào)度器的 pick next 算法非常簡單：對 runqueue 中所有進(jìn)程的優(yōu)先級進(jìn)行依次進(jìn)行比較，選擇最高優(yōu)先級的進(jìn)程作為下一個(gè)被調(diào)度的進(jìn)程。(Runqueue 是 Linux 內(nèi)核中保存所有就緒進(jìn)程的隊(duì)列) 。術(shù)語 pick next 用來指從所有候選進(jìn)程中挑選下一個(gè)要被調(diào)度的進(jìn)程的過程。

每個(gè)進(jìn)程被創(chuàng)建時(shí)都被賦予一個(gè)時(shí)間片。時(shí)鐘中斷遞減當(dāng)前運(yùn)行進(jìn)程的時(shí)間片，當(dāng)進(jìn)程的時(shí)間片被用完時(shí)，它必須等待重新賦予時(shí) 間片才能有機(jī)會(huì)運(yùn)行。Linux2.4 調(diào)度器保證只有當(dāng)所有 RUNNING 進(jìn)程的時(shí)間片都被用完之后，才對所有進(jìn)程重新分配時(shí)間片。這段時(shí)間被稱為一個(gè) epoch。這種設(shè)計(jì)保證了每個(gè)進(jìn)程都有機(jī)會(huì)得到執(zhí)行。

各種進(jìn)程對調(diào)度的需求并不相同，Linux2.4 調(diào)度器主要依靠改變進(jìn)程的優(yōu)先級，來滿足不同進(jìn)程的調(diào)度需求。事實(shí)上，所有后來的調(diào)度器都主要依賴修改進(jìn)程優(yōu)先級來滿足不同的調(diào)度需求。

實(shí)時(shí)進(jìn)程

實(shí)時(shí)進(jìn)程的優(yōu)先級是靜態(tài)設(shè)定的，而且始終大于普通進(jìn)程的優(yōu)先級。因此只有當(dāng) runqueue 中沒有實(shí)時(shí)進(jìn)程的情況下，普通進(jìn)程才能夠獲得調(diào)度。

實(shí)時(shí)進(jìn)程采用兩種調(diào)度策略：SCHED_FIFO 和 SCHED_RR。FIFO 采用先進(jìn)先出的策略，對于所有相同優(yōu)先級的進(jìn)程，最先進(jìn)入 runqueue 的進(jìn)程總能優(yōu)先獲得調(diào)度；Round Robin 采用更加公平的輪轉(zhuǎn)策略，使得相同優(yōu)先級的實(shí)時(shí)進(jìn)程能夠輪流獲得調(diào)度。

普通進(jìn)程

對于普通進(jìn)程，調(diào)度器傾向于提高交互式進(jìn)程的優(yōu)先級，因?yàn)樗鼈冃枰焖俚挠脩繇憫?yīng)。普通進(jìn)程的優(yōu)先級主要由進(jìn)程描述符中的 Counter 字段決定 (還要加上 nice 設(shè)定的靜態(tài)優(yōu)先級) 。進(jìn)程被創(chuàng)建時(shí)子進(jìn)程的 counter 值為父進(jìn)程 counter 值的一半，這樣保證了任何進(jìn)程不能依靠不斷地 fork() 子進(jìn)程從而獲得更多的執(zhí)行機(jī)會(huì)。

Linux2.4調(diào)度器是如何提高交互式進(jìn)程的優(yōu)先級的呢？如前所述，當(dāng)所有 RUNNING 進(jìn)程的時(shí)間片被用完之后，調(diào)度器將重新計(jì)算所有進(jìn)程的 counter 值，所有進(jìn)程不僅包括 RUNNING 進(jìn)程，也包括處于睡眠狀態(tài)的進(jìn)程。處于睡眠狀態(tài)的進(jìn)程的 counter 本來就沒有用完，在重新計(jì)算時(shí)，他們的 counter 值會(huì)加上這些原來未用完的部分，從而提高了它們的優(yōu)先級。交互式進(jìn)程經(jīng)常因等待用戶輸入而處于睡眠狀態(tài)，當(dāng)它們重新被喚醒并進(jìn)入 runqueue 時(shí)，就會(huì)優(yōu)先于其它進(jìn)程而獲得 CPU。從用戶角度來看，交互式進(jìn)程的響應(yīng)速度就提高了。

該調(diào)度器的主要缺點(diǎn)：

可擴(kuò)展性不好：調(diào)度器選擇進(jìn)程時(shí)需要遍歷整個(gè) runqueue 從中選出最佳人選，因此該算法的執(zhí)行時(shí)間與進(jìn)程數(shù)成正比。另外每次重新計(jì)算 counter 所花費(fèi)的時(shí)間也會(huì)隨著系統(tǒng)中進(jìn)程數(shù)的增加而線性增長，當(dāng)進(jìn)程數(shù)很大時(shí)，更新 counter 操作的代價(jià)會(huì)非常高，導(dǎo)致系統(tǒng)整體的性能下降。

高負(fù)載系統(tǒng)上的調(diào)度性能比較低：2.4的調(diào)度器預(yù)分配給每個(gè)進(jìn)程的時(shí)間片比較大，因此在高負(fù)載的服務(wù)器上，該調(diào)度器的效率比較低，因?yàn)槠骄總€(gè)進(jìn)程的等待時(shí)間于該時(shí)間片的大小成正比。

交互式進(jìn)程的優(yōu)化并不完善：Linux2.4識別交互式進(jìn)程的原理基于以下假設(shè)，即 交互式進(jìn)程比批處理進(jìn)程更頻繁地處于SUSPENDED狀態(tài)。然而現(xiàn)實(shí)情況往往并非如此，有些批處理進(jìn)程雖然沒有用戶交互，但是也會(huì)頻繁地進(jìn)行IO操作， 比如一個(gè)數(shù)據(jù)庫引擎在處理查詢時(shí)會(huì)經(jīng)常地進(jìn)行磁盤IO，雖然它們并不需要快速地用戶響應(yīng)，還是被提高了優(yōu)先級。當(dāng)系統(tǒng)中這類進(jìn)程的負(fù)載較重時(shí)，會(huì)影響真正 的交互式進(jìn)程的響應(yīng)時(shí)間。

對實(shí)時(shí)進(jìn)程的支持不夠：Linux2.4內(nèi)核是非搶占的，當(dāng)進(jìn)程處于內(nèi)核態(tài)時(shí)不會(huì)發(fā)生搶占，這對于真正的實(shí)時(shí)應(yīng)用是不能接受的。

為了解決這些問題，Ingo Molnar開發(fā)了新的O(1)調(diào)度器，在CFS和RSDL之前，這個(gè)調(diào)度器不僅被Linux2.6采用，還被backport到Linux2.4中，很多商業(yè)的發(fā)行版本都采用了這個(gè)調(diào)度器。

2.2 Linux2.6的O(1)調(diào)度器

從名字就可以看出O(1)調(diào)度器主要解決了以前版本中的擴(kuò)展性問題。O(1)調(diào)度算法所花費(fèi)的時(shí)間為常數(shù)，與當(dāng)前系統(tǒng)中的 進(jìn)程個(gè)數(shù)無關(guān)。此外Linux2.6內(nèi)核支持內(nèi)核態(tài)搶占，因此更好地支持了實(shí)時(shí)進(jìn)程。相對于前任，O (1) 調(diào)度器還更好地區(qū)分了交互式進(jìn)程和批處理式進(jìn)程。

Linux2.6內(nèi)核也支持三種調(diào)度策略。其中SCHED_FIFO和SCHED_RR用于實(shí)時(shí)進(jìn)程，而SCHED_NORMAL用于普通進(jìn)程。O(1)調(diào)度器在兩個(gè)方面修改了Linux2.4調(diào)度器，一是進(jìn)程優(yōu)先級的計(jì)算方法；二是pick next算法。

2.2.1 進(jìn)程的優(yōu)先級計(jì)算

普通進(jìn)程的優(yōu)先級計(jì)算

普通進(jìn)程優(yōu)先級是動(dòng)態(tài)計(jì)算的，計(jì)算公式中包含了靜態(tài)優(yōu)先級。一般來講，靜態(tài)優(yōu)先級越高，進(jìn)程所能分配到的時(shí)間片越長，用戶可以通過nice系統(tǒng)調(diào)用修改進(jìn)程的靜態(tài)優(yōu)先級。

動(dòng)態(tài)優(yōu)先級由 公式一 計(jì)算得出：

                
  dynamic priority = max (100, min ( static priority – bonus +5, 139))   

其中bonus 取決于進(jìn)程的平均睡眠時(shí)間。由此可以看出，在linux2.6中，一個(gè)普通進(jìn)程的優(yōu)先級和平均睡眠時(shí)間的關(guān)系為：平均睡眠時(shí)間越長，其bonus越大，從而得到更高的優(yōu)先級。

平均睡眠時(shí)間也被用來判斷進(jìn)程是否是一個(gè)交互式進(jìn)程。如果滿足下面的公式，進(jìn)程就被認(rèn)為是一個(gè)交互式進(jìn)程：

                
Dynamic priority ≤ 3 x static priority /4 + 28

平均睡眠時(shí)間是進(jìn)程處于等待睡眠狀態(tài)下的時(shí)間，該值在進(jìn)程進(jìn)入睡眠狀態(tài)時(shí)增加，而進(jìn)入RUNNING狀態(tài)后則減少。該值的 更新時(shí)機(jī)分布在很多內(nèi)核函數(shù)內(nèi)：時(shí)鐘中斷scheduler_tick()；進(jìn)程創(chuàng)建；進(jìn)程從TASK_INTERRUPTIBLE狀態(tài)喚醒；負(fù)載平衡 等。

實(shí)時(shí)進(jìn)程的優(yōu)先級計(jì)算

實(shí)時(shí)進(jìn)程的優(yōu)先級由sys_sched_setschedule()設(shè)置。該值不會(huì)動(dòng)態(tài)修改，而且總是比普通進(jìn)程的優(yōu)先級高。在進(jìn)程描述符中用rt_priority域表示。

2.2.2 pick next算法

普通進(jìn)程的調(diào)度選擇算法基于進(jìn)程的優(yōu)先級，擁有最高優(yōu)先級的進(jìn)程被調(diào)度器選中。2.4中，時(shí)間片counter同時(shí)也表示 了一個(gè)進(jìn)程的優(yōu)先級。2.6中時(shí)間片用任務(wù)描述符中的time_slice域表示，而優(yōu)先級用prio（普通進(jìn)程）或者rt_priority（實(shí)時(shí)進(jìn) 程）表示。

調(diào)度器為每一個(gè)CPU維護(hù)了兩個(gè)進(jìn)程隊(duì)列數(shù)組：active數(shù)組和expire數(shù)組。數(shù)組中的元素著保存某一優(yōu)先級的進(jìn)程隊(duì)列指針。系統(tǒng)一共有140個(gè)不同的優(yōu)先級，因此這兩個(gè)數(shù)組大小都是140。

當(dāng)需要選擇當(dāng)前最高優(yōu)先級的進(jìn)程時(shí)，2.6調(diào)度器不用遍歷整個(gè)runqueue，而是直接從active數(shù)組中選擇當(dāng)前最 高優(yōu)先級隊(duì)列中的第一個(gè)進(jìn)程。假設(shè)當(dāng)前所有進(jìn)程中最高優(yōu)先級為50(換句話說，系統(tǒng)中沒有任何進(jìn)程的優(yōu)先級小于50)。則調(diào)度器直接讀取 active[49]，得到優(yōu)先級為50的進(jìn)程隊(duì)列指針。該隊(duì)列頭上的第一個(gè)進(jìn)程就是被選中的進(jìn)程。這種算法的復(fù)雜度為O(1)，從而解決了2.4調(diào)度器 的擴(kuò)展性問題。

為了實(shí)現(xiàn)上述算法active數(shù)組維護(hù)了一個(gè)bitmap，當(dāng)某個(gè)優(yōu)先級別上有進(jìn)程被插入列表時(shí)，相應(yīng)的比特位就被置位。 Sched_find_first_bit()函數(shù)查詢該bitmap，返回當(dāng)前被置位的最高優(yōu)先級的數(shù)組下標(biāo)。在上例中 sched_find_first_bit函數(shù)將返回49。在IA處理器上可以通過bsfl等指令實(shí)現(xiàn)。

為了提高交互式進(jìn)程的響應(yīng)時(shí)間，O(1)調(diào)度器不僅動(dòng)態(tài)地提高該類進(jìn)程的優(yōu)先級，還采用以下方法：

每次時(shí)鐘tick中斷中，進(jìn)程的時(shí)間片(time_slice)被減一。當(dāng)time_slice為0時(shí)，調(diào)度器判斷當(dāng)前進(jìn) 程的類型，如果是交互式進(jìn)程或者實(shí)時(shí)進(jìn)程，則重置其時(shí)間片并重新插入active數(shù)組。如果不是交互式進(jìn)程則從active數(shù)組中移到expired數(shù) 組。這樣實(shí)時(shí)進(jìn)程和交互式進(jìn)程就總能優(yōu)先獲得CPU。然而這些進(jìn)程不能始終留在active數(shù)組中，否則進(jìn)入expire數(shù)組的進(jìn)程就會(huì)產(chǎn)生饑餓現(xiàn)象。當(dāng) 進(jìn)程已經(jīng)占用CPU時(shí)間超過一個(gè)固定值后，即使它是實(shí)時(shí)進(jìn)程或者交互式進(jìn)程也會(huì)被移到expire數(shù)組中。

當(dāng)active數(shù)組中的所有進(jìn)程都被移到expire數(shù)組中后，調(diào)度器交換active數(shù)組和expire數(shù)組。當(dāng)進(jìn)程被移入expire數(shù)組時(shí)，調(diào)度器會(huì)重置其時(shí)間片，因此新的active數(shù)組又恢復(fù)了初始情況，而expire數(shù)組為空，從而開始新的一輪調(diào)度。

2.2.3 O(1)調(diào)度器小節(jié)

Linux2.6調(diào)度器改進(jìn)了前任調(diào)度器的可擴(kuò)展性問題，schedule()函數(shù)的時(shí)間復(fù)雜度為O(1)。這取決于兩個(gè)改進(jìn)：

一．Pick next算法借助于active數(shù)組，無需遍歷runqueue；

二．取消了定期更新所有進(jìn)程counter的操作，動(dòng)態(tài)優(yōu)先級的修改分布在進(jìn)程切換，時(shí)鐘tick中斷以及其它一些內(nèi)核函數(shù)中進(jìn)行。

O(1)調(diào)度器區(qū)分交互式進(jìn)程和批處理進(jìn)程的算法與以前雖大有改進(jìn)，但仍然在很多情況下會(huì)失效。有一些著名的程序總能讓該調(diào)度器性能下降，導(dǎo)致交互式進(jìn)程反應(yīng)緩慢：

fiftyp.c, thud.c, chew.c, ring-test.c, massive_intr.c

這些不足催生了Con Kolivas的樓梯調(diào)度算法SD，以及后來的改進(jìn)版本RSDL。Ingo Molnar在RSDL之后開發(fā)了CFS，并最終被2.6.23內(nèi)核采用。接下來我們開始介紹這些新一代調(diào)度器。

回頁首

3 新一代調(diào)度器

Linux2.6.0發(fā)布之前，很多人都擔(dān)心調(diào)度器存在的問題將阻礙新版本的發(fā)布。它對于交互式應(yīng)用仍然存在響應(yīng)性差的問 題，對NUMA支持也不完善。為了解決這些問題，大量難以維護(hù)和閱讀的復(fù)雜代碼被加入Linux2.6.0的調(diào)度器模塊，雖然很多性能問題因此得到了解 決，可是另外一個(gè)嚴(yán)重問題始終困擾著許多內(nèi)核開發(fā)者。那就是代碼的復(fù)雜度問題。

Con Kolivas，在2004年提出了第一個(gè)改進(jìn)調(diào)度器設(shè)計(jì)的patch：staircase scheduler。為調(diào)度器設(shè)計(jì)提供了一個(gè)新的思路。之后的RSDL和CFS都基于SD的許多基本思想。本章中，我們將簡要探討這三個(gè)主要的調(diào)度器算法。

3.1 樓梯調(diào)度算法 staircase scheduler

樓梯算法(SD)在思路上和O(1)算法有很大不同，它拋棄了動(dòng)態(tài)優(yōu)先級的概念。而采用了一種完全公平的思路。前任算法的主要復(fù)雜性來自動(dòng)態(tài)優(yōu)先級的計(jì)算，調(diào)度器根據(jù)平均睡眠時(shí)間和一些很難理解的經(jīng)驗(yàn)公式來修正進(jìn)程的優(yōu)先級以及區(qū)分交互式進(jìn)程。這樣的代碼很難閱讀和維護(hù)。

樓梯算法思路簡單，但是實(shí)驗(yàn)證明它對應(yīng)交互式進(jìn)程的響應(yīng)比其前任更好，而且極大地簡化了代碼。

和O(1)算法一樣，樓梯算法也同樣為每一個(gè)優(yōu)先級維護(hù)一個(gè)進(jìn)程列表，并將這些列表組織在active數(shù)組中。當(dāng)選取下一個(gè)被調(diào)度進(jìn)程時(shí)，SD算法也同樣從active數(shù)組中直接讀取。

與O(1)算法不同在于，當(dāng)進(jìn)程用完了自己的時(shí)間片后，并不是被移到expire數(shù)組中。而是被加入active數(shù)組的低 一優(yōu)先級列表中，即將其降低一個(gè)級別。不過請注意這里只是將該任務(wù)插入低一級優(yōu)先級任務(wù)列表中，任務(wù)本身的優(yōu)先級并沒有改變。當(dāng)時(shí)間片再次用完，任務(wù)被再 次放入更低一級優(yōu)先級任務(wù)隊(duì)列中。就象一部樓梯，任務(wù)每次用完了自己的時(shí)間片之后就下一級樓梯。

任務(wù)下到最低一級樓梯時(shí)，如果時(shí)間片再次用完，它會(huì)回到初始優(yōu)先級的下一級任務(wù)隊(duì)列中。比如某進(jìn)程的優(yōu)先級為1，當(dāng)它到達(dá) 最后一級臺階140后，再次用完時(shí)間片時(shí)將回到優(yōu)先級為2的任務(wù)隊(duì)列中，即第二級臺階。不過此時(shí)分配給該任務(wù)的time_slice將變成原來的2倍。比 如原來該任務(wù)的時(shí)間片time_slice為10ms，則現(xiàn)在變成了20ms?；镜脑瓌t是，當(dāng)任務(wù)下到樓梯底部時(shí)，再次用完時(shí)間片就回到上次下樓梯的起 點(diǎn)的下一級臺階。并給予該任務(wù)相同于其最初分配的時(shí)間片。總結(jié)如下：

設(shè)任務(wù)本身優(yōu)先級為P，當(dāng)它從第N級臺階開始下樓梯并到達(dá)底部后，將回到第N+1級臺階。并且賦予該任務(wù)N+1倍的時(shí)間片。

以上描述的是普通進(jìn)程的調(diào)度算法，實(shí)時(shí)進(jìn)程還是采用原來的調(diào)度策略，即FIFO或者Round Robin。

樓梯算法能避免進(jìn)程饑餓現(xiàn)象，高優(yōu)先級的進(jìn)程會(huì)最終和低優(yōu)先級的進(jìn)程競爭，使得低優(yōu)先級進(jìn)程最終獲得執(zhí)行機(jī)會(huì)。

對于交互式應(yīng)用，當(dāng)進(jìn)入睡眠狀態(tài)時(shí)，與它同等優(yōu)先級的其他進(jìn)程將一步一步地走下樓梯，進(jìn)入低優(yōu)先級進(jìn)程隊(duì)列。當(dāng)該交互式進(jìn)程再次喚醒后，它還留在高處的樓梯臺階上，從而能更快地被調(diào)度器選中，加速了響應(yīng)時(shí)間。

樓梯算法的優(yōu)點(diǎn)

從實(shí)現(xiàn)角度看，SD基本上還是沿用了O(1)的整體框架，只是刪除了O(1)調(diào)度器中動(dòng)態(tài)修改優(yōu)先級的復(fù)雜代碼；還淘汰了expire數(shù)組，從而簡化了代碼。它最重要的意義在于證明了完全公平這個(gè)思想的可行性。

3.2 RSDL（The Rotating Staircase Deadline Schedule）

RSDL也是由Con Kolivas開發(fā)的，它是對SD算法的改進(jìn)。核心的思想還是“完全公平”。沒有復(fù)雜的動(dòng)態(tài)優(yōu)先級調(diào)整策略。

RSDL重新引入了expire數(shù)組。它為每一個(gè)優(yōu)先級都分配了一個(gè) “組時(shí)間配額”， 我們將組時(shí)間配額標(biāo)記為Tg；同一優(yōu)先級的每個(gè)進(jìn)程都擁有同樣的"優(yōu)先級時(shí)間配額"本文中用Tp表示，以便于后續(xù)描述。

當(dāng)進(jìn)程用完了自身的Tp時(shí)，就下降到下一優(yōu)先級進(jìn)程組中。這個(gè)過程和SD相同，在RSDL中這個(gè)過程叫做minor rotation。請注意Tp不等于進(jìn)程的時(shí)間片，而是小于進(jìn)程的時(shí)間片。下圖表示了minor rotation。進(jìn)程從priority1的隊(duì)列中一步一步下到priority140之后回到priority2的隊(duì)列中，這個(gè)過程如下圖左邊所示， 然后從priority 2開始再次一步一步下樓，到底后再次反彈到priority3隊(duì)列中，如圖1所示。

在SD算法中，處于樓梯底部的低優(yōu)先級進(jìn)程必須等待所有的高優(yōu)先級進(jìn)程執(zhí)行完才能獲得CPU。因此低優(yōu)先級進(jìn)程的等待時(shí)間 無法確定。RSDL中，當(dāng)高優(yōu)先級進(jìn)程組用完了它們的Tg(即組時(shí)間配額)時(shí)，無論該組中是否還有進(jìn)程Tp尚未用完，所有屬于該組的進(jìn)程都被強(qiáng)制降低到下 一優(yōu)先級進(jìn)程組中。這樣低優(yōu)先級任務(wù)就可以在一個(gè)可以預(yù)計(jì)的未來得到調(diào)度。從而改善了調(diào)度的公平性。這就是RSDL中Deadline代表的含義。

進(jìn)程用完了自己的時(shí)間片time_slice時(shí)（下圖中T2），將放入expire數(shù)組中它初始的優(yōu)先級隊(duì)列中(priority 1)。

當(dāng)active數(shù)組為空，或者所有的進(jìn)程都降低到最低優(yōu)先級時(shí)就會(huì)觸發(fā)major rotation：。Major rotation交換active數(shù)組和expire數(shù)組，所有進(jìn)程都恢復(fù)到初始狀態(tài)，再一次從新開始minor rotation的過程。

RSDL對交互式進(jìn)程的支持

和SD同樣的道理，交互式進(jìn)程在睡眠時(shí)間時(shí)，它所有的競爭者都因?yàn)閙inor rotation而降到了低優(yōu)先級進(jìn)程隊(duì)列中。當(dāng)它重新進(jìn)入RUNNING狀態(tài)時(shí)，就獲得了相對較高的優(yōu)先級，從而能被迅速響應(yīng)。

3.3 CFS 完全公平調(diào)度器

CFS是最終被內(nèi)核采納的調(diào)度器。它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進(jìn)程的睡眠時(shí)間，也不再企圖區(qū)分交互式進(jìn)程。它將所有的進(jìn)程都統(tǒng)一對待，這就是公平的含義。CFS的算法和實(shí)現(xiàn)都相當(dāng)簡單，眾多的測試表明其性能也非常優(yōu)越。

按照作者Ingo Molnar的說法："CFS百分之八十的工作可以用一句話概括：CFS在真實(shí)的硬件上模擬了完全理想的多任務(wù)處理器"。在“完全理想的多任務(wù)處理器 “下，每個(gè)進(jìn)程都能同時(shí)獲得CPU的執(zhí)行時(shí)間。當(dāng)系統(tǒng)中有兩個(gè)進(jìn)程時(shí)，CPU的計(jì)算時(shí)間被分成兩份，每個(gè)進(jìn)程獲得50%。然而在實(shí)際的硬件上，當(dāng)一個(gè)進(jìn)程 占用CPU時(shí)，其它進(jìn)程就必須等待。這就產(chǎn)生了不公平。

假設(shè)runqueue中有n個(gè)進(jìn)程，當(dāng)前進(jìn)程運(yùn)行了10ms。在“完全理想的多任務(wù)處理器”中，10ms應(yīng)該平分給n個(gè)進(jìn) 程(不考慮各個(gè)進(jìn)程的nice值)，因此當(dāng)前進(jìn)程應(yīng)得的時(shí)間是(10/n)ms，但是它卻運(yùn)行了10ms。所以CFS將懲罰當(dāng)前進(jìn)程，使其它進(jìn)程能夠在下 次調(diào)度時(shí)盡可能取代當(dāng)前進(jìn)程。最終實(shí)現(xiàn)所有進(jìn)程的公平調(diào)度。下面將介紹CFS實(shí)現(xiàn)的一些重要部分，以便深入地理解CFS的工作原理。

CFS如何實(shí)現(xiàn)pick next

CFS拋棄了active/expire數(shù)組，而使用紅黑樹選取下一個(gè)被調(diào)度進(jìn)程。所有狀態(tài)為RUNABLE的進(jìn)程都被插入紅黑樹。在每個(gè)調(diào)度點(diǎn)，CFS調(diào)度器都會(huì)選擇紅黑樹的最左邊的葉子節(jié)點(diǎn)作為下一個(gè)將獲得cpu的進(jìn)程。

tick中斷

在CFS中，tick中斷首先更新調(diào)度信息。然后調(diào)整當(dāng)前進(jìn)程在紅黑樹中的位置。調(diào)整完成后如果發(fā)現(xiàn)當(dāng)前進(jìn)程不再是最左邊 的葉子，就標(biāo)記need_resched標(biāo)志，中斷返回時(shí)就會(huì)調(diào)用scheduler()完成進(jìn)程切換。否則當(dāng)前進(jìn)程繼續(xù)占用CPU。從這里可以看到 CFS拋棄了傳統(tǒng)的時(shí)間片概念。Tick中斷只需更新紅黑樹，以前的所有調(diào)度器都在tick中斷中遞減時(shí)間片，當(dāng)時(shí)間片或者配額被用完時(shí)才觸發(fā)優(yōu)先級調(diào)整 并重新調(diào)度。

紅黑樹鍵值計(jì)算

理解CFS的關(guān)鍵就是了解紅黑樹鍵值的計(jì)算方法。該鍵值由三個(gè)因子計(jì)算而得：一是進(jìn)程已經(jīng)占用的CPU時(shí)間；二是當(dāng)前進(jìn)程的nice值；三是當(dāng)前的cpu負(fù)載。

進(jìn)程已經(jīng)占用的CPU時(shí)間對鍵值的影響最大，其實(shí)很大程度上我們在理解CFS時(shí)可以簡單地認(rèn)為鍵值就等于進(jìn)程已占用的 CPU時(shí)間。因此該值越大，鍵值越大，從而使得當(dāng)前進(jìn)程向紅黑樹的右側(cè)移動(dòng)。另外CFS規(guī)定，nice值為1的進(jìn)程比nice值為0的進(jìn)程多獲得10%的 CPU時(shí)間。在計(jì)算鍵值時(shí)也考慮到這個(gè)因素，因此nice值越大，鍵值也越大。

CFS為每個(gè)進(jìn)程都維護(hù)兩個(gè)重要變量：fair_clock和wait_runtime。在本文中，我們將為每個(gè)進(jìn)程維護(hù)的變量稱為進(jìn)程級變量，為每個(gè)CPU維護(hù)的稱作CPU級變量，為每個(gè)runqueue維護(hù)的稱為runqueue級變量。

進(jìn)程插入紅黑樹的鍵值即為 fair_clock – wait_runtime。

fair_clock從其字面含義上講就是一個(gè)進(jìn)程應(yīng)獲得的CPU時(shí)間，即等于進(jìn)程已占用的CPU時(shí)間除以當(dāng)前 runqueue中的進(jìn)程總數(shù)；wait_runtime是進(jìn)程的等待時(shí)間。它們的差值代表了一個(gè)進(jìn)程的公平程度。該值越大，代表當(dāng)前進(jìn)程相對于其它進(jìn)程 越不公平。

對于交互式任務(wù)，wait_runtime長時(shí)間得不到更新，因此它能擁有更高的紅黑樹鍵值，更靠近紅黑樹的左邊。從而得到快速響應(yīng)。

紅黑樹是平衡樹，調(diào)度器每次總最左邊讀出一個(gè)葉子節(jié)點(diǎn)，該讀取操作的時(shí)間復(fù)雜度是O(LgN)。

調(diào)度器管理器

為了支持實(shí)時(shí)進(jìn)程，CFS提供了調(diào)度器模塊管理器。各種不同的調(diào)度器算法都可以作為一個(gè)模塊注冊到該管理器中。不同的進(jìn)程 可以選擇使用不同的調(diào)度器模塊。2.6.23中，CFS實(shí)現(xiàn)了兩個(gè)調(diào)度算法，CFS算法模塊和實(shí)時(shí)調(diào)度模塊。對應(yīng)實(shí)時(shí)進(jìn)程，將使用實(shí)時(shí)調(diào)度模塊。對應(yīng)普通 進(jìn)程則使用CFS算法。Ingo Molnar還邀請Con Kolivas可以將RSDL/SD寫成一個(gè)調(diào)度算法模塊。

CFS源代碼分析

Sched.c中scheduler_tick()函數(shù)會(huì)被時(shí)鐘中斷直接調(diào)用。它首先更新runqueue級變量 clock；然后調(diào)用CFS的tick處理函數(shù)task_tick_fair()。task_tick_fair在sched_fair.c中。它主要的 工作是調(diào)用entity_tick()

函數(shù)entiry_tick源代碼如下：

                
static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	struct sched_entity *next;
	dequeue_entity(cfs_rq, curr, 0);
	enqueue_entity(cfs_rq, curr, 0);
	next = __pick_next_entity(cfs_rq);
	if (next == curr)
		return;
	__check_preempt_curr_fair(cfs_rq, next, curr,
			sched_granularity(cfs_rq));
}

首先調(diào)用dequeue_entity()函數(shù)將當(dāng)前進(jìn)程從紅黑樹中刪除，再調(diào)用enqueue_entity（）重新插 入。這兩個(gè)動(dòng)作就調(diào)整了當(dāng)前進(jìn)程在紅黑樹中的位置。_pick_next_entity()返回紅黑樹中最左邊的節(jié)點(diǎn)，如果不再是當(dāng)前進(jìn)程，就調(diào)用 _check_preempt_curr_fair。該函數(shù)設(shè)置調(diào)度標(biāo)志，當(dāng)中斷返回時(shí)就會(huì)調(diào)用schedule()進(jìn)行調(diào)度。

函數(shù)enqueue_entity()的源碼如下:

                
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
{
	/*
	 * Update the fair clock.
	 */
	update_curr(cfs_rq);
	if (wakeup)
		enqueue_sleeper(cfs_rq, se);
	update_stats_enqueue(cfs_rq, se);
	__enqueue_entity(cfs_rq, se);
}

它的第一個(gè)工作是更新調(diào)度信息。然后將進(jìn)程插入紅黑樹中。其中update_curr()函數(shù)是核心。完成調(diào)度信息的更新。

                
static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq_curr(cfs_rq);
	unsigned long delta_exec;
	if (unlikely(!curr))
		return;
	delta_exec = (unsigned long)(rq_of(cfs_rq)->clock - curr->exec_start);
	curr->delta_exec += delta_exec;
	if (unlikely(curr->delta_exec > sysctl_sched_stat_granularity)) {
		__update_curr(cfs_rq, curr);
		curr->delta_exec = 0;
	}
	curr->exec_start = rq_of(cfs_rq)->clock;
}

該函數(shù)首先統(tǒng)計(jì)當(dāng)前進(jìn)程所獲得的CPU時(shí)間，rq_of(cfs_rq)->clock值在tick中斷中被更 新，curr->exec_start就是當(dāng)前進(jìn)程開始獲得CPU時(shí)的時(shí)間戳。兩值相減就是當(dāng)前進(jìn)程所獲得的CPU時(shí)間。將該變量存入 curr->delta_exec中。然后調(diào)用__update_curr()

                
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	unsigned long delta, delta_exec, delta_fair, delta_mine;
	struct load_weight *lw = &cfs_rq-load;
	unsigned long load = lw->weight;
	delta_exec = curr->delta_exec;
	schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
	curr->sum_exec_runtime += delta_exec;
	cfs_rq->exec_clock += delta_exec;
	if (unlikely(!load))		return;
	delta_fair = calc_delta_fair(delta_exec, lw);
	delta_mine = calc_delta_mine(delta_exec, curr->load.weight, lw);
	if (cfs_rq->sleeper_bonus > sysctl_sched_min_granularity) {
		delta = min((u64)delta_mine, cfs_rq->sleeper_bonus);
		delta = min(delta, (unsigned long)(
			(long)sysctl_sched_runtime_limit - curr->wait_runtime));
		cfs_rq->sleeper_bonus -= delta;
		delta_mine -= delta;
	}
	cfs_rq->fair_clock += delta_fair;
	add_wait_runtime(cfs_rq, curr, delta_mine - delta_exec);
}

__update_curr()的主要工作就是更新前面提到的fair_clock和wait_runtime。這兩個(gè)值 的差值就是后面進(jìn)程插入紅黑樹的鍵值。變量Delta_exec保存了前面獲得的當(dāng)前進(jìn)程所占用的CPU時(shí)間。函數(shù)calc_delta_fair()根 據(jù)cpu負(fù)載（保存在lw變量中），對delta_exec進(jìn)行修正，然后將結(jié)果保存到delta_fair變量中，隨后將fair_clock增加 delta_fair。函數(shù)calc_delta_mine()根據(jù)nice值（保存在curr->load.weight中）和cpu負(fù)載修正 delta_exec，將結(jié)果保存在delta_mine中。根據(jù)源代碼中的注釋，delta_mine就表示當(dāng)前進(jìn)程應(yīng)該獲得的CPU時(shí)間。

隨后將delta_fair加給fair_clock而將delta_mine-delta_exec加給 wait_runtime。函數(shù)add_wait_runtime中兩次將wait_runtime減去delta_mine-delta_exec。由 于calc_delt_xx()函數(shù)對delta_exec僅做了較小的修改，為了討論方便，我們可以忽略它們對delta_exec的修改。最終的結(jié)果 可以近似看成fair_clock增加了一倍的delta_exec，而wait_runtime減小了兩倍的delta_exec。因此鍵值 fair_clock-wait_runtime最終增加了一倍的delta_exec值。鍵值增加，使得當(dāng)前進(jìn)程再次插入紅黑樹中就向右移動(dòng)了。

CFS小結(jié)

以上的討論看出CFS對以前的調(diào)度器進(jìn)行了很大改動(dòng)。用紅黑樹代替優(yōu)先級數(shù)組；用完全公平的策略代替動(dòng)態(tài)優(yōu)先級策略；引入 了模塊管理器；它修改了原來Linux2.6.0調(diào)度器模塊70%的代碼。結(jié)構(gòu)更簡單靈活，算法適應(yīng)性更高。相比于RSDL，雖然都基于完全公平的原理， 但是它們的實(shí)現(xiàn)完全不同。相比之下，CFS更加清晰簡單，有更好的擴(kuò)展性。

CFS還有一個(gè)重要特點(diǎn)，即調(diào)度粒度小。CFS之前的調(diào)度器中，除了進(jìn)程調(diào)用了某些阻塞函數(shù)而主動(dòng)參與調(diào)度之外，每個(gè)進(jìn)程 都只有在用完了時(shí)間片或者屬于自己的時(shí)間配額之后才被搶占。而CFS則在每次tick都進(jìn)行檢查，如果當(dāng)前進(jìn)程不再處于紅黑樹的左邊，就被搶占。在高負(fù)載 的服務(wù)器上，通過調(diào)整調(diào)度粒度能夠獲得更好的調(diào)度性能。

回頁首

4 總結(jié)

通過對Linux調(diào)度器歷史發(fā)展的探討，能進(jìn)一步了解CFS調(diào)度器開發(fā)的背景知識。其實(shí)目前任何調(diào)度器算法都還無法滿足所有應(yīng)用的需要，CFS也有一些負(fù) 面的測試報(bào)告。我們相信隨著Linux的不斷發(fā)展，還會(huì)出現(xiàn)新的調(diào)度算法，讓我們拭目以待。有抱負(fù)的程序員也可以嘗試著在這個(gè)領(lǐng)域?yàn)長inux作出貢獻(xiàn)。

參考資料

• "Article about The staircase scheduler on lwn"
  
  
• "Article about CFS on lwn"
  
  
• "Article about RSDL on lwn"
  
  
• "Understanding the Linux Kernel, Second Edition "
  
  
• "Understanding the Linux Kernel, 3rd Edition "
  
  

關(guān)于作者