The Linux Scheduler: a Decade of Wasted Cores 譯文一

2019 年 11 月 4 日
筆記

摘要

作為資源管理的核心部分，OS的執行緒調度器必須保持下面這樣簡單，不變的特性: 確保ready狀態的執行緒總是被調度到有效的CPU核上。雖然它看起來是簡單的，我們發現這個不變性在Linux上經常被打破。當ready狀態的執行緒在runqueue中等待時，有些CPU核卻還會空閑幾秒。以我們的經驗，這類性能方面的問題會導致重度依賴同步的應用的性能成倍的下降，針對Kernel編譯會多造成高達13%的延遲，針對廣泛使用的商用資料庫會造成23%的吞吐量降低。傳統的測試技術和調試工具對於確認和了解這類問題是無效的，因此這些問題的癥狀經常是難以捕獲的。為了能夠推動我們的調查，我們構建了新的工具來在線檢測這種違反不變性的情況並且將調度行為可視化。這些工具是簡單的，易於在多個kernel版本間移植的並且使用的代價很小。我們相信這些工具將成為內核開發者工具鏈的一部分來幫助其避免這類問題的出現。

引言

你必須要明白沒有多少東西比調度器還古老。這也恰恰是調度是容易的另一個證據。 Linux Torvalds, 2001

經典的調度問題圍繞著設置調度量的長度來提供互動式響應，並同時最小化上下文切換的開銷，在單一系統中同時提供批處理和互動式工作負載，同時需要有效地管理調度器的運行隊列。到了2000年，作業系統的設計者認為調度是一個已經被解決的問題。Linux Torvalds的引文也是當時這一普遍觀點的準確反映。

到了2004年，我們步入了多核時代並且能效成為了電腦系統設計中的首要問題。很多事情又一次使調度器變得有趣起來，但同時也讓它變得更複雜和更容易出錯。

我們最近使用Linux調度器的經驗是關於壓榨現代硬體設備的性能挑戰上，比如NUMA的訪問延遲，cache一致性和同步的高成本，分散的CPU和記憶體的延遲，導致調度器的實現異常複雜。其結果就是，確保可運行的執行緒使用空閑CPU核的這一調度器的最基本功能，被忽視。

這篇論文的主要作者發現並研究了Linux調度器的四個性能問題。這些問題導致Linux調度器在有可運行執行緒等待轉變成運行狀態的情況下還使CPU核空閑。導致針對典型的Linux工作負載情況，其性能下降了13-24%，在某些極端場景下性能下降138倍之多。因為這些問題對kernel子系統造成了損傷，會導致大的甚至是巨大的性能下降，並且它們逃避掉了傳統的測試和調試技術，搞清楚他們的本質和起源是很重要的。

這些問題是不同的根本原因，但是他們的外在表現都是一樣的。這個調度器在有可運行的執行緒在運行隊列中等待的時候無意間並且是長時間的讓CPU核處於空閑狀態。短期內出現這種情況是可以允許的：這個系統臨時進入到某種狀態，比如執行緒退出或者阻塞或者一個執行緒剛創建或者變成非阻塞。如果是長期的那就不是我們所期待的行為了。這個Linux調度器永遠不應該在有工作可作時讓CPU核空閑。這種現象如果長期存在，是沒有意義的：它會導致bug並且損害性能。

我們提出了這些問題的解決方案，並且觀察到性能的實質性改善。同步密集型的應用的速度有了數倍的提升；一些記憶體屏障敏感性的科學應用運行速度有了高達138倍的提升。Kernel編譯和在廣泛使用的商用DBMS系統上跑的TPC-H工作負載性能提升了13%-14%。受bug影響最大的TPC-H查詢速度提高了23% 。

