準備知識

想深入理解操作系統的進程調度，需要先獲得一些準備知識，這樣后面就不懵圈啦：

• 調度究竟是個啥
• 操作系統有哪幾種？常用的是哪種？
• 進程的分類和優先級是怎么回事
• 搶占式調度和非搶占式調度有啥區別
• 如何設計一個可用的調度器

調度的概念

科技源自生活，調度系統絕對不是計算機領域的專利，現實生活中調度無處不在：

• 連鎖超市某些熱門商品短缺，就需要在全城范圍內考慮人口密度、超市規模、商品缺口等多個因素，進行資源調配
• 鐵路部門為了應對春運會在熱門線路增加列車來緩解運輸壓力，春運結束則恢復正常

“

調度是為了解決資源和需求之間的不匹配問題，現實往往是資源少&需求多，計算機領域也是如此。

在操作系統中CPU資源是有限的，需要使用CPU的進程數量是不確定的，并且大部分情況下進程數量遠大于CPU數量，如何解決不匹配問題就是進程調度核心：

操作系統分類

操作系統的種類非常多，本身上是硬件層和應用層之間的中間層，對上與應用程序進行交互，對下實現硬件資源的管理。

• 批處理系統( Batch Processing System )

“

批處理是指用戶將一批作業提交給操作系統后就不再干預，由操作系統控制它們自動運行，這種采用批量處理作業任務的操作系統稱為批處理操作系統，不具有交互性，用戶無法干預任務的運行。

• 實時系統( Real-Time System)

“

實時系統最大的特點在于計算的正確性不僅取決于程序的邏輯正確性，也取決于結果產生的時間，如果系統的時間約束條件得不到滿足，將會發生系統出錯，強實時系統一般應用在航空航天、導彈導航制導、核工業等領域。

• 分時系統( Time Sharing System)

“

分時系統將計算機系統資源（比如CPU）進行時間上的分割，每個時間段稱為一個時間片，每個用戶依次輪流使用時間片，由于時間間隔很短，每個用戶的感覺就像他獨占計算機一樣，從而有效增加資源的使用率，提高用戶交互體驗。

Linux屬于分時系統，是互聯網服務器的主流操作系統，重點研究它就行！

進程分類

根據進程運行時的狀態，可以分為：

• I/O密集型( IO-bound )

“

在進程占用CPU期間頻繁有IO操作，出現IO阻塞等待情況，比如負責監聽socket的進程，真正使用CPU進行計算的時間并不多。

• CPU密集型( CPU-bound)

“

在進程占用CPU期間基本都在進行計算，很少進行IO操作，期間對CPU的真實使用率很高。

進程調度器需要根據進程是IO密集型還是CPU密集型會采用不同的策略。

在調度器中往往需要對IO密集型進程進行獎勵來提高其調度優先級，對CPU密集型進程進行懲罰降低其調度優先級。

對進程的獎懲策略是調度器的一項核心工作，希望大家務必理解：

“

交互進程往往伴隨較多的IO操作，同時也是響應時間敏感的任務，鼠標點一下半天沒響應，想想就很糟糕，因此屬于高優先級進程。

“

非交互進程往往是純CPU計算，用戶是無感知的，所以對響應時間的要求并沒有那么高，屬于低優先級進程。

進程優先級

根據進程的重要性，可以分為：

• 實時進程(Real-Time Process)
• 普通進程(Normal Process)

“

在操作系統中有很多進程，實時進程是相對重要的，需要保證其CPU占用優先級，普通進程并不需要額外照顧。

實時進程和普通進程的進程優先級不同，調度器都會根據優先級來確定進程的CPU優先權和運行時間。

在Linux中影響優先級的兩個因素：Nice謙讓值和Priority權重值。

• 實時進程PR值范圍是0~99，數值越大被調度優先級越高
• 普通進程PR值范圍是100~139，數值越小被調度優先級越高
• Nice值范圍是-20~19，并不是優先級但影響PR值，一般作用在普通進程上

