說個大事兒

各位吳彥祖&劉亦菲，大家好！

經(jīng)過深入思考，本號主決定花1-2年時間強(qiáng)更一個系列，暫且叫它《面霸導(dǎo)論》吧！

《面霸導(dǎo)論》有幾大塊內(nèi)容：

今天這篇是《面霸導(dǎo)論》第一彈，文章是需要反復(fù)琢磨的，今天先來搞一下進(jìn)程調(diào)度。

嘟嘟嘟！抓緊上車了！

準(zhǔn)備知識

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

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

調(diào)度的概念

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

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

“

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

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

操作系統(tǒng)分類

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

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

“

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

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

“

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

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

“

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

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

進(jìn)程分類

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

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

“

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

• CPU密集型( CPU-bound)

“

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

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

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

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

“

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

“

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

進(jìn)程優(yōu)先級

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

• 實(shí)時進(jìn)程(Real-Time Process)
• 普通進(jìn)程(Normal Process)

“

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

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

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

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

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

• PR_new = PR_old + Nice

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

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

非搶占和搶占式

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

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

“

進(jìn)程任務(wù)一旦占用CPU只有當(dāng)任務(wù)完成或者因?yàn)槟承┰蛑鲃俞尫臗PU，除上述兩種情況外不能被其他進(jìn)程奪走

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

“

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

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

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

設(shè)計目標(biāo)

有兩個指標(biāo)需要重視：

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

“

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

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

“

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

綜合來說：

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

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

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

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

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

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

本章重點(diǎn)

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

調(diào)度算法

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

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

先來先服務(wù)FCFS

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

• 場景一
  假如有ABC三個進(jìn)程依次進(jìn)入等候使用CPU資源的隊列FIFO，A進(jìn)程占用CPU運(yùn)行5ms，B進(jìn)程10ms，C進(jìn)程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三個進(jìn)程依次進(jìn)入等候使用CPU資源的隊列FIFO，A進(jìn)程占用CPU運(yùn)行100ms，B進(jìn)程10ms，C進(jìn)程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進(jìn)程的運(yùn)行時間長達(dá)100ms，這樣拉升了B和C的周轉(zhuǎn)時間5倍多。

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

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

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

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

• 場景一
  假如有ABC三個進(jìn)程同時進(jìn)入等候使用CPU資源的隊列FIFO，A進(jìn)程占用CPU運(yùn)行100ms，B進(jìn)程10ms，C進(jìn)程25ms，根據(jù)SJF算法的規(guī)則，可知：
