1. 任務切換

現(xiàn)在有一塊CPU，但是有兩個程序都想來執(zhí)行，我們需要開發(fā)一個任務調度程序。

只有兩個程序，so easy啦!讓它們交替執(zhí)行就行了。

為了實現(xiàn)切換，我們提供一個API，這兩個程序執(zhí)行一會兒就主動調用一下這個API，然后在這個API內部實現(xiàn)任務的切換。

所謂的切換，其實就是把當前進程的上下文(也就是CPU一堆的寄存器值)保存到進程的TCB(進程控制塊，每個進程對應的內存數(shù)據(jù)結構)里。然后把另一個進程TCB里的上下文寄存器的值裝載起來，開始運行。

這是一種主動配合式的調度。

2. 搶占

然而，理想很美好，現(xiàn)實很骨感。

這些個程序可能不是那么聽話，可能很久都不調用我們的API交出CPU，甚至可能搞了個死循環(huán)，另一個程序永遠也沒機會執(zhí)行。

看來：不能依賴程序主動交出執(zhí)行權，調度程序需要有搶占CPU的能力！

怎么搶占呢？

我們可以利用時鐘中斷！

因為一旦有中斷事件到來，CPU就得去執(zhí)行中斷處理程序。只要在時鐘中斷的處理函數(shù)里面加入調度入口，就能搶到CPU的執(zhí)行權。

為了公平起見，我們決定讓每個進程都執(zhí)行一小段時間，我們把這個叫做時間片，比如100ms，然后輪流執(zhí)行它們就可以了，差不多是這個樣子：

我們給CPU編程，讓它每1ms發(fā)送一次時鐘中斷。在每個時鐘中斷到來時，檢查當前的線程運行時間是否足夠100ms，如果沒有就將當前線程運行的時間+1ms，然后中斷處理結束，讓它繼續(xù)運行。

如果檢查發(fā)現(xiàn)時間已經到了100ms，就切換另一個進程來運行。

100ms對于人類幾乎感知不到，所以還以為兩個線程是在同時運行。

一個最最最簡單的任務調度程序就完成了。

3. 阻塞

漸漸地，進程多了起來，3個、4個、5個···

我們用一個隊列把它們存起來，先進先出，就叫做就緒隊列吧，意思是準備要排隊執(zhí)行的隊列。

所有就緒的進程，依次排隊被我們的調度程序翻牌子執(zhí)行。

沒過多久，我們發(fā)現(xiàn)有些進程經常占著茅坑不xx，在sleep或者等待鎖的時候，白白霸占著CPU空轉，搞得隊列里其他進程怨聲載道。

那咱們對調度程序再做一個優(yōu)化吧：當有進程等待鎖、I/O等待或者sleep的時候，調度程序也需要介入，即使分配給它的時間片還沒用完，也要讓它主動交出CPU，并把它放到另一個等待隊列里去，等到等待的條件滿足的時候，再把它請回到就緒隊列排隊。

現(xiàn)在，我們的調度程序不再允許有占著CPU卻摸魚的現(xiàn)象發(fā)生。

4. 優(yōu)先級

后來，進程進一步多了起來，6個、7個、···、100個。

每一個進程都執(zhí)行100ms，轉一圈下來就是10000ms=10s。

一個打字程序，按了鍵盤10s鐘之后才反應過來，這系統(tǒng)卡的一匹，簡直沒法用。

我們可以把每個進程執(zhí)行的時間縮短為10ms，轉一圈下來變成了1000ms=1s，情況好了很多，但還是有點卡。

而且這一招架不住進程越來越多，200個，300個，甚至更多，轉一圈的時間還是在變長。

但又不好繼續(xù)壓縮時間，否則就花太多時間在切換上了，真正執(zhí)行的時間變少。

歸根結底，問題在于進程多了以后，再按照順序輪轉不合時宜了。

得讓一些進程擁有VIP特權，能夠優(yōu)先執(zhí)行。

要不這樣吧，給每個進程設定一個優(yōu)先級，從1到40，總共40個優(yōu)先級，數(shù)字越大，優(yōu)先級越高。

調度的時候，把隊列遍歷一圈，找出里面優(yōu)先級最高的進程來執(zhí)行。

現(xiàn)在，我們只需要給打字程序這樣的交互式進程設定一個高優(yōu)先級，再次按下鍵盤后，很快就能得到響應了。

5. O(1)復雜度

每次調度的時候都得去遍歷所有的進程，這復雜度是O(N)。

進程少倒還不打緊，多了以后就有些惱火了，這效率太低了。

讓所有進程一起排在一個大的隊列里，不是一個明智的做法。

要不我們按照優(yōu)先級拆分成不同的隊列吧!每個優(yōu)先級單獨弄一個就緒隊列，就是40個隊列，分開排隊，找起來效率更高。