PR值由內核來確定，用戶可以修改Nice謙讓值，進而干預PR值：

• PR_new = PR_old + Nice

nice值也被稱為謙讓值，數值越大越謙讓，會哭的孩子有奶吃，總謙讓優先級肯定低了：

• 如果nice值是0，即用戶層認可內核的決定不額外干預，聽天由命
• 如果nice為負值表示毫不謙讓，即用戶層干預來提升被調度的優先級，把機會留給自己
• 如果nice為正值表示予以謙讓，即用戶層干預降低被調度的優先級，把機會留給別人

非搶占和搶占式

根據進程任務在占用CPU時，使用權是否會被奪取分為：

• 協作式調度( Cooperative Scheduling)

“

進程任務一旦占用CPU只有當任務完成或者因為某些原因主動釋放CPU，除上述兩種情況外不能被其他進程奪走

• 搶占式調度( Preemptive Scheduling)

“

進程任務占用CPU期間可以被其他進程奪走，具體由操作系統調度器決定下一個占用CPU的進程

Linux采用搶占式調度，其可以提高CPU利用率、降低進程的響應時間等，同時也增加了切換進程時的開銷，各有利弊。

調度器設計思路

設計目標

有兩個指標需要重視：

• 周轉時間( Cycling Time )

“

進程任務從開始排隊等待獲取CPU資源直到任務完成的時間差，就像超市排隊結賬時從開始排隊到結算完成離開的時間差。

• 響應時間Response Time

“

進程任務從開始排隊等待獲取CPU資源直到開始使用CPU的時間差，就像超市排隊結賬時從開始排隊到輪到結算的時間差。

綜合來說：

• 實時進程要更優先被調度，普通進程的優先級一定低于實時進程
• IO密集型進程要調度頻繁一些，IO密集型要少分配時間片，少吃多餐
• CPU密集型可以稍微懲罰，CPU密集型可以分配長一些的時間片，少餐多吃

只有做到這幾點，調度器才可能在周轉時間和響應時間上得到一個良好的表現。

設計實現

要實現一個調度器，主要包括兩個核心部分：

• 算法設計
• 工程實現

算法更多是一種思想，調度器基于某種調度算法進行工程化實現，捋清楚二者的關系對于后續內容的理解將大有裨益。

本章重點

• 調度是為了解決資源和需求之間的不匹配問題，現實生活和計算機領域都非常普遍
• 操作系統可以分為：批處理系統、實時系統、分時系統三大類，分時系統是研究重點
• 進程可以分為兩大類：IO密集型和CPU密集型，調度時采用不同的策略
• 進程可以分為普通進程和實時進程，實時進程優先級永遠高于普通進程
• 進程調度模型可以分為兩大類：協作式調度和搶占式調度，搶占式是主流
• 要設計一個進程調度器需要有設計目標后選擇合適的調度算法進行工程化實現

調度算法

調度算法也經歷了從簡單到復雜的演進，到目前為止也沒有哪種調度算法是萬能的，拋開場景來評判調度算法優劣并不明智。

以下介紹的主要是調度算法的思想，工程上使用的調度算法往往是其中一種或者幾種的變形，更加復雜。

先來先服務FCFS

先來先服務First Come First Service可以說是最早最簡單的調度算法，哪個進程先來就先讓它占用CPU，釋放CPU之后第二個進程再使用，依次類推。

• 場景一
  假如有ABC三個進程依次進入等候使用CPU資源的隊列FIFO，A進程占用CPU運行5ms，B進程10ms，C進程25ms，根據FCFS算法的規則，可知：
  • 周轉時間 A-5ms B-15ms C-40ms 平均(5+15+40)/3=20ms
  • 響應時間 A-0ms B-5ms C-15ms 平均(0+5+15)/3=6.67ms