偵測到這些bug是困難的。它們不會導致系統崩潰或者掛起，但是卻會吞掉系統性能，而且這種行為經常是很難使用標準性能監控工具來通知的。針對 TPC-H工作負載，比如這種現象發生的時間可能貫穿執行的始終，但是每一次它可能僅僅有幾百毫秒，這對於像htop, sar或者是perf這些工具來說偵測時間太短了。即使這種現象的發生持續很長一段時間，這個根本原因還是很難發現的，因為它可能是這個調度器的多個非同步事情共同作用的結果。

當我們在TPC-H資料庫工作負載中觀察到不能解釋的性能問題時，我們初步懷疑是調度器的bug。傳統的工具不能幫助我們確認或弄清楚它們的根本原因。為了搞明白這一些，我們設計了兩個新工具。第一個工具我們稱為「sanity checker」, 周期性的檢測前面提到的不變數的違規操作，在當前系統中捕獲bug並且為離線分析收集相關資訊。第二個工具為了加速調試能夠可視化調度行為。這兩個工具都很容易在從Linux 3.17到 4.3的內核版本間移植，運行它們的開銷很小，把它們保留在標準工具鏈里能夠幫助減少此類bug的發生。

Linux 調度器

我們首先討論一下Linux的完全公平調度演算法在單核，單用戶系統上是如何工作的。從這個角度看，這個演算法是相當簡單的。接著我們會解釋現代多核系統的限制是如何強迫開發者繞過潛在的性能瓶頸的。

在單CPU系統上，CFS是相當簡單的

Linux的CFS是一個加權公平隊列調度演算法的實現，它將一個有效的CPU周期按權重比例分配給各個執行緒。為了支援這個抽象，CFS像其他大多數CPU調度器一樣將CPU切分成時間片分到運行中的執行緒。完成這個調度器的關鍵討論是：如何確定執行緒的時間片和如何選擇下一個被調度執行的執行緒。

這個調度器定義一個固定的時間間隔，在這個間隔期間系統中的每一個執行緒都至少要運行一次。這個時間間隔按權重比例被分配到各處執行緒。這個被分配後生成的時間間隔我們就叫作時間片。一個執行緒的權重本質上就是它的優先順序，或者是UNIX系統所說的niceness。有更低niceness值的執行緒有更高的權重，反之亦然。

當一個執行緒運行時，它會統計其vruntime(這個runtime就是這個執行緒按其權重被分配到的運行時間)。一旦一個執行緒的vruntime超過了它被分配的時間片，如果此時有其它可運行的執行緒，那麼當前這個執行緒將被從當前執行緒搶佔。如果有最小的vruntime值的其它執行緒被喚醒，那麼光前這個執行緒也可能被搶佔。

所有的執行緒都被組織進用紅-黑樹實現的運行隊列中，且按照它們的vruntime遞增順序排序存儲。當一個 CPU是查找一個新的執行緒來運行時，它就直接獲取這個紅-黑樹最左側的葉子節點，因為這個節點包含的執行緒有最小的vruntime。

在多核系統上，CFS變得相當複雜

在多核環境中這個調度器的實現要變得複雜得多。需要使用pre-core的運行隊列來解決伸縮性問題。採用pre-core 運行隊列的動機是在上下文切換時，CPU核只訪問其本地的運行隊列。上下文切換處在關鍵路徑上，因此它的執行必須快。僅僅訪問本核的隊列能夠避免調度器遇到潛在的同步訪問的代價，如果沒有pre-cpu的運行隊列，那隻能訪問全局共享的運行隊列，這會有加鎖的代價。

然而，在存在pre-cpu運行隊列的情況下為了使調度演算法依然有效和正確，這個運行隊列必須保持平衡。考慮一個有兩個運行隊列的雙核系統，它的運行隊列是不平衡的。假設一個隊列有一個低優先順序的執行緒並且另一個有10個高優化級的執行緒。如果每個核只從自己的運行隊列來查找運行的執行緒，那麼高優先順序的執行緒獲取到的CPU時間將遠少於低優先順序的執行緒，這不是我們希望看到的（譯者註：在相同的CPU周期內，低優先順序任務獨佔它自己的一個核，高優先順序的10個任務瓜分另一個核的一個CPU周期，這樣分配一個高優先順序任務上的時間片就很少了）。我們可以讓每個核不僅只檢查他自己的隊列，同時也檢查其他核的隊列，但這樣又背離了per-code運行隊列的目的。因此，Linux和其他的調度器都會周期性的運行負載均衡演算法來保持各隊列大致的均衡。

