一、前言

隨著內(nèi)核版本的演進，其源代碼的膨脹速度也在遞增，這讓Linux的學(xué)習(xí)曲線變得越來越陡峭了。這對初識內(nèi)核的同學(xué)而言當然不是什么好事情，滿腔熱情很容易被當頭澆滅。我有一個循序漸進的方法，那就是先不要看最新的內(nèi)核，首先找到一個古老版本的內(nèi)核（一般都會比較簡單），將其吃透，然后一點點的迭代，理解每個版本變更背后的緣由和目的，最終推進到最新內(nèi)核版本。

本文就是從2.4時代的任務(wù)調(diào)度器開始，詳細描述其實現(xiàn)并慢慢向前遞進。當然，為了更好的理解Linux調(diào)度器設(shè)計和實現(xiàn)，我們在第二章給出了一些通用的概念。之后，我們會在第四章講述O（1）調(diào)度器如何改進并提升調(diào)度器性能。真正有劃時代意義的是CFS調(diào)度器，在2.6.23版本的內(nèi)核中并入主線。它的設(shè)計思想是那么的眩目，即便是目前最新的內(nèi)核中，完全公平的設(shè)計思想仍然沒有太大變化，這些我們會在第六章描述。第五章是關(guān)于公平調(diào)度思想的引入，通過這一章可以了解Con Kolivas的RSDL調(diào)度器，它是開啟公平調(diào)度的先鋒，通過這一章的鋪墊，我們可以更順暢的理解CFS。

二、任務(wù)調(diào)度器概述

為了不引起混亂，我們一開始先澄清幾個概念。進程調(diào)度器是傳統(tǒng)的說法，但是實際上進程是資源管理的單位，線程才是調(diào)度的單位，但是線程調(diào)度器的說法讓我覺得很不舒服，因此最終采用進程調(diào)度器或者任務(wù)調(diào)度器的說法。為了節(jié)省字，本文有些地方也直接簡稱調(diào)度器，此外，除非特別說明，本文中的“進程”指的是task struct代表的那個實體，畢竟這是一篇講調(diào)度器的文檔。

任務(wù)調(diào)度器是操作系統(tǒng)一個很重要的部件，它的主要功能就是把系統(tǒng)中的task調(diào)度到各個CPU上去執(zhí)行滿足如下的性能需求：

1、對于time-sharing的進程，調(diào)度器必須是公平的

2、快速的進程響應(yīng)時間

3、系統(tǒng)的throughput要高

4、功耗要小

當然，不同的任務(wù)有不同的需求，因此我們需要對任務(wù)進行分類：一種是普通進程，另外一種是實時進程。對于實時進程，毫無疑問快速響應(yīng)的需求是最重要的，而對于普通進程，我們需要兼顧前三點的需求。相信你也發(fā)現(xiàn)了，這些需求是互相沖突的，對于這些time-sharing的普通進程如何平衡設(shè)計呢？這里需要進一步將普通進程細分為交互式進程（interactive processs）和批處理進程（batch process）。交互式進程需要和用戶進行交流，因此對調(diào)度延遲比較敏感，而批處理進程屬于那種在后臺默默干活的，因此它更注重throughput的需求。當然，無論如何，分享時間片的普通進程還是需要兼顧公平，不能有人大魚大肉，有人連湯都喝不上。功耗的需求其實一直以來都沒有特別被調(diào)度器重視，當然在linux大量在手持設(shè)備上應(yīng)用之后，調(diào)度器不得不面對這個問題了，當然限于篇幅，本文就不展開了。

為了達到這些設(shè)計目標，調(diào)度器必須要考慮某些調(diào)度因素，比如說“優(yōu)先級”、“時間片”等。很多RTOS的調(diào)度器都是priority-based的，官大一級壓死人，調(diào)度器總是選擇優(yōu)先級最高的那個進程執(zhí)行。而在Linux內(nèi)核中，優(yōu)先級就是實時進程調(diào)度的主要考慮因素。而對于普通進程，如何細分時間片則是調(diào)度器的核心思考點。過大的時間片會嚴重損傷系統(tǒng)的響應(yīng)延遲，讓用戶明顯能夠感知到延遲，卡頓，從而影響用戶體驗。較小的時間片雖然有助于減少調(diào)度延遲，但是頻繁的切換對系統(tǒng)的throughput會造成嚴重的影響。因為這時候大部分的CPU時間用于進程切換，而忘記了它本來的功能其實就是推動任務(wù)的執(zhí)行。

由于Linux是一個通用操作系統(tǒng)，它的目標是星辰大海，既能運行在嵌入式平臺上，又能在服務(wù)器領(lǐng)域中獲得很好的性能表現(xiàn)，此外在桌面應(yīng)用場景中，也不能讓用戶有較差的用戶體驗。因此，Linux任務(wù)調(diào)度器的設(shè)計是一個極具挑戰(zhàn)性的工作，需要在各種有沖突的需求中維持平衡。還好，經(jīng)過幾十年內(nèi)核黑客孜孜不倦的努力，Linux內(nèi)核正在向著最終目標邁進。

三、2.4時代的O（n）調(diào)度器

網(wǎng)上有很多的linux內(nèi)核考古隊，挖掘非常古老內(nèi)核的設(shè)計和實現(xiàn)。雖然我對進程調(diào)度器歷史感興趣，但是我只對“近代史”感興趣，因此，讓我們從2.4時代開始吧，具體的內(nèi)核版本我選擇的是2.4.18版本，該版本的調(diào)度器相關(guān)軟件結(jié)構(gòu)可以參考下面的圖片：

本章所有的描述都是基于上面的軟件結(jié)構(gòu)圖。

1、進程描述符

對于2.4內(nèi)核，進程切換有兩種，一種是當進程由于需要等待某種資源而無法繼續(xù)執(zhí)行下去，這時候只能是主動將自己掛起（調(diào)用schedule函數(shù)），引發(fā)一次任務(wù)調(diào)度過程。另外一種是進程歡快執(zhí)行，但是由于各種調(diào)度事件的發(fā)生（例如時間片用完）而被迫讓出CPU，被其他進程搶占。這時候的調(diào)度并不是立刻發(fā)送，而是延遲執(zhí)行，具體的方法是設(shè)定當前進程的need_resched等于1，然后靜靜的等待最近一個調(diào)度點的來臨，當調(diào)度點到來的時候，內(nèi)核會調(diào)用schedule函數(shù)，搶占當前task的執(zhí)行。

nice成員就是普通進程的靜態(tài)優(yōu)先級，通過NICE_TO_TICKS宏可以將一個進程的靜態(tài)優(yōu)先級映射成缺省時間片，保存在counter成員中。因此在一次調(diào)度周期開始的時候，counter其實就是該進程分配的CPU時間額度（對于睡眠的進程還有些獎勵，后面會描述），以tick為單位，并且在每個tick到來的時候減一，直到耗盡其時間片，然后等待下一個調(diào)度周期從頭再來。

Policy是調(diào)度策略，2.4內(nèi)核主要支持三種調(diào)度策略，SCHED_OTHER是普通進程，SCHED_RR和SCHED_FIFO是實時進程。SCHED_RR和SCHED_FIFO的調(diào)度策略在rt_priority不同的時候，都是誰的優(yōu)先級高誰先執(zhí)行，唯一的不同是相同優(yōu)先級的處理：SCHED_RR采用時間片輪轉(zhuǎn)，而SCHED_FIFO采用的策略是先到先得，先占有CPU的進程會持續(xù)執(zhí)行，直到退出或者阻塞的時候才會讓出CPU。也只有這時候，其他同優(yōu)先級的實時進程才有機會執(zhí)行。如果進程是實時進程，那么rt_priority表示該進程的靜態(tài)優(yōu)先級。這個成員對普通進程是無效的，可以設(shè)定為0。除了上面描述的三種調(diào)度策略，policy成員也可以設(shè)定SCHED_YIELD的標記，當然它和調(diào)度策略無關(guān)，主要處理sched_yield系統(tǒng)調(diào)用的。