調度的時候，按照優(yōu)先級順序，依次來看每一個隊列是否有可以執(zhí)行的進程，找到后就從隊列里取出來執(zhí)行，相同優(yōu)先級隊列里面的進程，輪流執(zhí)行。

為了快速知道每一個優(yōu)先級隊列里面有沒有進程，咱們再弄一個位圖，40個bit，每一位表示一個優(yōu)先級隊列，如果是1就知道這個優(yōu)先級的隊列里有進程需要執(zhí)行，為0就沒有。

關于這個優(yōu)先級隊列，差不多可以這樣定義：

struct priority_queue {
    int nr_active;                      // 所有隊列的進程總數(shù)
    unsigned long bitmap[BITMAP_SIZE];  // 位圖
    struct list_head queue[MAX_PRIO];   // 隊列數(shù)組
};

現(xiàn)在找起來可方便了，進程再多也沒事，都可以在O(1)的時間復雜度里找到要調度的進程。

6. 餓死問題

系統(tǒng)運行了一段時間，發(fā)現(xiàn)了一個重要的問題：由于高優(yōu)先級進程的存在，低優(yōu)先級的程序很難得到執(zhí)行機會，容易被“餓死”。

除非高優(yōu)先級的進程執(zhí)行結束，或者在睡眠等待，否則只要它一直待在就緒隊列里，其他進程就沒有機會。

這可不行呀，雖然你優(yōu)先級高，但總得給別人分口吃的吧。

看來進程執(zhí)行完成之后，不能馬上把它再放回原來的隊列里去，得這一輪大家都執(zhí)行過后才行。

不放回原隊列，那放哪里去呢？

干脆再弄一個優(yōu)先級隊列，把它叫做expired隊列，并把原來的優(yōu)先級隊列叫做active隊列。

調度的時候，從active隊列里提取進程。完成一次調度后就把它放到expired隊列，等原來的隊列里的進程都挨個執(zhí)行完一圈，active隊列就空了，它們都來到了這個expired隊列，然后交換兩個隊列，從頭再來。

嗯，為了避免內存拷貝。把active和expired定義成指針，到時候直接交換兩個指針，更省事兒！

把原來的隊列封裝一下：

struct runqueue {
    struct priority_queue* active;
    struct priority_queue* expired;
    struct priority_queue array[2];
};

就這樣，所有進程在兩個隊列中兜兜轉轉，現(xiàn)在低優(yōu)先級的進程也有機會被執(zhí)行到了，不會被餓死了。

7. 優(yōu)先級與時間片

到目前為止，雖然進程有優(yōu)先級之分，但這只影響它們的調度順序，而不影響它們執(zhí)行的時間，所有的進程時間片依然是100ms。

現(xiàn)在，優(yōu)先級高的程序提出了抗議：我執(zhí)行的任務很重要，需要給我更長的CPU時間片!

于是，一個新的需求來了：不同優(yōu)先級進程，運行的時間片需要有區(qū)別。

優(yōu)先級高的，時間片得長一點;優(yōu)先級低的，時間片得短一些。

這個需求倒也好辦，我們以中間優(yōu)先級20為基礎，設定優(yōu)先級為20的進程時間片是100ms，優(yōu)先級每增加1級，時間片+5ms，每減少一級，時間片-5ms。

優(yōu)先級 ---- 時間片
1       5ms
2       10ms
3       15ms
···     ···
18      90ms
19      95ms
20      100ms   # base
21      105ms
···     ···
39      195ms
40      200ms

現(xiàn)在，高優(yōu)先級的進程不僅能夠優(yōu)先被執(zhí)行，給它分配的運行時間也更多了。

上面的時間片分配算法還不算是完美，它有一個問題：

如果現(xiàn)在只有兩個優(yōu)先級為20和21的進程在運行，時間片分別是100ms和105ms，那么兩個進程分別能獲取到的CPU時間占比是100/(100+105)=48.7%和105/(100+105)=51.2%。

優(yōu)先級增加1，CPU時間占比多了2.5%，看起來沒什么問題。

現(xiàn)在如果換成只有兩個優(yōu)先級為1和2的進程在運行，時間片分別是5ms和10ms，那么兩個進程分別能獲取到的CPU時間占比是5/(5+10)=33.3%和10/(5+10)=66.7%。

優(yōu)先級2只比優(yōu)先級1的進程高了一級，獲取的CPU時間占比就翻了一倍!

同樣是優(yōu)先級加1，這差距咋就這么大呢？

說好的公平呢？

8. 公平調度：時間分配

現(xiàn)在，我們換個思路，不用絕對時間片，而用相對時間片。