• 進(jìn)程執(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的算法思想有些理想化，但并非一無是處，升級改進(jìn)下也有用武之地：

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

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

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

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

• 場景一
  假如有ABC三個進(jìn)程間隔20ms(BC同時且晚于A)依次進(jìn)入等候使用CPU資源的隊列FIFO，A進(jìn)程占用CPU運(yùn)行100ms，B進(jìn)程10ms，C進(jìn)程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

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

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

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

時間片輪轉(zhuǎn)RR

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

“

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

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

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

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

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

RR算法在保障了多個進(jìn)程都能占用CPU，屬于公平策略的一種，但是RR算法將原本可以一次運(yùn)行完的任務(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輪詢機(jī)制
• 通過對任務(wù)運(yùn)行狀態(tài)的追蹤來調(diào)整優(yōu)先級，也就是所謂的Feedback反饋機(jī)制
• 任務(wù)在運(yùn)行期間有較多IO請求和等待，預(yù)測為交互進(jìn)程，優(yōu)先級保持或提升
• 任務(wù)在運(yùn)行期間一直進(jìn)行CPU計算，預(yù)測為非交互進(jìn)程，優(yōu)先級保持或下降
• 最初將所以任務(wù)都設(shè)置為高優(yōu)先級隊列，隨著后續(xù)的運(yùn)行狀態(tài)再進(jìn)行調(diào)整
• 運(yùn)行期間有IO操作則保持優(yōu)先級
• 運(yùn)行期間無IO操作則把任務(wù)放到低一級的隊列中
• 不同隊列分配不同的時間片
• 高優(yōu)先級隊列往往是IO型任務(wù)，配置較小的時間片來保障響應(yīng)時間
• 低優(yōu)先級隊列往往是CPU型任務(wù)，配置較長時間片來保障任務(wù)一直運(yùn)行

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

• 饑餓問題
• CPU密集型的任務(wù)隨著時間推移優(yōu)先級會越來越低，在IO型進(jìn)程多的場景下很容易出現(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)先級，相當(dāng)于作弊

針對上述問題MLFQ還需增加幾個補(bǔ)?。?/p>

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

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

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

Linux進(jìn)程調(diào)度器

Linux的進(jìn)程調(diào)度器是不斷演進(jìn)的，先后出現(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過程是需要遍歷進(jìn)程任務(wù)隊列來實(shí)現(xiàn)，O(1)版本性能上有較大提升可以實(shí)現(xiàn)O(1)復(fù)雜度的pick next過程。

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

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

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

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

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

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

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

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

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

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

struct?task_struct?{
????long?counter;
????long?nice;
????unsigned?long?policy;
????int?processor;
????unsigned?long?cpus_runnable,?cpus_allowed;
}

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

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

static?inline?int?goodness(struct?task_struct?*?p,?int?this_cpu,?struct?mm_struct?*this_mm)
{
????????int?weight;
????????weight?=?-1;
????????/*進(jìn)程可以設(shè)置調(diào)度策略為SCHED_YIELD即“禮讓”策略，這時候它的權(quán)值為-1,權(quán)值相當(dāng)?shù)?/
????????if?(p->policy?&?SCHED_YIELD)
????????????????goto?out;

????????/*
?????????*?Non-RT?process?-?normal?case?first.
?????????*/

????????/*對于調(diào)度策略為SCHED_OTHER的進(jìn)程，沒有實(shí)時性要求，它的權(quán)值僅僅取決于
?????????*?時間片的剩余和它的nice值，數(shù)值上nice越小，則優(yōu)先級越高，總的權(quán)值?=?時間片剩余?+?(20?-?nice)
?????????*?*/
????????if?(p->policy?==?SCHED_OTHER)?{
????????????????/*
?????????????????*?Give?the?process?a?first-approximation?goodness?value
?????????????????*?according?to?the?number?of?clock-ticks?it?has?left.
?????????????????*
?????????????????*?Don't?do?any?other?calculations?if?the?time?slice?is
?????????????????*?over..
?????????????????*/
????????????????weight?=?p->counter;
????????????????if?(!weight)
????????????????????????goto?out;
????????????????????????
#ifdef?CONFIG_SMP
????????????????/*?Give?a?largish?advantage?to?the?same?processor...???*/
????????????????/*?(this?is?equivalent?to?penalizing?other?processors)?*/
????????????????if?(p->processor?==?this_cpu)
????????????????????????weight?+=?PROC_CHANGE_PENALTY;
#endif

????????????????/*?..?and?a?slight?advantage?to?the?current?MM?*/
????????????????if?(p->mm?==?this_mm?||?!p->mm)
????????????????????????weight?+=?1;
????????????????weight?+=?20?-?p->nice;
????????????????goto?out;
????????}

????????/*
?????????*對于實(shí)時進(jìn)程，也就是SCHED_FIFO或者SCHED_RR調(diào)度策略，
?????????*具有一個實(shí)時優(yōu)先級，總的權(quán)值僅僅取決于該實(shí)時優(yōu)先級，
?????????*總的權(quán)值?= 1000?+?實(shí)時優(yōu)先級。
?????????*?*/
????????weight?=?1000?+?p->rt_priority;
out:
????????return?weight;
}

從代碼可以看到：

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

#if?HZ?
#define?TICK_SCALE(x)????????((x)?>>?2)
#elif?HZ?
#define?TICK_SCALE(x)????????((x)?>>?1)
#elif?HZ?
#define?TICK_SCALE(x)????????(x)
#elif?HZ?
#define?TICK_SCALE(x)????????((x)?<
#else
#define?TICK_SCALE(x)????????((x)?<
#endif

#define?NICE_TO_TICKS(nice)????????(TICK_SCALE(20-(nice))+1)

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

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

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

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

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)度器引入了多個隊列，并且增加了負(fù)載均衡機(jī)制，對新出現(xiàn)的進(jìn)行任務(wù)分配到合適的cpu-runqueue中：

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

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

struct?runqueue?{
????????spinlock_t?lock;
????????unsigned?long?nr_running;
????????unsigned?long?long?nr_switches;
????????unsigned?long?expired_timestamp,?nr_uninterruptible;
????????unsigned?long?long?timestamp_last_tick;
????????task_t?*curr,?*idle;
????????struct?mm_struct?*prev_mm;
????????prio_array_t?*active,?*expired,?arrays[2];
????????int?best_expired_prio;
????????atomic_t?nr_iowait;
????????......
};

• active和expired是指向prio_array_t的結(jié)構(gòu)體指針
• arrays是元素為prio_array_t的結(jié)構(gòu)體數(shù)組

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

#define?BITMAP_SIZE?((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
typedef?struct?prio_array?prio_array_t;
struct?prio_array?{
????????unsigned?int?nr_active;
????????unsigned?long?bitmap[BITMAP_SIZE];
????????struct?list_head?queue[MAX_PRIO];
};

O(1)調(diào)度器對pick-next的實(shí)現(xiàn)：

• 在runqueue結(jié)構(gòu)中有active和expire兩個數(shù)組指針，active指向就緒進(jìn)程的結(jié)構(gòu)，從active-bitmap中尋找優(yōu)先級最高且非空的數(shù)組元素，這個數(shù)組是元素是進(jìn)程鏈表，找該鏈表中第1個進(jìn)程即可。

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

• 當(dāng)active的nr_active=0時表示沒有活躍任務(wù)，此時進(jìn)行active和expire雙指針互換，速度很快。

array?=?rq->active;
if?(unlikely(!array->nr_active))?{
????????/*
?????????*?Switch?the?active?and?expired?arrays.
?????????*/
????????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)度器確定進(jìn)程優(yōu)先級的方法不一樣，O(1)借助了sleep_avg變量記錄進(jìn)程的睡眠時間，來識別IO密集型進(jìn)程，計算bonus值來調(diào)整優(yōu)先級：

#define?NICE_TO_PRIO(nice)????????(MAX_RT_PRIO?+?(nice)?+?20)
#define?NS_TO_JIFFIES(TIME)????????((TIME)?/?(1000000000?/?HZ))
#define?CURRENT_BONUS(p)?\
????????(NS_TO_JIFFIES((p)->sleep_avg)?*?MAX_BONUS?/?\
????????????????MAX_SLEEP_AVG)

static?int?effective_prio(task_t?*p)
{
????????int?bonus,?prio;

????????if?(rt_task(p))
????????????????return?p->prio;

????????bonus?=?CURRENT_BONUS(p)?-?MAX_BONUS?/?2;

????????prio?=?p->static_prio?-?bonus;
????????if?(prio?????????????????prio?=?MAX_RT_PRIO;
????????if?(prio?>?MAX_PRIO-1)
????????????????prio?=?MAX_PRIO-1;
????????return?prio;
}

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

CFS調(diào)度器

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

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

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

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

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

Con Kolivas針對O(1)調(diào)度器存在的維護(hù)和優(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ū)，但是事實(shí)上從后面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)驗(yàn)，由匈牙利人Ingo Molnar所提出和實(shí)現(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)度不同類型的進(jìn)程：

• 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)心實(shí)時進(jìn)程了，專注于普通進(jìn)程就可以了。

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

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

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

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

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

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

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

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

const?int?sched_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,
};