Processor、cpus_runnable和cpus_allowed這三個成員都是和CPU相關(guān)。Processor說明了該進程正在執(zhí)行（或者上次執(zhí)行）的邏輯CPU號；cpus_allowed是該task允許在那些CPU上執(zhí)行的掩碼；cpus_runnable是為了計算一個指定的進程是否適合調(diào)度到指定的CPU上去執(zhí)行而引入的，如果該進程沒有被任何CPU執(zhí)行，那么所有的bit被設(shè)定為1，如果進程正在被某個CPU執(zhí)行，那么正在執(zhí)行的CPU bit設(shè)定為1，其他設(shè)定為0。具體如何使用cpus_runnable可以參考can_schedule函數(shù)。

run_list成員是鏈接入各種鏈表的節(jié)點，下一小節(jié)會描述內(nèi)核如何組織task，這里不再贅述。

2、如何組織task

Linux2.4版本的進程調(diào)度器使用了非常簡陋的方法來管理可運行狀態(tài)的進程。調(diào)度器模塊定義了一個runqueue_head的鏈表頭變量，無論進程是普通進程還是實時進程，只要進程狀態(tài)變成可運行狀態(tài)的時候，它會被掛入這個全局runqueue鏈表中。隨著系統(tǒng)的運行，runqueue鏈表中的進程會不斷的插入或者移除。例如當fork進程的時候，新鮮出爐的子進程會掛入這個runqueue。當阻塞或者退出的時候，進程會從這個runqueue中刪除。但是無論如何變遷，調(diào)度器始終只是關(guān)注這個全局runqueue鏈表中的task，并把最適合的那個任務(wù)丟到CPU上去執(zhí)行。由于整個系統(tǒng)中的所有CPU共享一個runqueue，為了解決同步問題，調(diào)度器模塊定義了一個自旋鎖來保護對這個全局runqueue的并發(fā)訪問

除了這個runqueue隊列，系統(tǒng)還有一個囊括所有task（不管其進程狀態(tài)為何）的鏈表，鏈表頭定義為init_task，在一個調(diào)度周期結(jié)束后，重新為task賦初始時間片值的時候會用到該鏈表。此外，進入sleep狀態(tài)的進程分別掛入了不同的等待隊列中。當然，由于這些進程鏈表和調(diào)度關(guān)系不是那么密切，因此上圖中并沒有標識出來。

3、動態(tài)優(yōu)先級和靜態(tài)優(yōu)先級

所謂靜態(tài)優(yōu)先級就是task固有的優(yōu)先級，不會隨著進程的行為而改變。對于實時進程，靜態(tài)優(yōu)先級就是rt_priority，而對于普通進程，靜態(tài)優(yōu)先級就是（20 – nice）。然而實際上調(diào)度器在進行調(diào)度的時候，并沒有采用靜態(tài)優(yōu)先級，而是比對動態(tài)優(yōu)先級來決定誰更有資格獲得CPU資源，當然動態(tài)優(yōu)先級的計算是基于靜態(tài)優(yōu)先級的。

在計算動態(tài)優(yōu)先級（goodness函數(shù)）的時候，我們可以分成兩種情況：實時進程和普通進程。對于實時進程而言，動態(tài)優(yōu)先級等于靜態(tài)優(yōu)先級加上一個固定的偏移：

之所以這么做是為了將實時進程和普通進程區(qū)別開，這樣的操作也保證了實時進程會完全優(yōu)先于普通進程的調(diào)度。而對于普通進程，動態(tài)優(yōu)先級的計算稍微有些復(fù)雜，我們可以摘錄部分代碼如下：

對于普通進程，計算動態(tài)優(yōu)先級的策略如下：

（1） 如果該進程的時間片已經(jīng)耗盡，那么動態(tài)優(yōu)先級是0，這也意味著在本次調(diào)度周期中該進程已經(jīng)再也沒有機會獲取CPU資源了。

（2） 如果該進程的時間片還有剩余，那么其動態(tài)優(yōu)先級等于該進程剩余的時間片和靜態(tài)優(yōu)先級之和。之所以用（20-nice value）表示靜態(tài)優(yōu)先級，主要是為了讓靜態(tài)優(yōu)先級變成單調(diào)上升。之所以要考慮剩余時間片是為了獎勵睡眠的進程，因為睡眠的進程剩余的時間片較多，因此動態(tài)優(yōu)先級也就會高一些，更容易被調(diào)度器調(diào)度執(zhí)行。

調(diào)度器是根據(jù)動態(tài)優(yōu)先級來進行調(diào)度，誰大就先執(zhí)行誰。我們可以用普通進程作為例子：如果進程靜態(tài)優(yōu)先級高（即nice value小），剩余時間片多，那么必定是優(yōu)先執(zhí)行。如果靜態(tài)優(yōu)先級高，但是所剩時間片無幾，那么可能會讓位給其他剩余時間片較多，優(yōu)先級適中的任務(wù)。靜態(tài)優(yōu)先級低的任務(wù)毫無疑問是受到雙重打擊，因為本來它的缺省時間片就不多，而且優(yōu)先級也很低。不過，無論靜態(tài)優(yōu)先級如何高，只要時間片用完，那么低優(yōu)先級的任務(wù)總是能夠有機會執(zhí)行，不至于餓死。

在計算普通進程的動態(tài)優(yōu)先級的時候，除了考慮進程剩余時間片信息和靜態(tài)優(yōu)先級，調(diào)度器也會酌情考慮cache和TLB的性能問題。例如，例如A和B進程優(yōu)先級相同，剩余的時間片都是3個tick，但是A進程上一次就是運行在本CPU上，如果選擇A，可能會有更好的cache和TLB的命中率，從而提高性能。在這種情況下，調(diào)度器會提升A進程的動態(tài)優(yōu)先級。此外，如果備選進程和當前進程共享同一個地址空間，那么在計算調(diào)度指數(shù)的時候也會做小小的傾斜。這里有兩種可能的情況：一種是備選進程和當前進程在一個線程組中（即是進程中的兩個線程），另外一種情況是備選進程是內(nèi)核線程，這時候，它往往會借用上一個進程地址空間。不論是哪一種情況，在進程切換的時候，由于不需要進行進程地址空間的切換，因此也會有性能的優(yōu)勢。

3、調(diào)度時機

對于2.4內(nèi)核，產(chǎn)生調(diào)度的時機主要包括：

（1） 進程主動發(fā)起調(diào)度。

（2） 在timer中斷處理中發(fā)現(xiàn)當前進程耗盡其時間片

（3） 進程喚醒的時候（例如喚醒一個RT進程）。更詳細的信息可以參考下一個小節(jié)。

（4） 父進程在fork的時候，其時間片會均分到父子進程，但是如果只剩下一個tick，這個tick會分配給子進程，而父進程的時間片則被清零，這時候，進程遭遇的場景等同與在timer中斷處理中發(fā)現(xiàn)當前進程耗盡其時間片。如果父進程在fork的時候，其時間片較大，父子進程的時間片都不為0，這時候的場景類似于喚醒進程。因為這兩個場景都是向runqueue中添加了一個task node，從而引發(fā)的調(diào)度。

（5） 進程切換的時候。當在系統(tǒng)中的某個CPU上發(fā)生了進程切換，例如A任務(wù)切換到了B任務(wù)，這時候是否A任務(wù)就失去了執(zhí)行的機會了呢？當然也未必，因為雖然競爭本CPU失敗，但是也許其他的CPU上運行的task動態(tài)優(yōu)先級還不如A呢，抑或正好其他CPU有進入idle狀態(tài)，正等待著新進程入駐。

（6） 用戶進程主動讓出CPU的時候

（7） 用戶進程修改調(diào)度參數(shù)的時候

上面的種種場景，除了進程主動調(diào)度之外，其他的場景都不是立刻調(diào)度schedule函數(shù)，而是設(shè)定need_resched標記，然后等待調(diào)度點的到來。由于2.4內(nèi)核不是preemptive kernel，因此調(diào)度點總是在返回用戶空間的時候才會到來。當調(diào)度點到來的時候，進程調(diào)度就會在該CPU上啟動。搶占的場景太多，我們選擇進程喚醒的場景來詳細描述，其他場景大家自行分析吧。

4、進程喚醒的處理