• 場景二
  假如有ABC三個進程依次進入等候使用CPU資源的隊列FIFO，A進程占用CPU運行100ms，B進程10ms，C進程25ms，根據FCFS算法的規則，可知：
  • 周轉時間 A-100ms B-110ms C-135ms 平均(100+110+135)/3=115ms
  • 響應時間 A-0ms B-100ms C-110ms 平均(0+100+110)/3=70ms綜上，在場景二中A進程的運行時間長達100ms，這樣拉升了B和C的周轉時間5倍多。

在FCFS中優先被調度的進程如果耗時很長，后續進程都必須要等待這個大CPU消耗的進程，最終導致周轉時間直線拉升，也就是護航效應。

最短任務優先SJF

最短任務優先Shortest Job First的思想是當多個進程同時出現時，優先安排執行時間最短的任務，然后是執行時間次短，以此類推。

SJF可以解決FCFS中同時到達進程執行時間不一致帶來的護航效應問題：

• 場景一
  假如有ABC三個進程同時進入等候使用CPU資源的隊列FIFO，A進程占用CPU運行100ms，B進程10ms，C進程25ms，根據SJF算法的規則，可知：
  • 進程執行順序是B->C->A
  • 周轉時間 A-135ms B-10ms C-35ms 平均(135+10+35)/3=60ms
  • 響應時間 A-35ms B-0ms C-10ms 平均(35+0+10)/3=15ms

相比于FCFS可能的執行順序是A->C->B來說，周轉時間和響應時間都得到很大的改善。

SJF的算法思想有些理想化，但并非一無是處，升級改進下也有用武之地：

• 大部分場景下進程都是有先后順序進行等待隊列的，同時出現的概率并不高
• 進程執行時間的長短并不能預測

搶占式最短任務優先PSJF

SJF算法最具啟發的地方在于優先調度執行時間短的任務來解決護航效應，但是該算法屬于非搶占式調度，對于先后到達且執行時間差別較大的場景也束手無策。

當向SJF算法增加搶占調度時能力就大大增強了，這就是PSJF( Preemptive Shortest Job First )算法。

• 場景一
  假如有ABC三個進程間隔20ms(BC同時且晚于A)依次進入等候使用CPU資源的隊列FIFO，A進程占用CPU運行100ms，B進程10ms，C進程25ms，根據PSJF算法的規則，可知：
  • A先被執行20ms，再執行B10ms，再執行C25ms，再執行A80ms
  • 周轉時間 A-135ms B-10ms C-35ms 平均(135+10+35)/3=60ms
  • 響應時間 A-0ms B-0ms C-10ms 平均(0+0+10)/3=3.3ms

搶占機制有效削弱了護航效應，周轉時間和響應時間都降低了許多，但是還遠不夠完美。

PSJF算法對于進程A來說卻不友好，進程A在被搶占之后只能等待B和C運行完成后，此時如果再來短任務DEF都會搶占A，就會產生饑餓效應。

PSJF算法是基于對任務運行時間長短來進行調度的，但在調度前任務的運行時間是未知的，因此首要問題是通過歷史數據來預測運行時間。

時間片輪轉RR

時間片輪轉RR(Round-Robin)將CPU執行時間按照時鐘脈沖進行切割稱為時間切片Time-Slice，一個時間切片是時鐘周期的數倍，時鐘周期和CPU的主頻呈倒數關系。

“

比如 CPU的主頻是1000hz，則時鐘周期TimeClick=1ms，Time Slice = n*Time Click，時間切片可以是2ms/4ms/10ms等。

在一個時間片內CPU分配給一個進程，時間片耗盡則調度選擇下一個進程，如此循環。

進程往往需要多個循環獲取多次時間片才能完成任務，因此需要操作系統記錄上一次的數據，等進程下一次被分配時間片時再拿出來，這就是傳說中的上下文Context。

進程上下文被存儲和拿出的過程被稱為上下文切換Context Switch，上下文切換是比較消耗資源的，因此時間片的劃分就顯得很重要：

• 時間片太短，上下文頻繁切換，有效執行時間變少
• 時間片太大，無法保證多個進程可以雨露均沾，響應時間較大

RR算法在保障了多個進程都能占用CPU，屬于公平策略的一種，但是RR算法將原本可以一次運行完的任務切分成多個部分來完成，從而拉升了周轉時間。

