對于操作系統(tǒng)來講，它面對的 CPU 數(shù)量是有限的，往往需要執(zhí)行的進(jìn)程數(shù)目遠(yuǎn)超 CPU 數(shù)目，因而就需要合理的把 CPU 執(zhí)行時(shí)間分配給進(jìn)程。

既要保證進(jìn)程快速響應(yīng)，又要保證進(jìn)程相對公平的獲得執(zhí)行時(shí)間，這是一個(gè)十分復(fù)雜的事情。

今天我們就好好講講 Linux 是如何進(jìn)行進(jìn)程調(diào)度的。如果嚴(yán)謹(jǐn)一些的話， Linux 操作系統(tǒng)中應(yīng)該叫任務(wù)調(diào)度，不過本文就按照大家的習(xí)慣叫進(jìn)程調(diào)度了。

之前講過，可以把進(jìn)程細(xì)分為五種狀態(tài)，或者粗分為三種狀態(tài)。五種狀態(tài)已經(jīng)在之前講過了，今天在講進(jìn)程調(diào)度前咱們簡單看下三種基本狀態(tài)：

• 就緒（Ready）: 進(jìn)程已經(jīng)獲得了 CPU 以外的所有必要資源，如進(jìn)程空間、網(wǎng)絡(luò)連接等。就緒狀態(tài)下的進(jìn)程等到CPU，便可立即執(zhí)行。
• 執(zhí)行（Running）：進(jìn)程獲得 CPU，執(zhí)行程序。
• 阻塞（Blocked）：當(dāng)進(jìn)程由于等待某個(gè)事件而無法執(zhí)行時(shí)，便放棄 CPU，處于阻塞狀態(tài)。

調(diào)度器主要就是負(fù)責(zé)進(jìn)程在就緒態(tài)和執(zhí)行態(tài)之間轉(zhuǎn)換。Linux調(diào)度器主要負(fù)責(zé)做以下兩件事：（1）選擇出最合適的處于就緒態(tài)的進(jìn)程來執(zhí)行；（2）打斷某些執(zhí)行中的進(jìn)程，讓他們變?yōu)榫途w態(tài)。

Linux 操作系統(tǒng)把需要調(diào)度的進(jìn)程分為兩類：

普通進(jìn)程（Normal Process）：優(yōu)先級低的進(jìn)程。

實(shí)時(shí)進(jìn)程（Real-Time Process）：優(yōu)先級高、需要盡快被執(zhí)行的進(jìn)程。

對于普通進(jìn)程和實(shí)時(shí)進(jìn)程，會分配不同的優(yōu)先級。進(jìn)程的優(yōu)先級是 0 到 139 的整數(shù)，0-99 留給實(shí)時(shí)進(jìn)程，100-139 留給普通進(jìn)程。另外在調(diào)度過程中內(nèi)核根據(jù)進(jìn)程的情況，會對進(jìn)程的優(yōu)先級進(jìn)行一定的調(diào)整。

普通進(jìn)程和實(shí)時(shí)進(jìn)程對于調(diào)度器的需求也不一樣。對于實(shí)時(shí)進(jìn)程，最重要的是快速的對進(jìn)程進(jìn)行調(diào)度。

對于普通進(jìn)程，要兼顧調(diào)度的公平性、系統(tǒng)的吞吐量，以及進(jìn)程調(diào)度的響應(yīng)時(shí)間。

Part1進(jìn)程調(diào)度器的發(fā)展

最原始的Linux調(diào)度策略就是按照優(yōu)先級排好進(jìn)程，一個(gè)進(jìn)程運(yùn)行完后再運(yùn)行剩下進(jìn)程中優(yōu)先級最高的那一個(gè)。

但這種方式無法滿足多任務(wù)系統(tǒng)的需求。接下來我們按照出現(xiàn)順序介紹 3 種調(diào)度器進(jìn)化過程中經(jīng)典的調(diào)度器。

在下面的介紹中，主要介紹調(diào)度器的一個(gè)演化思路，不會特別注重細(xì)節(jié)，我們都從調(diào)度器的設(shè)計(jì)理念、進(jìn)程執(zhí)行時(shí)間設(shè)計(jì)、組織進(jìn)程的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)具有的問題來介紹。

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

設(shè)計(jì)理念

O(n) 調(diào)度器把時(shí)間分成大量的微小時(shí)間片（Epoch）。在每個(gè)時(shí)間片開始的時(shí)候，調(diào)度器會檢查所有處在就緒狀態(tài)的進(jìn)程。

