Zircon Fair Scheduler

簡介

整體排程器開發工作中，Zircon 將邁向全新的 做為系統的主要排程器本文件討論 排程器的屬性，以及如何在進行 。

啟用 Fair Scheduler

公平排程器預設為停用。新排程器啟用時間： 將 GN 建構引數 enable_fair_scheduler 設為 true，即可編譯時間。

您可以在 GN 叫用中設定此變數，如下所示：

gn gen build-zircon --args='enable_fair_scheduler=true'

詳細排程器追蹤

新的排程器提供詳細的追蹤檢測功能，可分析 排程器的行為、與競爭者的互動情形，以及對競爭的影響 工作負載編譯時，系統會透過設定 GN 建構引數 detailed_scheduler_tracing 設為 true。

您可以在 GN 叫用中設定此變數，如下所示：

gn gen build-zircon --args='enable_fair_scheduler=true detailed_scheduler_tracing=true'

使用 kernel:sched 追蹤記錄類別，加入詳細排程器 擷取的資訊建議你一併顯示 kernel:irq 類別，因為幹擾可能會造成排程器活動 在其他事件中顯示。

ffx trace start --categories kernel:sched,kernel:irq,<other categories> --duration 4 --buffer-size 64

排程器事件摘要

詳細排程器事件主要為持續時間和流量事件。 事件顯示在 Chromium 追蹤檢視器中，名為「cpu-0」的事件 至 cpu-N，其中 N 是系統中的 CPU 數量。這些時間表 代表核心中的個別 CPU 活動，包含中斷情形， 執行緒排程

公平排程器發出的時間長度事件包括：

  • sched_block：Zircon 物件上的使用中執行緒區塊 (futex)， 核心內部鎖定。
  • sched_unblock：運作中的執行緒會解除封鎖其他執行緒，原因如下： 與 Zircon 物件、futex 或 kernel-internal 的鎖定互動。
  • sched_unblock_list：動作發生時，sched_block 的變化版本 使用中的執行緒可能會同時喚醒一或多個執行緒 (例如 wait_queue_wake_all)。
  • sched_yield：有效的執行緒，稱為 zx_thread_yield。
  • sched_preempt：重新評估執行佇列的中斷要求。這個 是由於時間切片計時器到期，另一個 CPU 要求使用 在修改 CPU 的執行佇列或硬體中斷後重新排程 處理常式喚醒 CPU 上的執行緒。
  • sched_reschedule：核心作業變更了目前作業佇列的執行佇列 CPU 和不同的執行緒「可能」需要執行。

公平排程器會發出流程事件，包括：

  • sched_latency：在執行緒之後，立即連結該時間點的流程 會進入執行佇列到 目標 CPU 結構定義會切換至執行緒。這個流程事件 能以視覺化方式呈現跨 CPU 排程活動 執行緒在任何時間點的可執行排程器延遲時間。

關於流程事件的注意事項：有時候，顯示流量事件的指令並非啟用 預設使用此功能。使用右上方的「View Options」選單 並確認已勾選 [Flow events] 核取方塊。

如果流程事件過多且轉譯 變得太慢請先縮小區域，再啟用流程事件 顯示較高效能的追蹤記錄。

公平排程總覽

公平排程是可將 CPU 頻寬分配給競爭的 讓每個執行緒在一段時間內都獲得 CPU 的加權比例。 在這項學科中，每個執行緒會獲派一個權重，相近 達成其他排程作業的優先順序執行緒接收 CPU 作業時間 (相對於其他競爭執行緒的權重)。 這種比例分配的實用屬性能 安排良好的時間，做為主要排程作業 以及用途

簡單來說，這些屬性包括：

  • 直覺式頻寬分配機制：權重為兩倍的執行緒 另一個執行緒則會收到大約兩倍的 CPU 作業時間 持續追蹤其他執行緒。而另一個權重相同的執行緒 收到的 CPU 作業時間 (相對於其他執行緒) 大致相同 長期下來。
  • 所有討論串皆可自由加上星號：依比例分配頻寬， 不管是哪一種情況，所有競爭執行緒都能及時接收 CPU 作業時間 執行緒權重相對於其他執行緒的下限。值得注意的是 以防止沒有限制的優先順序反轉
  • 系統超載的公平回應：系統超載時 在緩慢工作階段中，我們會按比例分享這些執行緒。解決超載條件 比起管理 安排 AI 作業
  • 不斷演進的需求來維持穩定性：適用於各種工作負載 盡可能減少介入措施。

關於觸發事件的注意事項：雖然公平排程適用於大型主機 大多數的工作負載都有需要特別花時間完成的工作 且/或者對超載條件未妥善調整舉例來說 包括低延遲音訊 / 圖形、高頻率感應器，以及高速率 / 低延遲網路但若使用情境訓練資料， 期限排程器 (預計於日後於 Zircon 排程器推出) 開發週期

Zircon 公平排程

Zircon 公平排程器主要以 Weighted Fair Queuing (WFQ) 為基礎 其他類似佇列和排程訓練的深入見解。 採用了 Worst-Case Fair Weighted Fair Queuing (WF2Q) 紀元 WFQ 的修改作業預計能改善對延遲時間的調整 以及處理量

以下各小節將概述在 Zircon 中實作的演算法。最低價格： 我正在接受「公平排程器」以及「Zircon Fair 排程器」可以交替使用

排序執行緒執行作業

排程器的其中一項主要工作是決定要執行的順序 彼此競爭公平排程器會做出決定 分別在各 CPU 上運作基本上，每個 CPU 都會執行 和管理自己的執行佇列

