準備知識

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

• 調(diào)度究竟是個啥
• 操作系統(tǒng)有哪幾種？常用的是哪種？
• 進程的分類和優(yōu)先級是怎么回事
• 搶占式調(diào)度和非搶占式調(diào)度有啥區(qū)別
• 如何設(shè)計一個可用的調(diào)度器

調(diào)度的概念

科技源自生活，調(diào)度系統(tǒng)絕對不是計算機領(lǐng)域的專利，現(xiàn)實生活中調(diào)度無處不在：

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

“

調(diào)度是為了解決資源和需求之間的不匹配問題，現(xiàn)實往往是資源少&需求多，計算機領(lǐng)域也是如此。

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

操作系統(tǒng)分類

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

• 批處理系統(tǒng)( Batch Processing System )

“

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

• 實時系統(tǒng)( Real-Time System)

“

實時系統(tǒng)最大的特點在于計算的正確性不僅取決于程序的邏輯正確性，也取決于結(jié)果產(chǎn)生的時間，如果系統(tǒng)的時間約束條件得不到滿足，將會發(fā)生系統(tǒng)出錯，強實時系統(tǒng)一般應(yīng)用在航空航天、導(dǎo)彈導(dǎo)航制導(dǎo)、核工業(yè)等領(lǐng)域。

• 分時系統(tǒng)( Time Sharing System)

“

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

Linux屬于分時系統(tǒng)，是互聯(lián)網(wǎng)服務(wù)器的主流操作系統(tǒng)，重點研究它就行！

進程分類

根據(jù)進程運行時的狀態(tài)，可以分為：

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

“

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

• CPU密集型( CPU-bound)

“

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

進程調(diào)度器需要根據(jù)進程是IO密集型還是CPU密集型會采用不同的策略。

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

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

“

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

“

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

進程優(yōu)先級

根據(jù)進程的重要性，可以分為：

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

“

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

實時進程和普通進程的進程優(yōu)先級不同，調(diào)度器都會根據(jù)優(yōu)先級來確定進程的CPU優(yōu)先權(quán)和運行時間。

在Linux中影響優(yōu)先級的兩個因素：Nice謙讓值和Priority權(quán)重值。

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

PR值由內(nèi)核來確定，用戶可以修改Nice謙讓值，進而干預(yù)PR值：

• PR_new = PR_old + Nice

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

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

非搶占和搶占式

根據(jù)進程任務(wù)在占用CPU時，使用權(quán)是否會被奪取分為：

• 協(xié)作式調(diào)度( Cooperative Scheduling)

“

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

• 搶占式調(diào)度( Preemptive Scheduling)

“

進程任務(wù)占用CPU期間可以被其他進程奪走，具體由操作系統(tǒng)調(diào)度器決定下一個占用CPU的進程

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

調(diào)度器設(shè)計思路

設(shè)計目標

有兩個指標需要重視：

• 周轉(zhuǎn)時間( Cycling Time )

“

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

• 響應(yīng)時間Response Time

“

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

綜合來說：

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

只有做到這幾點，調(diào)度器才可能在周轉(zhuǎn)時間和響應(yīng)時間上得到一個良好的表現(xiàn)。

設(shè)計實現(xiàn)

要實現(xiàn)一個調(diào)度器，主要包括兩個核心部分：

• 算法設(shè)計
• 工程實現(xiàn)

算法更多是一種思想，調(diào)度器基于某種調(diào)度算法進行工程化實現(xiàn)，捋清楚二者的關(guān)系對于后續(xù)內(nèi)容的理解將大有裨益。

本章重點

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

調(diào)度算法

調(diào)度算法也經(jīng)歷了從簡單到復(fù)雜的演進，到目前為止也沒有哪種調(diào)度算法是萬能的，拋開場景來評判調(diào)度算法優(yōu)劣并不明智。

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

先來先服務(wù)FCFS

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

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

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

