這是一篇介紹Linux排程問題的文章，源自這篇文章。文章中涉及到的一些問題可能已經得到解決，但可以學習一下本文所表達的思想和對CPU排程的了解。
這是EuroSys 2016系列論文中的第一篇，講述了三個部分：首先，介紹了Linux核心排程任務的背景；其次，介紹了軟體老化以及修改需求和維護是如何導緻代碼腐化的；最後，作者給出了Linux排程的四個錯誤，這些錯誤導緻即使在有大量任務等待排程的前提下，仍然有CPU核處于空閑狀态。是以，論文題目為"A Decade of Wasted Cores."
在我們的實驗中，這些性能錯誤會導緻大量重同步的應用的性能下降數倍，增加13%的核心延遲，并導緻通用的商用資料庫的吞吐量下降14-23%。
總的來說，到2000年為止，作業系統設計者考慮到排程是一個需要解決的問題，2004年終結了Dennard 縮放比例定律，迎來了多核時代，使能效成為計算機系統設計中的頭等大事。這些事件使排程器再度熱門起來，但同時也增加了複雜度，且經常會導緻排程失效。
Linux使用完全公平算法(CFS)，該算法使用了一個基于權重的公平隊列。想象在單獨的CPU系統上：CFS會給運作的線程配置設定時間片。該算法為系統上的每個線程設定了一個每次運作固定的最小運作間隔，該間隔會除以配置設定給線程的權重，進而算出時間片。
一個線程的權重本質上是其優先級，或UNIX上的<code>nice</code>值。具有最低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隊列中；應用的性能可能會下降很多倍。這些問題的本質使得很難用常用的工具進行探測。我們修複了這些錯誤，了解了其根本原因并提供了工具，這些工具可以友善地捕獲和修複這些錯誤，參見http://git.io/vaGOW.。
在本篇文章的讨論中，有人提到了BFS排程算法，感興趣的可以看下這篇文章。