主要內(nèi)容：

• 什么是調(diào)度
• 調(diào)度實(shí)現(xiàn)原理
• Linux上調(diào)度實(shí)現(xiàn)的方法
• 調(diào)度相關(guān)的系統(tǒng)調(diào)用

1. 什么是調(diào)度

現(xiàn)在的操作系統(tǒng)都是多任務(wù)的，為了能讓更多的任務(wù)能同時(shí)在系統(tǒng)上更好的運(yùn)行，需要一個(gè)管理程序來(lái)管理計(jì)算機(jī)上同時(shí)運(yùn)行的各個(gè)任務(wù)（也就是進(jìn)程）。

這個(gè)管理程序就是調(diào)度程序，它的功能說(shuō)起來(lái)很簡(jiǎn)單：

1. 決定哪些進(jìn)程運(yùn)行，哪些進(jìn)程等待
2. 決定每個(gè)進(jìn)程運(yùn)行多長(zhǎng)時(shí)間

此外，為了獲得更好的用戶(hù)體驗(yàn)，運(yùn)行中的進(jìn)程還可以立即被其他更緊急的進(jìn)程打斷。

總之，調(diào)度是一個(gè)平衡的過(guò)程。一方面，它要保證各個(gè)運(yùn)行的進(jìn)程能夠最大限度的使用CPU(即盡量少的切換進(jìn)程，進(jìn)程切換過(guò)多，CPU的時(shí)間會(huì)浪費(fèi)在切換上)；另一方面，保證各個(gè)進(jìn)程能公平的使用CPU(即防止一個(gè)進(jìn)程長(zhǎng)時(shí)間獨(dú)占CPU的情況)。

2. 調(diào)度實(shí)現(xiàn)原理

前面說(shuō)過(guò)，調(diào)度功能就是決定哪個(gè)進(jìn)程運(yùn)行以及進(jìn)程運(yùn)行多長(zhǎng)時(shí)間。

決定哪個(gè)進(jìn)程運(yùn)行以及運(yùn)行多長(zhǎng)時(shí)間都和進(jìn)程的優(yōu)先級(jí)有關(guān)。為了確定一個(gè)進(jìn)程到底能持續(xù)運(yùn)行多長(zhǎng)時(shí)間，調(diào)度中還引入了時(shí)間片的概念。

2.1 關(guān)于進(jìn)程的優(yōu)先級(jí)

進(jìn)程的優(yōu)先級(jí)有2種度量方法，一種是nice值，一種是實(shí)時(shí)優(yōu)先級(jí)。

nice值的范圍是-20～+19，值越大優(yōu)先級(jí)越低，也就是說(shuō)nice值為-20的進(jìn)程優(yōu)先級(jí)最大。

實(shí)時(shí)優(yōu)先級(jí)的范圍是0～99，與nice值的定義相反，實(shí)時(shí)優(yōu)先級(jí)是值越大優(yōu)先級(jí)越高。

實(shí)時(shí)進(jìn)程都是一些對(duì)響應(yīng)時(shí)間要求比較高的進(jìn)程，因此系統(tǒng)中有實(shí)時(shí)優(yōu)先級(jí)高的進(jìn)程處于運(yùn)行隊(duì)列的話，它們會(huì)搶占一般的進(jìn)程的運(yùn)行時(shí)間。

進(jìn)程的2種優(yōu)先級(jí)會(huì)讓人不好理解，到底哪個(gè)優(yōu)先級(jí)更優(yōu)先？一個(gè)進(jìn)程同時(shí)有2種優(yōu)先級(jí)怎么辦？

其實(shí)linux的內(nèi)核早就有了解決辦法。

對(duì)于第一個(gè)問(wèn)題，到底哪個(gè)優(yōu)先級(jí)更優(yōu)先？

答案是實(shí)時(shí)優(yōu)先級(jí)高于nice值，在內(nèi)核中，實(shí)時(shí)優(yōu)先級(jí)的范圍是 0～MAX_RT_PRIO-1 MAX_RT_PRIO的定義參見(jiàn) include/linux/sched.h

