第 8 章 SMPng 设计文档

版权 © 2002, 2004-2005 John Baldwin, Robert Watson

8.1. 绪论

这份文档对目前 SMPng 架构的设计与实现进行了介绍。 它首先介绍了基本的原语和相关工具， 其后是关于 FreeBSD 内核的同步与执行模型， 接下来讨论了具体系统中的锁策略， 并描述了在各个子系统中引入细粒度的同步和实现并行化的步骤， 最后是详细的实现说明， 用以解释最初做出某些设计决策的动机， 并使读者了解使用特定的原语所可能产生的重大影响。

这份文档仍在撰写当中， 并将不断更新以反映与 SMPng 项目有关的最新设计与实现的情况。 其中有许多小节目前还只是提纲， 但我们会逐渐为其充实内容。 关于这份文档的更新和建议， 请发给文档编辑。

SMPng 的目标是使内核能够并发执行。 基本上， 内核是一个很大而复杂的程序。 要让内核能够多线程地执行， 我们需要使用某些其它多线程程序在实现时所用到的工具， 这包括互斥体(mutex)、 共享/排他锁(shared/exclusive lock)、 信号量(semaphores) 和条件变量(condition variable)。 如果希望了解它们以及其它 SMP 术语， 请参阅本文的 术语表 一节。

8.2. 基本工具与上锁的基础知识

8.2.1. 原子操作指令和内存栅

关于内存栅和原子操作指令已经有很多介绍材料， 因此这一节并不打算对其进行详尽的介绍。 简而言之， 如果有对某一变量上写锁， 就不能在不获得相应的锁时对其进行读取操作。 也就是说， 内存栅的作用在于保证内存操作的相对顺序， 但并不保证内存操作的严格时序。 换言之， 内存栅并不保证 CPU 将本地快取缓存或存储缓冲的内容刷写回内存， 而是在锁释放时确保其所保护的数据， 对于能看到刚释放的那个锁的 CPU 或设备可见。 持有内存栅的 CPU 可以在其快取缓存或存储缓冲中将数据保持其所希望的、 任意长的时间， 但如果其它 CPU 在同一数据元上执行原子操作， 则第一个 CPU 必须保证， 其所更新的数据值， 以及内存栅所要求的任何其它操作， 对第二个 CPU 可见。

例如， 假设在一简单模型中， 认为在主存 (或某一全局快取缓存) 中的数据是可见的， 当某一 CPU 上触发原子操作时， 其它 CPU 的存储缓冲和快取缓存就必须对同一快取缓存线上的全部写操作， 以及内存栅之后的全部未完成操作进行刷写。

这样一来， 在使用由原子操作保护的内存单元时就需要特别小心。 例如， 在实现 sleep mutex 时， 我们就必须使用 atomic_cmpset 而不是 atomic_set 来打开 MTX_CONTESTED 位。 这样做的原因是， 我们需要把 mtx_lock 的值读到某个变量， 并据此进行决策。 然而， 我们读到的值可能是过时的， 也可能在我们进行决策的过程中发生变化。 因此， 当执行 atomic_set 时， 最终可能会对另一值进行置位， 而不是我们进行决策的那一个。 这就必须通过 atomic_cmpset 来保证只有在我们的决策依据是最新的时， 才对相应的变量进行置位。

最后， 原子操作只允许一次更新或读一个内存单元。 需要原子地更新多个单元时， 就必须使用锁来代替它了。 例如， 如果需要更新两个相互关联的计数器时， 就必须使用锁， 而不是两次单独的原子操作了。

8.2.2. 读锁与写锁

读锁并不需要像写锁那样强。 这两种类型的锁， 都需要确保通过它们访问的不是过时的数据。 然而， 只有写操作必须是排他的， 而多个线程则可以安全地读同一变量的值。 使用不同类型的锁用于读和写操作有许多各自不同的实现方式。

第一种方法是用 sx 锁， 它可以用于实现写时使用的排他锁， 而读时则作为共享锁。 这种方法十分简单明了。