RR算法也非銀彈，但是響應時間和公平性得到了有效保障，是個非常有意義的算法模型。

多級反饋隊列MLFQ

多級反饋隊列( Multi-Level Feedback Queue )嘗試去同時解決響應時間和周轉時間兩個問題，具體做法：

• 設置了多個任務隊列，每個隊列對應的優先級不同，隊列內部的優先級相同
• 優先分配CPU給高優先級的任務，同優先級隊列中的任務采用RR輪詢機制
• 通過對任務運行狀態的追蹤來調整優先級，也就是所謂的Feedback反饋機制
  • 任務在運行期間有較多IO請求和等待，預測為交互進程，優先級保持或提升
  • 任務在運行期間一直進行CPU計算，預測為非交互進程，優先級保持或下降
• 最初將所以任務都設置為高優先級隊列，隨著后續的運行狀態再進行調整
  • 運行期間有IO操作則保持優先級
  • 運行期間無IO操作則把任務放到低一級的隊列中
• 不同隊列分配不同的時間片
  • 高優先級隊列往往是IO型任務，配置較小的時間片來保障響應時間
  • 低優先級隊列往往是CPU型任務，配置較長時間片來保障任務一直運行

上述是MLFQ算法的基本規則，在實際應用中仍然會有一些問題：

• 饑餓問題
  • CPU密集型的任務隨著時間推移優先級會越來越低，在IO型進程多的場景下很容易出現饑餓問題，一直無法得到調度
  • 任務是CPU密集型還是IO密集型可能是動態變化的，低優先級隊列中的IO型任務的響應時間被拉升，調度頻率下降
• 作弊問題
  • 基于MLFQ對IO型任務的偏愛，用戶可能為CPU密集型任務編寫無用的IO空操作，從而人為提升任務優先級，相當于作弊

針對上述問題MLFQ還需增加幾個補丁：

• 周期性提升所有任務的優先級到最高，避免饑餓問題
• 調度程序記錄任務在某個層級隊列中消耗的時間片，如果達到某個比例，無論期間是否有IO操作都降低任務的優先級，通過計時來確定真正的IO型任務

MLFQ的算法思想在1962年被提出，其作者也獲得了圖靈獎，可謂是影響深遠。

在樸素MLFQ算法基礎上出現一些變種，通過工程實現和經驗配置最終被使用到操作系統中，成為真正的工業級進程調度器。

Linux進程調度器

Linux的進程調度器是不斷演進的，先后出現過三種里程碑式的調度器：

• O(n)調度器 內核版本 2.4-2.6
• O(1) 調度器 內核版本 2.6.0-2.6.22
• CFS調度器 內核版本 2.6.23-至今

O(n)屬于早期版本在pick next過程是需要遍歷進程任務隊列來實現，O(1)版本性能上有較大提升可以實現O(1)復雜度的pick next過程。

CFS調度器可以說是一種O(logn)調度器，但是其算法思想相比前兩種有些不同，并且設計實現上也更加輕量，一直被Linux內核沿用至今。

調度器設計核心

要理解這些復雜的調度器設計，我們必須要有一個核心主線，再去理解精髓。

調度器需要解決的關鍵問題：

• 采用何種數據結構來組織進程以及如何實現pick next
• 如何根據進程優先級來確定進程運行時間
• 如何判斷進程類型
  • 判斷進程的交互性質，是否為IO密集
  • 獎勵IO密集型&懲罰CPU密集型
  • 實時進程高優&普通進程低優
• 如何確定進程的動態優先級
  • 影響因素：靜態優先級、nice值、IO密集型和CPU密集型產生的獎懲

事實上，調度器在設計實現上考慮的問題還有很多，篇幅所限只列舉幾個公共問題。

O(n) 調度器

O(n)調度器采用一個全局隊列runqueue作為核心數據結構，具備以下特點：

