1. 任務切換

現在有一塊CPU，但是有兩個程序都想來執行，我們需要開發一個任務調度程序。

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

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

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

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

2. 搶占

然而，理想很美好，現實很骨感。

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

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

怎么搶占呢？

我們可以利用時鐘中斷！

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

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

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

如果檢查發現時間已經到了100ms，就切換另一個進程來運行。

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

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

3. 阻塞

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

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

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

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

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

現在，我們的調度程序不再允許有占著CPU卻摸魚的現象發生。

4. 優先級

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

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

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

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

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

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

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

得讓一些進程擁有VIP特權，能夠優先執行。

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

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

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

5. O(1)復雜度

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

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

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

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

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

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

關于這個優先級隊列，差不多可以這樣定義：

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

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

6. 餓死問題

系統運行了一段時間，發現了一個重要的問題：由于高優先級進程的存在，低優先級的程序很難得到執行機會，容易被“餓死”。

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

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

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

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

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

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

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

把原來的隊列封裝一下：

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

就這樣，所有進程在兩個隊列中兜兜轉轉，現在低優先級的進程也有機會被執行到了，不會被餓死了。

7. 優先級與時間片

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

現在，優先級高的程序提出了抗議：我執行的任務很重要，需要給我更長的CPU時間片!

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

優先級高的，時間片得長一點;優先級低的，時間片得短一些。

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

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

現在，高優先級的進程不僅能夠優先被執行，給它分配的運行時間也更多了。

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

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

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

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

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

同樣是優先級加1，這差距咋就這么大呢？

說好的公平呢？

8. 公平調度：時間分配

現在，我們換個思路，不用絕對時間片，而用相對時間片。

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

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

當然是按照優先級來分。

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

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

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

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

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

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

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

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

9. 公平調度：進程選擇

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

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

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

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

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

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

比如優先級高的進程，分配的時間多，統計它的運行時間的時候，就讓它流逝的慢一些。

而優先級低的進程，分配的時間少，統計它的運行時間的時候，就讓它流逝的快一些。

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

這才叫公平嘛！

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

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

數組？插入不方便。

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

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

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

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

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

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

完美！

總結

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

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

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