當進程被喚醒的時候（try_to_wake_up），該task會被加入到那個全局runqueue中，但是是否啟動調(diào)度還需要進行一系列的判斷。為了能清楚的描述這個場景，我們定義執(zhí)行喚醒的那個進程是waker，而被喚醒的進程是wakee。Wakeup有兩種，一種是sync wakeup，另外一種是non-sync wakeup。所謂sync wakeup就是waker在喚醒wakee的時候就已經(jīng)知道自己很快就進入sleep狀態(tài)，而在調(diào)用try_to_wake_up的時候最好不要進行搶占，因為waker很快就主動發(fā)起調(diào)度了。此外，一般而言，waker和wakee會有一定的親和性（例如它們通過share memory進行通信），在SMP場景下，waker和wakee調(diào)度在一個CPU上執(zhí)行的時候往往可以獲取較佳的性能。而如果在try_to_wake_up的時候就進行調(diào)度，這時候wakee往往會調(diào)度到系統(tǒng)中其他空閑的CPU上去。這時候，通過sync wakeup，我們往往可以避免不必要的CPU bouncing。對于non-sync wakeup而言，waker和wakee沒有上面描述的同步關(guān)系，waker在喚醒wakee之后，它們之間是獨立運作，因此在喚醒的時候就可以嘗試去觸發(fā)一次調(diào)度。

當然，也不是說sync wakeup就一定不調(diào)度，假設(shè)waker在CPU A上喚醒wakee，而根據(jù)wakee進程的cpus_allowed成員發(fā)現(xiàn)它根本不能在CPU A上調(diào)度執(zhí)行，那么管他sync不sync，這時候都需要去嘗試調(diào)度（調(diào)用reschedule_idle函數(shù)），反正waker和wakee命中注定是天各一方（在不同的CPU上執(zhí)行）。

我們首先看看UP上的情況。這時候waker和wakee在同一個CPU上運行（當然系統(tǒng)中也只有一個CPU，哈哈），這時候誰能搶占CPU資源完全取決于waker和wakee的動態(tài)優(yōu)先級，如果wakee的動態(tài)優(yōu)先級大于waker，那么就標記waker的need_resched標志，并在調(diào)度點到來的時候調(diào)用schedule函數(shù)進行調(diào)度。

SMP情況下，由于系統(tǒng)的CPU資源比較多，waker和wakee沒有必要爭個你死我活，wakee其實也可以選擇去其他CPU執(zhí)行，相關(guān)的算法大致如下：

（1） 優(yōu)先調(diào)度wakee去系統(tǒng)其他空閑的CPU上執(zhí)行，如果wakee上次運行的CPU恰好處于idle狀態(tài)的時候，可以考慮優(yōu)先將wakee調(diào)度到那個CPU上執(zhí)行。如果不是，那么需要掃描系統(tǒng)中所有的CPU找到最合適的idle CPU。所謂最合適就是指最近才進入idle的那個CPU。

（2） 如果所有的CPU都是busy的，那么需要遍歷所有CPU上當前運行的task，比對它們的動態(tài)優(yōu)先級，找到動態(tài)優(yōu)先級最低的那個CPU。

（3） 如果動態(tài)優(yōu)先級最低的那個task的優(yōu)先級仍然高于wakee，那么沒有必要調(diào)度，runqueue中的wakee需要耐心等待下一次機會。如果wakee的動態(tài)優(yōu)先級高于找到的那個動態(tài)優(yōu)先級最低的task，那么標記其need_resched標志。如果不是搶占waker，那么我們還需要發(fā)送IPI去觸發(fā)該CPU的調(diào)度。

當然，這是2.4內(nèi)核調(diào)度器的設(shè)計選擇，實際上這樣的操作值得商榷。限于篇幅，本文就不再展開敘述，如果有機會寫負載均衡的文章就可以好好的把這些關(guān)系梳理一下。

5、主調(diào)度器算法

主調(diào)度器（schedule函數(shù)）核心代碼如下：

list_for_each用來遍歷runqueue_head鏈表上的所有的進程，臨時變量p就是本次需要檢查的進程描述符。如何判斷哪一個進程是最適合調(diào)度執(zhí)行的進程呢？我們需要計算進程的動態(tài)優(yōu)先級（對應(yīng)上面程序中的變量weight），它是通過goodness函數(shù)實現(xiàn)的。動態(tài)優(yōu)先級最大的那個進程就是當前最適合調(diào)度到CPU執(zhí)行的進程。一旦選中，調(diào)度器會啟動進程切換，運行該進程以替換之前的那個進程。

根據(jù)代碼可知：即便鏈表第一個節(jié)點就是最合的下一個要調(diào)度執(zhí)行的進程，調(diào)度器算法仍然會遍歷全局runqueue鏈表，一一比對。由此我們可以判斷2.4內(nèi)核中的調(diào)度器的算法復(fù)雜度是O（n）。一旦選中了下一個要執(zhí)行的進程，進程切換模塊就會在該CPU上執(zhí)行具體的進程切換。

對于SCHED_RR的實時進程，優(yōu)先級相等的情況下還需要有一個時間片輪轉(zhuǎn)的概念。因此，在遍歷鏈表之前我們就先處理該進程的時間片處理：

如果時間片（對應(yīng)上面程序中的prev->counter）用完，SCHED_RR的實時進程會被移到runqueue鏈表的尾部。通過這樣的處理，優(yōu)先級相等的SCHED_RR在遍歷runqueue鏈表的時候會命中鏈表中的第一個task，從而實現(xiàn)時間片輪轉(zhuǎn)的概念。這里有一個比較奇葩的事情就是SCHED_RR的時間片是根據(jù)其nice value設(shè)定，而實際上nice value應(yīng)該只適用于普通進程的。

6、時間片處理

普通進程的時間片處理思路是這樣：

（1）每個進程根據(jù)其靜態(tài)優(yōu)先級可以固定分配一個缺省的時間片，靜態(tài)優(yōu)先級越大，分配的時間片就越大。

（2）一旦Runqueue中的進程被調(diào)度執(zhí)行，那么其時間片就會在tick到來的時候遞減，如果進程時間片耗盡，那么該進程將失去分配CPU資源的資格。

（3）Runqueue中的進程的時間片全部被用完之后，我們稱一個調(diào)度周期結(jié)束，這時候需要為runqueue中的進程重新設(shè)定其缺省時間片，這樣，一個新的調(diào)度周期又開始了。

如何確定每個進程的缺省時間片呢？由于時間片是按照tick來分配的，那么最小的時間片也是1個tick，也就是說最低優(yōu)先級（nice value等于19）的缺省時間片就是1個tick。對于中間優(yōu)先級（nice value等于0）的時間片，我們將其設(shè)定為50ms左右，具體的算法大家可以自行參考NICE_TO_TICKS的代碼實現(xiàn)。不得不承認這個根據(jù)nice value計算缺省時間片的過程還是很丑陋的，不同的HZ設(shè)定，計算得到的缺省時間片是不一樣的。也就是說系統(tǒng)的調(diào)度行為和HZ的設(shè)定有關(guān)，這叫有代碼潔癖的同學(xué)如何能夠接受。不論如何，我們還是給出實際的例子來感受一下：

當runqueue中所有進程的時間片耗盡之后，這時候就會開啟一次重新加載進程缺省時間片的過程，代碼如下（在schedule函數(shù)中）：

這里c就是遍歷runqueue鏈表之后找到的最大動態(tài)優(yōu)先級，如果它等于0則說明：首先，系統(tǒng)中沒有處于可運行狀態(tài)的實時進程，其次，所有的處于可運行狀態(tài)的普通進程都已經(jīng)消耗完了它們的時間片，這時候是需要重新“充值”了。for_each_task這個宏是遍歷所有系統(tǒng)中的進程描述符，不論是否是可運行狀態(tài)的。對于掛入runqueue鏈表中的普通進程而言，其當前的時間片p->counter已經(jīng)是等于0了，因此它獲得的新的時間片就是NICE_TO_TICKS(p->nice)，也就是根據(jù)nice value計算得到的缺省時間片。對于掛入等待隊列中處于睡眠狀態(tài)的進程而言，其時間片p->counter還有剩余，當然會累積到進程時間片配額中，這也算是對睡眠進程的一種獎勵吧。為了防止經(jīng)常睡眠的交互式進程獲得過于龐大的時間片，這里并不是累積其全部存留時間片，而是打了個對折(p->counter >> 1)。

