一、前言

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

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

二、任務調度器概述

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

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

1、對于time-sharing的進程，調度器必須是公平的

2、快速的進程響應時間

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

4、功耗要小

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

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

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

三、2.4時代的O（n）調度器

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

本章所有的描述都是基于上面的軟件結構圖。

1、進程描述符

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

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

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

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

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

2、如何組織task

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

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

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）。然而實際上調度器在進行調度的時候，并沒有采用靜態(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)先于普通進程的調度。而對于普通進程，動態(tài)優(yōu)先級的計算稍微有些復雜，我們可以摘錄部分代碼如下：

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

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

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

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

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

3、調度時機

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

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

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

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

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

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

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

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

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

4、進程喚醒的處理

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

當然，也不是說sync wakeup就一定不調度，假設waker在CPU A上喚醒wakee，而根據(jù)wakee進程的cpus_allowed成員發(fā)現(xiàn)它根本不能在CPU A上調度執(zhí)行，那么管他sync不sync，這時候都需要去嘗試調度（調用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標志，并在調度點到來的時候調用schedule函數(shù)進行調度。

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

（1） 優(yōu)先調度wakee去系統(tǒng)其他空閑的CPU上執(zhí)行，如果wakee上次運行的CPU恰好處于idle狀態(tài)的時候，可以考慮優(yōu)先將wakee調度到那個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，那么沒有必要調度，runqueue中的wakee需要耐心等待下一次機會。如果wakee的動態(tài)優(yōu)先級高于找到的那個動態(tài)優(yōu)先級最低的task，那么標記其need_resched標志。如果不是搶占waker，那么我們還需要發(fā)送IPI去觸發(fā)該CPU的調度。

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

5、主調度器算法

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

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

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

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

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

6、時間片處理

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

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

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

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

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

當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的時候，調度器剝奪其執(zhí)行的權力，從而從而引發(fā)一次調度，選擇其他時間片不是0的進程運行，直到runqueue中的所有進程時間片耗盡，又會重新賦值，開始一個新的周期。調度器就這樣周而復始，推動整個系統(tǒng)的運作。

四、2.6時代的O（1）調度器

1、Why O（1）調度器

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

（1）算法復雜度問題

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

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

（2）SMP擴展性問題

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

（3）CPU空轉問題

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

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

（4）task bouncing issue

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

（5）RT進程調度性能問題

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

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

（6）交互式普通進程的調度延遲問題

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

（7）時間片粒度問題。

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

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

2、O（1）調度器的軟件功能劃分

下圖是一個O（1）調度器的軟件框架：

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

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

通過上面的軟件結構劃分可以解決O（n）調度的SMP擴展性問題和CPU空轉問題。此外，好的復雜均衡算法也可以解決O（n）調度器的task bouncing 問題。

3、O（1）調度器的runqueue結構

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

在調度器中，runqueue是一個很重要的數(shù)據(jù)結構，它最重要的作用是管理那些處于可運行狀態(tài)的進程。O（1）調度器引入了優(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）調度器中，RT進程和普通進程被區(qū)分開了，普通進程根本不會影響RT進程的調度。

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

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

4、核心調度算法

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

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

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

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

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）調度器的調度算法又統(tǒng)一了，都是根據(jù)動態(tài)優(yōu)先級進行調度。

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)先級最低），分別對應nice value的-20 ～ 19。

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

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

6、時間片處理

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

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

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

6、識別用戶交互式進程

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

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

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

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

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

五、公平調度思想的引入

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

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

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

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

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

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

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

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

3、RSDL調度器

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

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

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

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

六、CFS調度器

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

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

1、模塊化思想的引入

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

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

2、關于公平

和RSDL調度器一樣，CFS調度器追求的公平是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)先級映射成進程權重，而所謂的權重就是進程應該占有cpu資源的比重。例如：系統(tǒng)中有3個runnable thread A、B和C，權重分別是a、b、c，那么A thread應該分配到的CPU資源是a/(a+b+c)。因此CFS調度器的公平就是保證所有的可運行狀態(tài)的進程按照權重分配其CPU資源。

3、時間粒度

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

對于理想的完全公平調度算法，無論觀察的時間段多么短，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調度器是有一個時間粒度的定義，我們稱之調度周期。也就是說，在一個調度周期內(nèi)，CFS調度器可以保證所有的可運行狀態(tài)的進程平均分配CPU時間。下一小節(jié)我們會詳細描述調度周期的概念。

4、如何保證有界的調度延遲？

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

CFS調度器設計之初就確定了調度延遲的參數(shù)，我們稱之targeted latency，這個概念類似傳統(tǒng)調度器中的調度周期的概念，只不過在過去，一個調度周期中的時間片被固定分配給了runnable的進程，而在CFS中，調度器會不斷的檢查在一個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ù)就是一段一個進程被調度執(zhí)行，它需要至少執(zhí)行的時間片大小，設立這個參數(shù)是為了防止overscheduling而產(chǎn)生的性能下降。

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

5、為何引入虛擬時間？

雖然Con Kolivas提出了精采絕倫的設計思想，但是在具體實現(xiàn)的時候相對保守。CFS調度器則不然，它采用了相對激進的方法，把runqueue中管理task的優(yō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的權重）/進程的權重

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

根據(jù)上面的公式，我們可以看出：實際上對于靜態(tài)優(yōu)先級是120（即nice value等于0）的進程，其物理時間軸等于虛擬時間軸，而其他的靜態(tài)優(yōu)先級的虛擬時間都是根據(jù)其權重和nice 0的權重進行尺度縮放。對于更高優(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資源。再強調一次，上面說的時間都是虛擬時間。

6、如何計算virtual runtime

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

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

7、CFS調度器的運作

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

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