簡介
Zircon 公平排程器是系統中一般工作負載的主要排程規範。這項功能會在競爭執行緒之間分配 CPU 頻寬，讓每個執行緒在一段時間內獲得加權比例的 CPU。
如要概略瞭解排程器架構，包括 Deadline 排程和電源管理，請參閱「Zircon 排程器總覽」。
公平排程總覽
公平排程是一種學科，可將 CPU 頻寬分配給競爭執行緒，讓每個執行緒在一段時間內獲得加權比例的 CPU。在這個學科中，每個執行緒都會獲派權重，這與其他排程學科中的優先順序有些類似。執行緒會根據權重，相對於其他競爭執行緒的權重，取得 CPU 時間。這種頻寬分配方式具有實用屬性，因此公平排程非常適合做為一般用途作業系統的主要排程規範。
簡而言之，這些屬性包括：
- 直覺式頻寬分配機制：權重是其他執行緒兩倍的執行緒，相較於其他執行緒，隨著時間經過，大約會獲得兩倍的 CPU 時間。如果執行緒的權重與另一個執行緒相同，則相對於其他執行緒，該執行緒在一段時間內會獲得大致相同的 CPU 時間。
- 所有執行緒都不會發生資源不足的情況：比例式頻寬分配機制可確保所有競爭執行緒及時獲得 CPU 時間，無論執行緒權重相對於其他執行緒有多低，值得注意的是，這項屬性可避免無界優先權反轉。
- 系統過載時的公平回應：系統過載時，所有執行緒都會按比例減速。相較於其他排程領域中複雜的優先互動管理作業，解決過載情況通常較為簡單。
- 因應不斷變化的需求，維持穩定性：相較於其他排程領域，可適應各種工作負載，且干預程度極低。
Zircon 中的公平排程
Zircon 公平排程器主要以加權公平佇列 (WFQ) 規範為基礎，並參考其他類似的佇列和排程規範。
以下小節會說明 Zircon 實作的演算法。從現在開始，「公平排程器」和「Zircon 公平排程器」會交替使用。
排序執行緒執行作業
排程器的主要工作之一，是決定要在 CPU 上執行競爭執行緒的順序。公平調度器會在每個 CPU 上分別做出這些決策。基本上，每個 CPU 都會執行獨立的排程器執行個體，並管理自己的執行佇列。
採用這種方法時，執行緒一次只能在一個 CPU 上競爭。執行緒可處於三種狀態：就緒、執行中或遭到封鎖 (其他狀態與本次討論無關)。每個 CPU 在任何時間最多只能有一個處於「執行」狀態的執行緒：這個執行緒會在 CPU 上執行，所有其他競爭執行緒則處於「就緒」狀態，等待執行，而遭到封鎖的執行緒則不會參與競爭。處於「就緒」狀態的執行緒會加入 CPU 的執行佇列，執行佇列中的執行緒順序會決定下一個執行的執行緒。
與優先順序循環(RR) 等 O (1) 排程規範不同，公平排程器會使用排序條件，比較並排序執行佇列中的執行緒。這項功能是透過平衡二元樹實作，因此排程決策通常需要 O(log n) 的執行成本。雖然這比 O(1) 排程器更昂貴，但所有競爭執行緒的結果接近最佳最差情況延遲界限 (排隊時間)。
排序條件
系統會使用兩個概念，在執行佇列中排序執行緒：虛擬時間軸和每個執行緒的標準化速率。虛擬時間軸會追蹤執行佇列中的每個執行緒何時會完成標準化時間片段 (如果執行至完成)。標準化時間片段與執行緒的標準化速率成正比，而標準化速率則與執行緒的權重成反比。執行佇列中的執行緒會依虛擬時間軸的完成時間遞增排序。
由於權重與優先順序成反比，因此權重較高的執行緒會比抵達時間相近的權重較低執行緒，更早插入執行佇列前端。不過，這會受到時間限制：執行緒在執行佇列中等待的時間越長，新抵達的執行緒就越不可能插入到該執行緒之前，即使新執行緒的權重很高也一樣。這項屬性是排程器公平性的關鍵。
收益
立即產生會使執行緒的時間片段立即到期，並將其傳回執行佇列。這種行為類似於 O(1) 排程中的產生作業：產生作業的執行緒保證會排在相同或較大權重的執行緒後面。不過，視其他執行緒等待執行的時間長度而定，產生執行緒可能會或可能不會跳過權重較低的執行緒。