第二种方法则略显晦涩。 可以用多个锁来保护同一数据元。 读时， 只需锁其中的一个读锁即可。 然而， 如果要写数据的话， 则需要首先上所有的写锁。 这会大大提高写操作的代价， 但当可能以多种方式访问数据时却可能非常有用。 例如， 父进程指针是同时受 proctree_lock sx 锁和进程 mutex 保护的。 在只希望检查已锁进程的父进程时， 用 proc 锁更为方便。 但是， 其它一些地方， 例如 inferior 这类需要通过父指针在进程树上进行搜索， 并对每个进程上锁的地方就不能这样做了， 否则， 将无法保证在对我们所获得的结果执行操作时， 之前检查时的状况依旧有效。

8.2.3. 上锁状态和结果

如果您需要使用锁来保持所检查变量的状态， 并据此执行某些操作时， 是不能仅仅在读变量之前对其上锁， 并在执行操作之前解锁的。 过早解锁将使变量再次可变， 这可能会导致之前所做的决策失效。 因此， 在所做检测引发的动作结束之前， 必须继续保持上锁状态。

8.3. 架构与设计概览

8.3.1. 对中断的处理

与许多其它多线程 UNIX® 内核所采取的模式类似， FreeBSD 会赋予中断处理程序独立的线程上下文， 这样做能够让中断线程在遇到锁时阻塞。 但为了避免不必要的延迟， 中断线程在内核中， 是以实时线程的优先级运行的。 因此， 中断处理程序不应执行过久， 以免饿死其它内核线程。 此外， 由于多个处理程序可以分享同一中断线程， 中断处理程序不应休眠， 或使用可能导致休眠的锁， 以避免将其它中断处理程序饿死。

目前在 FreeBSD 中的中断线程是指重量级中断线程。 这样称呼它们的原因在于， 转到中断线程需要执行一次完整的上下文切换操作。 在最初的实现中， 内核不允许抢占， 因此中断在打断内核线程之前， 必须等待内核线程阻塞或返回用户态之后才能执行。

为了解决响应时间问题， FreeBSD 内核现在采用了抢占式调度策略。 目前， 只有释放休眠 mutex 或发生中断时才能抢断内核线程， 但最终目标是在 FreeBSD 上实现下面所描述的全抢占式调度策略。

并非所有的中断处理程序都在独立的线程上下文中执行。 相反， 某些处理程序会直接在主中断上下文中执行。 这些中断处理程序， 现在被错误地命名为 “快速” 中断处理程序， 因为早期版本的内核中使用了 INTR_FAST 标志来标记这些处理程序。 目前只有时钟中断和串口 I/O 设备中断采用这一类型。 由于这些处理程序没有独立的上下文， 因而它们都不能获得阻塞性锁， 因此也就只能使用自旋 mutex。

最后， 还有一种称为轻量级上下文切换的优化， 可以在 MD 代码中使用。 因为中断线程都是在内核上下文中执行的， 所以它可以借用任意进程的 vmspace (虚拟内存地址空间)。 因此， 在轻量级上下文切换中， 切换到中断线程并不切换对应的 vmspace， 而是借用被中断线程的 vmspace。 为确保被中断线程的 vmspace 不在中断处理过程中消失， 被中断线程在中断线程不再借用其 vmspace 之前是不允许执行的。 刚才提到的情况可能在中断线程阻塞或完成时发生。 如果中断线程发生阻塞， 则它再次进入可运行状态时将使用自己的上下文， 这样一来， 就可以释放被中断的线程了。

这种优化的坏处在于它们和硬件紧密相关， 而且实现比较复杂， 因此只有在这样做能带来大幅性能改善时才应采用。 目前这样说可能还为时过早， 而且事实上可能会反而导致性能下降， 因为几乎所有的中断处理程序都会立即被全局锁 (Giant) 阻塞， 而这种阻塞将进而需要线程修正。 另外， Mike Smith 提议采用另一种方式来处理中断线程：

1. 每个中断处理程序分为两部分， 一个在主中断上下文中运行的主体 (predicate) 和一个在自己的线程上下文中执行的处理程序 (handler)。

2. 如果中断处理程序拥有主体， 则当触发中断时， 执行该主体。 如果主体返回真， 则认为该中断被处理完毕， 内核从中断返回。 如果主体返回假， 或者中断没有主体， 则调度运行线程式处理程序。

在这一模式中适当地采用轻量级上下文切换可能是非常复杂的。 因为我们可能会希望在未来改变这一模式， 因此现在最好的方案， 应该是暂时推迟在轻量级上下文切换之上的工作， 以便进一步完善中断处理架构， 随后再考察轻量级上下文切换是否适用。