新的一個周期開始了，當前進程已經(jīng)在CPU上奔跑了，消耗其時間片的代碼位于timer中斷處理中，如下：

每一個tick到來的時候，進程的時間片都會減一，當時間片是0的時候，調(diào)度器剝奪其執(zhí)行的權(quán)力，從而從而引發(fā)一次調(diào)度，選擇其他時間片不是0的進程運行，直到runqueue中的所有進程時間片耗盡，又會重新賦值，開始一個新的周期。調(diào)度器就這樣周而復(fù)始，推動整個系統(tǒng)的運作。

四、2.6時代的O（1）調(diào)度器

1、Why O（1）調(diào)度器

如果簡單是判斷調(diào)度器好壞的唯一標準，那么無疑O（n）調(diào)度器是最優(yōu)秀的調(diào)度器。雖然它非常的簡單，容易理解，但是存在嚴重的擴展性問題和性能問題。下面讓我們一起來控訴O（n）調(diào)度器的“七宗罪”，同時這也是Ingo Molnar發(fā)起O（1）調(diào)度器項目背后的原因。

（1）算法復(fù)雜度問題

讓人最不爽的就是對runqueue隊列的遍歷，當系統(tǒng)中runnable進程不多的時候，遍歷鏈表的開銷還可以接受，但是隨著系統(tǒng)中runnable狀態(tài)的進程數(shù)目增多，那么調(diào)度器select next的運算量也隨之呈線性的增長，這也是我們?yōu)槭裁唇兴麿（n）調(diào)度器的原因。

此外，調(diào)度周期結(jié)束后，調(diào)度器會為所有進程的時間片進行“充值“的動作。在大型系統(tǒng)中，同時存在的進程（包括睡眠的進程）可能會有數(shù)千個，為每一個進程計算其時間片的過程太耗費時間。

（2）SMP擴展性問題

2.4內(nèi)核的O（n）調(diào)度器有非常差的SMP擴展性。我們知道，O（n）調(diào)度器是通過一個鏈表來管理系統(tǒng)中的所有的等待調(diào)度的進程，訪問這個runqueue鏈表的場景很多：進行調(diào)度的時候，我們需要遍歷runqueue，找到合適的next task；wakeup或者block進程的時候，我們需要從runqueue中增加節(jié)點或者刪除節(jié)點……在訪問runqueue這個鏈表的時候，我們都會首先會上自旋鎖，同時disable本地CPU中斷，然后訪問鏈表執(zhí)行相應(yīng)的動作，完成之后釋放鎖，開中斷。通過這樣的內(nèi)核同步機制，我們可以保證來自多個CPU對runqueue鏈表的并發(fā)訪問。當系統(tǒng)中的CPU數(shù)目比較少的時候，自旋鎖的開銷還可以接受，但是在大型系統(tǒng)中，CPU數(shù)目非常多，這時候runqueue spin lock就成為系統(tǒng)的性能瓶頸。

（3）CPU空轉(zhuǎn)問題

每當runqueue鏈表中的所有進程耗盡了其時間片，這時候就需要啟動對系統(tǒng)中所有進程時間片重新計算的過程。這個計算過程異常丑陋，需要遍歷系統(tǒng)中的所有進程（注意：是所有進程?。?，為進程描述符的counter成員賦一個新值。而這個操作足以把該CPU上的L1 cache全部干掉。當完成了時間片重新計算過程后，你幾乎面對的就是一個全空的L1 cache（當然不是全空，主要是cache中的數(shù)據(jù)沒有任何意義，這時候L1 cache的命中率急劇下降）。除此之外，時間片重新計算過程會帶來CPU資源的浪費，我們用下面的圖片來描述：

在runqueue隊列中的全部進程時間片被耗盡之前，系統(tǒng)總會處于這樣一個狀態(tài)：最后的一組尚存時間片的進程分分別調(diào)度到各個CPU上去。我們以4個CPU為例，T0～T3分別運行在CPU0~CPU3上。隨著系統(tǒng)的運行，CPU2上的T2首先耗盡了其時間片，但是這時候，其實CPU2上也是無法進行調(diào)度的，因為遍歷runqueue鏈表，找不到適合的進程調(diào)度運行，因此它只能是處于idle狀態(tài)。也許隨后T0和T3也耗盡其時間片，從而導(dǎo)致CPU0和CPU3也進入了idle狀態(tài)?，F(xiàn)在只剩下最后一個進程T1仍然在CPU1上運行，而其他系統(tǒng)中的處理器處于idle狀態(tài)，白白的浪費資源。唯一能改變這個狀態(tài)的是T1耗盡其時間片，從而啟動一個重新計算時間片的過程，這時候，正常的調(diào)度就可以恢復(fù)了。隨著系統(tǒng)中CPU數(shù)目的加大，資源浪費會越來越嚴重。

（4）task bouncing issue

一般而言，一個進程最好是從一而終，假如它運行在系統(tǒng)中的某個CPU中，那么在其處于可運行狀態(tài)的過程中，最好是一直保持在該CPU上運行。不過在O（n）調(diào)度器下，很多人都反映有進程在CPU之間跳來跳去的現(xiàn)象。其根本的原因也是和時間片算法相關(guān)。在一個新的周期開后，runqueue中的進程時間片都是滿滿的，在各個CPU上調(diào)度進程的時候，它可選擇的比較多，再加上調(diào)度器傾向于調(diào)度上次運行在本CPU的進程，因此調(diào)度器有很大的機會把上次運行的進程調(diào)度到同一個處理器上。但是隨著runqueue中的進程一個個的耗盡其時間片，cpu可選擇的余地在不斷的壓縮，從而導(dǎo)致進程執(zhí)行在一個和它親和性不大的處理器（例如上次該進程運行在CPU0，但是這個將其調(diào)度到CPU1執(zhí)行，但是實際上該進程和CPU0的親和性更大些）。

（5）RT進程調(diào)度性能問題

實時調(diào)度的性能一般。通過上一節(jié)的介紹，我們知道，實時進程和普通進程掛在一個鏈表中。當調(diào)度實時進程的時候，我們需要遍歷整個runqueue列表，掃描并計算所有進程的調(diào)度指數(shù)，從而選擇出心儀的那個實時進程。按理說實時進程和普通進程位于不同的調(diào)度空間，兩不相干，但是現(xiàn)在調(diào)度實時進程還需要掃描計算普通進程，這樣糟糕的算法讓那些關(guān)注實時性的工程師不能忍受。

當然，上面的這些還不是關(guān)鍵，最重要的是整個linux內(nèi)核不是搶占式內(nèi)核，在整個內(nèi)核態(tài)都不能被搶占。對于一些比較耗時（可能幾個毫秒）的系統(tǒng)調(diào)用或者中斷處理，必須返回用戶空間才啟動調(diào)度是不可接受的。除了內(nèi)核搶占性之外，優(yōu)先級翻轉(zhuǎn)問題也需要引起調(diào)度器的重視，否則即便一個rt進程變成runnable狀態(tài)了，但是也只能眼睜睜的看著比它優(yōu)先級低的進程運行，直到該rt進程等待的資源被釋放。

（6）交互式普通進程的調(diào)度延遲問題

O（n）并不區(qū)分交互式進程和批處理進程，它只是獎勵經(jīng)常睡眠的那些進程。但是有些批處理進程也屬于IO-bound進程，例如數(shù)據(jù)庫服務(wù)進程，它本身是一個后臺進程，對調(diào)度延遲不敏感，但是由于它需要和磁盤打交道，因此也會經(jīng)常阻塞在disk IO上。對這樣的后臺進程進行動態(tài)優(yōu)先級的升高其實是沒有意義的，會增大其他交互式進程的調(diào)度延遲。另外一方面，用戶交互式進程也可能是CPU-bound的，而這時候調(diào)度器不會正確的了解到該進程的調(diào)度需求并對其進行補償。

（7）時間片粒度問題。

