共计 7455 个字符，预计需要花费 19 分钟才能阅读完成。
前言
本篇算是对 从零开始写 OS 内核 – 锁与多线程同步 的一个补充修改，那篇文章里探讨了 lock 的基本原理和几种不同类型的 lock 以及它们的实用场景，但都只是原理性的，而且其实更偏差于 lock 在 user 态下的应用情景；而对于 kernel 中的 lock，尤其是 spinlock，以及 lock 在单核 / 多核 CPU 上的个性，都还没有具体地开展。本文将会从源头登程，从新探讨 kernel 下各种 lock 的实现和应用形式。
race 的本源
lock 是用来解决 data race 的，那么咱们首先要问本人一个问题，data race 的本源是什么？
一个通常的答复是：多个 threads 在多个 CPU 上的同时运行，或者在同一 CPU 上的切换并发运行，如果拜访 / 批改了同一数据，那么就会导致 race。
这个答复对 user 态下兴许是对的；然而对于 kernel，它还并不残缺，甚至从某种意义上说还有点轻重倒置。
这里咱们先抛开多核 CPU，先探讨单核的情景，这也是咱们的这个 scroll 我的项目所应用的。咱们来纠正下面的这个答复里的几个不足之处和认知偏差。
代码交错（interleave）
对于 kernel 而言，除了 threads 之间的切换，还有一个很重要的角色是 interrupt（留神这里的术语应用，interrupt 是指内部中断，即硬中断），它也能打断一个正在执行的代码，进而可能导致 data race。
因而严格来说，引起 race 的实质起因是代码执行流的 交错 （interleave）。在 kernel 中，它既可能是由 threads 切换导致，也可能是因为 interrupt 导致。对于 interrupt，你必须要意识到以下几点：
- 它随时可能产生，不受管制，无奈预测；
- interrupt 的处理过程，即 中断上下文 （
interrupt context），不属于任何 thread，而是一个独立的执行流，它只是临时“打断”一下以后的执行流而已；既然它不属于任何 thread，那么它就不可能成为被scheduler调度的对象，也就是说它不能够yield，sleep等，这也意味着在 interrupt 里不能够应用yieldlock或者阻塞锁；
preempt 与 interrupt
在 user 空间下，咱们通常认为引起 data race 的次要起因是 threads 的切换，导致可能对同一数据的并发拜访 / 批改。然而到了 kernel 中，这种观点其实须要从新扫视一下。诚然线程在 kernel 态下也会产生互相切换，但咱们须要意识到，这种切换行为的本源其实就来自于 kernel 本人：是 kernel 的 scheduler 管制着 threads 的切换调度，所以这里有点因果关系倒置的意思。咱们无妨思考：如果 kernel 暂停了 threads 切换调度，那么由 threads 切换引起的 data race 问题是不是就不复存在了？
从专门术语上讲，threads 之间的切换执行，叫做 抢占 （preempt），也就是说在 threads-A 运行过程中，kernel 将它从 CPU 上换下，并换上 thread-B 执行。留神这里的切换，可能是 thread-A 被动放弃了 CPU（例如期待某个资源而 sleep），也可能是被 kernel 强制的（例如工夫片用完了）。因而前面咱们就用 preempt 这个术语来指代 threads 切换。
这里要分清 preempt 和 interrupt 之间的区别，它们尽管都会暂停以后执行流而换到另一个，然而它们之间是有着本质区别的：
preempt是基于 thread 的，而interrupt是独立的个体，它尽管会打断 thread，但并不和这个 thread 有任何株连关系；preempt行为是同步的，齐全受 kernel 逻辑管制的；interrupt则是异步产生的，无奈预知的；
对于 Linux 内核，产生 preempt 决策的几个最重要的工夫点是：
- 从
interrupt解决返回时； - 从
syscall返回时； - 代码被动调用 scheduler 时，例如线程 yield，sleep，exit 等行为；
对应到咱们 scroll 我的项目的实现上，最常见的切换点在 timer interrupt 解决中，这里咱们会查看以后运行的 thread 工夫片是否曾经用完，如果用完了则调用 scheduler，触发 threads 切换（即 preempt）。所以咱们通常说多 threads 的轮转切换是由 timer interrupt 驱动的，这种说法诚然没有错，但并不严格。更通常的做法是，将调用 scheduler 的动作移出 timer interrupt handler，而延后到 interrupt 的通用退出过程中，这对于 timer interrupt 来说，最终的成果其实没有什么本质区别；当然有一个扭转就是，所有的 interrupt 在退出都会去调用 scheduler，不仅仅是 timer。
咱们来看批改后的 timer interrupt 处理函数，它不再调用 scheduler，而是只将以后（interrupt 前）运行的 thread 的运行工夫 ticks 减少，如果达到了工夫片下限，那么设置这个 thread 的 need_reschedule = true，标记该 thread 须要切换：
static void timer_callback(isr_params_t regs) {
// ...
tcb_t* crt_thread = get_crt_thread();
crt_thread->ticks++;
if (crt_thread->ticks >= crt_thread->time_silice) {crt_thread->need_reschedule = true;}
}在 interrupt 退出时，会调用 scheduler：
[EXTERN schedule]
interrupt_exit:
; call scheduler
call schedule
;... 在 schedule 函数里会查看 need_reschedule，如果为 true，则产生切换（preempt）。
敞开 preempt
正因为 preempt 的行为齐全是由 kernel 本人管制的，所以当咱们须要排除 preempt 导致的 data race 问题时，能够从本源上解决它，即禁止 preempt：既然 threads 不切换，又何来 data race 呢？
当然敞开 preempt 是有代价的，它会让以后 thread 独占以后 CPU，对 threads 调度的公平性有所侵害，所以应该使敞开 preempt 工夫尽量短。
敞开 interrupt
敞开 preempt 只能解决 threads 切换导致的 race 问题，然而如果咱们须要爱护一个被 thread 和 interrupt 都拜访的数据，那么仅仅是敞开 preempt 是不够的。例如 thread-A 在运行，只管 preempt 禁用了，不可能有其它 thread 干预了，然而 interrupt 可能随时会打断 thread-A，如果此时 thread-A 持有了一个 lock，同时 interrupt 处理过程中也须要获取这个 lock，那么 interrupt 就会卡住，这是相对不容许的，因为 interrupt 不能够 sleep 或者 yield，然而此时 thread-A 又被打断了无奈持续运行并开释这个 lock，所以这里产生了 deadlock。以上探讨依然仅限于在一个 CPU 上产生的状况。
总而言之，interrupt 一旦开始解决，必须解决完（而且要尽可能地快）。当在 interrupt 里须要获取 lock 时，必须保障：
- lock 不能够被本 CPU 上的其它人持有；
- lock 如果在其它 CPU 上被持有了，那么本 interrupt 只能原地 spin 期待，不能够被剥夺 CPU，也就是说 yield，sleep 等都是禁止的；你不能够推延 interrupt 的解决；
然而 interrupt 是不可预知的，所以为了满足上述要求的第一点，只能反其道而行之：确保在 lock 被持有之后，不能够再有 interrupt 横插进来。也就是说如果 lock 可能会被 interrupt 应用到，上锁时须要敞开 interrupt，这样就能够齐全杜绝 interrupt 引发的问题。
最典型的利用场景就是各种输出设施的驱动，例如键盘，每次有新的按键输出，就会触发键盘 interrupt，那么 interrupt 处理函数就会从硬件端口上读取输出，并搁置到 kernel 里的一个缓冲区；而用户线程可能正在期待读取这个缓冲区；这是典型的 producer-consumer 模型，这个缓冲区必定须要 lock 来爱护，它既要避免多个用户 threads 之间对该缓冲区的并发 race 问题，也要避免 thread 和键盘 interrupt 处理函数之间的 race 问题，这把锁就须要敞开中 interrupt。
敞开 interrupt 同样是有代价的，它会升高系统对 interrupt 的响应速度，这对于对实时性要求高的零碎是不可容忍的，例如控制系统，人机交互的零碎等。所以敞开 interrupt 的工夫同样须要管制得十分短。
同时，敞开了 interrupt 后，实际上 preempt 的大多数触发点也就被敞开了，因为没了 interrupt，也就不会有 interrupt 退出时的 scheduler 调用点。然而这并意味着齐全平安了，因为 preempt 依然有可能产生，例如 thread 被动调用 scheduler（这种状况应该不多见，我并不确定，欢送斧正）。但不管怎样，最保险的做法是，敞开 interrupt 同时也敞开 preempt，它保障了在以后代码执行流对本 CPU 的齐全独占（mutual exclusive），也就彻底防止了 data race。
再看 spinlock
咱们当初来从新考查 kernel 中的 spinlock，它和 user 态下的 spinlock 齐全不同，远非看上去的那么简略。咱们当初开始要思考有无 interrupt，以及在单核 / 多核 CPU 上的不同情景。
没有 interrupt
首先思考没有 interrupt 的状况：这里是指 lock 不会被 interrupt handler 应用到，也就是说只有失常的 threads 之间的竞争。当初开始咱们须要对单个 / 多个 CPU 离开探讨。
如果是一个 CPU（留神这里的“一个 CPU”，能够是指单核处理器，也能够指多核处理器上的某一个 CPU，并且两个竞争的 threads 都运行在这个核上，它实际上就等效于单核处理器了），在以前的探讨中咱们提到过，单纯的 spin 期待在一个 CPU 上是没有任何意义的，因为持有 lock 的 thread 无奈失去运行并开释 lock，所以以后 thread 在它的运行周期内 spin 空转齐全是浪费时间。所以 spinlock 要做的第一件事件就是，敞开 preempt，这样别的 thread 页也就不可能在这个 CPU 上 spin 空转了。
你可能说这样还算什么 spinlock，齐全是让一个 thread 霸占了这个 CPU。这么说当然也没错，然而这仅仅是对于一个 CPU 而言，而且你会发现对于单个 CPU，这其实是最正当的做法了。
如果进一步思考多个 CPU 的状况，那么 spin 的语义实际上还是存在的。多个 CPU 上的 threads 可能同时竞争这个 lock，那么仅仅敞开本 CPU 上的 preempt 是不够的，其它 CPU 还是可能退出竞争，所以这里还须要真正的 atomic 竞争机制，也就是后面文章里讲过的 CAS 原子操作：
void spinlock_lock(spinlock_t *splock) {
// Disable preempt on local cpu.
disable_preempt();
// CAS competition for multi-processor.
#ifndef SINGLE_PROCESSOR
while (atomic_exchange(&splock->hold , LOCKED_YES) != LOCKED_NO) {}
#endif
}再强调一下下面的 lock 不能够被 interrupt 应用，咱们的探讨临时还没有将 interrupt 思考进来，仅仅解决 threads 之间的竞争问题。
另外后面的文章里也提到过，spinlock 通常用于爱护比拟小的 critical section，这在多核 CPU 上能够防止 spin 空转节约太多 CPU 工夫；对于单核的情景，小的 critical section 保障了以后持有 lock 的 thread 不要霸占 CPU（即敞开 preempt）太久，影响调度公平性。
你可能会问 disable_preempt() 是怎么实现的。仿照 Linux 的做法，在 thread 的构造体里定义一个整数 preempt_count，每次调用 disable_preempt() 就将它加 1，enable_preempt 就减 1。只有当 preempt_count 为 0 时才能够 preempt，否则 scheduler 就认为以后 preempt 在该 thread 所在的 CPU 上是敞开的：
struct task_struct {
// ...
uint32 preempt_count;
};
void disable_preempt() {get_crt_thread()->preempt_count += 1;
}
void enable_preempt() {get_crt_thread()->preempt_count -= 1;
}所以能够发现，所谓的敞开 preempt，只能敞开以后 thread 所在的 CPU 上的 preempt，使以后 thread 独占该 CPU；然而你无奈影响到多核处理器上的其它 CPU，这也是为什么在多核的状况下，须要下面的 CAS 竞争机制保障平安。
引入 interrupt
接下来思考 interrupt 和 thread 之间竞争的状况。后面曾经剖析过，interrupt 不依靠于任何 thread，所以它不能够 sleep 或者 yield，所以它只能原地 spin 期待。如果某个 lock 可能会被 interrupt 应用，那么其它使用者在获取这个 lock 时，必须先敞开 interrupt，这样能力彻底杜绝 interrupt 的干预。
因而在 kernel 的 spinlock 的实现上，除了失常的 lock 接口，它还须要提供一个敞开 interrupt 的接口，例如 spinlock_lock_irqsave：
void spinlock_lock_irqsave(spinlock_t *splock) {
// First disable preempt.
disable_preempt();
// Now disable local interrupt and save interrupt flag bit.
uint32 eflags = get_eflags();
disable_interrupt();
splock->interrupt_mask = (eflags & (1 << 9));
// For multi-processor, competing for CAS is still needed.
#ifndef SINGLE_PROCESSOR
while (atomic_exchange(&splock->hold , LOCKED_YES) != LOCKED_NO) {}
#endif
}这个接口不仅敞开 preempt，同时也敞开了 interrupt，确保该 lock 能够被 interrupt 应用；在 Linux 内核里也有相似的 API 用法。
之所以叫 spinlock_lock_irqsave，是因为它会将之前的 interrupt 状态保留下来，在 unlock 时复原之，而不是简略的关上 interrupt，因为有可能在 lock 前 interrupt 原本就是敞开的，那么你不能够在 unlock 时擅自关上，只能复原原样。
同样，即便是同时敞开 preempt 和 interrupt，也只能保障本 CPU 平安；而对于多核的状况，依然须要和其它 CPU 持续 CAS 竞争 lock，确保多核之间的安全性。
spin 还是 yield
在 scroll 我的项目里咱们还实现过一种 yieldlock，即获取不到 lock 时被动放弃 CPU，然而不睡眠，只是 yield，这也是一种轻量级的 lock，它不像 spinlock 那样可能会有工夫节约。
yieldlock 显然不能够被 interrupt 应用，起因还是之前说过的，interrupt 不属于任何 thread，所以它不能够 yield，否则可能会导致死锁。例子还是下面那个，一个 thread-A 持有一个 lock，如果被 interrupt 打断了，interrupt 也想获取这个 lock，然而它曾经被 thread-A 持有，interrupt 此时没有任何方法，它不能够 yield，因为它不是一个 thread。无妨构想一下，就算你此时真的想 yield，那 yield 谁呢，thread-A 吗？但此刻咱们想要的是 thread-A 持续运行并开释 lock，那这显然是矛盾的。
对于没有 interrupt 染指的场景（即只有 threads 之间竞争），应用 spinlock（这里是指非 interrupt 版本的接口函数）和 yieldlock 都是能够的，这里比拟一下它们的原理：
spinlock会间接敞开preempt保障本 CPU 的独占；如果是多核 CPU，还须要 CAS 竞争，失败时原地 spin 期待；yieldlock间接采取 CAS 竞争的形式，不论是本 CPU 还是多核的状况；如果竞争失败，则临时让出 CPU，等下一次有机会再重试；
后面也提到过，在单核状况下，spinlock 略微有点徒有虚名，它甚至不须要 CAS 竞争，也不会呈现 spin 期待，而是间接敞开 preempt 来杜绝 threads 竞争。不过这也没关系，只有达到 lock 的目标就能够了，而且这也可能是最正当的做法了。
再来看一下它们各自的毛病：
spinlock因为敞开了 preempt 而临时霸占 CPU，可能会稍稍影响公平性；yieldlock实质上是一种提早的重试，有可能重试好几次都还是失败，这会节约一些 CPU 工夫；
然而还是要强调，这两种 lock 都是用于爱护十分小的 critical section，所以下面所说的问题都会被管制在尽可能小的范畴之内，减小竞争带来的损耗。
总结
本文重新整理探讨了 kernel 中的 lock 问题，尤其是 spinlock，作为一种在 kernel 中十分罕用的锁，它充分体现了 kernel 下锁的复杂性和多样性。这外面最重要的概念就是 preempt 和 interrupt，以及它们的区别。kernel 中锁的原理和应用场景，简直都是间接和这两个概念相干的，这也是 kernel 和 user 态下锁的不同之处。