1611 #define MAX_USER_RT_PRIO        100
1612 #define MAX_RT_PRIO             MAX_USER_RT_PRIO

nice值在內(nèi)核中的范圍是 MAX_RT_PRIO～MAX_RT_PRIO+40 即 MAX_RT_PRIO～MAX_PRIO

1614 #define MAX_PRIO                (MAX_RT_PRIO + 40)

第二個(gè)問(wèn)題，一個(gè)進(jìn)程同時(shí)有2種優(yōu)先級(jí)怎么辦？

答案很簡(jiǎn)單，就是一個(gè)進(jìn)程不可能有2個(gè)優(yōu)先級(jí)。一個(gè)進(jìn)程有了實(shí)時(shí)優(yōu)先級(jí)就沒(méi)有Nice值，有了Nice值就沒(méi)有實(shí)時(shí)優(yōu)先級(jí)。

我們可以通過(guò)以下命令查看進(jìn)程的實(shí)時(shí)優(yōu)先級(jí)和Nice值：(其中RTPRIO是實(shí)時(shí)優(yōu)先級(jí)，NI是Nice值)

$ ps -eo state,uid,pid,ppid,rtprio,ni,time,comm
S   UID   PID  PPID RTPRIO  NI     TIME COMMAND
S     0     1     0      -   0 00:00:00 systemd
S     0     2     0      -   0 00:00:00 kthreadd
S     0     3     2      -   0 00:00:00 ksoftirqd/0
S     0     6     2     99   - 00:00:00 migration/0
S     0     7     2     99   - 00:00:00 watchdog/0
S     0     8     2     99   - 00:00:00 migration/1
S     0    10     2      -   0 00:00:00 ksoftirqd/1
S     0    12     2     99   - 00:00:00 watchdog/1
S     0    13     2     99   - 00:00:00 migration/2
S     0    15     2      -   0 00:00:00 ksoftirqd/2
S     0    16     2     99   - 00:00:00 watchdog/2
S     0    17     2     99   - 00:00:00 migration/3
S     0    19     2      -   0 00:00:00 ksoftirqd/3
S     0    20     2     99   - 00:00:00 watchdog/3
S     0    21     2      - -20 00:00:00 cpuset
S     0    22     2      - -20 00:00:00 khelper

2.2 關(guān)于時(shí)間片

有了優(yōu)先級(jí)，可以決定誰(shuí)先運(yùn)行了。但是對(duì)于調(diào)度程序來(lái)說(shuō)，并不是運(yùn)行一次就結(jié)束了，還必須知道間隔多久進(jìn)行下次調(diào)度。

于是就有了時(shí)間片的概念。時(shí)間片是一個(gè)數(shù)值，表示一個(gè)進(jìn)程被搶占前能持續(xù)運(yùn)行的時(shí)間。

也可以認(rèn)為是進(jìn)程在下次調(diào)度發(fā)生前運(yùn)行的時(shí)間(除非進(jìn)程主動(dòng)放棄CPU，或者有實(shí)時(shí)進(jìn)程來(lái)?yè)屨糃PU)。

時(shí)間片的大小設(shè)置并不簡(jiǎn)單，設(shè)大了，系統(tǒng)響應(yīng)變慢(調(diào)度周期長(zhǎng))；設(shè)小了，進(jìn)程頻繁切換帶來(lái)的處理器消耗。默認(rèn)的時(shí)間片一般是10ms

2.3 調(diào)度實(shí)現(xiàn)原理（基于優(yōu)先級(jí)和時(shí)間片）

下面舉個(gè)直觀的例子來(lái)說(shuō)明：

假設(shè)系統(tǒng)中只有3個(gè)進(jìn)程ProcessA(NI=+10)，ProcessB(NI=0)，ProcessC(NI=-10)，NI表示進(jìn)程的nice值，時(shí)間片=10ms