• 多個cpu共享全局隊列，并非每個cpu有單獨的隊列
• 實時進程和普通進程混合且無序存放，尋找最合適進程需要遍歷
• 就緒進程將被添加到隊列，運行結束被刪除
• 全局隊列增刪進程任務時需要加鎖
• 進程被掛到不同CPU運行，緩存利用率低

在Linux中進程使用task_struct結構體來表示，其中有個counter表示進程剩余的CPU時間片：

structtask_struct{
longcounter;
longnice;
unsignedlongpolicy;
intprocessor;
unsignedlongcpus_runnable,cpus_allowed;
}

counter值在調度周期開始時被賦值，隨著調度的進行遞減，直至counter=0表示無可用CPU時間，等待下一個調度周期。

O(n)調度器中調度權重是在goodness函數中完成計算的：

staticinlineintgoodness(structtask_struct*p,intthis_cpu,structmm_struct*this_mm)
{
intweight;
weight=-1;
/*進程可以設置調度策略為SCHED_YIELD即“禮讓”策略，這時候它的權值為-1,權值相當低*/
if(p->policy&SCHED_YIELD)
gotoout;

/*
*Non-RTprocess-normalcasefirst.
*/

/*對于調度策略為SCHED_OTHER的進程，沒有實時性要求，它的權值僅僅取決于
*時間片的剩余和它的nice值，數值上nice越小，則優先級越高，總的權值=時間片剩余+(20-nice)
**/
if(p->policy==SCHED_OTHER){
/*
*Givetheprocessafirst-approximationgoodnessvalue
*accordingtothenumberofclock-ticksithasleft.
*
*Don'tdoanyothercalculationsifthetimesliceis
*over..
*/
weight=p->counter;
if(!weight)
gotoout;

#ifdefCONFIG_SMP
/*Givealargishadvantagetothesameprocessor...*/
/*(thisisequivalenttopenalizingotherprocessors)*/
if(p->processor==this_cpu)
weight+=PROC_CHANGE_PENALTY;
#endif

/*..andaslightadvantagetothecurrentMM*/
if(p->mm==this_mm||!p->mm)
weight+=1;
weight+=20-p->nice;
gotoout;
}

/*
*對于實時進程，也就是SCHED_FIFO或者SCHED_RR調度策略，
*具有一個實時優先級，總的權值僅僅取決于該實時優先級，
*總的權值= 1000+實時優先級。
**/
weight=1000+p->rt_priority;
out:
returnweight;
}

從代碼可以看到：

• 當進程的剩余時間片Counter為0時，無論靜態優先級是多少都不會被選中
• 普通進程的優先級=剩余時間片Counter+20-nice
• 實時進程的優先級=1000+進程靜態優先級
• 實時進程的動態優先級遠大于普通進程，更容易被選中
• 剩余時間片counter越多說明進程IO較多，分配給它的沒用完，被調度的優先級需要高一些

#ifHZ
#defineTICK_SCALE(x)((x)>>2)
#elifHZ
#defineTICK_SCALE(x)((x)>>1)
#elifHZ
#defineTICK_SCALE(x)(x)
#elifHZ
#defineTICK_SCALE(x)((x)<
#else
#defineTICK_SCALE(x)((x)<
#endif

#defineNICE_TO_TICKS(nice)(TICK_SCALE(20-(nice))+1)

NICE_TO_TICKS是個宏函數，根據不同的調度頻率HZ有對應的TICK_SCALE宏定義，這樣就解決了不同優先級的進程的時間片分配問題。

O(n)調度器對實時進程和普通進程采用不同的調度策略：

• 實時進程采用的是SCHED_RR或者SCHED_FIFO，高級優先&同級輪轉或者順序執行
• 普通進程采用的是SCHED_OTHER
• 進程采用的策略在task_struct中policy體現

在runqueue中搜索下一個合適的進程是基于動態優先級來實現的，動態優先級最高的就是下一個被執行的進程。

O(n)調度器設計和實現上存在一些問題，但是其中的很多思想為后續調度器設計指明了方向，意義深遠。

O(1)調度器

