The Linux Scheduler: a Decade of Wasted Cores
The Linux Scheduler: a Decade of Wasted Cores
這是一篇介紹Linux調度問題的文章，源自這篇文章。文章中涉及到的一些問題可能已經得到解決，但可以學習一下本文所表達的思想和對CPU調度的理解。
這是EuroSys 2016系列論文中的第一篇，講述了三個部分：首先，介紹了Linux內核調度任務的背景；其次，介紹了軟體老化以及修改需求和維護是如何導致程式碼腐化的；最後，作者給出了Linux調度的四個錯誤，這些錯誤導致即使在有大量任務等待調度的前提下，仍然有CPU核處於空閑狀態。因此，論文題目為”A Decade of Wasted Cores.”
在我們的實驗中，這些性能錯誤會導致大量重同步的應用的性能下降數倍，增加13%的內核延遲，並導致通用的商用資料庫的吞吐量下降14-23%。
Linux調度的演化
總的來說，到2000年為止，作業系統設計者考慮到調度是一個需要解決的問題，2004年終結了Dennard 縮放比例定律，迎來了多核時代，使能效成為電腦系統設計中的頭等大事。這些事件使調度器再度熱門起來，但同時也增加了複雜度，且經常會導致調度失效。
Linux使用完全公平演算法(CFS)，該演算法使用了一個基於權重的公平隊列。想像在單獨的CPU系統上：CFS會給運行的執行緒分配時間片。該演算法為系統上的每個執行緒設置了一個每次運行固定的最小運行間隔，該間隔會除以分配給執行緒的權重，進而算出時間片。
一個執行緒的權重本質上是其優先順序，或UNIX上的
nice值。具有最低nice值的執行緒具有最高的權重，反之亦然。
一個運行的執行緒會累積vruntime (runtime / weight)。當一個執行緒的vruntime 超過分配給它的時間片後，該執行緒將會被搶佔。
執行緒會被組織在CPU的run隊列中(該隊列使用紅黑樹實現)，並按照vruntime從小到大排序。當一個CPU查找一個新執行緒運行時，它將選擇紅黑樹中最左側的節點，即具有最小vruntime的執行緒。
到目前為止一切正常，下面考慮一下多核系統。
首先每個核都有一個run隊列，這樣可以快速地切換上下文。現在出現了一個新的問題，需要在多個run隊列中進行負載均衡。
考慮一個具有兩個run隊列且不會進行負載均衡的雙核系統。假設一個隊列包含1個最小優先順序的執行緒，而另外一個隊列包含10個高優先順序的執行緒。如果每個核僅從本地run隊列中查找執行緒，那麼高優先順序的執行緒可能會獲得比低優先順序執行緒更少的CPU時間，這是不我們想要的。可以讓每個核不僅檢查其run隊列，還檢查其他核的隊列，但這麼做又違背了單核單run隊列的初衷。因此Linux和大多數類型的調度器會周期性地運行一個負載均衡演算法，使隊列大致保持平衡。
由於負載均衡的代價比較昂貴，因此會限制調度器執行的頻率。除了周期性地進行負載均衡，調度器還可以在一個核空閑的時候觸發緊急負載均衡。CFS會根據權重和負載(結合了執行緒的權重和平均CPU利用率)來均衡run隊列。為了解決當一個進程具有多個執行緒而另一個進程具有很少的執行緒時可能發生的偏差，在Linux2.6.37版本中引入了一個組調度特性(cgroup)。
當一個執行緒屬於一個cgroup時，其負載會除以其cgroup中的執行緒總數。此功能後來被擴展為自動將屬於不同tty的進程分配給不同的cgroup（autogroup 功能）。
那麼此時可以通過比較所有核的負載將任務從負載最大的核轉移到負載最小的核嗎？很不幸，這樣會導致執行緒的遷移(而沒有考慮快取位置和NUMA)。因此負載均衡器會使用一個分層策略。層次體系中的每一級都稱為一個調度域。最底層為單個核，更高級別的分組取決於如何共享電腦的物理資源。
看下面的例子：
上圖展示了一個32核的機器，包含4個node(每個node 8個核)，每對核使用SMT級別的共享。四個灰色的區域表示與機器的第一個核相關的調度域。注意，層次體系中的第二級為一個三個節點構成的組，這是因為第一個核可以通過一跳到達這三個節點。在第四級，包含了機器上所有的節點，因為所有的節點都在兩跳內可達。
每個調度域都會運行負載均衡，調度的方向為從底層到上層。在每一層中，每個域都會使用一個核運行負載均衡。這個核可以是調度域中第一個空閑的核(如果該域包含空閑的核，且可以為負載均衡分配足夠的CPU周期)，也可以是調度域中的第一個核。此後，會計算調度域中的每個調度組的平均負載，並(根據偏好超載和不均衡組的啟發式方法)選擇最繁忙的組。如果最繁忙的組的負載低於本地組的負載，則會考慮在這一層進行負載均衡。否則，負載將在本地CPU和組中最繁忙的CPU之間進行負載均衡，並進行調整以確保即使在存在任務集的情況下，負載平衡也能正常工作。
調度程式會通過僅在給定調度域的指定核上運行負載均衡演算法來防止重複工作。如果所有核都處於繁忙狀態，則它是域中編號最小的核；如果一個或多個核處於空閑狀態，則使用編號最小的空閑核。如果空閑核正在休眠（電源管理），那麼使它們工作的唯一方法就是被另一個核喚醒。如果某個核認為自身已經過載，則會在一段時間內檢查系統中是否存在空閑核，如果存在，則喚醒第一個，並使其代表自己和所有其他空閑核定期運行負載均衡實例。
四個調度錯誤
由於關於何時不執行負載均衡器的規則如此之多，因此很難推斷出在有工作要做的情況下，一個空閑核應該保持多長時間的空閑狀態，以及在系統中有空閑核的情況下，一個任務可能要在一個run隊列中等待的時長。
論文作者發現的四個錯誤為：組失衡錯誤，調度組構建錯誤，過載喚醒錯誤，以及丟失調度域錯誤。
組失衡
對於平均負載，Gil Tene(Azul Systems的CTO?)有說過：
當一個核嘗試從其他節點(或其他調度組)拿取任務時，它不會檢查組中的每個核的負載，僅會查看組的平均負載。如果選中的調度組的平均負載高於其本身的負載，則它會嘗試從這個組中獲取任務，反之則不會。這也是為什麼在我們的環境下，低負載核無法從其他節點的高負載核上獲取任務的原因。這些低負載核會觀察那些平均負載高於它們的節點上的調度組，然後從高負載R執行緒所在的節點中獲取任務，這類執行緒歪曲了該節點的平均負載的含義，可能存在某些核本身就處於空閑狀態的事實。同時在經過調度之後的節點上，即使在(獲取到任務的CPU和提供任務的組的)平均負載大致相同的情況下，仍然有很多等待執行緒。
可以通過比較最低負載而不是平均負載來修復這個問題。最低負載就是組中的最低負載的核上的負載。如果”調度組中的最低負載低於另外一個調度組的最低負載，則意味著，第一個調度組中存在一個核，其負載低於另外一個組中所有核的負載，因此第一個組中的核必須從第二個組中獲取任務”。應用此修復程式後，使得一個執行R工作負載的完成時間減少了13％，使用60執行緒對具有四個單執行緒R進程的基準測試的運行速度提高了13倍。
調度組構建
Linux的taskset命令可以將應用固定到一組可用的核上。但將應用程式固定在相距兩跳的節點上時，會存在阻止負載均衡演算法在它們之間遷移執行緒的錯誤。
該錯誤是由於調度組的構建方式導致的，我們的實驗中使用了一個不適用於NUMA機器的調度組構建的方式。簡而言之，這些組是從特定核(核0)的角度進行構建的，但它們應該從負責每個節點的負載均衡的核的角度進行構建。
最終導致的結果是節點可能會包含到多個調度組中。假設節點1和節點2分到了兩個組中：
假設一個應用固定到了節點1和2，且在節點1上創建了所有執行緒(Linux會在與其父執行緒相同的核上生成執行緒；當一個程式在初始階段生成多個執行緒時，這些執行緒極有可能會在相同的核上進行創建–通常是這麼做的)。最終，我們想要在節點1和節點2之間進行負載均衡。然而，當一個節點2的核嘗試獲取任務時，它會按照上面描述的方式對比兩個調度組之間的負載。由於調度組同時包含節點1和節點2，導致平均負載是相同的，這樣節點2將無法獲取到任何任務！
不同的調度組(cgroup)應該使用不同的節點
過載喚醒
當一個執行緒在節點X上休眠，而後續喚醒它的執行緒在同一節點上運行時，調度器僅會考慮使用節點X上的核來調度被喚醒的執行緒。如果節點X上的所有核都處於繁忙狀態時，將會在一個已經繁忙的核上喚醒該執行緒，導致這個執行緒失去了在其他節點的空閑核上運行的機會。這會導致電腦的利用率嚴重不足，尤其是在執行緒頻繁等待的工作負載上。
該實現的初衷是提高快取的重用率，但通過讓某些應用在run隊列中等待來提高快取重用率的方式並不可行。該問題是由配置有64個工作執行緒的廣泛使用的商業資料庫觸發的。
為了修復這個錯誤，需要更改執行緒喚醒時執行的程式碼，修改為在本地核上喚醒執行緒，即，執行緒最後調度的核(如果該核是空閑的)；否則如果系統的其他地方有空閑的核，則在空閑時間最長的核上喚醒該執行緒。如果不存在空閑的核，則回退到原始演算法來查找喚醒執行緒的核。
該修復程式在第18個TPC-H查詢上的性能提高了22.2％，在整個TPC-H工作負載上的性能提高了13.2％。
丟失調度域
最後的一個錯誤似乎是在維護期間無意中引入的。
當使用/proc介面禁用一個核，然後啟用該核時，所有NUMA節點之間將不會執行負載均衡。我們跟蹤了問題根因，發現程式碼重新生成了機器的調度域。每禁用一個核，Linux都會重新生成調度域。重新生成調度域分為兩步：內核重新生成NUMA節點內部的域，然後生成跨NUMA節點的域。不幸的是，Linux開發者在程式碼重構時丟棄了生成跨NUMA節點的域的函數。添加該函數之後，問題被修復。
在修復前，禁用然後啟用一個核會導致所有應用的執行緒都跑在同一個核上，而不是分布在八個核上。毫無疑問，該系統的修復效果要好得多（某種情況下，提高了138倍！）。
經驗教訓和工具
新的調度器設計不斷出現，但一個新的設計，即使最初是乾淨的且被認為沒有任何錯誤的，也無法做作為一個長期的解決方案。Linux是一個大型的開源系統，由大量貢獻者共同開發。在這種環境下，我們不可避免地會看到新功能和”hacks “被更新到源程式碼庫中，以應對不斷發展的硬體和應用程式。
改進的模組化是答案嗎？
現在，我們了解到，如今硬體的快速發展將推動越來越多的調度器的優化。調取器必須能夠提供一個合理的方式來輕鬆地集成並組合這些優化。我們設想了一個調度器，它是一系列模組的集合：核心模組和優化模組…
很難用傳統的工具來捕獲本論文描述的問題(這些問題並不會導致崩潰或記憶體耗盡)，並且使用htop，sar或perf等工具無法注意到丟失的短暫的CPU核空閑時間。
我們的經驗促使我們建立了新的工具，使用這些工具可以有效地確認錯誤並理解錯誤發生的原因。
論文作者描述的第一個工具是sanity checker(具體可以參見原始論文)。它會在一個核的run隊列中有等待的執行緒時，檢測是否存在空閑的核。該工具允許短暫出現這種場景，但如果一直存在，則會告警。第二個工具可以可視化展示調度活動，這樣就可以剖析並繪製run隊列的大小，run隊列的總負載，以及負載均衡期間可以考慮的核以及喚醒的執行緒。
論文作者的總結：
將CPU周期切分到執行緒的調度方式被認為是一種解決問題的途徑。但在我們的展示中，情況並非如此。為了適應現代硬體的複雜性，一個簡單的調度策略最終演變成了一個非常複雜且非常容易導致問題的實現。我們發現Linux調度器違反了一個基本的節省工作時採用的不可變因素：將等待執行緒調度到空閑核上。最終可能導致在系統中有空閑核的情況下，一些執行緒仍然阻塞在run隊列中；應用的性能可能會下降很多倍。這些問題的本質使得很難用常用的工具進行探測。我們修復了這些錯誤，了解了其根本原因並提供了工具，這些工具可以方便地捕獲和修復這些錯誤，參見//git.io/vaGOW.。
相關主題
在本篇文章的討論中，有人提到了BFS調度演算法，感興趣的可以看下這篇文章。