8.3.2. 内核抢占与临界区

8.3.2.1. 内核抢占简介

内核抢占的概念很简单， 其基本思想是 CPU 总应执行优先级最高的工作。 当然， 至少在理想情况下是这样。 有些时候， 达成这一理想的代价会十分高昂， 以至于在这些情况下抢占会得不偿失。

实现完全的内核抢占十分简单： 在调度将要执行的线程并放入运行队列时， 检查它的优先级是否高于目前正在执行的线程。 如果是这样的话， 执行一次上下文切换并立即开始执行该线程。

尽管锁能够在抢占时保护多数数据， 但内核并不是可以安全地处处抢占的。 例如， 如果持有自旋 mutex 的线程被抢占， 而新线程也尝试获得同一自旋 mutex， 新线程就可能一直自旋下去， 因为被中断的线程可能永远没有机会运行了。 此外， 某些代码， 例如在 Alpha 上的 exec 对进程地址空间编号进行赋值的代码也不能被抢断， 因为它被用来支持实际的上下文切换操作。 在这些代码段中， 会通过使用临界区来临时禁用抢占。

8.3.2.2. 临界区

临界区 API 的责任是避免在临界区内发生上下文切换。 对于完全抢占式内核而言， 除了当前线程之外的其它线程的每个 setrunqueue 都是抢断点。 critical_enter 的一种实现方式是设置一线程私有标记， 并由其对应方清除。 如果调用 setrunqueue 时设置了这个标志， 则无论新线程和当前线程相比其优先级高低， 都不会发生抢占。 然而， 由于临界区会在自旋 mutex 中用于避免上下文切换， 而且能够同时获得多个自旋 mutex， 因此临界区 API 必须支持嵌套。 由于这个原因， 目前的实现中采用了嵌套计数， 而不仅仅是单个的线程标志。

为了尽可能缩短响应时间， 在临界区中的抢占被推迟， 而不是直接丢弃。 如果线程应被抢断， 并被置为可运行， 而当前线程处于临界区， 则会设置一线程私有标志， 表示有一个尚未进行的抢断操作。 当最外层临界区退出时， 会检查这一标志， 如果它被置位， 则当前线程会被抢断， 以允许更高优先级的线程开始运行。

中断会引发一个和自旋 mutex 有关的问题。 如果低级中断处理程序需要锁， 它就不能中断任何需要该锁的代码， 以避免可能发生的损坏数据结构的情况。 目前，这一机制是透过临界区 API 以 cpu_critical_enter 和 cpu_critical_exit 函数的形式实现的。 目前这一 API 会在所有 FreeBSD 所支持的平台上禁用和重新启用中断。 这种方法并不是最优的， 但它更易理解， 也更容易正确地实现。 理论上， 这一辅助 API 只需要配合在主中断上下文中的自旋 mutex 使用。 然而， 为了让代码更为简单， 它被用在了全部自旋 mutex， 甚至包括所有临界区上。 将其从 MI API 中剥离出来放入 MD API， 并只在需要使用它的 MI API 的自旋 mutex 实现中使用可能会有更好的效果。 如果我们最终采用了这种实现方式， 则 MD API 可能需要改名， 以彰显其为一单独 API 这一事实。

8.3.2.3. 设计折衷

如前面提到的， 当完全抢占并非总能提供最佳性能时， 采取了一些折衷的措施。

第一处折衷是， 抢占代码并不考虑其它 CPU 的存在。 假设我们有两个 CPU， A 和 B， 其中 A 上线程的优先级为 4， 而 B 上线程的优先级是 2。 如果 CPU B 令一优先级为 1 的线程进入可运行状态， 则理论上， 我们希望 CPU A 切换至这一新线程， 这样就有两个优先级最高的线程在运行了。 然而， 确定哪个 CPU 在抢占时更合适， 并通过 IPI 向那个 CPU 发出信号， 并完成相关的同步工作的代价十分高昂。 因此， 目前的代码会强制 CPU B 切换至更高优先级的线程。 请注意这样做仍会让系统进入更好的状态， 因为 CPU B 会去执行优先级为 1 而不是 2 的那个线程。

