Linux性能優化10：理解Linux調度模型

[介紹]

這一篇介紹一下Linux的調度模型，作為調優考慮問題的參考。

這不是說要介紹Linux現在具體調度演算法，Linux代碼最大的特點就是「不斷變化」，所以，介紹一個兩個的調度演算法不能解決調優的問題，我們要理解的是這些演算法背後不變的東西，然後根據情況看代碼才有意義。

[單核調度]

Linux的調度演算法換過很多次了，最新的調度演算法稱為CFS（完全公平調度器），在我們介紹這個演算法的特點前，我們先理解一下調度器到底解決什麼問題。

從一個線程切換到一個線程是平台相關代碼，原理也比較死板簡單，就是把上一個線程的CPU環境全部保存在TCB上，然後把下一個線程的TCB恢復到CPU寄存器中。這個不是調度器的重點。調度器的重點是選哪個線程投入運行。所以，嚴格來說，調度器是個數學問題：我給你一組參數（比如線程的優先順序，使用了的時間等），你告訴我下一個要運行的線程是誰。

首先，休眠或者掛起的任務是不需要調度的，所以，理論上，我們可以認為，調度器只需要考慮需要運行的線程，這種線程的數量，就稱為CPU當前的load。正如我們在這個系列的第一個文檔中說的，這是調度隊列的「長度」。

CPU把什麼線程投入運行呢？這個問題在RTOS中是很好解決的，就是按優先順序唄，誰的優先順序高就誰運行，一直運行到這個線程不需要CPU為止。我們以前招過一位來自老牌伺服器OS的專家來帶領我們的OS開發團隊，這個專家和我們討論調度演算法的時候就說：RTOS的調度器有什麼好做的？玩來玩去不就那麼點東西？這種說法顯得有點驕傲了，但至少說明，在這些老牌伺服器OS的人眼中，是不把實時調度演算法看作是調度器要解決的主要問題的。

我們真正要解決的是SCHED_NORMAL的線程如何調度。自然的想法是按時間片，每人50ms，一路執行過去即可。 這就是CFS的所謂「公平」的含義：大家都用那麼多時間，誰也不要虧欠誰。但這樣帶來一個基本的問題：比如你有200個線程，每人執行50ms，其中你有一個編輯器，那麼你在這個編輯器上敲一個a，這個a得10秒以後回顯給你——這個系統怎麼用？

一個簡單的補救是，把這個線程定義為實時線程，這樣，這個線程會優先得到調度。但伺服器不是嵌入式系統，伺服器是不能這麼乾的。因為伺服器是通用系統，如果隨便一個編輯器就是實時線程，那很輕鬆就可以用一個編輯把這個CPU完全佔用了，別的程序就不用跑了。所以每一代Linux調度器都要解決這個最基本的問題：找出誰是「編輯器」。這種線程，調度器稱為「交互線程」，如果你看的是Linux傳統的O(1)調度器，或者更早的調度器實現，調度器是有明確的交互線程的概念在演算法中的。其基本原理是挑出每次都用不完自己時間片的線程。提升這種線程的優先順序，這種就是交互線程。

CFS沒有這個問題，CFS的演算法是這樣的：給每個在調度隊列中的線程一個vruntime的變數，記錄這個線程運行了多久，每次調度，都調度vruntime最小的線程，這樣，自動優先執行的就是交互線程了。

這是理解Linux調度器的基礎，無論哪個演算法，Linux必須保證交互線程優先得到調度。然後才考慮其他問題。這是我們調優調度問題的基礎。

有了這個基礎，線程的nice值就僅僅是個如何加權的問題了。比如在CFS演算法中，nice值作為vruntime流逝的加權， 這個nice大的進程時間流逝就快，它佔據的時間片就少了。

[多核調度]

多核調度其實是單核調度演算法的複製。多核的CPU其實互相是看不到對方的，CPU不過就是一條指令一條指令向下執行。所謂多核調度，就是每個CPU有一個run queue（下面簡稱rq），創建線程（下面簡稱task）的時候把線程扔到一個rq中，那個CPU就對這個rq執行單核的調度演算法而已。

當然，那個僅僅是基礎。多核調度還有一個任務是平衡調度。就是一個核特別忙，另一個核特別閑，就需要把task從一個核遷移到另一個核的runqueue中。

遷移要考慮的問題比前面說的這個模型複雜，因為有很多額外的要素要考慮：比如，一個核的兩個超線程，它們共享相同的執行部件，很多時候平衡它們是沒有意義的。又比如說，兩個CPU，有不同的L2 Cache，你輕易切換它們，就有可能發生大量的Cache失效。還有，如果你把線程從NUMA系統的一個Node遷移到另一個，就把它的內存和它運行CPU拉遠了，這會直接降低這個線程的執行性能。

所以Linux把線程組織在多個不同的sched_domain中，每個domain包含一組線程，每個domain有自己獨立的演算法，這些演算法自行決定是否進行調度平衡。我們可以通過lscpu看CPU的組成結構，但真正有哪些domain，以及domain的參數，則需要看/proc/sys/kernel/sched_domain（或者簡單一點可以看/proc/schedstat）。

不過要我說，如果你不能看懂調度演算法，其實只要記住兩個技巧就好了：

1. 通過ftrace跟蹤sched:sched_migrate_task跟蹤任務轉移的頻度

2. 把老切換的任務綁定在特定的核上

其他問題還是留給調度器專家吧。

[功耗問題]

在伺服器上，我們一般只關注通量和時延，但現在的調度器開始要關心功耗問題了。這個真的讓這個問題變成一個數學問題了。功耗要考慮的要素包括幾個：

1. 休眠：CPU休眠就可以降功耗，那麼你是把兩個任務放兩個CPU上以便提高速度呢？還是把它們合併到一個CPU上讓其中一個CPU休眠呢？

2. DVFS：CPU可以調頻來降功耗，還是那句話，你是把兩個任務合併到一個CPU上，讓另一個休眠呢，還是分在兩個CPU上，讓兩個一起降頻呢？

3. CPU熱插拔：休眠可以降功耗，但比不上把這個CPU直接下電，但下了電，要恢復就很不容易了，那你要更快恢復還是要降功耗呢？

ARM現在嘗試通過AWS項目（Energy-Aware Scheduling (EAS) Project）把這三個要素整合在一起。但最終內核會修改成什麼樣子，還有待觀察。在EAS可以商用前，每個手機還要考慮自己用那種策略去聚合前面的要素。

謝天謝地，我現在不用搞手機了：）