在FCFS中優(yōu)先被調(diào)度的進程如果耗時很長，后續(xù)進程都必須要等待這個大CPU消耗的進程，最終導(dǎo)致周轉(zhuǎn)時間直線拉升，也就是護航效應(yīng)。

最短任務(wù)優(yōu)先SJF

最短任務(wù)優(yōu)先Shortest Job First的思想是當多個進程同時出現(xiàn)時，優(yōu)先安排執(zhí)行時間最短的任務(wù)，然后是執(zhí)行時間次短，以此類推。

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

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

相比于FCFS可能的執(zhí)行順序是A->C->B來說，周轉(zhuǎn)時間和響應(yīng)時間都得到很大的改善。

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

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

搶占式最短任務(wù)優(yōu)先PSJF

SJF算法最具啟發(fā)的地方在于優(yōu)先調(diào)度執(zhí)行時間短的任務(wù)來解決護航效應(yīng)，但是該算法屬于非搶占式調(diào)度，對于先后到達且執(zhí)行時間差別較大的場景也束手無策。

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

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

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

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

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

時間片輪轉(zhuǎn)RR

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

“

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

在一個時間片內(nèi)CPU分配給一個進程，時間片耗盡則調(diào)度選擇下一個進程，如此循環(huán)。

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

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

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

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

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

多級反饋隊列MLFQ

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

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

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

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

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

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

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

在樸素MLFQ算法基礎(chǔ)上出現(xiàn)一些變種，通過工程實現(xiàn)和經(jīng)驗配置最終被使用到操作系統(tǒng)中，成為真正的工業(yè)級進程調(diào)度器。

Linux進程調(diào)度器

Linux的進程調(diào)度器是不斷演進的，先后出現(xiàn)過三種里程碑式的調(diào)度器：

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

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

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

調(diào)度器設(shè)計核心

要理解這些復(fù)雜的調(diào)度器設(shè)計，我們必須要有一個核心主線，再去理解精髓。

調(diào)度器需要解決的關(guān)鍵問題：

• 采用何種數(shù)據(jù)結(jié)構(gòu)來組織進程以及如何實現(xiàn)pick next
• 如何根據(jù)進程優(yōu)先級來確定進程運行時間
• 如何判斷進程類型
  • 判斷進程的交互性質(zhì)，是否為IO密集
  • 獎勵I(lǐng)O密集型&懲罰CPU密集型
  • 實時進程高優(yōu)&普通進程低優(yōu)
• 如何確定進程的動態(tài)優(yōu)先級
  • 影響因素：靜態(tài)優(yōu)先級、nice值、IO密集型和CPU密集型產(chǎn)生的獎懲

事實上，調(diào)度器在設(shè)計實現(xiàn)上考慮的問題還有很多，篇幅所限只列舉幾個公共問題。

O(n) 調(diào)度器

O(n)調(diào)度器采用一個全局隊列runqueue作為核心數(shù)據(jù)結(jié)構(gòu)，具備以下特點：

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

在Linux中進程使用task_struct結(jié)構(gòu)體來表示，其中有個counter表示進程剩余的CPU時間片：

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

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

O(n)調(diào)度器中調(diào)度權(quán)重是在goodness函數(shù)中完成計算的：

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

/*
*Non-RTprocess-normalcasefirst.
*/

/*對于調(diào)度策略為SCHED_OTHER的進程，沒有實時性要求，它的權(quán)值僅僅取決于
*時間片的剩余和它的nice值，數(shù)值上nice越小，則優(yōu)先級越高，總的權(quán)值=時間片剩余+(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調(diào)度策略，
*具有一個實時優(yōu)先級，總的權(quán)值僅僅取決于該實時優(yōu)先級，
*總的權(quán)值= 1000+實時優(yōu)先級。
**/
weight=1000+p->rt_priority;
out:
returnweight;
}

從代碼可以看到：

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

#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是個宏函數(shù)，根據(jù)不同的調(diào)度頻率HZ有對應(yīng)的TICK_SCALE宏定義，這樣就解決了不同優(yōu)先級的進程的時間片分配問題。

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