第二处折衷是限制对于实时优先级的内核线程的立即抢占。 在前面所定义的抢占操作的简单情形中， 低优先级总会被立即抢断 (或在其退出临界区后被抢断)。 然而， 许多在内核中执行的线程， 有很多只会执行很短的时间就会阻塞或返回用户态。 因此， 如果内核抢断这些线程并执行其它非实时的内核线程， 则内核可能会在这些线程马上要休眠或执行完毕之前切换出去。 这样一来， CPU 就必须调整快取缓存以配合新线程的执行。 当内核返回到被抢断的线程时， 它又需要重新填充之前丢失的快取缓存信息。 此外， 如果内核能够将对将阻塞或返回用户态的那个线程的抢断延迟到这之后的话， 还能够免去两次额外的上下文切换。 因此， 默认情况下， 只有在优先级较高的线程是实时线程时， 抢占代码才会立即执行抢断操作。

启用针对所有内核线程的完全抢占对于调试非常有帮助， 因为它会暴露出更多的竞态条件 (race conditions)。 在难以模拟这些竞态条件的单处理器系统中， 这显得尤其有用。 因此， 我们提供了内核选项 FULL_PREEMPTION 来启用针对所有内核线程的抢占， 这一选项主要用于调试目的。

8.3.3. 线程迁移

简单地说， 线程从一个 CPU 移动到另一个上的过程称作迁移。 在非抢占式内核中， 这只会在明确定义的点， 例如调用 msleep 或返回至用户态时才会发生。 但是， 在抢占式内核中， 中断可能会在任何时候强制抢断， 并导致迁移。 对于 CPU 私有的数据而言这可能会带来一些负面影响， 因为除 curthread 和 curpcb 以外的数据都可能在迁移过程中发生变化。 由于存在潜在的线程迁移， 使得未受保护的 CPU 私有数据访问变得无用。 这就需要在某些代码段禁止迁移， 以获得稳定的 CPU 私有数据。

目前我们采用临界区来避免迁移， 因为它们能够阻止上下文切换。 但是， 这有时可能是一种过于严厉的限制， 因为临界区实际上会阻止当前处理器上的中断线程。 因而， 提供了另一个 API， 用以指示当前进程在被抢断时， 不应迁移到另一 CPU。

这组 API 也叫线程牵制， 它由调度器提供。 这组 API 包括两个函数： sched_pin 和 sched_unpin。 这两个函数用于管理线程私有的计数 td_pinned。 如果嵌套计数大于零， 则线程将被锁住， 而线程开始运行时其嵌套计数为零， 表示处于未牵制状态。 所有的调度器实现中， 都要求保证牵制线程只在它们首次调用 sched_pin 时所在的 CPU 上运行。 由于只有线程自己会写嵌套计数， 而只有其它线程在受牵制线程没有执行， 且持有 sched_lock 锁时才会读嵌套计数， 因此访问 td_pinned 不必上锁。 sched_pin 函数会使嵌套计数递增， 而 sched_unpin 则使其递减。 注意， 这些函数只操作当前线程， 并将其绑定到其执行它时所处的 CPU 上。 要将任意线程绑定到指定的 CPU 上， 则应使用 sched_bind 和 sched_unbind。

8.3.4. 调出 (Callout)

内核机制 timeout 允许内核服务注册函数， 以作为 softclock 软件中断的一部分来执行。 事件将基于所希望的时钟嘀嗒的数目进行， 并在大约指定的时间回调用户提供的函数。

未决 timeout (超时) 事件的全局表是由一全局 mutex， callout_lock 保护的； 所有对 timeout 表的访问， 都必须首先拿到这个 mutex。 当 softclock 唤醒时， 它会扫描未决超时表， 并找出应启动的那些。 为避免锁逆序， softclock 线程会在调用所提供的 timeout 回调函数时首先释放 callout_lock mutex。 如果在注册时没有设置 CALLOUT_MPSAFE 标志， 则在调用调出函数之前， 还会抓取全局锁， 并在之后释放。 其后， callout_lock mutex 会在继续处理前再次获得。 softclock 代码在释放这个 mutex 时会非常小心地保持表的一致状态。 如果启用了 DIAGNOSTIC， 则每个函数的执行时间会被记录， 如果超过了某一阈值， 则会产生警告。

8.4. 特定数据的锁策略

8.4.1. 凭据