調(diào)度器計(jì)算每個(gè)進(jìn)程的優(yōu)先級，然后選擇優(yōu)先級最高的進(jìn)程來執(zhí)行。一旦被調(diào)度器切換到執(zhí)行，進(jìn)程可以用盡這個(gè)時(shí)間片。如果進(jìn)程沒有用盡時(shí)間片，那么該時(shí)間片的剩余時(shí)間會增加到下一個(gè)時(shí)間片中。

進(jìn)程執(zhí)行時(shí)間的設(shè)計(jì)

O（n）在設(shè)計(jì)默認(rèn)時(shí)間片時(shí)根據(jù)進(jìn)程的靜態(tài)優(yōu)先級固定分配一個(gè)默認(rèn)的時(shí)間片，優(yōu)先級越高，所得到的時(shí)間片就越大。分配的具體算法叫 NICE_TO_TICKS。大家感興趣的可以自行學(xué)習(xí)。

說到優(yōu)先級，O（n）調(diào)度器把優(yōu)先級分為靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級，剛提到的靜態(tài)優(yōu)先級就是進(jìn)程創(chuàng)建時(shí)初始的優(yōu)先級，不會改變，進(jìn)程默認(rèn)的時(shí)間片就是根據(jù)靜態(tài)優(yōu)先級進(jìn)行計(jì)算分配。

而每次進(jìn)程調(diào)度的過程中，都會基于進(jìn)程的靜態(tài)優(yōu)先級和該進(jìn)程所剩的時(shí)間片，計(jì)算一個(gè)動態(tài)優(yōu)先級，動態(tài)優(yōu)先級最高的就是下一次要調(diào)度的。該進(jìn)程靜態(tài)優(yōu)先級越高，所剩的時(shí)間片越多，那么這個(gè)進(jìn)程的動態(tài)優(yōu)先級也就越高。

數(shù)據(jù)結(jié)構(gòu)

O（n）調(diào)度器采用一個(gè)全局隊(duì)列將進(jìn)程組織起來。只要進(jìn)程變?yōu)榫途w態(tài)，進(jìn)程就會被掛到這個(gè)隊(duì)列中，每一次進(jìn)程調(diào)度，都需要把隊(duì)列中所有進(jìn)程的動態(tài)優(yōu)先級計(jì)算一遍，選出動態(tài)優(yōu)先級最高的進(jìn)程。

問題

看上面的架構(gòu)圖。O（n）最大的問題就在于以一個(gè)隊(duì)列就把所有的進(jìn)程組織起來，每次要選擇出下一個(gè)要執(zhí)行的進(jìn)程時(shí)， 都需要把隊(duì)列全部遍歷一遍。且要把隊(duì)列中所有進(jìn)程的動態(tài)優(yōu)先級都計(jì)算一遍。這對于隊(duì)列中進(jìn)程較多時(shí)是難以接受的。

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

設(shè)計(jì)理念

由于O（n）調(diào)度器的性能受進(jìn)程數(shù)量的影響很大，后續(xù)調(diào)度器一直想解決這個(gè)問題，于是O（1）調(diào)度器被設(shè)計(jì)了出來。O（1）調(diào)度器的目得是，不管進(jìn)程隊(duì)列中有幾個(gè)進(jìn)程，都要直接能把下一個(gè)要執(zhí)行得進(jìn)程挑出來。

然后接下來就和O（n）調(diào)度器基本一致，讓得到執(zhí)行的進(jìn)程不受打擾的執(zhí)行完自己分到的時(shí)間片，除非自己因?yàn)槟承┰蚍艞増?zhí)行。

進(jìn)程執(zhí)行時(shí)間的設(shè)計(jì)

和O（n）調(diào)度器類似，O（1）也是基于進(jìn)程的優(yōu)先級計(jì)算分給該進(jìn)程的時(shí)間片。計(jì)算公式如下：

優(yōu)先級120以下進(jìn)程時(shí)間片 =  （140 - 優(yōu)先級） x 20 毫秒                                  //進(jìn)程優(yōu)先級數(shù)字越小優(yōu)先級越高
優(yōu)先級120及以上進(jìn)程時(shí)間片 = （140 - 優(yōu)先級）x 5 毫秒

O（1）調(diào)度器還會根據(jù)平均休眠時(shí)間來調(diào)整進(jìn)程優(yōu)先級。其實(shí)也就是進(jìn)程和用戶交互越多，進(jìn)程優(yōu)先級就越高。

數(shù)據(jù)結(jié)構(gòu)

