背景
任何调度程序的主要责任都是在希望使用处理器时间的所有线程之间共享有限的处理器时间资源。在通用操作系统中，它会尝试以公平的方式执行此操作，以确保允许所有线程取得一些进展。
我们的调度器是 LK 调度器的升级版。因此，它最初只是一个最低限度的调度程序实现，随着项目的发展，它经过扩展以满足我们的需求。
设计
概览
实质上，机器中的每个逻辑 CPU 上都有一个运行的调度器。这些调度器独立运行，并使用 IPI（处理器间中断）进行协调。不过，每个 CPU 都负责调度在其上运行的线程。请参阅下面的 CPU 分配，了解我们如何确定线程所在的 CPU 及其迁移方式/时间。
每个 CPU 都有自己的一组优先级队列。系统中的每个优先级对应一个优先级，目前为 32。请注意，这些是 fifo 队列，而不是称为优先级队列的数据结构。每个队列中都有一个有序列表，其中列出了等待执行的可运行线程。当新线程到了运行时，调度程序只会查看包含一个线程的最高编号队列，从该队列中弹出头并运行该线程。如需详细了解它如何确定在哪个队列中，请参阅下面的优先级管理。如果队列中没有线程要运行，则会改为运行空闲线程，请参阅下面的实时线程和空闲线程了解详情。
当选择线程开始运行时，系统会为每个线程分配相同的时间片大小 (THREAD_INITIAL_TIME_SLICE)。如果它用完整个时间片，则会在适当的优先级队列末尾重新插入。但是，如果上次运行还有一部分时间片，则它会插入优先级队列的开头，以便能够尽快恢复。当再次被拾起时，它将仅在其前一个时间片的剩余时间内运行。
当调度程序从优先级队列中选择新线程时，它会针对整个时间片或上一个时间片的其余部分设置 CPU 的抢占计时器。当该计时器触发时，调度程序将停止该线程的执行，将其添加到适当的队列，选择其他线程并重新开始。
如果某个线程阻塞等待共享资源，则该线程会从其优先级队列中取出，并放入到共享资源的等待队列中。当它被取消屏蔽后，系统会将其重新插入符合条件的 CPU 的相应优先级队列中（CPU 分配），如果它还有剩余时间片需要运行，则会添加到队列前面，以加快处理速度。
优先级管理
可通过三种不同的因素来确定线程的有效优先级，有效优先级是用于确定线程将进入哪个队列的因素。
第一个因素是基准优先级，即线程请求的优先级。目前有 32 个级别，0 表示最低，31 表示最高。
第二个因素是优先级提升。这是一个介于 [-MAX_PRIORITY_ADJ, MAX_PRIORITY_ADJ] 之间的值，用于偏移基准优先级，它可在以下情况下进行修改：
当线程处于未阻塞状态时，在等待共享资源或进入休眠状态后，系统会对其进行 1 分提升。
当某个线程退让（自愿放弃控制权）或自愿放弃控制权时，其增强幅度减少 1，但上限为 0（不会变差）。
当线程被抢占并用完其整个时间片时，其提升会减 1，但可能会变为负。
第三个因素是其继承的优先级。如果该线程控制着某个共享资源，并且阻塞了另一个优先级更高的线程，则临时提升该线程的优先级，使其快速完成，并允许优先级较高的线程恢复。
线程的有效优先级要么是继承优先级（如果有），要么是基础优先级加上其增强优先级。当此优先级由于任何因素而发生变化时，调度程序会将其移至新的优先级队列并重新调度 CPU。允许它控制它现在是否是最高优先级任务，或放弃控制（如果它不再是最高优先级任务）。
该系统的目的是确保交互式线程得到快速处理。这些线程通常是与用户直接交互并导致用户可感知的延迟的线程。这些线程通常不会执行任何操作，并且大部分时间处于阻塞状态，等待另一个用户事件。因此，它们通过取消屏蔽可以获得更高的优先级，而完成大部分处理的后台线程会因使用整个时间片而受到优先级惩罚。
CPU 分配和迁移
线程能够使用 CPU 亲和性掩码（32 位掩码）请求它们要在哪些 CPU 上运行，其中 0b001 为 CPU 1、0b100 为 CPU 3，而 0b101 为 CPU 1 或 CPU 3。系统通常会遵循此掩码，但如果它请求的 CPU 都处于非活动状态，则会将其分配给另一个 CPU。另外值得注意的是，如果该线程“固定”到某个 CPU，即其掩码仅包含一个 CPU，并且该 CPU 变为非活动状态，则该线程将一直处于静止状态，直到该 CPU 再次变为活动状态。如需了解详情，请参阅下文的 CPU 激活部分。
在为线程选择 CPU 时，调度程序将按以下顺序选择 CPU：
执行选择（如果处于空闲状态且在亲和性掩码中）的 CPU。
线程上次运行所在的 CPU（如果该线程处于空闲状态且位于亲和性掩码中）。
亲和性掩码中的任何空闲 CPU。
线程上次运行所在的 CPU（如果该线程处于活动状态且位于亲和性掩码中）。
如果 CPU 是亲和性掩码中的唯一一个，或者该掩码中的所有 CPU 均不处于活动状态，则执行选择的 CPU。
相似性掩码中的任何活跃 CPU。
如果线程是在未在其亲和性掩码范围内的 CPU 上运行（由于上述第 5 种情况），则在每次线程被抢占、让出或主动重新调度时，调度程序都会尝试纠正此错误。此外，如果线程更改了其亲和性掩码，则调度程序可能会迁移该线程。
每当线程等待共享资源或进入休眠状态并需要分配优先级队列时，调度程序都会使用上述逻辑重新评估其线程 CPU 选择，并且可能会移动它。
CPU 激活
当停用（即关闭）并从系统中移除 CPU 时，调度程序会将所有正在运行的线程转移到其他 CPU。唯一的例外情况是“固定”的线程，也就是说，它们的亲和性掩码中只有正在停用的 CPU，这些线程会被放回运行队列，在该队列中，它们将处于无服务状态，直到被重新激活 CPU。
重新激活 CPU 时，它会为处于等待状态的已固定线程提供服务，而根据上述规则，CPU 调度程序应该迅速将那些在非相似性 CPU 上运行的线程迁移回来。系统不会主动将线程再平衡到新唤醒的 CPU，但由于 CPU 应更频繁地处于空闲状态，因此它应该会因上面 CPU 分配和迁移中列出的逻辑而进行一些迁移。
实时线程和空闲线程
这些是特殊线程，处理方式略有不同。
当没有其他线程可运行时，空闲线程将运行。每个 CPU 上有一个，它位于优先级队列之外，但实际上位于优先级为 -1 的优先级队列中。它用于跟踪空闲时间，可供平台实现用于低功耗等待模式。
实时线程（标有 THREAD_FLAG_REAL_TIME）可以在不抢占的情况下运行，直到它们阻塞、让出或手动重新调度为止。