PDFFreeBSD 5.2 中的线程调度
为了更好地了解线程调度，我们来看看 FreeBSD 5.2 是如何处理它的。
MARSHALL KIRK McKUSICK，顾问
GEORGE V. NEVILLE-NEIL，顾问
繁忙的系统每秒钟会做出数千个调度决策，因此调度决策的速度对于系统的整体性能至关重要。本文——摘自即将出版的《FreeBSD 操作系统设计与实现》一书——以开源 FreeBSD 系统为例，帮助我们理解线程调度。最初的 FreeBSD 调度器是在 20 世纪 80 年代为大型单处理器系统设计的。尽管它在今天的环境中仍然运行良好，但新的 ULE 调度器是专门为优化多处理器和多线程环境而设计的。本文首先研究了最初的 FreeBSD 调度器，然后描述了新的 ULE 调度器。本文不描述 FreeBSD 中也提供的实时调度器。
其他 Unix 系统添加了一个动态调度器开关，每次调度决策都必须遍历该开关。为了避免这种开销，FreeBSD 要求在构建内核时选择调度器。因此，所有对调度代码的调用都在编译时解析，而不是为每个调度决策都通过间接函数调用的开销。默认情况下，FreeBSD 5.1 及更早版本的内核使用调度器。从 FreeBSD 5.2 开始，默认使用 ULE 调度器。
最初的 FreeBSD 调度器
所有可运行的线程都被分配一个调度优先级，该优先级决定了它们被放置在哪个运行队列中。在选择要运行的新线程时，系统从最高优先级到最低优先级扫描运行队列，并选择第一个非空队列中的第一个线程。如果多个线程驻留在队列中，系统将以轮询方式运行它们——也就是说，系统按照它们在队列中找到的顺序运行它们，并允许相等的运行时间。如果线程阻塞，则不会将其放回任何运行队列。如果线程用完了允许的时间片（或时间配额），则将其放置在它来自的队列的末尾，并选择队列前面的线程运行。
时间片越短，交互响应越好。然而，更长的时间片提供更高的系统吞吐量，因为系统因上下文切换造成的开销更少，处理器缓存被刷新的次数也更少。FreeBSD 使用的时间片是 0.1 秒。这个值是通过经验发现的，它是可以使用的最长时间片，而不会损失编辑器等交互式作业所需的响应。令人惊讶的是，时间片在过去 20 年中一直没有改变。尽管时间片最初是在具有许多用户的集中式分时系统上选择的，但它对于今天的分布式工作站仍然是正确的。虽然工作站用户期望的响应时间比 20 年前的分时用户预期的响应时间更快，但典型工作站上较短的运行队列使得较短的时间片变得不必要。
分时线程调度
FreeBSD 分时调度算法基于多级反馈队列。系统动态调整线程的优先级，以反映资源需求（例如，阻塞等待事件）和线程消耗的资源量（例如，CPU 时间）。线程根据其调度优先级的变化在运行队列之间移动（因此在名称多级反馈队列中使用了反馈一词）。当除了当前正在运行的线程之外的线程获得更高的优先级时（通过分配优先级或在唤醒时给予优先级），如果当前线程处于用户模式，系统会立即切换到该线程。否则，系统会在当前线程退出内核后立即切换到更高优先级的线程。系统定制了这种短期调度算法，通过提高阻塞等待 I/O 一秒或更长时间的线程的调度优先级，以及降低累积了大量 CPU 时间的线程的优先级，来偏向交互式作业。
短期线程调度分为两个部分。下一节描述何时以及如何更改线程的调度优先级；之后的部分描述运行队列的管理以及线程调度和上下文切换之间的交互。
线程优先级计算
线程的调度优先级直接由与线程结构关联的两个值确定：kg_estcpu 和 kg_nice。kg_estcpu 的值提供了线程最近 CPU 利用率的估计值。kg_nice 的值是一个用户可设置的权重因子，数值范围在 -20 到 20 之间。kg_nice 的正常值为零。负值会提高线程的优先级，而正值会降低其优先级。
线程的用户模式调度优先级在每次时钟滴答（通常为 40 毫秒）之后计算，如果发现线程正在运行，则使用以下公式
小于 PRI_MIN_TIMESHARE (160) 的值设置为 PRI_MIN_TIMESHARE（见表 1）；大于 PRI_MAX_TIMESHARE (223) 的值设置为 PRI_MAX_TIMESHARE。此计算导致优先级根据最近的 CPU 利用率线性降低。用户可控的 kg_nice 参数充当有限的权重因子。负值通过抵消包含 kg_estcpu 的加法项来延迟重 CPU 利用率的影响。否则，如果我们忽略第二项，kg_nice 只是简单地将优先级移动一个常数因子。
每次系统时钟滴答并且发现线程正在执行时，CPU 利用率 kg_estcpu 都会递增。此外，kg_estcpu 每秒通过数字衰减滤波器调整一次。衰减会导致大约 90% 的在一秒间隔内累积的 CPU 使用率在一段时间内被遗忘，这段时间取决于系统负载平均值。确切地说，kg_estcpu 根据以下公式进行调整
其中 load 是系统运行前一分钟的运行队列和短期睡眠队列长度之和的采样平均值。
为了理解衰减滤波器的效果，考虑单个计算密集型线程独占 CPU 的情况。线程的 CPU 利用率将以取决于时钟频率的速率累积时钟滴答。负载平均值将有效地为 1，从而导致衰减为
kg_estcpu = 0.66 kg_estcpu + kg_nice。
如果我们假设线程在时间间隔 i 内累积了 Ti 个时钟滴答，并且 kg_nice 为零，则每个时间间隔的 CPU 利用率将根据以下公式计入 kg_estcpu 的当前值
kg_estcpu = 0.66 T0
kg_estcpu = 0.66 (T1 + 0.66 T0) = 0.66 T1 + 0.44 T0
kg_estcpu = 0.66 T2 + 0.44 T1 + + 0.30 T0
kg_estcpu = 0.66 T3 + . . . + 0.20 T0
kg_estcpu = 0.66 T4 + . . . + 0.13 T0。
因此，在五次衰减计算之后，当前线程的 CPU 利用率值中仅保留了 13% 的 T0。由于衰减滤波器每秒应用一次，因此大约 90% 的 CPU 利用率在五秒后被遗忘。
可运行的线程会定期调整优先级，如前所述。但是，系统会忽略阻塞等待事件的线程：这些线程无法累积 CPU 使用率，因此可以一步计算出其过滤后的 CPU 使用率估计值。当存在许多阻塞线程时，这种优化可以显着减少系统的调度开销。当线程被唤醒并且睡眠时间超过一秒时，系统会重新计算线程的优先级。系统维护一个值 kg_slptime，它是线程阻塞等待事件所花费的时间的估计值。当线程调用 sleep() 时，kg_slptime 的值设置为零，并且当线程保持在 SLEEPING 或 STOPPED 状态时，每秒递增一次。当线程被唤醒时，系统根据以下公式计算 kg_estcpu 的值
然后使用此公式重新计算调度优先级。此分析忽略了 kg_nice 的影响；此外，使用的负载是当前负载平均值，而不是线程阻塞时的负载平均值。
ULE 调度器
ULE 调度器是 FreeBSD 支持 SMP（对称多处理）的全面改革的一部分而开发的。进行新的调度器有几个原因
• 解决 SMP 系统中处理器亲和性的需求
• 为 SMT（对称多线程）提供更好的支持——具有多个片上 CPU 核心的处理器
• 提高调度算法的性能，使其不再依赖于系统中的线程数
多处理器系统的目标是将多个 CPU 的能力应用于一个问题或一组问题，以在比在单处理器系统上运行更少的时间内获得结果。如果系统的可运行线程数与其 CPU 数相同，那么实现此目标很容易。每个可运行线程都获得一个 CPU 并运行完成。通常，许多可运行线程正在争夺少量处理器。调度器的一项工作是确保 CPU 始终处于繁忙状态，而不是浪费其周期。当线程完成其工作或阻塞等待资源时，会将其从其正在运行的处理器中移除。当线程在处理器上运行时，它会将其工作集——它正在执行的指令和它正在操作的数据——带入 CPU 的内存缓存中。
迁移线程是有成本的。当线程从一个处理器移动到另一个处理器时，其缓存中的工作集会丢失，并且必须从其正在运行的处理器中删除，然后加载到已迁移到的新 CPU 中。不考虑此成本的幼稚调度器的 SMP 系统的性能可能会低于单处理器系统。术语处理器亲和性描述了一种调度器，该调度器仅在必要时迁移线程，以便为空闲处理器提供工作。
许多微处理器现在提供对对称多线程的支持，其中处理器由多个 CPU 核心构建而成，每个 CPU 核心都可以执行一个线程。SMT 处理器中的 CPU 核心共享处理器的所有资源，例如内存缓存和对主内存的访问，因此它们比 SMP 系统中的处理器更紧密地同步。从线程的角度来看，它不知道其他线程正在同一处理器上运行，因为处理器正在独立处理它们。系统中需要意识到多个核心的代码片段是调度算法。SMT 情况是 SMP 系统提出的处理器亲和性问题的略有不同的版本。每个 CPU 核心都可以被视为具有自己的一组线程的处理器。在由支持 SMT 的 CPU 组成的 SMP 系统中，调度器将处理器上的每个核心视为资源较少但迁移线程成本较低的资源。
最初的 FreeBSD 调度器维护一个全局线程列表，它每秒遍历一次以重新计算其优先级。对所有线程使用单个列表意味着调度器的性能取决于系统中的任务数量，并且随着任务数量的增长，必须在调度器中花费更多的 CPU 时间来维护列表。ULE 调度器的设计目标是避免需要考虑系统中的所有可运行线程来做出调度决策。
ULE 调度器为系统中的每个 CPU 创建一组三个队列。拥有每个处理器的队列使得在 SMP 系统中实现处理器亲和性成为可能。
一个队列是空闲队列，其中存储所有空闲线程。另外两个队列被指定为当前队列和下一个队列。从当前队列中按优先级顺序选择要运行的线程，直到队列为空，此时当前队列和下一个队列被交换，并再次开始调度。空闲队列中的线程仅在其他两个队列为空时运行。实时线程和中断线程始终插入到当前队列中，以便它们具有尽可能低的调度延迟。交互式线程也插入到当前队列中，以保持系统可接受的交互响应。如果线程的自愿睡眠时间与运行时间之比低于某个阈值，则认为该线程是交互式的。交互性阈值在 ULE 代码中定义，并且不可配置。ULE 使用两个方程来计算线程的交互性得分。对于睡眠时间超过运行时间的线程，使用以下方程
当线程的运行时间超过其睡眠时间时，则使用以下方程
缩放因子是最大交互性得分除以二。得分低于交互性阈值的线程被认为是交互式的；所有其他线程都是非交互式的。sched_interact_update() 例程在线程存在的几个点被调用——例如，当线程被 wakeup() 调用唤醒时——以更新线程的运行时和睡眠时间。睡眠时间和运行时值仅允许增长到一定限制。当运行时和睡眠时间之和超过限制时，这些值将减小以使其回到范围内。完全不记住交互式线程的睡眠历史将不会保持交互性，从而导致较差的用户体验。记住交互式线程的睡眠时间过长会使线程获得超过其公平份额的 CPU。保留的历史记录量和交互性阈值是强烈影响用户在系统上的交互体验的两个值。
非交互式线程被放入下一个队列，并在队列切换时被调度运行。切换队列保证线程至少每两次队列切换运行一次，而与优先级无关，这确保了处理器公平共享。
使用两种机制在多个处理器之间迁移线程。当 CPU 在其任何队列中都没有工作要做时，它会在所有处理器共享的位掩码中标记一个位，表示它处于空闲状态。每当活动 CPU 即将向其自己的运行队列添加工作时，它首先检查以查看它是否有多余的工作以及系统中是否有另一个处理器处于空闲状态。如果找到空闲处理器，则使用 IPI（处理器间中断）将线程迁移到空闲处理器。通过检查共享位掩码做出迁移决策比扫描所有其他处理器的运行队列要快得多。在添加新任务时寻找空闲处理器效果很好，因为它在系统呈现负载时分散了负载。
第二种形式的迁移称为推送迁移，由系统定期执行，并且更积极地将工作卸载到系统中的其他处理器。每秒两次，sched_balance() 例程选择系统中负载最重和负载最轻的处理器，并均衡其运行队列。平衡仅在两个处理器之间完成，因为人们认为双处理器系统将是最常见的，并且为了防止平衡算法过于复杂并对调度器的性能产生不利影响。推送迁移确保了可运行线程之间的公平性。例如，在具有三个可运行线程的双处理器系统上，一个线程获得一个处理器而其他两个线程必须共享第二个处理器是不公平的。通过将线程从具有两个线程的处理器推送到具有一个线程的处理器，没有一个线程会无限期地单独运行。
处理 SMT 情况是全功能 CPU 之间负载平衡的派生形式，由处理器组处理。SMT 处理器中的每个 CPU 核心都有其自己的 kseq 结构，这些结构分组在一个 kseq 组结构下。图 1 显示了具有两个核心的单个处理器的示例。在具有多个支持 SMT 的处理器的 SMP 系统中，每个 CPU 将有一个处理器组。当调度器决定将线程迁移到哪个处理器或核心时，它会尝试首先选择同一处理器上的核心，然后再选择另一个处理器上的核心，因为这是成本最低的迁移路径。
结论
最初的 FreeBSD 调度器在许多情况下仍然运行良好。其优雅的简洁性（它用少于 100 行 C 代码编写）易于理解且难以作弊。但是，它不了解多处理器环境的复杂性；因此，它无法适应进行亲和性处理或为一组线程分配处理器份额。ULE 调度器是为了更有效地处理这些需求而开发的。
致谢
本文部分摘自 Marshall Kirk McKusick 和 George Neville-Neil 的《FreeBSD 操作系统设计与实现》第 4 章“进程管理”（表 1 来自同一章前面部分“进程状态”）。经 Pearson Education Inc. 许可转载 (0-201-70245-2)。版权所有 2005 年。要了解更多信息：http://www.awprofessional.com/title/0201702452。问
参考文献
1. Roberson, J. ULE: FreeBSD 的现代调度器。BSDCon 2003 会议论文集（2003 年 9 月）。
喜欢还是讨厌？请告诉我们
[email protected] 或 www.acmqueue.com/forums
MARSHALL KIRK McKUSICK 在加利福尼亚州伯克利拥有一家咨询公司，撰写关于 Unix 和 BSD 相关主题的书籍和文章，并教授课程。他在 Unix 领域的工作超过 20 年。在加州大学伯克利分校期间，他实现了 4.2 BSD 快速文件系统，并担任伯克利 CSRG（计算机系统研究组）的研究计算机科学家，负责监督 4.3 BSD 和 4.4 BSD 的开发和发布。他的兴趣领域是虚拟内存系统和文件系统。他获得了康奈尔大学的电气工程学士学位，并在加州大学伯克利分校完成了研究生学业，在那里他获得了计算机科学和工商管理硕士学位以及计算机科学博士学位。他是 Usenix 协会主席，也是 和 IEEE 的成员。
GEORGE V. NEVILLE-NEIL 为乐趣和利润而从事网络和操作系统代码工作。他还教授有关编程相关主题的课程。他的兴趣领域是代码探寻、操作系统和网络。他获得了马萨诸塞州波士顿东北大学的计算机科学学士学位。他是 、Usenix 协会和 IEEE 的成员。他是一位狂热的自行车手和旅行家，在东京和旧金山之间分配时间。
© 2004 1542-7730/04/1000 $5.00
最初发表于 Queue vol. 2, no. 7—
在 数字图书馆 中评论本文
更多相关文章
Amanda Casari, Julia Ferraioli, Juniper Lovato - 超越存储库
关于开源的大部分现有研究选择研究软件存储库而不是生态系统。开源存储库通常指的是版本控制系统中记录的工件，偶尔包括围绕存储库本身的交互。开源生态系统指的是存储库的集合、社区、它们的交互、激励、行为规范和文化。开源的去中心化性质使得对生态系统进行整体分析成为一项艰巨的任务，社区和身份以有机和不断发展的方式交叉。尽管存在这些复杂性，但对软件安全和供应链日益严格的审查使得在进行有关开源的研究时，采取基于生态系统的方法至关重要。
Guenever Aldrich, Danny Tsang, Jason McKenney - 为那些还不理解的项目经理们提供的三部分和谐
本文探讨了系统采购工具箱中的三种工具，它们可以加快开发和采购速度，同时降低项目风险：OSS、开放标准和敏捷/Scrum 软件开发流程都是 DoD 采购项目管理工具箱的强大补充。
Jessie Frazelle - 开源固件
开源固件可以通过使固件的行为更可见且更不可能造成危害，从而帮助将计算带到一个更安全的地方。本文的目标是使读者感到有能力要求供应商提供更多帮助，以推动这种改变。
Bart Decrem - 桌面 Linux：你在哪里？
桌面 Linux 已经走过了漫长的道路——而且这是一段过山车般的旅程。在互联网泡沫的顶峰时期，大约在 Red Hat 首次公开募股时，人们期望 Linux 很快就能在桌面上起飞。几年后，在股市崩盘和几家备受瞩目的 Linux 公司倒闭之后，权威人士迅速宣布桌面 Linux 胎死腹中。
© 保留所有权利。