看該調(diào)度器的架構(gòu)圖，O（n）調(diào)度器其實(shí)也很暴力，之前說進(jìn)程得優(yōu)先級是0-139 的整數(shù)。那就直接生成了 139 個(gè)隊(duì)列，進(jìn)程的優(yōu)先級是多少就放在哪個(gè)隊(duì)列中。相同優(yōu)先級的進(jìn)程放在同一個(gè)隊(duì)列中。

這樣，按照優(yōu)先級依次執(zhí)行，遇到一個(gè)隊(duì)列中有多個(gè)進(jìn)程的情況，就從隊(duì)列中隨機(jī)選擇一個(gè)。

問題

可以看出，進(jìn)程的運(yùn)行順序和所得時(shí)間片太依賴優(yōu)先級了。另外O（1）調(diào)度器根據(jù)平均休眠時(shí)間來調(diào)整進(jìn)程優(yōu)先級是基于頻繁和用戶交互得信息是需要更高優(yōu)先級的假設(shè)，如果這個(gè)假設(shè)不成立，那么調(diào)度器對CPU的調(diào)配就有問題了。

3完全公平調(diào)度器（CFS）

完全公平調(diào)度器（CFS）的出現(xiàn)在調(diào)度器的發(fā)展史上具有劃時(shí)代的意義。CFS 在進(jìn)程執(zhí)行時(shí)間片和進(jìn)程排列的數(shù)據(jù)結(jié)構(gòu)上都有一個(gè)很大的創(chuàng)新。

設(shè)計(jì)理念

CFS 調(diào)度器是這樣一個(gè)邏輯，每一個(gè)進(jìn)程都有一個(gè)虛擬運(yùn)行時(shí)間，每次執(zhí)行進(jìn)程時(shí)，都挑出虛擬執(zhí)行時(shí)間最短的進(jìn)程分給時(shí)間片讓他執(zhí)行。

但是呢，優(yōu)先級高的進(jìn)程需要更多的執(zhí)行時(shí)間，所以，就要照顧優(yōu)先級高的進(jìn)程能更多的時(shí)間片。

這樣，就需要在虛擬運(yùn)行時(shí)間上做一些措施，對于高優(yōu)先級的進(jìn)程，就讓他的虛擬運(yùn)行時(shí)間增的慢一點(diǎn)，而優(yōu)先級低的進(jìn)程，就讓它的虛擬運(yùn)行時(shí)間增的快一點(diǎn)。

另外，該進(jìn)程調(diào)度器還是需要能直接的找到運(yùn)行虛擬時(shí)間最少的進(jìn)程，進(jìn)而分給它時(shí)間片讓它執(zhí)行。

進(jìn)程執(zhí)行時(shí)間設(shè)計(jì)

CFS 調(diào)度器增加了一個(gè)虛擬運(yùn)行時(shí)間的概念。每次一個(gè)進(jìn)程在 CPU 中執(zhí)行一段時(shí)間，就會增加它的虛擬運(yùn)行時(shí)間，但是這個(gè)虛擬運(yùn)行時(shí)間增加的幅度會受進(jìn)程優(yōu)先級的影響。

比如同樣實(shí)際運(yùn)行了 300ms，高優(yōu)先級的進(jìn)程虛擬時(shí)間只增加了100ms，而低優(yōu)先級的進(jìn)程虛擬運(yùn)行時(shí)間卻增加了300ms，因?yàn)槊看芜x擇要執(zhí)行的進(jìn)程時(shí)，選取虛擬運(yùn)行時(shí)間最少的進(jìn)程去執(zhí)行，所以下次執(zhí)行時(shí)高優(yōu)先級的進(jìn)程優(yōu)先執(zhí)行的可能性更大。

虛擬運(yùn)行時(shí)間的計(jì)算是基于這樣一個(gè)公式  vruntime += 實(shí)際運(yùn)行時(shí)間 / 權(quán)重。大家也應(yīng)該能猜出，高優(yōu)先級的權(quán)重會高，低優(yōu)先級的權(quán)重就低一些，這樣就能達(dá)到我們的目的了。

數(shù)據(jù)結(jié)構(gòu)

為了方便找到虛擬運(yùn)行時(shí)間最少的進(jìn)程，CFS 將進(jìn)程采用了紅黑樹的方式組織了起來。就像上面的架構(gòu)圖，每次通過遍歷，可以很方便快捷的找到虛擬運(yùn)行時(shí)間最短的進(jìn)程。

參考資料：

1.https://www.cnblogs.com/vamei/p/9364382.html

2.http://www.wowotech.net/process_management/scheduler-history.html

3.極客時(shí)間《趣談 Linux 操作系統(tǒng)》