通過可擴展的任務竊取進行負載平衡

Linux 任務調度程序通過將喚醒的任務推送到空閒的 CPU，以及在 CPU 空閒時從繁忙的 CPU 中拉取任務來平衡整個系統的負載。在大型系統上的推送側和拉取側，有效的伸縮都是挑戰。對於拉取，調度程序搜索連續的更大範圍中的所有 CPU，直到找到過載的 CPU，然後從最繁忙的組中拉取任務。這代價非常昂貴，在大型系統上要花費 10 到 100 微秒，因此搜索時間受到平均空閒時間的限制，並且某些範圍不會被搜索。並非總能達到平衡，而且閒置的 CPU 依舊閒置。

我實現了一種備用機制，該機制在 idle_balance() 中的現有搜索中自身受限並且沒有找到之後被調用。我維護了一個過載的 CPU 的位圖，當可運行的 CFS 任務計數超過 1 時，CPU 會設置該位。這個位圖是稀疏的，每個高速緩存線的有效位數量有限。當許多線程同時設置、清除和訪問元素時，這可以減少緩存爭用。每個末級緩存都有一個位圖。當 CPU 空閒時，它將搜索該位圖以查找第一個具有可遷移任務的過載 CPU，然後將其竊取。這種簡單的竊取會比單獨的 idle_balance() 產生更高的 CPU 利用率，因為該搜索的成本很便宜，花費 1 到 2 微秒，因此每次 CPU 即將空閒時都可以調用它。竊取不會減輕全局最繁忙的隊列的負擔，但是它比根本不執行任何操作要好得多。

結果

偷竊僅在調度程序代碼中佔用少量 CPU 開銷即可提高利用率。在以下實驗中，以不同數量的組（每個組 40 個任務）運行 hackbench，並對每次運行結果顯示 /proc/schedstat 中的增量（按 CPU 平均），並增加了這些非標準的統計信息：

％find：在舊函數和新函數中花費的時間百分比，這些函數用於搜索空閒的 CPU 和任務以竊取並設置過載的 CPU 位圖。
steal：任務從另一個 CPU 竊取的次數。經過的時間增加了 8％到 36％，最多增加了 0.4％的發現時間。

load balancing

如下圖的綠色曲線所示，新內核的 CPU 繁忙利用率接近 100％，作為比較的基線內核是橙色曲線：

根據負載的不同，竊取可將 Oracle 數據庫 OLTP 性能提高多達 9％，並且我們已經看到 MySQL、Pgsql、gcc、Java 和網絡方面有了一些不錯的改進。通常，竊取對上下文切換率高的工作負載最有幫助。

代碼

截至撰寫本文時，這項工作尚未完成，但最新的修補程序系列位於 https://lkml.org/lkml/2018/12/6/1253 。如果你的內核是使用 CONFIG_SCHED_DEBUG=y 構建的，則可以使用以下命令驗證其是否包含竊取優化：

# grep -q STEAL /sys/kernel/debug/sched_features && echo Yes

Yes

如果要嘗試使用，請注意，對於具有 2 個以上 NUMA 節點的系統，禁用了竊取功能，因為 hackbench 在此類系統上發生了迴歸，正如我在 https://lkml.org/lkml/2018/12/6/1250 中解釋的那樣。但是，我懷疑這種影響是特定於 hackbench 的，並且竊取將有助於多節點系統上的其他工作負載。要嘗試使用它，請用內核參數 sched_steal_node_limit=8（或更大）重新啟動。