1) 調(diào)度前，把進(jìn)程優(yōu)先級(jí)按一定的權(quán)重映射成時(shí)間片(這里假設(shè)優(yōu)先級(jí)高一級(jí)相當(dāng)于多5msCPU時(shí)間)。

    假設(shè)ProcessA分配了一個(gè)時(shí)間片10ms，那么ProcessB的優(yōu)先級(jí)比ProcessA高10(nice值越小優(yōu)先級(jí)越高)，ProcessB應(yīng)該分配10*5+10=60ms，以此類(lèi)推，ProcessC分配20*5+10=110ms

2) 開(kāi)始調(diào)度時(shí)，優(yōu)先調(diào)度分配CPU時(shí)間多的進(jìn)程。由于ProcessA(10ms),ProcessB(60ms),ProcessC(110ms)。顯然先調(diào)度ProcessC

3) 10ms(一個(gè)時(shí)間片)后，再次調(diào)度時(shí)，ProcessA(10ms),ProcessB(60ms),ProcessC(100ms)。ProcessC剛運(yùn)行了10ms，所以變成100ms。此時(shí)仍然先調(diào)度ProcessC

4) 再調(diào)度4次后(4個(gè)時(shí)間片)，ProcessA(10ms),ProcessB(60ms),ProcessC(60ms)。此時(shí)ProcessB和ProcessC的CPU時(shí)間一樣，這時(shí)得看ProcessB和ProcessC誰(shuí)在CPU運(yùn)行隊(duì)列的前面，假設(shè)ProcessB在前面，則調(diào)度ProcessB

5) 10ms(一個(gè)時(shí)間片)后，ProcessA(10ms),ProcessB(50ms),ProcessC(60ms)。再次調(diào)度ProcessC

6) ProcessB和ProcessC交替運(yùn)行，直至ProcessA(10ms),ProcessB(10ms),ProcessC(10ms)。

    這時(shí)得看ProcessA，ProcessB，ProcessC誰(shuí)在CPU運(yùn)行隊(duì)列的前面就先調(diào)度誰(shuí)。這里假設(shè)調(diào)度ProcessA

7) 10ms(一個(gè)時(shí)間片)后，ProcessA(時(shí)間片用完后退出),ProcessB(10ms),ProcessC(10ms)。

8) 再過(guò)2個(gè)時(shí)間片，ProcessB和ProcessC也運(yùn)行完退出。

這個(gè)例子很簡(jiǎn)單，主要是為了說(shuō)明調(diào)度的原理，實(shí)際的調(diào)度算法雖然不會(huì)這么簡(jiǎn)單，但是基本的實(shí)現(xiàn)原理也是類(lèi)似的：

1）確定每個(gè)進(jìn)程能占用多少CPU時(shí)間(這里確定CPU時(shí)間的算法有很多，根據(jù)不同的需求會(huì)不一樣)

2）占用CPU時(shí)間多的先運(yùn)行

3）運(yùn)行完后，扣除運(yùn)行進(jìn)程的CPU時(shí)間，再回到 1）

3. Linux上調(diào)度實(shí)現(xiàn)的方法

Linux上的調(diào)度算法是不斷發(fā)展的，在2.6.23內(nèi)核以后，采用了“完全公平調(diào)度算法”，簡(jiǎn)稱(chēng)CFS。

CFS算法在分配每個(gè)進(jìn)程的CPU時(shí)間時(shí)，不是分配給它們一個(gè)絕對(duì)的CPU時(shí)間，而是根據(jù)進(jìn)程的優(yōu)先級(jí)分配給它們一個(gè)占用CPU時(shí)間的百分比。

比如ProcessA(NI=1)，ProcessB(NI=3)，ProcessC(NI=6)，在CFS算法中，分別占用CPU的百分比為：ProcessA(10%)，ProcessB(30%)，ProcessC(60%)

因?yàn)榭偣彩?00%，ProcessB的優(yōu)先級(jí)是ProcessA的3倍，ProcessC的優(yōu)先級(jí)是ProcessA的6倍。