從概念上講，負載均衡是簡單的。在2001年， CPU大部分還是單核的並且商用服務系統典型的還只有很少的處理器。因此，很難預知現代多核系統負載均衡將變成挑戰。負載均衡對於今天的系統來說是很昂貴的過程，從計算角度講，它需要遍歷所有的運行隊列，從通訊的角度講，它會更改最新快取數據，導致非常昂貴的cache miss和同步。其結果就是，調度器應竭力避免經常的負載均衡操作。同時，如果不經常性的負載均衡又會使運行隊列不均衡。當這種情況發生時，即使有工作需要作，有些核也可能變成空閑狀態，從而降低性能。因此除了周期性的負載均衡外，調度器可以僅在有核變為空閑時作「緊急」的負載均衡，並且在新執行緒創建或者喚醒時作負載均衡邏輯。如果有工作可以作，這個機制可以保證各個核保持忙碌狀態。

接下來我們會來描述下負載是如何工作的，首先我們來解釋下這個演算法並且講解下使這個調度器保持低開銷和節能方面的優化。最後我們展示一下一些優化使程式碼變得更複雜並導致了bug。

負載均衡演算法

弄明白負載均衡演算法的關鍵是這個CFS調度器用來跟蹤負載的metric。我們先解釋下這些metric，然後描述下這個實際的演算法。

一個假的負載均衡演算法只是簡單的確保每個運行隊列有大致相同數量的執行緒，這不是我們想要的。考慮這樣一個場景，有兩個運行隊列，其中一個有一些高優先順序的執行緒，另一個是同樣多的低優先順序執行緒，然後這些高優先順序執行緒將得到與低優先順序執行緒同樣多的CPU時間，這不是我們希望的。均衡應該是基於執行緒權重的，而不是基於它們的數量的（因此，這個load metric不應該只是執行緒的數量）。

不幸的是，僅僅依據執行緒權重來均衡負載是不夠的。考慮這樣一種場景，有十個執行緒在兩個運行隊列里：一個執行緒是高優先順序的並且另外九個是低優先順序的。讓我們假設這個高優先順序執行緒的權重是低優先順序的九倍。如果依據執行緒權重作負載均衡，一個運行隊列將包含這個高優先線執行緒，另一個運行隊列將包含其餘的九個執行緒，這恰好是我們希望的。然而，假設這個高優先順序執行緒經常會有短暫的睡眠，因此這第一個核將經常空閑。這個核就會頻繁地從其他的核來拉取任務來保持自己的忙碌狀態。然而我們不希望這是一種常態，因為它破壞了per-coer運行隊列的設計目的。考慮到實際上高優先順序執行緒不需要整個核，我們實際希望的是通過一種更聰明的方法來均衡運行隊列。

為了達到這個目的，CFS不僅僅基於權重來均衡運行隊列，它還基於稱為load的metric來作均衡。它組合了執行緒的權重和平均CPU使用率。如果一個執行緒沒有使用太多的CPU，它的負載將會相應的降低。

另外，這個負載跟蹤指標的統計也要考慮在不同進程中的多個執行緒。考慮這樣一種場景，我們有一個進程，它有大量的執行緒；另一個進程只有少量的執行緒，那麼第一個進程分配的CPU時間將遠遠大於第二個進程。這是不公平的。因此在Linux 2.6.38版本增加了組調度特性來使執行緒組之間調度趨於公平。當執行緒屬於某個cgroup時，它的負載將進一步除以這個cgroup組裡的執行緒數上計算得出。這個特性後來擴展為將屬於不同ttys的進程自動賦給不同的cgroup。