在此方法中，執行緒一次只能在一個 CPU 上競爭。討論串可以 處於以下三種狀態之一：已就緒、執行中或 blocked (其他狀態未 與這個討論相關)。對每個 CPU 來說 最多一個執行緒位於 running 狀態：這個執行緒會在 CPU 上執行，所有其他 競爭執行緒等待執行狀態為就緒，而已封鎖的執行緒 而非競爭者。狀態為 Ready 的執行緒會排入 CPU 的執行佇列；執行佇列中的執行緒順序，決定了哪個執行緒 接著執行

公平排程器，與優先度等 O(1) 排程訓練不同 循環制 (RR) 不同，會使用排序標準來比較和排序 執行佇列系統會使用平衡的二進位樹狀結構進行實作 排程決定通常需要 O(log n) 才能完成。雖然這個 比 O(1) 排程器昂貴，因此算是接近最佳效果 所有競爭執行緒的延遲 (佇列時間)。

排序條件

將執行佇列中的執行緒排序時，會使用以下兩個概念：虛擬時間軸和 每個執行緒的正規化速率。虛擬時間軸會追蹤 執行佇列會在執行完畢後完成正規化時間片段。 正規化時間片段與執行緒的正規化比率成正比。 而該訊息的權重與執行緒的權重成反比。執行緒是 按照虛擬時間軸中的 finish time 遞增排序，以便在執行佇列中排序。

權重的反比例關係會增加執行緒的權重 插入比執行佇列前方更接近執行佇列前方的 Pod 抵達時間相近不過，隨著時間經過的變化，事件越長 執行緒都在執行佇列中等待，但新到達執行緒的可能性較低 系統會將權重相加。這個屬性是 確保排程器公平性

以下各節會以更精確的方式定義排程器。

每個執行緒排程狀態

我們會為每個執行緒 P[i] 定義下列狀態：

  • 權重 w[i]：代表執行緒相對權重的實數。
  • 開始時間 s[i]：CPU 虛擬物件中執行緒的開始時間 時間軸上。
  • 完成時間 f[i]：CPU 虛擬化中執行緒的結束時間 時間軸上。
  • 時間片段 t[i]：目前時段的時間片段大小。

每個 CPU 排程狀態

我們會為每個 CPU C[j] 定義下列狀態：

  • 執行緒數量 n[j]：可執行的執行緒數量 也就是 CPU
  • 排程期間 p[j]：所有參與競爭的執行緒的時間範圍 CPU 大約會執行一次
  • 總權重 W[j]：執行緒上競爭的執行緒權重總和 也就是 CPU

執行緒進入 CPU 競爭後，其權重就會加入 CPU 的 總權重同樣地，執行緒封鎖或遷移至其他 CPU 時 執行緒權重會從 CPU 的總權重減去。總計包括 「就緒」執行緒和目前執行中執行緒的權重。

可調整狀態

定義以下可微調狀態 (可以是全域或個別 CPU)：

  • 最小精細程度 M：分配給任何執行緒的最短時間片段。
  • 目標延遲時間 L：CPU 的目標排程期間 (除非已設定) 執行緒過多，因此每個執行緒至少應提供一個精細程度的下限 片段

定義

我們為關鍵排程器變數定義下列關係：

排定時段

排程時間範圍可控制時段區塊的大小。很少 排程期間預設為「目標延遲時間」。這個 從而取得更長的時間切片和先佔式減少，進而改善處理量，並 可能耗電量如果執行緒數量過大 排程週期會延展，讓每項任務至少獲得 細分時間片段。

讓 N 在經期延展前的競爭執行緒數量上限。

 N = floor(L / M)

p[j] = n[j] > N --> M * n[j], L

虛擬時間軸

當執行緒進入執行佇列時，方法可以是新加入 CPU 或完成時間片段，執行緒的虛擬開始和結束時間 由於目前的公平排程器是以 WFQ 為依據，因此結束時間為 用來選取執行緒在執行佇列中的相對位置 。之後當執行 WF2Q 時，開始和結束時間都會增加 考慮成形

部分 WFQ 實作會使用執行緒的實際時間片段來計算 正規化時間片段。不過，實際時間片段取決於 會反映 CPU 總權重 (請見下方)，這個值會隨著執行緒進入的執行緒變更而改變 競爭。Zircon 公平排程器會將排程期間視為 虛擬時間軸的理想統一時間片段，因為其值 並且減少大幅度的變動針對所有執行緒使用統一的值，以免出現偏差 虛擬時間軸，以不公平的方式加入提前加入的執行緒。

當執行緒 P[i] 進入執行作業時，請將 T 設為 CPU C[j] 的系統時間 佇列。

s[i] = T

f[i] = s[i] + p[j] / w[i]

時間片段

選取要執行的執行緒時，系統會依據執行緒時間片段計算 相對費率和時段設定

此處的 g 為最小精細度單位 M 的整數 CPU C[j] 目前的排程期間 p[j]。

並以 R 為執行緒 P[i] 的相對速率。

 g = floor(p[j] / M)

 R = w[i] / W[j]

 t[i] = ceil(g * R) * M

這個定義可確保 t[i] 為最小值的整數倍數 精細程度 M，而與相對 執行緒速率

收益

產生作業會立即結束執行緒的時間片段，並傳回執行作業 佇列。這個行為類似於在 O(1) 排程中產生： 執行緒保證會排在權重相同或更大的執行緒之後。 但是，產生的執行緒不一定會跳過權重較低的執行緒之前 取決於其他執行緒等待執行的時間