“

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

比如現(xiàn)有進(jìn)程A sched_prio=0，進(jìn)程B sched_prio=-5，通過sched_prio_to_weight的映射：

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

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

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

虛擬運(yùn)行時間

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

那虛擬運(yùn)行時間該如何計算呢？

“

virtual_time = wall_time * nice_0_weight/sched_prio_to_weigh

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

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

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

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

“

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同樣可以：

const?u32?sched_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)過一番計算，各個進(jìn)程的虛擬運(yùn)行時間一致了，似乎我們理解了"完全公平"的思想。

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

• nice=0 虛擬運(yùn)行時間 = 物理運(yùn)行時間
• nice>0 虛擬運(yùn)行時間 > 物理運(yùn)行時間
• nice<0 虛擬運(yùn)行時間 < 物理運(yùn)行時間

“

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

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

pick-next和紅黑樹

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

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

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

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

本章重點(diǎn)

• 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)度器采用紅黑樹來實(shí)現(xiàn)O(logn)復(fù)雜度的pick-next算法，摒棄固定時間片機(jī)制，采用調(diào)度周期內(nèi)的動態(tài)時間機(jī)制
• O(1)和O(n)都在交互進(jìn)程的識別算法上下了功夫，但是無法做的100%準(zhǔn)確
• CFS另辟蹊徑采用完全公平思想以及虛擬運(yùn)行時間來實(shí)現(xiàn)進(jìn)行的調(diào)度
• CFS調(diào)度器也并非銀彈，在某些方面可能不如O(1)

參考資料

• https://cs334.cs.vassar.edu/slides/04_Linux_CFS.pdf
• http://www.eecs.harvard.edu/~cs161/notes/scheduling-case-studies.pdf
• http://www.wowotech.net/process_management/scheduler-history.html