比如設定我們的調度周期為100ms，這100ms讓所有可以運行的進程來瓜分，100ms之后所有就緒的進程都被執(zhí)行了一圈兒。

那么問題來了，如何讓進程們來瓜分這100ms呢？

當然是按照優(yōu)先級來分。

我們給不同優(yōu)先級的進程設置不同的權重，優(yōu)先級高的，權重值高，就多分一點兒，優(yōu)先級越低的，權重值低，就少分一點兒。

那這個權重值設定為多少好呢？

別急，有人已經幫我們想好了，就是下面這個數(shù)組。

想知道為什么是這些數(shù)字而不是別的，是有講究的，不過先不用管。

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

現(xiàn)在，各個進程按照自己優(yōu)先級對應的權重，來從這100ms的調度周期里來分配時間。

不知道你發(fā)現(xiàn)沒有，如果進程特別多，那可能分下來的時間就會很少。咱們還得設定一個最小值，不然一天天的凈跑去調度切換了，真正執(zhí)行的時間少了。

這個最小值，就是進程至少得運行這么久才能切換。

9. 公平調度：進程選擇

時間分配的問題解決了，還有一個問題：調度的時候，如何挑選下一個需要執(zhí)行的進程呢？

前面我們按照權重來給大家分配了時間，但肯定有一些進程，因為I/O、鎖、睡眠等原因沒有把分配的時間用完，這一些進程應該得到補償，一旦它們符合執(zhí)行條件后，應該優(yōu)先被執(zhí)行。

主動放棄了CPU的進程，它們運行的時間肯定比分配的短。要不，按照進程運行的時間來排個序，挑選時間最短的進程來運行？

但是，不同進程優(yōu)先級不一樣，分配到的時間本來就有長短啊。

要是能夠消除因為權重造成的時間分配長短不一問題就好了，就能用運行時間來排序了。

要不咱們再弄一個虛擬運行時間，把權重帶來的影響再給修復回去？

比如優(yōu)先級高的進程，分配的時間多，統(tǒng)計它的運行時間的時候，就讓它流逝的慢一些。

而優(yōu)先級低的進程，分配的時間少，統(tǒng)計它的運行時間的時候，就讓它流逝的快一些。

這樣所有進程在沒有任何睡眠、等待、I/O的情況下，大家都是用完了自己的時間，消除權重后的虛擬時間都應該是一樣一樣的，都是整個調度周期的1/N！

這才叫公平嘛！

現(xiàn)在只需要把所有進程按照虛擬時間來排個序，排在前面的虛擬時間短，調度的時候就選擇它來運行。

好主意，那用什么樣的數(shù)據(jù)結構來組織管理進程呢？

數(shù)組？插入不方便。

鏈表？尋找插入位置的時候時間復雜度是O(N)。

用二叉搜索樹貌似是個不錯的方案。左節(jié)點虛擬時間比父節(jié)點和右節(jié)點的虛擬時間小，只要找到最左邊的節(jié)點就是要調用的進程，時間復雜度是O(LogN)。

但二叉搜索樹有個毛病，一個不小心就容易變成一棵“跛腳”的樹，這時間復雜度就又上去了。

紅黑樹沒有這個問題，它自帶平衡性，要不就它吧！

根據(jù)虛擬時間來把所有待運行的進程組織成一棵紅黑樹，只要找到整棵樹最左邊的節(jié)點，就是要運行的進程。

不過為了更高效，樹調整更新導致最左邊節(jié)點發(fā)生變化的時候，把它給緩存起來，這樣調度的時候就直接拿到這個緩存節(jié)點就好了。

完美！

總結

上面講述的進程調度模型其實就是Linux中O(1)調度算法和CFS(完全公平調度算法)調度算法的雛形，為了便于理解，文中進行了一定程度的簡化。包括但不限于：

• 在實際的Linux中，進程優(yōu)先級有140個，分為實時進程和非實時進程。
• 在實際的Linux中，進程通過一個叫nice值(對其他進程的友好度，nice越大，越友好，越謙讓，優(yōu)先級越低)的東西映射到優(yōu)先級，優(yōu)先級數(shù)字越大，優(yōu)先級反而越低。
• 在實際的Linux中，進程的優(yōu)先級分為靜態(tài)和動態(tài)，是會隨著運行而變化的，不是固定不變。
• 在多核模式下，為了防止加鎖帶來的性能損失，每一個CPU核都有自己的調度隊列。
• 在實際的Linux中，參與調度的是線程，而不是進程。但在早期的Linux中，沒有線程的概念，調度就是基于進程來進行，引入線程后，線程又稱為輕量級進程?，F(xiàn)在我們平時所說的進程和線程在語義上有所不同，這一點要注意區(qū)別。

看完了這篇文章，再去看Linux的調度算法，應該會輕松不少。