struct ucred 是内核内部的凭据结构体， 它通常作为内核中以进程为导向的访问控制的依据。 BSD-派生的系统采用一种 “写时复制” 的模型来处理凭据数据： 同一凭据结构体可能存在多个引用， 如果需要对其进行修改， 则这个结构体将被复制、 修改， 然后替换该引用。 由于在打开时用于实现访问控制的凭据快取缓存广泛存在， 这种做法会极大地节省内存。 在迁移到细粒度的 SMP 时， 这一模型也省去了大量的锁操作， 因为只有未共享的凭据才能实施修改， 因而避免了在使用共享凭据时额外的同步操作。

凭据结构体只有一个引用时， 被认为是可变的； 不允许改变共享的凭据结构体， 否则将可能导致发生竞态条件。 cr_mtxp mutex 用于保护 struct ucred 的引用计数， 以维护其一致性。 使用凭据结构体时， 必须在使用过程中保持有效的引用， 否则它就可能在这个不合理的消费者使用过程中被释放。

struct ucred mutex 是一种叶 mutex， 出于性能考虑， 它通过 mutex 池实现。

由于多用于访问控制决策， 凭据通常情况下是以只读方式访问的， 此时一般应使用 td_ucred， 因为它不需要上锁。 当更新进程凭据时， 检查和更新过程中必须持有 proc 锁。 检查和更新操作必须使用 p_ucred， 以避免检查时和使用时的竞态条件。

如果所调系统调用将在更新进程凭据之后进行访问控制检查， 则 td_ucred 也必须刷新为当前进程的值。 这样做能够避免修改后使用过时的凭据。 内核会自动在进程进入内核时， 将线程结构体的 td_ucred 指针刷新为进程的 p_ucred， 以保证内核访问控制能用到新的凭据。

8.4.2. 文件描述符和文件描述符表

详细内容将在稍后增加。

8.4.3. Jail 结构体

struct prison 保存了用于维护那些通过 jail(2) API 创建的 jail 所用到的管理信息。 这包括 jail 的主机名、 IP 地址， 以及一些相关的设置。 这个结构体包含引用计数， 因为指向这一结构体实例的指针会在多种凭据结构之间共享。 用了一个 mutex， pr_mtx 来保护对引用计数以及所有 jail 结构体中可变变量的读写访问。 有一些变量只会在创建 jail 的时刻发生变化， 只需持有有效的 struct prison 就可以开始读这些值了。 关于每个项目具体的上锁操作的文档， 可以在 sys/jail.h 的注释中找到。

8.4.4. MAC 框架

TrustedBSD MAC 框架会以 struct label 的形式维护一系列内核对象的数据。 一般来说， 内核中的 label (标签) 是由与其对应的内核对象同样的锁保护的。 例如， struct vnode 上的 v_label 标签是由其所在 vnode 上的 vnode 锁保护的。

除了嵌入到标准内核对象中的标签之外， MAC 框架也需要维护一组包含已注册的和激活策略的列表。 策略表和忙计数由一个全局 mutex (mac_policy_list_lock) 保护。 由于能够同时并行地进行许多访问控制检查， 对策略表的只读访问， 在增减忙计数时， 框架的入口处需要首先持有这个 mutex。 MAC 入口操作的过程中并不需要长时间持有此 mutex -- 有些操作， 例如文件系统对象上的标签操作 -- 是持久的。 要修改策略表， 例如在注册和解除注册策略时， 需要持有此 mutex， 而且要求引用计数为零， 以避免在用表时对其进行修改。

对于需要等待表进入闲置状态的线程， 提供了一个条件变量 mac_policy_list_not_busy， 但这一条件变量只能在调用者没有持有其它锁时才能使用， 否则可能会引发锁逆序问题。 忙计数在整个框架中事实上还扮演了某种形式的 共享/排他 锁的作用： 与 sx 锁不同的地方在于， 等待列表进入闲置状态的线程可以饿死， 而不是允许忙计数和其它在 MAC 框架入口 (或内部) 的锁之间的逆序情况。

8.4.5. 模块

对于模块子系统， 用于保护共享数据使用了一个单独的锁， 它是一个 共享/排他 (SX) 锁， 许多情况需要获得它 (以共享或排他的方式)， 因此我们提供了几个方便使用的宏来简化对这个锁的访问， 这些宏可以在 sys/module.h 中找到， 其用法都非常简单明了。 这个锁保护的主要是 module_t (当以共享方式上锁) 和全局的 modulelist_t 这两个结构体， 以及模块。 要更进一步理解这些锁策略， 需要仔细阅读 kern/kern_module.c 的源代码。