O(n)調度器在linux內核中大約使用了4年，在Linux 2.6.0采納了Red Hat公司Ingo Molnar設計的O(1)調度算法，該調度算法的核心思想基于Corbato等人提出的多級反饋隊列算法。

O(1)調度器引入了多個隊列，并且增加了負載均衡機制，對新出現的進行任務分配到合適的cpu-runqueue中：

為了實現O(1)復雜度的pick-next算法，內核實現代碼量增加了一倍多，其有以下幾個特點：

• 實現了per-cpu-runqueue，每個CPU都有一個就緒進程任務隊列
• 引入活躍數組active和過期數組expire，分別存儲就緒進程和結束進程
• 采用全局優先級：實時進程0-99，普通進程100-139，數值越低優先級越高，更容易被調度
• 每個優先級對應一個鏈表，引入bitmap數組來記錄140個鏈表中的活躍任務情況
  任務隊列的數據結構：

structrunqueue{
spinlock_tlock;
unsignedlongnr_running;
unsignedlonglongnr_switches;
unsignedlongexpired_timestamp,nr_uninterruptible;
unsignedlonglongtimestamp_last_tick;
task_t*curr,*idle;
structmm_struct*prev_mm;
prio_array_t*active,*expired,arrays[2];
intbest_expired_prio;
atomic_tnr_iowait;
......
};

• active和expired是指向prio_array_t的結構體指針
• arrays是元素為prio_array_t的結構體數組

prio_array_t結構體的定義：

#defineBITMAP_SIZE((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
typedefstructprio_arrayprio_array_t;
structprio_array{
unsignedintnr_active;
unsignedlongbitmap[BITMAP_SIZE];
structlist_headqueue[MAX_PRIO];
};

O(1)調度器對pick-next的實現：

• 在runqueue結構中有active和expire兩個數組指針，active指向就緒進程的結構，從active-bitmap中尋找優先級最高且非空的數組元素，這個數組是元素是進程鏈表，找該鏈表中第1個進程即可。

idx=sched_find_first_bit(array->bitmap);
queue=array->queue+idx;
next=list_entry(queue->next,task_t,run_list);

• 當active的nr_active=0時表示沒有活躍任務，此時進行active和expire雙指針互換，速度很快。

array=rq->active;
if(unlikely(!array->nr_active)){
/*
*Switchtheactiveandexpiredarrays.
*/
rq->active=rq->expired;
rq->expired=array;
array=rq->active;
rq->expired_timestamp=0;
rq->best_expired_prio=MAX_PRIO;
}

O(1)和O(n)調度器確定進程優先級的方法不一樣，O(1)借助了sleep_avg變量記錄進程的睡眠時間，來識別IO密集型進程，計算bonus值來調整優先級：

#defineNICE_TO_PRIO(nice)(MAX_RT_PRIO+(nice)+20)
#defineNS_TO_JIFFIES(TIME)((TIME)/(1000000000/HZ))
#defineCURRENT_BONUS(p)
(NS_TO_JIFFIES((p)->sleep_avg)*MAX_BONUS/
MAX_SLEEP_AVG)