用戶感知到的響應(yīng)延遲是和系統(tǒng)負載相關(guān)，我們可以用runnable進程數(shù)目來粗略的描述系統(tǒng)的負載。當系統(tǒng)負載高的時候，runqueue中的進程數(shù)目會比較多，一次調(diào)度周期的時間就會比較長，例如在HZ=100的情況下，runqueue上有5個runnable進程，nice value是0，每個時間片配額是60ms，那么一個調(diào)度周期就是300ms。隨著runnable進程增大，調(diào)度周期也變大。當一個進程耗盡其時間片之后，只能等待下一個調(diào)度周期到來。因此隨著調(diào)度周期變大，系統(tǒng)響應(yīng)也會變的較差。

雖然O（n）調(diào)度器存在不少的issue，但是社區(qū)的人還是基本認可這套算法的，因此在設(shè)計新的調(diào)度器的時候并不是完全推翻O（n）調(diào)度器的設(shè)計，而是針對O（n）調(diào)度器的問題進行改進。在本章中我們選擇2.6.11版本的內(nèi)核來描述O（1）調(diào)度器如何運作。鑒于O（1）調(diào)度器和O（n）調(diào)度器沒有本質(zhì)區(qū)別，因此我們只是描述它們之間不同的地方。

2、O（1）調(diào)度器的軟件功能劃分

下圖是一個O（1）調(diào)度器的軟件框架：

O（n）調(diào)度器中只有一個全局的runqueue，嚴重影響了擴展性，因此在O（1）調(diào)度器中引入了per-CPU runqueue的概念。系統(tǒng)中所有的可運行狀態(tài)的進程首先經(jīng)過負載均衡模塊掛入各個CPU的runqueue，然后由主調(diào)度器和tick調(diào)度器驅(qū)動該CPU上的調(diào)度行為。由于篇幅的原因，我們在本文中不講解負載均衡模塊，把重點放在單個CPU上的任務(wù)調(diào)度算法。

由于引入了per-CPU runqueue，O（1）調(diào)度器刪除了全局runqueue的spin lock，而是把這個spin lock放入到per-CPU runqueue數(shù)據(jù)結(jié)構(gòu)中（rq->lock），通過把一個大鎖細分成小鎖，可以大大降低調(diào)度延遲，提升系統(tǒng)響應(yīng)時間。這種方法在內(nèi)核中經(jīng)常使用，是一個比較通用的性能優(yōu)化方法。

通過上面的軟件結(jié)構(gòu)劃分可以解決O（n）調(diào)度的SMP擴展性問題和CPU空轉(zhuǎn)問題。此外，好的復(fù)雜均衡算法也可以解決O（n）調(diào)度器的task bouncing 問題。

3、O（1）調(diào)度器的runqueue結(jié)構(gòu)

O（1）調(diào)度器的基本優(yōu)化思路就是把原來runqueue上的單鏈表變成多個鏈表，即每一個優(yōu)先級的進程被掛入不同鏈表中。相關(guān)的軟件結(jié)構(gòu)可以參考下面的圖片：

在調(diào)度器中，runqueue是一個很重要的數(shù)據(jù)結(jié)構(gòu)，它最重要的作用是管理那些處于可運行狀態(tài)的進程。O（1）調(diào)度器引入了優(yōu)先級隊列的概念來管理task，具體由struct prio_array抽象：

由于支持140個優(yōu)先級，因此queue成員中有140個分別表示各個優(yōu)先級的鏈表頭，不同優(yōu)先級的進程掛入不同的鏈表中。bitmap 是表示各個優(yōu)先級進程鏈表是空還是非空。nr_active表示這個隊列中有多少個task。在這些隊列中，100～139是普通進程的優(yōu)先級，其他的是實時進程的優(yōu)先級。因此，在O（1）調(diào)度器中，RT進程和普通進程被區(qū)分開了，普通進程根本不會影響RT進程的調(diào)度。

Runqueue中有兩個優(yōu)先級隊列（struct prio_array）分別用來管理active（即時間片還有剩余）和expired（時間片耗盡）的進程。Runqueue中有兩個優(yōu)先級隊列的指針，分別指向這兩個優(yōu)先級隊列。隨著系統(tǒng)的運行，active隊列的task一個個的耗盡其時間片，掛入到expired隊列。當active隊列的task為空的時候，切換active和expired隊列，開始一輪新的調(diào)度過程。

雖然在O（1）調(diào)度器中task組織的形式發(fā)生了變化，但是其核心思想仍然和O（n）調(diào)度器一致的，都是把CPU資源分成一個個的時間片，分配給每一個runnable的進程。進程用完其額度后被搶占，等待下一個調(diào)度周期的到來。

4、核心調(diào)度算法

主調(diào)度器（就是schedule函數(shù)）的主要功能是從該CPU的runqueue找到一個最合適的進程調(diào)度執(zhí)行。其基本的思路就是從active優(yōu)先級隊列中尋找，代碼如下：

首先在當前active優(yōu)先級隊列的bitmap尋找第一個非空的進程鏈表，然后從該鏈表中找到的第一個節(jié)點就是最適合下一個調(diào)度執(zhí)行的進程。由于沒有遍歷整個鏈表的操作，因此這個調(diào)度器的算法復(fù)雜度是一個常量，從而解決了O（n）算法復(fù)雜度的issue。

如果當前active優(yōu)先級隊列中“空無一人”（nr_active等于0），那么這時候就需要切換active和expired優(yōu)先級隊列了：

切換很快，并沒有一個遍歷所有進程重新賦default時間片的操作（大大縮減了runqueue臨界區(qū)的size）。這些都避免了O（n）調(diào)度器帶來的種種問題，從而提高了調(diào)度器的性能。

5、靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級

在前面的小節(jié)中，我們有意的忽略了優(yōu)先級隊列中“優(yōu)先級”的具體含義，現(xiàn)在是需要澄清的時候了。其實優(yōu)先級隊列中“優(yōu)先級”指的是動態(tài)優(yōu)先級，從這個角度看，O（1）和O（n）調(diào)度器的調(diào)度算法又統(tǒng)一了，都是根據(jù)動態(tài)優(yōu)先級進行調(diào)度。

O（1）的靜態(tài)優(yōu)先級的概念和O（n）是類似的，對于實時進程保存在進程描述符的rt_priority成員中，取值范圍是1（優(yōu)先級最低）～99（優(yōu)先級最高）。對于普通進程，靜態(tài)優(yōu)先級則保存在static_prio成員中，取值范圍是100（優(yōu)先級最高）～139（優(yōu)先級最低），分別對應(yīng)nice value的-20 ～ 19。

了解了靜態(tài)優(yōu)先級之后，我們一起來看看動態(tài)優(yōu)先級（保存在進程描述符的prio成員中）。鑒于在實際調(diào)度的時候使用的是動態(tài)優(yōu)先級，我們必須要保證它是單調(diào)的（靜態(tài)優(yōu)先級未能保持單調(diào)，rt的99和普通進程的100都是靜態(tài)優(yōu)先級的最高點，也就是說在靜態(tài)優(yōu)先級數(shù)軸上，rt段是單調(diào)上升，而在普通進程段是單調(diào)下降的）。為了解決這個問題，在計算實時進程動態(tài)優(yōu)先級的時候進行了一個簡單的映射：

通過這樣的轉(zhuǎn)換，rt的動態(tài)優(yōu)先級在數(shù)軸上也是單調(diào)下降的了。普通進程的動態(tài)優(yōu)先級計算沒有那么簡單，除了靜態(tài)優(yōu)先級，還需要考慮進程的平均睡眠時間（保存在進程描述符的sleep_avg成員中），并根據(jù)該值對進程進行獎懲。具體代碼可以參考effective_prio函數(shù)，這里不再詳述，最終普通進程的動態(tài)優(yōu)先級是100（優(yōu)先級最高）～139（優(yōu)先級最低），和靜態(tài)優(yōu)先級的取值范圍是一致的。