8.4.6. Newbus 设备树

newbus 系统使用了一个 sx 锁。 读的一方应持有共享 (读) 锁 (sx_slock(9)) 而写的一方则应持有排他 (写) 锁 (sx_xlock(9))。 内部函数一般不需要进行上锁， 而外部可见的则应根据需要上锁。 有些项目不需上锁， 因为这些项目在全程是只读的， (例如 device_get_softc(9))， 因而并不会产生竞态条件。 针对 newbus 数据结构的修改相对而言非常少， 因此单个的锁已经足够使用， 而不致造成性能折损。

8.4.7. 管道

...

8.4.8. 进程和线程

- 进程层次结构

- proc 锁及其参考

- 在系统调用过程中线程私有的 proc 项副本， 包括 td_ucred

- 进程间操作

- 进程组和会话

8.4.9. 调度器

本文在其它地方已经提供了很多关于 sched_lock 的参考和注释。

8.4.10. Select 和 Poll

select 和 poll 这两个函数允许线程阻塞并等待文件描述符上的事件 -- 最常见的情况是文件描述符是否可读或可写。

...

8.4.11. SIGIO

SIGIO 服务允许进程请求在特定文件描述符的读/写状态发生变化时， 将 SIGIO 信号群发给其进程组。 任意给定内核对象上， 只允许一进程或进程组注册 SIGIO， 这个进程或进程组称为属主 (owner)。 每一支持 SIGIO 注册的对象， 都包含一指针字段， 如果对象未注册则为 NULL， 否则是一指向描述这一注册的 struct sigio 的指针。 这一字段由一全局 mutex， sigio_lock 保护。 调用 SIGIO 维护函数时， 必须以 “传引用” 方式传递这一字段， 以确保本地注册副本的中这个字段不脱离锁的保护。

每个关联到进程或进程组的注册对象， 都会分配一 struct sigio 结构， 并包括指回该对象的指针、 属主、 信号信息、 凭据， 以及关于这一注册的一般信息。 每个进程或进程组都包含一个已注册 struct sigio 结构体的列表， 对进程来说是 p_sigiolst， 而对进程组则是 pg_sigiolst。 这些表由相应的进程或进程组锁保护。 除了用以将 struct sigio 连接到进程组上的 sio_pgsigio 字段之外， 在 struct sigio 中的多数字段在注册过程中都是不变量。 一般而言， 开发人员在实现新的支持 SIGIO 的内核对象时， 会希望避免在调用 SIGIO 支持函数， 例如 fsetown 或 funsetown 持有结构体锁， 以免去需要在结构体锁和全局 SIGIO 锁之间定义锁序。 通常可以通过提高结构体上的引用计数来达到这样的目的， 例如， 在进行管道操作时， 使用引用某个管道的文件描述符这样的操作， 就可以照此办理。

8.4.12. Sysctl

sysctl MIB 服务会从内核内部， 以及用户态的应用程序以系统调用的方式触发。 这会引发至少两个和锁有关的问题： 其一是对维持命名空间的数据结构的保护， 其二是与那些通过 sysctl 接口访问的内核变量和函数之间的交互。 由于 sysctl 允许直接导出 (甚至修改) 内核统计数据以及配置参数， sysctl 机制必须知道这些变量相应的上锁语义。 目前， sysctl 使用一个全局 sx 锁来实现对 sysctl 操作的串行化； 然而， 这些是假定用全局锁保护的， 并且没有提供其它保护机制。 这一节的其余部分将详细介绍上锁和 sysctl 相关变动的语义。

- 需要将 sysctl 更新值所进行的操作的顺序， 从原先的读旧值、 copyin 和 copyout、 写新值， 改为 copyin、 上锁、 读旧值、 写新值、 解锁、 copyout。 一般的 sysctl 只是 copyout 旧值并设置它们 copyin 所得到的新值， 仍然可以采用旧式的模型。 然而， 对所有 sysctl 处理程序采用第二种模型并避免锁操作方面， 第二种方式可能更规矩一些。