staticinteffective_prio(task_t*p)
{
intbonus,prio;

if(rt_task(p))
returnp->prio;

bonus=CURRENT_BONUS(p)-MAX_BONUS/2;

prio=p->static_prio-bonus;
if(prioif(prio>MAX_PRIO-1)
prio=MAX_PRIO-1;
returnprio;
}

O(1)調度器為了實現復雜場景IO密集型任務的識別，做了大量的工作仍然無法到達100%的準確，但不可否認O(1)調度器是一款非常優秀的產品。

CFS調度器

O(1)調度器本質上是MLFQ算法的思想，隨著時間的推移也暴露除了很多問題，主要集中在O(1)調度器對進程交互性的判斷上積重難返。

無論是O(n)還是O(1)都需要去根據進程的運行狀況判斷它屬于IO密集型還是CPU密集型，再做優先級獎勵和懲罰，這種推測本身就會有誤差，而且場景越復雜判斷難度越大。

是繼續優化進程交互性算法，還是另辟蹊徑呢？一直困擾著Linux社區的大神們。

Con Kolivas和RSDL調度器

在CFS出現之前，不得不提一位有態度&有實力的麻醉師Con Kolivas，同時也是linux內核開發者，他在進程調度領域有自己獨到的見解。

Con Kolivas針對O(1)調度器存在的維護和優化問題，提出了樓梯調度算法（Staircase Deadline Scheduler）和 基于公平策略RSDL調度器(The Rotating Staircase Deadline Schedule)，遺憾的是Linux之父并沒有采納RDSL調度器。

對此Con Kolivas感到很憤怒，離開了Linux內核開發社區，但是事實上從后面CFS調度器幾個版本的修訂來看，Con Kolivas的大方向是正確的，離開之后的Con Kolivas又開發了BFS(Brain Fuck Scheduler)來對抗CFS調度器。

“

沒錯，BFS調度器譯為腦殘調度器，可見Con Kolivas的憤怒和不滿。

Linux之父選擇了CFS調度器，它借鑒了Con Kolivas的樓梯調度算法和RSDL調度器的經驗，由匈牙利人Ingo Molnar所提出和實現，并在Linux kernel 2.6.23之后取代O(1)調度器，名震江湖。

CFS調度器

在2.6.23內核中引入scheduling class的概念，將調度器模塊化，系統中可以有多種調度器，使用不同策略調度不同類型的進程：

• DL Scheduler 采用sched_deadline策略
• RT Scheduler 采用sched_rr和sched_fifo策略
• CFS Scheduler 采用sched_normal和sched_batch策略
• IDEL Scheduler 采用sched_idle策略

這樣一來，CFS調度器就不關心實時進程了，專注于普通進程就可以了。

CFS( Completely Fair Scheduler )完全公平調度器，從實現思想上和之前的O(1)/O(n)很不一樣。

我的腦海里浮現了這幅漫畫，我想右邊的應該更好，按需分配&達成共贏。

這個世界怎么會有絕對的公平呢？為啥這個調度器敢說自己是完全公平呢？

這一切CFS是如何實現的呢？我們繼續看！

優先級和權重

O(1)和O(n)都將CPU資源劃分為時間片，采用了固定額度分配機制，在每個調度周期進程可使用的時間片是確定的，調度周期結束被重新分配。

CFS摒棄了固定時間片分配，采用動態時間片分配，本次調度中進程可占用的時間與進程總數、總CPU時間、進程權重等均有關系，每個調度周期的值都可能會不一樣。

CFS調度器從進程優先級出發，它建立了優先級prio和權重weight之間的映射關系，把優先級轉換為權重來參與后續的計算：

constintsched_prio_to_weight[40]={
/*-20*/88761,71755,56483,46273,36291,
/*-15*/29154,23254,18705,14949,11916,
/*-10*/9548,7620,6100,4904,3906,
/*-5*/3121,2501,1991,1586,1277,
/*0*/1024,820,655,526,423,
/*5*/335,272,215,172,137,
/*10*/110,87,70,56,45,
/*15*/36,29,23,18,15,
};

“

普通進程的優先級范圍是[100,139]，prio整體減小120就和代碼左邊的注釋對上了，也就是nice值的范圍[-20,19]，因此sched_prio=0相當于static_prio=120。

比如現有進程A sched_prio=0，進程B sched_prio=-5，通過sched_prio_to_weight的映射：

• 進程A weight=1024，進程B weight = 3121
• 進程A的CPU占比 = 1024/(1024+3121)= 24.7%
• 進程B的CPU占比 = 3121/(1024+3121) = 75.3%
• 假如CPU總時間是10ms，那么根據A占用2.47ms，B占用7.53ms

在CFS中引入sysctl_sched_latency(調度延遲)作為一個調度周期，真實的CPU時間表示為：

顯然這樣根據權重計算后的各個進程的運行時間是不等的，也就違背了"完全公平"思想，于是CFS引入了虛擬運行時間(virtual runtime)。

虛擬運行時間

每個進程的物理運行時間時肯定不能一樣的，CFS調度器只要保證的就是進程的虛擬運行時間相等即可。

那虛擬運行時間該如何計算呢？

“

virtual_time = wall_time * nice_0_weight/sched_prio_to_weigh

比如現有進程A sched_prio=0，進程B sched_prio=-5：

• 調度延遲=10ms，A的運行時間=2.47ms B的運行時間=7.53ms，也就是wall_time
• nice_0_weight表示sched_prio=0的權重為1024
• 進程A的虛擬時間：2.47*1024/1024=2.47ms
• 進程B的虛擬時間：7.53*1024/3121=2.47ms

經過這樣映射，A和B的虛擬時間就相等了。

上述公式涉及了除法和浮點數運算，因此需要轉換成為乘法來保證數據準確性，再給出虛擬時間計算的變形等價公式：

“

virtual_time = (wall_time * nice_0_weight * 2^32/sched_prio_to_weigh)>>32

“

令 inv_weight = 2^32/sched_prio_to_weigh

“

則 virtual_time = (wall_time * 1024 * inv_weight)>>32

由于sched_prio_to_weigh的值存儲在數組中，inv_weight同樣可以：

constu32sched_prio_to_wmult[40]={
/*-20*/48388,59856,76040,92818,118348,
/*-15*/147320,184698,229616,287308,360437,
/*-10*/449829,563644,704093,875809,1099582,
/*-5*/1376151,1717300,2157191,2708050,3363326,
/*0*/4194304,5237765,6557202,8165337,10153587,
/*5*/12820798,15790321,19976592,24970740,31350126,
/*10*/39045157,49367440,61356676,76695844,95443717,
/*15*/119304647,148102320,186737708,238609294,286331153,
};

經過一番計算，各個進程的虛擬運行時間一致了，似乎我們理解了"完全公平"的思想。

虛擬運行時間與優先級的衰減因子有關，也就是inv_weight隨著nice值增大而增大，同時其作為分母也加速了低優先級進程的衰減。

• nice=0 虛擬運行時間 = 物理運行時間
• nice>0 虛擬運行時間 > 物理運行時間
• nice<0 虛擬運行時間 < 物理運行時間

“

簡言之：CFS將物理運行時間在不同優先級進程中發生了不同的通脹。

摒棄了固定時間片機制也是CFS的亮點，系統負載高時大家都少用一些CPU，系統負載低時大家都多用一些CPU，讓調度器有了一定的自適應能力。

pick-next和紅黑樹

那么這些進程應該采用哪種數據結構來實現pick-next算法呢？

CFS調度器采用了紅黑樹來保存活躍進程任務，紅黑樹的增刪查復雜度是O(logn)，但是CFS引入了一些額外的數據結構，可以免去遍歷獲得下一個最合適的進程。

紅黑樹的key是進程已經使用的虛擬運行時間，并且把虛擬時間數值最小的放到最左的葉子節點，這個節點就是下一個被pick的進程了。

前面已經論證了，每個進程的虛擬運行時間是一樣的，數值越小表示被調度的越少，因此需要更偏愛一些，當虛擬運行時間耗盡則從紅黑樹中刪除，下個調度周期開始后再添加到紅黑樹上。

本章重點

• O(n)調度器采用全局runqueue，導致多cpu加鎖問題和cache利用率低的問題
• O(1)調度器為每個cpu設計了一個runqueue，并且采用MLFQ算法思想設置140個優先級鏈表和active/expire兩個雙指針結構
• CFS調度器采用紅黑樹來實現O(logn)復雜度的pick-next算法，摒棄固定時間片機制，采用調度周期內的動態時間機制
• O(1)和O(n)都在交互進程的識別算法上下了功夫，但是無法做的100%準確
• CFS另辟蹊徑采用完全公平思想以及虛擬運行時間來實現進行的調度
• CFS調度器也并非銀彈，在某些方面可能不如O(1)