說明
為完成整體排程器開發，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-N 到 cpu-0 的時間軸中，N 是系統中的 CPU 數量。這些時間軸代表核心中每個 CPU 的活動，包括中斷和執行緒排程。
公平排程器會發出時間長度事件，包括：
- sched_block：針對 Zircon 物件、futex 和 kernel-internal 鎖定的使用中執行緒區塊。
- sched_unblock：由於與 Zircon 物件、futex 或核心內部鎖定互動，使用中的執行緒會解除封鎖另一個執行緒。
- 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 排程活動，以及觀察執行緒在任何時間點可以執行且可供執行的排程器延遲時間。
流程事件注意事項：Chromium 追蹤檢視器中，有時並未預設啟用流程事件。使用頁面右上角的 View Options 選單，並確認已勾選 Flow events 核取方塊。
如果流程過多且轉譯速度過慢，您也可以停用流程事件的顯示功能。請嘗試將區域放大，再啟用流程事件的顯示功能，以改善極大量追蹤記錄的效能。
公平排程總覽
公平排程是一種策略，將競爭執行緒之間的 CPU 頻寬分隔開來，讓每個執行緒在一段時間內都會獲得 CPU 的加權比例。在本方面，每個執行緒都會獲派權重，大致上與其他排程領域中的優先順序差不多。執行緒接收 CPU 作業時間時，會比其他競爭執行緒的權重與權重成比例。這種按比例分配的頻寬分配具有實用的屬性，因此在一般用途作業系統中，您可以將公平排程做為主要排程依據。
簡單來說，這些屬性如下：
- 直覺的頻寬分配機制：如果執行緒的權重為另一個執行緒的兩倍，其 CPU 作業時間會隨時間從其他執行緒的兩倍。然而，與其他執行緒具有相同權重的執行緒，會隨著時間收到大約相同的 CPU 作業時間 (相較於其他執行緒)。
- 為所有執行緒免費加上星號：無論執行緒的權重與其他執行緒相對低，一律確保所有競爭執行緒都能及時接收 CPU 時間。值得注意的是，這個屬性可避免優先順序反轉。
- 系統超載的公平回應：系統超載時，所有執行緒在速度變慢中會按比例共用。解決超載狀況通常比管理其他排程領域中所需的複雜優先互動更容易。
- 可因應不斷變化的需求提供穩定性：與各種工作負載相比可妥善調整，在最少的排定作業中也能有效執行。
注意事項：公平安排原則適用於大多數的工作負載，但有些工作需要非常明確的時間，且/或無法妥善因應超載情況。舉例來說，這些工作負載包括低延遲音訊 / 圖形、高頻率感應器，以及高速率/低延遲網路。使用期限排程器能提供更優異的特殊工作，我們預計在 Zircon 排程器開發週期的稍後進行這項規劃。
Zircon 的公平排程
Zircon 公平排程器主要是根據「加權公平放送」(WFQ) 學科為基礎，其中包含其他類似佇列和排程領域的深入分析。預計採用 Worst-Case Fair Weighted Fair Queuing (WF2Q) 學科中的各個層面；WFQ 經過修改，計劃針對延遲調整與處理量的調整方式提供更佳的控制。
以下各節將概略說明 Zircon 中實作的演算法。然後，「Ffair 排程器」和「Zircon 公平排程器」會交替使用。
排序執行緒執行作業
排程器的主要工作之一是決定在 CPU 上執行競爭執行緒的順序。公平排程器會在每個 CPU 上分別做出這些決定。基本上，每個 CPU 會分別執行排程器的執行個體，並管理自己的執行佇列。
在這個方法中，執行緒一次只能在一個 CPU 上競爭。執行緒可能為下列三種狀態之一：「就緒」、「執行中」或「已封鎖」 (其他狀態與本討論無關)。對於每個 CPU，隨時最多一個執行緒處於「Running」狀態：此執行緒在 CPU 上執行，所有其他競爭執行緒在等待「就緒」狀態時執行，而封鎖的執行緒則不會競爭。處於 Ready 狀態的執行緒會排入 CPU 執行佇列中的佇列；執行佇列中的執行緒順序將決定接下來要執行的執行緒。
與 O(1) 排程方法 (例如優先順序循環 (RR)) 不同，公平排程器會使用排序條件來比較執行佇列中的執行緒並排序。這會使用平衡的二進位樹狀圖來實作，這表示排程決策通常需要花費 O(log n) 執行。雖然這比 O(1) 排程器的費用更高，但結果對所有競爭執行緒而言，是近乎最佳情況的最糟情況延遲 (排入佇列時間)。
排序條件
您可以使用兩種概念為執行佇列中的執行緒排序：虛擬時間軸和每個執行緒的正規化速率。虛擬時間軸會追蹤執行佇列中每個執行緒在完成正規化時間配量的時間。「正規化時間片段」與執行緒的「正規化率」成正比，後者則與執行緒權重成反比。在虛擬時間軸中，執行緒會按「finish time」遞增排序，在執行佇列中會排序執行緒。
權重的反比例關係會使權重較高的執行緒插入更靠近執行佇列前端的執行緒，比抵達時間相近且權重較高的執行緒更靠近。但是，有時間限制：執行緒在執行佇列中的等待時間越長，越不可能在新抵達執行緒之前插入執行緒。這個屬性是排程器公平性的關鍵。
下列各節以更精準的術語定義排程器。
每個執行緒的排程狀態
我們會為每個執行緒 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 為 CPU C[j] 目前排程週期 p[j] 的最小精細度單位 M 的整數。
允許 R 做為執行緒 P[i] 的相對率。
g = floor(p[j] / M)
R = w[i] / W[j]
t[i] = ceil(g * R) * M
這個定義可確保 t[i] 是最小精細度 M 的整數倍數，同時仍與執行緒的相對率大致成正比。
收益
產生後會立即過期執行緒的時間片段，並將其傳回至執行佇列。這個行為與在 O(1) 排程中產生類似：產生的執行緒保證會排入權重相同或更多的執行緒後方。不過，產生執行緒不一定會跳轉至較低權重執行緒，取決於其他執行緒等待執行的時間長度。