- 对于通常的情况， sysctl 可以内嵌一个 mutex 指针到 SYSCTL_FOO 宏和结构体中。 这对多数 sysctl 都是有效的。 对于使用 sx 锁、 自旋 mutex， 或其它除单一休眠 mutex 之外的锁策略， 可以用 SYSCTL_PROC 节点来完成正确的上锁。

8.4.13. 任务队列 (Taskqueue)

任务队列 (taskqueue) 的接口包括两个与之关联的用于保护相关数据的锁。 taskqueue_queues_mutex 是用于保护 taskqueue_queues TAILQ 的锁。 与这个系统关联的另一个 mutex 锁是位于 struct taskqueue 结构体上。 在此处使用同步原语的目的在于保护 struct taskqueue 中数据的完整性。 应注意的是， 并没有单独的、 帮助用户对其自身的工作进行锁的细化用的宏， 因为这些锁基本上不会在 kern/subr_taskqueue.c 以外的地方用到。

8.5. 实现说明

8.5.1. 休眠队列

休眠队列是一种用于保存同处一个等待通道 (wait channel) 上休眠线程列表的数据结构。 在等待通道上， 每个处于非睡眠状态的线程都会携带一个休眠队列结构。 当线程在等待通道上发生阻塞时， 它会将休眠队列结构体送给那个等待通道。 与等待通道关联的休眠队列则保存在一个散列表中。

休眠队列散列表中保存了包含至少一个阻塞线程的等待通道上的休眠队列。 这个散列表上的项称作 sleepqueue (休眠队列) 链。 它包含了一个休眠队列的链表， 以及一个自旋 mutex。 此处的自旋 mutex 用于保护休眠队列表， 以及其上休眠队列结构的内容。 一个等待通道上只会关联一个休眠队列。 如果有多个线程在同一等待通道上阻塞， 则休眠队列中将关联除第一个线程之外的全部线程。 当从休眠队列中删除线程时， 如果它不是唯一的阻塞的休眠线程， 则会获得主休眠队列的空闲表上的休眠队列结构。 最后一个线程会在恢复运行时获得主休眠队列。 由于线程有可能以和加入休眠队列不同的次序从其中删除， 因此， 线程离开队列时可能会携带与其进入时不同的休眠队列。

sleepq_lock 函数会锁住指定等待通道上休眠队列链的自旋 mutex。 sleepq_lookup 函数会在主休眠队列散列表中查找给定的等待通道。 如果没有找到主休眠队列， 它会返回 NULL。 sleepq_release 函数会对给定等待通道所关联的自旋 mutex 进行解锁。

将线程加入休眠队列是通过 sleepq_add 来完成的。 这个函数的参数包括等待通道、 指向保护等待通道的 mutex 的指针、 等待消息描述串， 以及一个标志掩码。 调用此函数之前， 应通过 sleepq_lock 为休眠队列链上锁。 如果等待通道不是通过 mutex 保护的 (或者它由全局锁保护)， 则应将 mutex 指针设置为 NULL。 而 flags (标志) 参数则包括了一个类型字段， 用以表示线程即将加入到的休眠队列的类型， 以及休眠是否是可中断的 (SLEEPQ_INTERRUPTIBLE)。 目前只有两种类型的休眠队列： 通过 msleep 和 wakeup 函数管理的传统休眠队列 (SLEEPQ_MSLEEP)， 以及基于条件变量的休眠队列 (SLEEPQ_CONDVAR)。 休眠队列类型和锁指针这两个参数完全是用于内部的断言检查。 调用 sleepq_add 的代码， 应明示地在关联的 sleepqueue 链透过 sleepq_lock 进行上锁之后， 并使用等待函数在休眠队列上阻塞之前解锁所有用于保护等待通道的 interlock。

通过使用 sleepq_set_timeout 可以为休眠设置超时。 这个函数的参数包括等待通道， 以及以相对时钟嘀嗒数为单位的超时时间。 如果休眠应被某个到来的信号打断， 则还应调用 sleepq_catch_signals 函数， 这个函数唯一的参数就是等待通道。 如果此线程已经有未决信号， 则 sleepq_catch_signals 将返回信号编号； 其它情况下， 其返回值则是 0。