• 實時進程采用的是SCHED_RR或者SCHED_FIFO，高級優(yōu)先&同級輪轉(zhuǎn)或者順序執(zhí)行
• 普通進程采用的是SCHED_OTHER
• 進程采用的策略在task_struct中policy體現(xiàn)

在runqueue中搜索下一個合適的進程是基于動態(tài)優(yōu)先級來實現(xiàn)的，動態(tài)優(yōu)先級最高的就是下一個被執(zhí)行的進程。

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

O(1)調(diào)度器

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

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

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

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

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的結(jié)構(gòu)體指針
• arrays是元素為prio_array_t的結(jié)構(gòu)體數(shù)組

prio_array_t結(jié)構(gòu)體的定義：

#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)調(diào)度器對pick-next的實現(xiàn)：

• 在runqueue結(jié)構(gòu)中有active和expire兩個數(shù)組指針，active指向就緒進程的結(jié)構(gòu)，從active-bitmap中尋找優(yōu)先級最高且非空的數(shù)組元素，這個數(shù)組是元素是進程鏈表，找該鏈表中第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時表示沒有活躍任務(wù)，此時進行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)調(diào)度器確定進程優(yōu)先級的方法不一樣，O(1)借助了sleep_avg變量記錄進程的睡眠時間，來識別IO密集型進程，計算bonus值來調(diào)整優(yōu)先級：

#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)調(diào)度器為了實現(xiàn)復(fù)雜場景IO密集型任務(wù)的識別，做了大量的工作仍然無法到達100%的準確，但不可否認O(1)調(diào)度器是一款非常優(yōu)秀的產(chǎn)品。

CFS調(diào)度器

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

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

是繼續(xù)優(yōu)化進程交互性算法，還是另辟蹊徑呢？一直困擾著Linux社區(qū)的大神們。

Con Kolivas和RSDL調(diào)度器

在CFS出現(xiàn)之前，不得不提一位有態(tài)度&有實力的麻醉師Con Kolivas，同時也是linux內(nèi)核開發(fā)者，他在進程調(diào)度領(lǐng)域有自己獨到的見解。

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

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

“

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

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

CFS調(diào)度器

在2.6.23內(nèi)核中引入scheduling class的概念，將調(diào)度器模塊化，系統(tǒng)中可以有多種調(diào)度器，使用不同策略調(diào)度不同類型的進程：

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

這樣一來，CFS調(diào)度器就不關(guān)心實時進程了，專注于普通進程就可以了。

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

我的腦海里浮現(xiàn)了這幅漫畫，我想右邊的應(yīng)該更好，按需分配&達成共贏。

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

這一切CFS是如何實現(xiàn)的呢？我們繼續(xù)看！

優(yōu)先級和權(quán)重

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

CFS摒棄了固定時間片分配，采用動態(tài)時間片分配，本次調(diào)度中進程可占用的時間與進程總數(shù)、總CPU時間、進程權(quán)重等均有關(guān)系，每個調(diào)度周期的值都可能會不一樣。

CFS調(diào)度器從進程優(yōu)先級出發(fā)，它建立了優(yōu)先級prio和權(quán)重weight之間的映射關(guān)系，把優(yōu)先級轉(zhuǎn)換為權(quán)重來參與后續(xù)的計算：

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,
};

“

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

比如現(xiàn)有進程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，那么根據(jù)A占用2.47ms，B占用7.53ms

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

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

虛擬運行時間

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

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

“

virtual_time = wall_time * nice_0_weight/sched_prio_to_weigh

比如現(xiàn)有進程A sched_prio=0，進程B sched_prio=-5：

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

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

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

“

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的值存儲在數(shù)組中，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,
};

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

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

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

“

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

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

pick-next和紅黑樹

那么這些進程應(yīng)該采用哪種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)pick-next算法呢？

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

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

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

本章重點

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