在本小節(jié)的最后，我們一起來對比普通進程在O（1）和O（n）調(diào)度器的動態(tài)優(yōu)先級算法。這個兩個調(diào)度器的基本思路是一致的：考慮靜態(tài)優(yōu)先級，輔以對該進程的“用戶交互指數(shù)”的評估，用戶交互指數(shù)高的，調(diào)升其動態(tài)優(yōu)先級，反之則降低。不過在評估用戶交互指數(shù)上，O（1）顯然做的更好。O（n）調(diào)度器僅僅考慮了睡眠進程的剩余時間片，而O（1）的“平均睡眠時間”算法顯然考慮更多的因素：在cpu上的執(zhí)行時間、在runqueue中的等待時間、睡眠時間、睡眠時候的進程狀態(tài)（是否可被信號打斷），什么上下文喚醒（中斷上下文喚醒還是在進程上下文中喚醒）……因此O（1）調(diào)度器更好的判斷了進程是屬于interactive process還是batch process，從而精準的為interactive process打call。

6、時間片處理

缺省時間片的計算是通過task_timeslice完成的，在O（1）調(diào)度器中，缺省時間片已經(jīng)和HZ無關(guān)了，無論如何設(shè)置HZ，靜態(tài)優(yōu)先級為[ -20 ... 0 ... 19 ]的普通進程其缺省時間片為[800ms ... 100ms ... 5ms]。

在tick到來的時候，當前task的時間片會遞減（--p->time_slice），當時間片等于0的時候，會將該task從active優(yōu)先級列表中摘下，設(shè)定resched標記，并且重置時間片，代碼如下：

task_timeslice函數(shù)就是用來計算進程時間片的配額的。對于O（1）調(diào)度器，時間片的重新賦值是分散處理的，在各個task耗盡其時間片之后立刻進行的。這樣的改動也修正了O（n）調(diào)度器一次性的遍歷系統(tǒng)所有進程，重新為時間片賦值的過程。

6、識別用戶交互式進程

一般而言，時間片耗盡之后，該task會被掛入到expired優(yōu)先級隊列，這時候如果想要被調(diào)度只能等到下次active和expired切換了。不過，有些特殊的場景需要特殊處理：

這里TASK_INTERACTIVE是用來判斷一個進程是否是一個用戶交互式進程（也是和平均睡眠時間相關(guān)，由此可見，平均睡眠時間不僅用于計算動態(tài)優(yōu)先級，還用來決定一個進程是否回插入active隊列），如果是的話，說明該進程對用戶響應(yīng)比較敏感，這時候不能粗暴的掛入expired隊列，而是重新掛入active隊列，繼續(xù)有機會獲取調(diào)度執(zhí)行的機會。由此可見，O（1）調(diào)度器真是對用戶交互式進程非常的照顧，一旦被判斷是用戶交互型進程，那么它將獲取連續(xù)執(zhí)行的機會。當然，調(diào)度器也不能太過分，如果用戶交互型進程持續(xù)占用CPU，那么在expired隊列中苦苦等待進程怎么辦？這時候就要看看expired隊列中的進程的饑餓狀態(tài)了，這也就是EXPIRED_STARVING這個宏定義的功能。如果expired隊列中的進程等待了太長的時間，那么說明調(diào)度器已經(jīng)出現(xiàn)嚴重不公平的現(xiàn)象，因此這時候即便是判斷當前耗盡時間片的進程是用戶交互型進程，也把它掛入expired隊列，盡快的完成本次調(diào)度周期，讓active和expired發(fā)生切換。

O（1）調(diào)度器使用非常復(fù)雜的算法來判斷進程的用戶交互指數(shù)以及進程是否是交互式進程，hardcode了很多的不知其所以然的常數(shù)，估計也是通過各種大量的實驗場景總結(jié)出來的。這部分的設(shè)計概念我是在是沒有勇氣去探索，因此這里就略過了。但是無論如何，它總是比僅僅考慮睡眠時間的O（n）調(diào)度器性能要好。

7、搶占式內(nèi)核

2.4時代，大部分的Linux應(yīng)用都集中在服務(wù)器領(lǐng)域，因此非搶占式內(nèi)核的設(shè)計選擇也無可厚非。不過隨著Linux在桌面和嵌入式上的滲透，系統(tǒng)響應(yīng)慢慢的稱為用戶投訴的主要方面，因此，在2.5的開發(fā)過程中，Linux引入了搶占式內(nèi)核的概念（CONFIG_PREEMPT），如果沒有配置該選項，那么一切和2.4內(nèi)核保持一致，如果配置了該選項，那么不需要在返回用戶空間的時候才苦苦等到調(diào)度點，大部分的內(nèi)核執(zhí)行路徑都是可以被搶占的。同樣的，限于篇幅，這里不再展開描述。

五、公平調(diào)度思想的引入

1、傳統(tǒng)調(diào)度器時間片悖論

在O（n）和O（1）調(diào)度器中，時間片是固定分配的，靜態(tài)優(yōu)先級高的進程獲取更大的time slice。例如nice value等于20的進程獲取的default timeslice是5ms，而nice value等于0的進程獲取的是100ms。直觀上，這樣的策略沒有毛?。ǜ邇?yōu)先級的獲取更多的執(zhí)行時間），但是，這樣的設(shè)定潛臺詞就是：高優(yōu)先級的進程會獲得更多的連續(xù)執(zhí)行的機會，這是CPU-bound進程期望的，但是實際上，CPU-bound進程往往在后臺執(zhí)行，其優(yōu)先級都是比較低的。

因此，假設(shè)我們調(diào)度策略就是根據(jù)進程靜態(tài)優(yōu)先級確定一個固定大小的時間片，這時候我們在如何分配時間片上會遇到兩難的狀況：想要給用戶交互型進程設(shè)定高優(yōu)先級，以便它能有更好的用戶體驗，但是分配一個大的時間片是毫無意義的，因為這種進程多半是處于阻塞態(tài)，等待用戶的輸入。而后臺進程的優(yōu)先級一般不高，但是根據(jù)其優(yōu)先級分配一個較小的時間片往往會影響其性能，這種類型的進程最好是趁著cache hot的時候狂奔。

怎么辦？或者傳統(tǒng)調(diào)度器固定分配時間片這個設(shè)計概念就是錯誤的。

2、傳統(tǒng)調(diào)度器的卡頓問題

在Linux 2.5版本的開發(fā)過程中，Ingo Molnar設(shè)計的O（1）調(diào)度器替換掉了原始的、簡陋的O（n）調(diào)度器，從而解決了擴展性很差，性能不佳的問題。在大部分的場景中，該調(diào)度器都獲得了滿意的性能，在商用的Linux 2.4發(fā)行版中，O（1）調(diào)度器被很多廠商反向移植到Linux 2.4中，由此可見O（1）調(diào)度器性能還是優(yōu)異的。

然而O（1）并非完美，在實際的使用過程中，還是有不少的桌面用戶在抱怨用戶交互性比較差。當一個相當消耗CPU資源的進程啟動的時候，現(xiàn)存的那些用戶交互程序（例如你在通過瀏覽器查看網(wǎng)頁）都可以感覺到明顯的延遲。針對這些issue，很多天才工程師試圖通過對用戶交互指數(shù)算法的的修改來解決問題，這里面就包括公平調(diào)度思想的提出者Con Kolivas。不過無論如何調(diào)整算法，總是有點拆東墻補西墻的感覺，一個場景的issue修復(fù)了，另外一個場景又冒出來交互性不好的issue，刁鉆的客戶總是能夠在邊邊角角的場景中找到讓用戶感覺到的響應(yīng)延遲。

在反反復(fù)復(fù)修復(fù)用戶卡頓issue的過程中，工程師最容易煩躁，而往往這時候最需要冷靜的思考。Con Kolivas仔細的檢視了調(diào)度器代碼，他發(fā)現(xiàn)出問題的是評估進程用戶交互指數(shù)的代碼。為何調(diào)度器要根據(jù)進程的行為猜測其對交互性的需求？這根本是一項不可能完成的任務(wù)，因為你總是不會100％全部猜中，就好像你去猜測你喜歡的女孩子的心事一樣，你細心的收集了關(guān)于這個女孩子的性格特點，業(yè)余愛好，做事風(fēng)格，邏輯思維水平，星座……甚至生理周期，并期望著能總是正確的猜中其心中所想，坦率的講這是不可能的。在進程調(diào)度這件事情上為何不能根據(jù)實實在在確定的東西來調(diào)度呢？一個進程的靜態(tài)優(yōu)先級已經(jīng)完成的說明了其調(diào)度需求了，這就足夠了，不需要猜測進程對交互性的需求，只要維持公平就OK了，而所謂的公平就是進程獲取和其靜態(tài)優(yōu)先級匹配的CPU執(zhí)行時間。在這樣的思想指導(dǎo)下，Con Kolivas提出了RSDL（Rotating Staircase Deadline）調(diào)度器。

