Zircon 内核调度设计

内核调度程序的主要职责是在希望使用它的所有线程之间共享有限的处理器时间资源。在通用操作系统中，它尝试以公平的方式执行此操作，确保允许所有线程取得一些进展

Zircon调度程序是LK调度程序的演变。因此，它最初只是一个最小的调度程序实现，并随着项目的发展而扩展以满足更复杂的需求。

本质上，在机器中的每个逻辑CPU上运行调度程序。这些调度程序独立运行并使用IPI（处理器间中断）进行协调。但是，每个CPU负责调度在其上运行的线程。

每个CPU都有自己的优先级队列集。一个用于系统中的每个优先级，是fifo队列，而不是称为优先级队列的数据结构。在每个队列中都有一个等待执行的可运行线程的有序列表。当新线程运行时，调度程序只查看包含线程的编号最高的队列，弹出该队列的头并运行该线程。如果队列中没有线程要运行，它将运行空闲线程。

当挑选开始运行时，为每个线程分配相同的时间片大小（THREAD_INITIAL_TIME_SLICE）。如果它使用整个时间片，它将被重新插入适当的优先级队列的末尾。但是，如果它的某些时间片保留在先前的运行中，它将被插入优先级队列的头部，以便它能够尽快恢复。当它再次被重新拾取时，它将仅运行其先前时间片的剩余部分。

当调度程序从优先级队列中选择一个新线程时，它会将CPU的抢占计时器设置为完整的时间片或前一个时间片的剩余部分。当该计时器触发时，调度程序将停止在该线程上执行，将其添加到适当的队列，选择另一个线程并重新开始。

如果线程阻塞等待共享资源，则它将从其优先级队列中取出，并被置于共享资源的等待队列中。当它被解锁时，它将被重新插入符合条件的CPU,CPU Assignment的适当优先级队列中，如果它有剩余的时间片运行，它将被添加到队列的前面以​​便加速处理。

内核优先级管理

有三种不同的因素用于确定线程的有效优先级，有效优先级是用于确定它将在哪个队列中的优先级。

第一个因素是基本优先级，它只是线程的请求优先级。目前有32个级别，其中0表示最低，31表示最高级别。

第二个因素是优先级提升。这是用于偏移基本优先级的[-MAX_PRIORITY_ADJ，MAX_PRIORITY_ADJ]之间的值，它由以下情况修改：

• 当线程被解除阻塞时，在等待共享资源或休眠之后，它被给予一点提升。
• 当一个线程产生（志愿者放弃控制）或志愿者重新安排时，它的提升减少一个但是上限为0（不会变为负数）。
• 当一个线程被抢占并且已用完它的整个时间片时，它的增强会减1，但能够消极。

第三个因素是其继承的优先权。如果线程控制共享资源并且它阻塞了另一个具有更高优先级的线程，那么它将被临时提升到该线程的优先级，以允许它快速完成并允许更高优先级的线程恢复。

线程的有效优先级是继承的优先级，或者基本优先级加上它的提升。当此优先级发生更改时，由于任何因素都会发生变化，调度程序会将其移至新的优先级队列并重新安排CPU。如果它现在是最高优先级的任务，则允许它控制，或者如果它不再是最高任务则放弃控制。

该系统的目的是确保快速处理交互式线程。这些通常是与用户直接交互并导致用户可感知的延迟的线程。这些线程通常很少工作，并且大部分时间都被阻止等待另一个用户事件。因此，他们通过解锁来获得优先级提升，而执行大部分处理的后台线程在使用整个时间片时会受到优先级惩罚。

CPU分配和迁移

线程能够使用CPU关联掩码请求他们希望运行哪些CPU，32位掩码请求他们希望运行哪些CPU，其中0b001是CPU 1,0b100是CPU 3,0b101是CPU 1或CPU 3.

通常会遵循此掩码，但如果它请求的CPU全部处于非活动状态，则会将其分配给另一个CPU。另外值得注意的是，如果它被“固定”到CPU，那么它的掩码只包含一个CPU，并且该CPU变为非活动状态，线程将保持不受控制，直到该CPU再次变为活动状态。

为线程选择CPU时，调度程序将按顺序选择：

• 1. 执行选择的CPU，如果它处于空闲状态且在关联掩码中。
• 2. 线程最后运行的CPU，如果它是空闲的并且在关联掩码中。
• 3. 关联掩码中的任何空闲 CPU。
• 4. 线程最后运行的CPU，如果它处于活动状态且在关联掩码中。
• 5. 执行选择的CPU，如果它是亲和掩码中的唯一一个或掩码中的所有cpus都不活动。
• 6. 关联掩码中的任何活动CPU。

如果线程在不在其关联掩码中的CPU上运行（由于上面的情况5），则每次线程被抢占，产生或自愿重新安排时，调度程序将尝试纠正此问题。此外，如果线程更改其关联掩码，则调度程序可以迁移它。

每次线程从等待共享资源或休眠状态返回并需要为其分配优先级队列时，调度程序将使用上述逻辑重新评估其对线程的CPU选择，并可以移动它。

CPU激活

当CPU被停用时，即关闭并从系统中删除，调度程序将所有正在运行的线程转换到其他CPU。唯一的例外是“固定”的线程，即它们仅在其关联掩码中具有停用CPU，这些线程被放回到运行队列中，在这些队列中它们将被保持不被服务直到CPU被重新激活。

重新激活CPU时，它将为等待固定的线程提供服务，并且由于上述规则，应由CPU调度程序快速迁移在非Affinity CPU上运行的线程。没有主动重新平衡线程到新唤醒的CPU，但由于它应该更频繁地闲置，因此应该看到一些迁移，因为上面列出了CPU分配和迁移中的逻辑。

实时和空闲线程

这些特殊线程的处理方式略有不同。

当没有其他线程可运行时，空闲线程运行。每个CPU上都有一个，它位于优先级队列之外，但有效地位于-1的优先级队列中。它用于跟踪空闲时间，并可由平台实现用于低功耗等待模式。

THREAD_FLAG_REAL_TIME允许实时线程（标记为）在没有抢占的情况下运行，并且将一直运行直到它们阻塞，产生或手动重新安排。