一個基本的負載均衡演算法將比較所有核上的負載然後將任務從負載高的核遷移到負載低的核。不幸的是，這將導致執行緒在機器上遷移，沒有考慮到快取本地化或者NUMA架構。作為替代，負載均衡器將使用分層策略。我們先來將一下分層調度域的概念。

1.jpg

在上面這張圖中，這個機器上有32個核，四個node, 這個node8個核並且SMT層是在核間共享的。這四塊灰色區域表示相對於機器的第一個核心的調度域。第二層是一個由三個node組成的組，因為這三個node從第一個核開始都可以在1跳內到達。在第四層，我們擁有這機器上的所有node,因為它們都可以在兩跳內到達。

上面這個是原文的直譯，我覺得沒能很好的表達出分層調度域的概念，我們再簡要地說明下。先說明一個目前的電腦CPU架構: 機器上可以用多個處理器，每個處理器又可以有多個核心，每個核心又可以開啟超執行緒技術來點亮邏輯CPU，上面這個架構基本可以說成是SMP架構，多個SMP架構又可以構成NUMA架構。上面說的這些每一個層次都可以作為一個調度域。我們用下圖（借了dog250的圖，誠表謝意，若侵刪）表示：

2.jpg

越向下的層級，在其內部遷移執行緒的代價越小，因此負載均衡盡量在最低層級內完成。

我們來看下負載均衡演算法的偽碼。如下圖是針對每個CPU的負載均衡演算法：

3.jpg

負載均衡演算法針對每一個調度域都會運行，並且是從調度域的低層級向高層級運行。在每一層次，調度域中的一個核負責均衡這個負載。如果當前調度域中有空閑的核可以用來作負載均衡，那此時就選取出這個空閑核中的第一個，或者調度域中剩餘核的第一個（Line 2-9）。接下來，計算當前調度域中每個調度組的負載，然後選出一個最忙的組。如果這個最忙組的負載小於當前本地group的負載，這一層的負載被認為是均衡的（Line 16）。否則，需要在這個本地CPU和最忙CPU間作負載均衡。如果有tasksets存在，不能作均衡，我們需要重新返回到Line 18行，選取新的最忙的CPU。

負載均衡演算法優化

調度器針對給定的調度域通過在指定的核上運行負載均衡演算法來避免重複性工作。當每個活動的核接收到周期性的時鐘中斷時開始運行負載均衡演算法，它首先會檢查它自己是不是這個域內的最小編號的核或者是否是最小編號的空閑的號。如果這個條件滿足，這個核被認為是這次負載均衡操作認定的核，開始負載均衡操作。

能耗相關的優先是進一步減少空閑核上負載均衡的頻率。起初空閑核總是被每次時間周期喚醒並且運行負載均衡演算法。但在Linux 2.6.21版本後多了一個選項（現在已經是默認行為）來避免周期性的喚醒睡眠的核：它們會進入到tickless空閑狀態，每種狀態下能夠減少能耗。這種狀態下的核心獲取到工作的唯一方法是被過載的其他核喚醒。為了作到這一點，在每一個調度時鐘周期內，如果一個核認定自己是過載的，它將檢查此時系統中是否存在tickless狀態的空閑核並且將NOHZ balancer的規則施加其上。這個NOHZ均衡器核心負責在每一個時鐘周期內運行自己的周期性負載均衡程式，並且代表了所有無時鐘的空閑的核心。

在周期性負載均衡之上，調度器在執行緒被喚醒時也會作負載均衡。睡眠或等待特定資源後，這個執行緒被喚醒，調度器嘗試將它放入一個空閑核。當這個執行緒被另一執行緒喚醒後，一個特殊規則將被應用，在這種情況下調度器在選擇核時偏愛這個喚醒者所有的核，這樣有利用cache復用。