3、RSDL調(diào)度器

RSDL調(diào)度器仍然沿用了O（1）調(diào)度的數(shù)據(jù)結(jié)構(gòu)和軟件結(jié)構(gòu)，當然刪除了那些令人毛骨悚然的評估進程交互指數(shù)的代碼。我們這一小節(jié)不可能詳細描述RSDL算法，不過只要講清楚Rotating、Staircase和Deadline這三個基本概念，大家就應(yīng)該對RSDL有基本的了解了。

首先看Staircase概念，它更詳細表述應(yīng)該是priority staircase，即在進程調(diào)度過程中，其優(yōu)先級會象下樓梯那樣一點點的降低。在傳統(tǒng)的調(diào)度概念中，一個進程有一個和其靜態(tài)優(yōu)先級相匹配的時間片，在RSDL中，同樣也存在這樣的時間片，但是時間片是散布在很多優(yōu)先級中。例如如果一個進程的優(yōu)先級是120，那么整個時間片散布在120～139的優(yōu)先級中，在一個調(diào)度周期，進程開始是掛入120的優(yōu)先級隊列，并在其上運行6ms（這是一個可調(diào)參數(shù)，我們假設(shè)每個優(yōu)先級的時間配額是6ms），一旦在120級別的時間配額使用完畢之后，該進程會轉(zhuǎn)入121的隊列中（優(yōu)先級降低一個level），發(fā)生一次Rotating，更準確的說是Priority minor rotating。之后，該進程沿階而下，直到139的優(yōu)先級，在這個優(yōu)先級上如果耗盡了6ms的時間片，這時候，該進程所有的時間片就都耗盡了，就會被掛入到expired隊列中去等待下一個調(diào)度周期。這次rotating被稱為major rotating。當然，這時候該進程會掛入其靜態(tài)優(yōu)先級對應(yīng)的expired隊列，即一切又回到了調(diào)度的起點。

Deadline是指在RSDL算法中，任何一個進程可以準確的預(yù)估其調(diào)度延遲。一個簡單的例子，假設(shè)runqueue中有兩個task，靜態(tài)優(yōu)先級分別是130的A進程和139的B進程。對于A進程，只有在進程沿著優(yōu)先級樓梯從130走到139的時候，B進程才有機會執(zhí)行，其調(diào)度延遲是9 x 6ms ＝ 54ms。

多么簡潔的算法，只需要維持公平，沒有對進程睡眠/運行時間的統(tǒng)計，沒有對用戶交互指數(shù)的計算，沒有那些奇奇怪怪的常數(shù)……調(diào)度，就是這么簡單。

六、CFS調(diào)度器

Con Kolivas的RSDL調(diào)度器始終沒有能夠進入kernel mainline，取而代之的是同樣基于公平調(diào)度思想的CFS調(diào)度器，在CFS調(diào)度器并入主線的同時，仍然提供了模塊化的設(shè)計，為RSDL或者其他的調(diào)度器可以進入內(nèi)核提供了方便。然而Con Kolivas帶著對內(nèi)核開發(fā)模式的不滿永遠的退出了社區(qū)，正所謂有人的地方就有江湖，其中的是非留給后人評說吧。

CFS的設(shè)計理念就是一句話：在真實的硬件上實現(xiàn)理想的、精準、完全公平的多任務(wù)調(diào)度。當然，這樣的調(diào)度器不存在，在實際設(shè)計和實現(xiàn)的時候還是需要做一些折衷。其實CFS調(diào)度器的所有的設(shè)計思想在上一章都已經(jīng)非常明晰，本章我們唯一需要描述的是Ingo Molnar如何把完全公平調(diào)度的理想照進現(xiàn)實。

1、模塊化思想的引入

從2.6.23內(nèi)核開始，調(diào)度器采用了模塊化設(shè)計的思想，從而把進程調(diào)度的軟件分成了兩個層次，一個是core scheduler layer，另外一個是specific scheduler layer：

從功能層面上看，進程調(diào)度仍然分成兩個部分，第一個部分是通過負載均衡模塊將各個runnable task根據(jù)負載情況平均分配到各個CPU runqueue上去。第二部分的功能是在各個CPU的Main scheduler和Tick scheduler的驅(qū)動下進行單個CPU上的調(diào)度。調(diào)度器處理的task各不相同，有RT task，有normal task，有Deal line task，但是無論哪一種task，它們都有共同的邏輯，這部分被抽象成Core scheduler layer，同時各種特定類型的調(diào)度器定義自己的sched_class，并以鏈表的形式加入到系統(tǒng)中。這樣的模塊化設(shè)計可以方便用戶根據(jù)自己的場景定義specific scheduler，而不需要改動Core scheduler layer的邏輯。

2、關(guān)于公平

和RSDL調(diào)度器一樣，CFS調(diào)度器追求的公平是CPU資源分配的公平，即CPU的運算資源被精準的平均分配給在其上運行的task。例如：如果有2個靜態(tài)優(yōu)先級一樣的task運行在某一個CPU上，那么每一個task都消耗50％的CPU計算資源。如果靜態(tài)優(yōu)先級不一樣，那么，CPU資源是根據(jù)其靜態(tài)優(yōu)先級來具體分配。具體如何根據(jù)優(yōu)先級來分配CPU資源呢？這里就需要引入一個load weight的概念。

在CFS中，我們是通過一個常量數(shù)組（sched_prio_to_weight）可以把進程靜態(tài)優(yōu)先級映射成進程權(quán)重，而所謂的權(quán)重就是進程應(yīng)該占有cpu資源的比重。例如：系統(tǒng)中有3個runnable thread A、B和C，權(quán)重分別是a、b、c，那么A thread應(yīng)該分配到的CPU資源是a/(a+b+c)。因此CFS調(diào)度器的公平就是保證所有的可運行狀態(tài)的進程按照權(quán)重分配其CPU資源。

3、時間粒度

CPU資源分配是一個抽象的概念，最終在實現(xiàn)調(diào)度器的時候，我們需要把它具體化。一個最簡單的方法就是把CPU資源的分配變成CPU時間片的分配?？吹健皶r間片”這個術(shù)語，你可能本能的覺得CFS和O（1）也沒有什么不同，不都是分配時間片嗎？其實不然，Linux內(nèi)核的CFS調(diào)度器已經(jīng)摒棄了傳統(tǒng)的固定時間片的概念了。O（1）調(diào)度器會為每一個進程分配一個缺省的時間片，當進程使用完自己的時間片之后就會被掛入expire隊列，當系統(tǒng)中的所有進程都耗光了自己的時間片，那么一切從來，所有的進程又恢復(fù)了自己的時間片，進入active隊列。CFS調(diào)度器沒有傳統(tǒng)的靜態(tài)時間片的概念，她的時間片是動態(tài)的，和當前CPU的可運行狀態(tài)的進程以及它們的優(yōu)先級相關(guān)，因此CFS調(diào)度器中，時間片是動態(tài)變化的。

對于理想的完全公平調(diào)度算法，無論觀察的時間段多么短，CPU的時間片都是公平分配的。以100ms的粒度來觀察，那么兩個可運行狀態(tài)的進程A和B（靜態(tài)優(yōu)先級一樣）各分50ms。當然，也不是一定是A執(zhí)行50ms，切換到B，然后再執(zhí)行50ms，在觀察過程中，A和B可能切換了很多次，但是A進程總共占用CPU的時間和就是50ms，B進程亦然。如果用1ms的粒度來觀察呢？是否A和B個運行500us？如果繼續(xù)縮減觀察時間，在一個微秒的時間段觀察呢？顯然，不太可能每個進程運行500ns，如果那樣的話，CPU的時間大量的消耗在了進程切換上，真正做事情的CPU時間變得越來越少了。因此，CFS調(diào)度器是有一個時間粒度的定義，我們稱之調(diào)度周期。也就是說，在一個調(diào)度周期內(nèi)，CFS調(diào)度器可以保證所有的可運行狀態(tài)的進程平均分配CPU時間。下一小節(jié)我們會詳細描述調(diào)度周期的概念。

