YVR18資料關注點5：當前的Linux調度器設計

來自專欄軟體架構設計23 人贊了文章

演講220對Linux當前的調度器做了一個科普，感覺不深不淺的，不知道對大部分讀者是否具有參考價值。我對來說，已經很久沒有看Linux的調度器了，很多原來沒有很明確的概念，經過這些年的發展，現在變得非常清晰，所以參考價值還是挺大的。我就著這個演講描述的概念，以及我自己掌握的一些東西，為這裡的讀者普及一些Linux調度器的初步知識，也算是我自己對這部分信息的一個總結吧。

我們先來理解一下調度器面對的問題。我不知道沒有寫過調度器的讀者是否會和我一樣，在我自己做操作系統設計之前，比如在學校學習操作系統原理的時候，我對調度器的認識，有一個很大的誤區，似乎調度器是「決定把哪個進程投入運行」的一個演算法，但實際上，它是「決定把哪個要運行的進程投入運行」的一個演算法。這句話聽起來一樣，其實是不一樣的，後者意味著，在每個調度「時刻」，你只需要管要運行的進程，不用管其他進程。我們很容易從一個時間廣度上考慮這個問題，覺得調度器需要考慮所有的進程的狀態，實際上調度器只考慮現在就可以運行的進程的狀態，演算法只需要考慮在調度序列中的進程，其他進程，都是不管的。這個現在單獨跟你說，你會覺得「這誰不知道啊」，但等你看演算法的時候，你可能就暈菜了。我們先把這個前提放在這裡，以便讀者後面更容易理解概念。

其實也正因為這個理解不同，我們更多人能接受「CPU佔用率」這個概念，而不是Load這個概念，CPU佔用率是時間廣度的，是人的概念，而Load是一個時刻深度的，是調度器的概念。人關心的是某段時間內，CPU的利用率有多高，一個時刻是沒有CPU佔用率這個概念的。而調度器關心的是現在還有多少了進程等著被我調度，我讓誰先上來，所以，這些被等著調度的進程，就是我的Load。

理解CPU佔用率和Load的分別，我們就會發現，調度器其實比我們想像中簡單，因為調度器是不考慮你的歷史的，調度器考慮的是你這個進程加入到我的調度中後，我把你排在第幾位執行，如果你休眠了，你的歷史就被清除了，我才不在乎你過去用了多少CPU呢（其實不完全是這樣，但我們先這樣理解）。

有了這些基礎，我們現在來理解一下調度器面對的問題。首先，我們有一些任務是很重要的，如果它要運行，就必須讓它先運行。這我們稱為實時任務。實時任務是最容易處理的。我剛入行的時候，一位做Unix OS的前輩就跟我說，RT調度器那就是玩具，基本上就讓它先執行就好了。同是RT進程的話，也只有Round Robin和FIFO兩種演算法，如何工作你猜都能猜到，最多就是補充一些優先順序反轉之類的保護，基本上沒有什麼值得發展的。這部分的演算法，本文也會忽略。

難的是普通的任務怎麼調度。一個簡單的思路，根據任務的優先順序（nice），每個任務給定一個調度時間片，然後每個任務用完自己的時間片，就等著，等到所有的任務都用完自己的時間片了，就重新開始。

但你真的按這樣的方法來試試，你就會發現，你這個系統基本上不可用。為什麼呢？因為任務有兩種，一種是io bound，一種是cpu bound的。io bound的任務處理io，cpu bound的是長時間執行，只是在消耗CPU。如果你平等地對待他們，每個任務執行50ms，10個cpu bound的任務，1個shell，然後你在shell上按下一個a，這個a要等500ms才能回顯出來，這玩意兒沒法用。要保證io bound的進程在前面，否則這東西沒法用。這是大部分普通調度器要解決的問題。

Linux在O(1)之前的調度器基本上是個玩具，那個東西我們就忽略了。我們先看O(1)調度器的原理。從名字就能看出來，O(1)演算法是要保證取下一個運行任務的時候，演算法複雜度是O(1)，它用這樣的數據結構：

待運行的任務都掛在Active隊列下面，每個Active分優先順序Hash開，在用一個bitmap標記哪個隊列中有任務，這樣，要投入運行，只要檢查一下bitmap，然後拿那個隊列的第一個任務運行就可以了（這就是這個演算法稱為O(1)的原因）。當一個任務的時間片用完了，就改掛到Expired隊列。等Active隊列空了，就把兩者換過來，問題就遞歸了。

這個演算法最大的破綻你也看到了，它區分不了誰是io bound進程。所以O(1)演算法有一個非常不好看的補充演算法，主要是根據每個任務是否能用完自己的時間片就離開調度隊列，如果是這樣，調度器就「補償」它，提高它的Effective優先順序，這樣，它回來的時候，就可以比較早得到調度了。我以前玩得比較多的就是這個演算法，這個東西經常錯判，而且很難調試。後來，它就逐步被CFS取代了。

CFS在2.6.23開始引入內核，在2.6.30徹底取代了O(1)演算法。它引入的變化首先是用sched_class把不同的調度演算法徹底分開了。正如演講220中提到的，現在調度分了兩層，先按調度類別分類，優先調度高優先順序類別的任務。這樣，我們做普通調度的時候，就不再需要考慮比如實時任務這樣的任務了。

比如現在的內核中就包含了這些類別：

STOP：系統任務，比如RCU，ftrace，核間遷移。這些任務凌駕於所有其他任務有限調度

DL：Dead Line任務，這些任務有「必須什麼時候完成」這樣的訴求，所以在所有客戶任務中優先調度

RT：就是過去的實時任務了

CFS：這才是普通的任務調度

IDLE：這是IDLE任務swapper/N

這一層的原理非常直白了。

然後，我們仍單獨理解CFS。完全公平調度。首先我們理解一下什麼是「完美的公平調度」，比如說，你有4個任務a, b, c, d，分別要運行4,4,8,12毫秒，CPU的時間片單位是4ms。

那麼前四個4ms，應該是a, b, c, d每個周期各運行1ms，第五、六個4ms，a，b不在了，c，d應該每個周期各運行2ms，這樣，c也運行完了，剩下的d，再運行第七個4ms，把4ms全部用完。這樣就是完美的完全公平。

但我們做不到，因為我們不能無時無刻去比這些時間。所以，CFS就是一種「盡量公平調度的方法」，每次到了一個調度點（比如時鐘中斷），它馬上算一下現在的任務花了多少時間，把這個時間加到它的vruntime中，之後調度的時候，總是取一個vruntime最短的任務來執行。

這樣，天然地，運行得最少，經常休眠的任務的優先順序就會變高，總是優先得到調度了。

這個演算法純從計算上逼近iobound進程優先執行。比O(1)演算法可控多了。

但它的破綻也是很明顯的，如果你要裝你是個iobound進程，你只要避開vruntime的計算點，每次休眠一點點時間，就能保持你的優先順序。

所以，實際上CFS還有很多補充演算法來解決很多具體的問題，但無論如何，這個模型還是比O(1)可控。

其實吧，也沒有保證能公平的調度演算法，這最後基本上就是調整出來的。也許等待AI的影響力足夠強，這東西應該是通過神經網路自動訓練出來的？