简介
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) 调度器更昂贵，但对于所有竞争线程，结果是近乎最佳的最坏情况延迟界限（排队时间）。
排序条件
系统使用两个概念来对运行队列中的线程进行排序：虚拟时间轴和每个线程的标准化速率。虚拟时间轴用于跟踪运行队列中的每个线程在运行至完成时将完成的标准化时间片。归一化时间片与线程的归一化速率成正比，而归一化速率又与线程的权重成反比。线程在运行队列中按虚拟时间轴中升序的完成时间排序。
与权重成反比的关系会导致权重较高的线程比到达时间相近的权重较低的线程更靠近运行队列的前端。不过，这种等待时间是有限的：线程在运行队列中等待的时间越长，新到达的线程（无论权重有多高）就越不可能插入到该线程之前。此属性对于调度程序的公平性至关重要。
收益率
立即让出 CPU 会使线程的时间片过期，并将其返回到运行队列。此行为类似于 O(1) 调度中的让步：让步线程保证排在相同或更重权重的线程之后。不过，让出线程可能会也可能不会跳过较低权重的线程，具体取决于其他线程等待运行的时间长短。