4、如何保證有界的調(diào)度延遲？

傳統(tǒng)的調(diào)度器無法保證調(diào)度延遲，為了說明這個問題我們設(shè)想這樣一個場景：CPU runqueue中有兩個nice value等于0的runnable進程A和B，傳統(tǒng)調(diào)度器會為每一個進程分配一個固定的時間片100ms，這時候A先運行，直到100ms的時間片耗盡，然后B運行。這兩個進程會交替運行，調(diào)度延遲就是100ms。隨著系統(tǒng)負荷的加重，例如又有兩個兩個nice value等于0的runnable進程C和D掛入runqueue，這時候，A、B、C、D交替運行，調(diào)度延遲就是300ms。因此，傳統(tǒng)調(diào)度器的調(diào)度延遲是和系統(tǒng)負載相關(guān)的，當系統(tǒng)負載增加的時候，用戶更容易觀察到卡頓現(xiàn)象。

CFS調(diào)度器設(shè)計之初就確定了調(diào)度延遲的參數(shù)，我們稱之targeted latency，這個概念類似傳統(tǒng)調(diào)度器中的調(diào)度周期的概念，只不過在過去，一個調(diào)度周期中的時間片被固定分配給了runnable的進程，而在CFS中，調(diào)度器會不斷的檢查在一個targeted latency中，公平性是否得到了保證。下面的代碼說明了targeted latency的計算過程：

當runqueue中的runnable進程的數(shù)目小于sched_nr_latency（8個）的時候，targeted latency就是sysctl_sched_latency（6ms），當runqueue中的runnable進程的數(shù)目大于等于sched_nr_latency的時候，targeted latency等于runnable進程數(shù)目乘以sysctl_sched_min_granularity（0.75ms）。顯然sysctl_sched_min_granularity這個參數(shù)就是一段一個進程被調(diào)度執(zhí)行，它需要至少執(zhí)行的時間片大小，設(shè)立這個參數(shù)是為了防止overscheduling而產(chǎn)生的性能下降。

CFS調(diào)度器保證了在一個targeted latency中，所有的runnable進程都會至少執(zhí)行一次，從而保證了有界的、可預(yù)測的調(diào)度延遲。

5、為何引入虛擬時間？

雖然Con Kolivas提出了精采絕倫的設(shè)計思想，但是在具體實現(xiàn)的時候相對保守。CFS調(diào)度器則不然，它采用了相對激進的方法，把runqueue中管理task的優(yōu)先級鏈表變成了紅黑樹結(jié)構(gòu)。有了這樣一顆runnable進程的紅黑樹，在插入操作的時候如何確定進程在紅黑樹中的位置？也就是說這棵樹的“key”是什么？

CFS的紅黑樹使用vruntime（virtual runtime）作為key，為了理解vruntime，這里需要引入一個虛擬時間軸的概念。在上一章中，我們已經(jīng)清楚的表述了公平的含義：按照進程的靜態(tài)優(yōu)先級來分配CPU資源，當然，CPU資源也就是CPU的時間片，因此在物理世界中，公平就是分配和靜態(tài)優(yōu)先級匹配的CPU時間片。但是紅黑樹需要一個單一數(shù)軸上的量進行比對，而這里有兩個度量因素：靜態(tài)優(yōu)先級和物理時間片，因此我們需要把它們映射到一個虛擬的時間軸上，屏蔽掉靜態(tài)優(yōu)先級的影響，具體的計算公式如下：

Virtual runtime ＝ （physical runtime） X （nice value 0的權(quán)重）/進程的權(quán)重

通過上面的公式，我們構(gòu)造了一個虛擬的世界。二維的（load weight，physical runtime）物理世界變成了一維的virtual runtime的虛擬世界。在這個虛擬的世界中，各個進程的vruntime可以比較大小，以便確定其在紅黑樹中的位置，而CFS調(diào)度器的公平也就是維護虛擬世界vruntime的公平，即各個進程的vruntime是相等的。

根據(jù)上面的公式，我們可以看出：實際上對于靜態(tài)優(yōu)先級是120（即nice value等于0）的進程，其物理時間軸等于虛擬時間軸，而其他的靜態(tài)優(yōu)先級的虛擬時間都是根據(jù)其權(quán)重和nice 0的權(quán)重進行尺度縮放。對于更高優(yōu)先級的進程，其虛擬時間軸過的比較慢，而對于優(yōu)先級比較低的進程，其虛擬時間軸過的比較快。

我們可以舉一個簡單的例子來描述虛擬世界的公平性：例如在時間點a到b之間（虛擬時間軸），如果有兩個可運行狀態(tài)的進程A和B，那么從a到b這個時間段上去觀察，CPU的時間是平均分配到每個一個進程上，也就是說A和B進程各自運行了（b-a）/2的時間，也就是各占50％的時間片。在b時間點，一個新的可運行狀態(tài)的進程C產(chǎn)生了，直到c時間點。那么從b到c這個時間段上去觀察，進程A、B和進程C都是執(zhí)行了（c-b）/3的時間，也就是各占1/3的CPU資源。再強調(diào)一次，上面說的時間都是虛擬時間。

6、如何計算virtual runtime

想要計算時間我們必須有類似手表這樣的計時工具，對于CFS調(diào)度器，這個“手表”保存在runqueue中（clock和clock_task成員）。Runqueue戴兩塊表，一塊記錄實際的物理時間，另外一塊則是記錄執(zhí)行task的時間（clock_task）。之所以有clock_task是為了更準確的記錄進程執(zhí)行時間。實際上一個task執(zhí)行過程中不免會遇到一些異步事件，例如中斷。這時候，進程的執(zhí)行被打斷從而轉(zhuǎn)入到對異步事件的處理過程。如果把這些時間也算入該進程的執(zhí)行時間會有失偏頗，因此clock_task會把這些異步事件的處理時間去掉，只有在真正執(zhí)行任務(wù)的時候，clock_task的counter才會不斷累加計時。

有了clock進程計時變得比較簡單了，當進程進入執(zhí)行狀態(tài)的時候，看一下clock_task這塊“手表”，記錄數(shù)值為A。在需要統(tǒng)計運行時間的時候，再次看一下clock_task這塊“手表”，記錄數(shù)值為B。B-A就是該進程已經(jīng)運行的物理時間。當然，CFS關(guān)心的是虛擬時間，這時候還需要通過calc_delta_fair函數(shù)將這個物理時間轉(zhuǎn)換成虛擬時間，然后累積的該進程的virtual runtime中（sched_entity中的vruntime），而這個vruntime就是紅黑樹的key。

7、CFS調(diào)度器的運作

對于CFS調(diào)度器，沒有固定分配時間片的概念，只有一個固定權(quán)重的概念，是根據(jù)進程靜態(tài)優(yōu)先級計算出來的。CFS調(diào)度器一旦選擇了一個進程進入執(zhí)行狀態(tài)，會立刻開啟對其virtual runtime的跟蹤過程，并且在tick到來時會更新這個virtual runtime。有了這個virtual runtime信息，調(diào)度器就可以不斷的檢查目前系統(tǒng)的公平性（而不是檢查是否時間片用完），具體的方法是：根據(jù)當前系統(tǒng)的情況計算targeted latency（調(diào)度周期），在這個調(diào)度周期中計算當前進程應(yīng)該獲得的時間片（物理時間），然后計算當前進程已經(jīng)累積執(zhí)行的物理時間，如果大于當前應(yīng)該獲得的時間片，那么更新本進程的vruntime并標記need resched flag，并在最近的一個調(diào)度點發(fā)起調(diào)度。

在進行進程調(diào)度時候，調(diào)度器需要選擇下一個占用CPU資源的那個next thread。對于CFS而言，其算法就是從紅黑樹中找到left most的那個task并調(diào)度其運行。這時候，失去CPU執(zhí)行權(quán)的那個task會被重新插入紅黑樹，其在紅黑樹中的位置是由task的vruntime值決定的。