Linux上的CFS算法主要有以下步驟：(還是以ProcessA(10%)，ProcessB(30%)，ProcessC(60%)為例)

1)計(jì)算每個(gè)進(jìn)程的vruntime(注1)，通過(guò)update_curr()函數(shù)更新進(jìn)程的vruntime。

2)選擇具有最小vruntime的進(jìn)程投入運(yùn)行。（注2）

3)進(jìn)程運(yùn)行完后，更新進(jìn)程的vruntime，轉(zhuǎn)入步驟2) （注3）

注1. 這里的vruntime是進(jìn)程虛擬運(yùn)行的時(shí)間的總和。vruntime定義在：kernel/sched_fair.c 文件的 struct sched_entity 中。

注2. 這里有點(diǎn)不好理解，根據(jù)vruntime來(lái)選擇要運(yùn)行的進(jìn)程，似乎和每個(gè)進(jìn)程所占的CPU時(shí)間百分比沒(méi)有關(guān)系了。

1）比如先運(yùn)行ProcessC，(vr是vruntime的縮寫(xiě))，則10ms后：ProcessA(vr=0)，ProcessB(vr=0)，ProcessC(vr=10)

2）那么下次調(diào)度只能運(yùn)行ProcessA或者ProcessB。(因?yàn)闀?huì)選擇具有最小vruntime的進(jìn)程)

長(zhǎng)時(shí)間來(lái)看的話，ProcessA、ProcessB、ProcessC是公平的交替運(yùn)行的，和優(yōu)先級(jí)沒(méi)有關(guān)系。

而實(shí)際上vruntime并不是實(shí)際的運(yùn)行時(shí)間，它是實(shí)際運(yùn)行時(shí)間進(jìn)行加權(quán)運(yùn)算后的結(jié)果。

比如上面3個(gè)進(jìn)程中ProcessA(10%)只分配了CPU總的處理時(shí)間的10%，那么ProcessA運(yùn)行10ms的話，它的vruntime會(huì)增加100ms。

以此類(lèi)推，ProcessB運(yùn)行10ms的話，它的vruntime會(huì)增加(100/3)ms,ProcessC運(yùn)行10ms的話，它的vruntime會(huì)增加(100/6)ms。

實(shí)際的運(yùn)行時(shí)，由于ProcessC的vruntime增加的最慢，所以它會(huì)獲得最多的CPU處理時(shí)間。

上面的加權(quán)算法是我自己為了理解方便簡(jiǎn)化的，Linux對(duì)vruntime的加權(quán)方法還得去看源碼^-^

注3.Linux為了能快速的找到具有最小vruntime，將所有的進(jìn)程的存儲(chǔ)在一個(gè)紅黑樹(shù)中。這樣樹(shù)的最左邊的葉子節(jié)點(diǎn)就是具有最小vruntime的進(jìn)程，新的進(jìn)程加入或有舊的進(jìn)程退出時(shí)都會(huì)更新這棵樹(shù)。

其實(shí)Linux上的調(diào)度器是以模塊方式提供的，每個(gè)調(diào)度器有不同的優(yōu)先級(jí)，所以可以同時(shí)存在多種調(diào)度算法。

每個(gè)進(jìn)程可以選擇自己的調(diào)度器，Linux調(diào)度時(shí)，首先按調(diào)度器的優(yōu)先級(jí)選擇一個(gè)調(diào)度器，再選擇這個(gè)調(diào)度器下的進(jìn)程。

4. 調(diào)度相關(guān)的系統(tǒng)調(diào)用

調(diào)度相關(guān)的系統(tǒng)調(diào)用主要有2類(lèi)：

1) 與調(diào)度策略和進(jìn)程優(yōu)先級(jí)相關(guān) (就是上面的提到的各種參數(shù)，優(yōu)先級(jí)，時(shí)間片等等) - 下表中的前8個(gè)

2) 與處理器相關(guān) - 下表中的最后3個(gè)