更好的任務竊取可以使 Linux 更快嗎？

Oracle Linux 核心開發人員 Steve Sistare 參與了這場有關核心排程程式改進的討論。

通過可延伸的任務竊取進行負載平衡

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％ 的發現時間。

??如下圖的綠色曲線所示，新核心的 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 YesYes

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

進一步工作

在將基本盜用演算法推向上游之後，我正在考慮以下增強功能：

• 如果在末級快取中進行竊取找不到候選者，在 LLC 和 NUMA 節點之間進行竊取。
• 維護稀疏點陣圖以標識 RT 排程類中的偷竊候選者。當前 pull_rt_task() 搜尋所有執行佇列。
• 從 idle_balance() 中刪除核心和通訊端級別，因為竊取會處理這些級別。當支援跨 LLC 竊取時，完全刪除 idle_balance()。
• 維護點陣圖以標識空閒核心和空閒 CPU，以實現推平衡。

這篇文章最初發布於 Oracle Developers Blog。