一旦将线程加入到休眠队列中， 就可以使用 sleepq_wait 函数族之一将其阻塞了。 目前总共提供了四个等待函数， 使用哪个取决于调用这是否希望允许使用超时、 收到信号， 或用户态线程调度器打断休眠状态。 其中， sleepq_wait 函数简单地等待， 直到当前线程通过某个唤醒 (wakeup) 函数显式地恢复运行； sleepq_timedwait 函数则等待， 直到当前线程被显式地唤醒， 或者达到早前使用 sleepq_set_timeout 设置的超时； sleepq_wait_sig 函数会等待显式地唤醒， 或者其休眠被中断； 而 sleepq_timedwait_sig 函数则等待显式地唤醒、 达到用 sleepq_set_timeout 设置的超时， 或线程的休眠被中断这三种条件之一。 所有这些等待函数的第一个参数都是等待通道。 除此之外， sleepq_timedwait_sig 的第二个参数是一个布尔值， 表示之前调用 sleepq_catch_signals 时是否有发现未决信号。

如果线程被显式地恢复运行， 或其休眠被信号终止， 则等待函数会返回零， 表示休眠成功。 如果线程的休眠被超时或用户态线程调度器打断， 则会返回相应的 errno 数值。 需要注意的是， 因为 sleepq_wait 只能返回 0， 因此调用者不能指望它返回什么有用信息， 而应假定它完成了一次成功的休眠。 同时， 如果线程的休眠时间超时， 并同时被终止， 则 sleepq_timedwait_sig 将返回一个表示发生超时的错误代码。 如果返回错误代码是 0 而且使用 sleepq_wait_sig 或 sleepq_timedwait_sig 来执行阻塞， 则应调用 sleepq_calc_signal_retval 来检查是否有未决信号， 并据此选择合适的返回值。 较早前调用 sleepq_catch_signals 得到的信号编号， 应作为参数传给 sleepq_calc_signal_retval。

在同一休眠通道上休眠的线程， 可以由 sleepq_broadcast 或 sleepq_signal 函数来显式地唤醒。 这两个函数的参数均包括希望唤醒的等待通道、 将唤醒线程的优先级 (priority) 提高到多少， 以及一个标志 (flags) 参数表示将要恢复运行的休眠队列类型。 优先级参数将作为最低优先级， 如果将恢复的线程的优先级比此参数更高 (数值更低) 则其优先级不会调整。 标志参数主要用于函数内部的断言， 用以确认休眠队列没有被当做错误的类型对待。 例如， 条件变量函数不应恢复传统休眠队列的执行。 sleepq_broadcast 函数将恢复所有指定休眠通道上的阻塞线程， 而 sleepq_signal 则只恢复在等待通道上优先级最高的阻塞线程。 在调用这些函数之前， 应首先使用 sleepq_lock 对休眠队列上锁。

休眠线程也可以通过调用 sleepq_abort 函数来中断其休眠状态。 这个函数只有在持有 sched_lock 时才能调用， 而且线程必须处于休眠队列之上。 线程也可以通过使用 sleepq_remove 函数从指定的休眠队列中删除。 这个函数包括两个参数， 即休眠通道和线程， 它只在线程处于指定休眠通道的休眠队列之上时才将其唤醒。 如果线程不在那个休眠队列之上， 或同时处于另一等待通道的休眠队列上， 则这个函数将什么都不做而直接返回。

8.5.2. 十字转门 (turnstile)

- 与休眠队列的比较和不同。

- 查询/等待/释放 (lookup/wait/release) - 介绍 TDF_TSNOBLOCK 竞态条件。

- 优先级传播。

8.5.3. 关于 mutex 实现的一些细节

- 我们是否应要求 mtx_destroy() 持有 mutex， 因为无法安全地断言它们没有被其它对象持有？

8.5.3.1. 自旋 mutex

- 使用一临界区...

8.5.3.2. 休眠 mutex

- 描述 mutex 冲突时的竞态条件

- 为何在持有十字转门链锁时， 可以安全地读冲突 mutex 的 mtx_lock。

8.5.4. Witness

- 它能做什么

- 它如何工作

8.6. 其它话题

8.6.1. 中断源和 ICU 抽象

- struct isrc

- pic 驱动

8.6.2. 其它问题/话题

- 是否应将 interlock 传给 sema_wait？

- 是否应提供非休眠式 sx 锁？

- 增加一些关于正确使用引用计数的介绍。