今天聊聊 6.S081 第八部分的内容锁。读到这一章的时候我明显感觉到操作系统课程开始“进入状态”了。前面几章讲页表、讲 trap、讲调度虽然也有各种复杂指针和寄存器操作但基本还停留在“单线程思考”的层面。一旦进入多核环境很多事情就变得不可预测。程序明明逻辑上是对的可跑起来就是会错错的还不是每次都错是偶发性的。这种问题最折磨人而锁就是用来回应这种不确定性的核心工具。这篇文章我会从一段并发 Bug 讲起把 xv6 中自旋锁的实现、内存屏障、关中断这些底层细节一层层拆开再看实际实验里怎么把一把大锁优化成 per-CPU 结构最后聊死锁和排查技巧。如果你正在做 6.S081 的 lab或者想理解操作系统和并发程序里最底层的同步机制这篇应该能帮你省不少时间。1. 先从一个并发Bug说起锁到底在解决什么问题1.1 一段注定出错的多核代码我在做实验的时候曾经构造过一个很简单的场景两个 CPU 上的进程同时调用一个内核对进程表进行遍历比如一个进程在 fork另一个进程在 wait两边都在寻找或者修改同一个proc结构。如果不加任何保护结果完全取决于两个 CPU 的执行速度。A 核刚刚把p-state改成RUNNABLEB 核立刻读到了这个值而 A 核其实还没写完p-parent。这种交错会让两个进程看到一个“半更新”的结构轻则行为异常重则直接崩溃。可能有人觉得这不就是一个赋值操作嘛应该没什么问题。但真实的操作系统里没有任何一个操作是“天然原子”的。即使是一次看起来只有一条 C 语句的赋值编译成 RISC-V 指令之后也可能包含加载、移位、位运算、存储多个步骤。更别说像cnt这种它本质上是“读、改、写”三步。多核环境下两个核同时执行这三步就会互相覆盖。解决办法不是靠编译器而是靠操作系统自己提供互斥机制也就是锁。1.2 临界区、竞态与互斥的本质锁要保护的那段代码叫做临界区。临界区里的共享数据结构在一次只有一个 CPU 可以进入。这种“只允许一个执行者进入”的规则就是互斥。竞态条件指的就是多个执行流同时进入临界区导致最终结果取决于执行顺序的情况。竞态条件的可怕之处在于它不是必现的可能跑一万次才出现一次而这一万次跑出来的结论也可能完全不一致排查起来非常痛苦。打个比方临界区就像一间只有一个钥匙的会议室。两个人都想进去改同一份文件只有拿到钥匙的人才能进去改另一个人只能在门口等。问题是操作系统里“等”的方式有很多种可以不停敲门自旋也可以先去睡一觉等被叫醒再来睡眠。xv6 的内核里两种方式都有我后面会详细讲。需要强调的一点是锁本身并不保证临界区里的代码“原子执行”。它只保证同一个时刻只有一个 CPU 能进来但进入之后 CPU 还是会被中断打断、还是会被调度器切走。理解这一点特别重要因为很多人写着写着就会把“上了锁”和“不会被打断”混在一起这恰恰是出 Bug 的根源。2. 自旋锁实现拆解RISC-V指令与中断开关2.1 锁的结构一个整数加一个名字xv6 里自旋锁的定义在kernel/spinlock.h中结构体很短只有三个字段struct spinlock { int locked; char *name; struct cpu *cpu; };我来逐个解释。locked是核心状态0 表示无人持有1 表示已经被某个 CPU 持有。name纯粹是为了调试方便当你 panic 或者打印锁状态的时候能看到到底是哪把锁出了问题。cpu字段记录当前持有这把锁的 CPU 结构指针主要作用是方便调试以及某些场合下判断是否重复加锁。你可能好奇为什么用的是int而不是bool一方面是因为历史原因另外也是因为后面要用的原子指令直接对整数地址操作用int最顺手。真正的加锁和解锁逻辑在kernel/spinlock.c里代码量很少但每一行都值得细扣。2.2 acquire自旋、关中断与内存屏障acquire的完整实现如下void acquire(struct spinlock *lk) { push_off(); if(holding(lk)) panic(acquire); while(__sync_lock_test_and_set(lk-locked, 1) ! 0) ; __sync_synchronize(); lk-cpu mycpu(); }这段代码有几个关键点。第一push_off()在进入循环之前就关掉了当前 CPU 的中断。为什么要先关中断考虑这种情况CPU0 正在持有lk突然来了一个定时器中断CPU0 转而执行中断处理函数如果中断处理函数里也要获取这把锁那它就会一直自旋等锁。但持有锁的 CPU 正是 CPU0 自己它现在被中断打断了根本不可能返回去释放锁于是系统直接死锁。关闭中断之后同一个 CPU 在执行临界区期间不可能被中断打断这种死锁就避免了。第二__sync_lock_test_and_set(lk-locked, 1)是 GCC 提供的内建原子函数在 RISC-V 平台上会被编译成amoswap指令。这条指令完成“读旧值、写新值”两个动作并且在硬件层面保证这是一个原子操作。原子操作的引入是为了解决“两个 CPU 同时读都看到 0于是同时把自己当成锁的持有者”的问题。用生活化的说法amoswap就是“我把门牌号换成我的名字同时看看原来是谁”。这个操作本身是不可分割的硬件帮你保证了这一点。如果在 while 循环里发现locked原本是 1说明锁被别人持有当前 CPU 就在这里死等。这个过程就是“自旋”。以前我看这行代码总觉得有点浪费 CPU明明可以去干别的但操作系统底层就是这么设计的。自旋锁适用于临界区非常短、持有锁的时间可以控制在几十条指令以内的场景因为此时切换线程的开销可能比自旋等待还要大忙等反而是最高效的方案。第三拿到锁之后立即执行__sync_synchronize()这是一个全屏障。它的作用是把之前在临界区之前发生的所有内存操作顺序都固定下来防止编译器和 CPU 对指令进行重排。为什么需要这一步在无锁的情况下我们读写的普通内存操作CPU 为了性能可能会乱序执行或者缓存还没有及时刷到共享内存。如果我们在把locked置 1 之后立刻开始改共享数据别的 CPU 可能看不到我们之前写入的结果。所以需要一个屏障告诉硬件从这里开始我之前的写入必须对其他 CPU 可见我后续的读取也必须是看到别人最新的写入。延迟释放的一个小细节release 和 acquire 是对称的释放锁的代码是这样void release(struct spinlock *lk) { if(!holding(lk)) panic(release); lk-cpu 0; __sync_synchronize(); __sync_lock_release(lk-locked); pop_off(); }释放时先把cpu清空然后放一个屏障最后用__sync_lock_release把locked置回 0。这里屏障的作用是确保临界区里的写入全部完成后才把锁置为 0否则可能另一个 CPU 拿走锁后读到旧数据。你可以想象这样一个场景你写完一份报告把报告锁进抽屉然后把钥匙交给别人。如果钥匙先交出去报告还没放好别人打开抽屉看到的可能是一份不完整的文件。内存屏障就是强制“先放好文件再交钥匙”。pop_off()会恢复之前的中断状态。注意它不只是简单打开中断而是维护了一个嵌套计数器因为acquire可能会被嵌套调用比如在持有锁 A 的临界区里又去拿锁 B每一次 acquire 都会 push_offrelease 时必须一层层 pop 回来最后才能真正恢复中断标志。2.3 关中断的必要性和代价关中断解决了单核内死锁的问题但也带来了代价中断关闭期间这个 CPU 上的时钟中断无法触发调度器也无法切换进程。这意味着如果你的临界区写得太长其他进程在这个 CPU 上会感觉“卡顿”。更严重的是如果你在持有自旋锁的临界区里无意中调用了可能会睡眠的函数那么整个系统可能会僵死。xv6 的开发理念是内核代码必须非常谨慎地控制临界区长度这也是为什么后面会有另一类锁睡眠锁。3. xv6里的锁分布与典型使用场景3.1 查一遍内核里的锁都保护了什么我在做完 lab 之后闲着没事把 xv6 的内核main.c到各个文件里的锁都列了一遍发现锁的分布其实很有规律。下面是我整理的表格锁名保护的数据位置类型tickslock全局时钟计数器tickskernel/trap.cspinlockproc_table_lock进程表proc[]kernel/proc.cspinlockwait_lock等待队列相关状态kernel/proc.cspinlockbcache.lock块缓存链表kernel/bio.cspinlockicache.lock打开 inode 缓存链表kernel/fs.cspinlockfile_table_lock打开文件表kernel/file.cspinlockftable.lock文件描述符表kernel/file.cspinlocksleeplock文件系统的读写元数据过程kernel/fs.c等sleeper可以看到锁的粒度基本上和资源类型是对应的。每个子系统都有自己的锁而不是全内核只用一把“大锁”。原因很简单如果所有资源共用一把锁那么一个 CPU 在写文件的时候另一个 CPU 连进程表都不敢动多核的并行能力就完全浪费了。xv6 是教学系统锁数量还不算多但设计思路上已经是“每类资源一把锁细粒度控制”。3.2 中断处理器为什么也要锁中断处理函数里经常也会出现锁。以时钟中断为例CPU 进入 trap 之后会调用clockintr()里面会执行ticks。如果两个 CPU 同时产生时钟中断并且同时执行ticks那么计数就可能丢失。所以 xv6 在trap.c里用tickslock来保护这个变量。问题来了中断处理函数会打断正在执行的用户进程而用户进程是可抢占的此时acquire已经帮我们关闭了本地 CPU 的中断所以中断处理函数和普通代码之间不会出现互相持有锁的僵局。但这里有个非常容易踩的坑如果你在写某个驱动时需要在中断处理函数里获取一把锁那这个锁在所有普通代码路径中都必须以“关中断 拿锁”的顺序来使用。如果你在普通代码里先拿了锁但忘了关中断中断一来又把同一把锁拿了一次系统就死锁了。xv6 的acquire强制做了push_off()所以只要你在内核代码里使用自旋锁中断就已经是关上的。但当你自己写一些底层代码时一定不要试图跳过这一步或者在已经持有锁的情况下又手动打开中断那基本等于制造一颗定时炸弹。3.3 自旋锁不够用sleep lock 解决 IO 等待自旋锁只适合临界区极短的场景一旦临界区里需要等待 I/O比如磁盘读写自旋就是灾难。一个进程在等磁盘时CPU 死等不放其他进程也碰不了这块数据。更好的做法是让当前进程进入睡眠状态把 CPU 让给其他进程等 I/O 完成再被唤醒。xv6 用sleeplock实现这一点。它的结构里有一个自旋锁保护内部状态外加一个chan等待队列和locked标志。核心思路是想拿锁的时候先在自旋锁的保护下检查locked如果已经有人持有就调用sleep()把当前进程挂到等待队列上主动让出 CPU。等持有者调用release时再唤醒等待队列中的进程。这实际上是“中断睡眠”和“锁”的组合它能有效减少自旋浪费适合临界区可能阻塞的场景。一个典型例子是文件系统的读写。一个进程读一个磁盘块可能需要几十毫秒甚至更久。如果用自旋锁其他进程在这段时间内一直在忙等浪费整个 CPU 时间片。而用 sleep lock等待的进程直接睡过去CPU 可以去调度别的进程系统的吞吐量明显更高。学习这个章节时我最大的感受就是锁不是只有一种形式锁的选择本质上是在“浪费 CPU”和“阻塞延迟”之间找平衡。4. 锁的粒度从一把大锁拆到 per-CPU4.1 一把大锁的问题缓存行乒乓如果我们把所有共享状态都塞到一把锁里会发生什么假设系统有 8 个 CPU每个 CPU 在某一时刻都在执行自己的任务但每过 100 条指令就要碰到同一把锁。那么 7 个 CPU 都在自旋只有 1 个 CPU 在干活。这还是理想情况。从硬件层面看更隐蔽的问题是缓存一致性的开销。现代 CPU 采用缓存行机制每个核有自己的 L1/L2 缓存。当一个变量被多个核读写时这个缓存行会在不同核的缓存之间来回传输术语叫“缓存行乒乓”。在 xv6 的模拟环境里可能看不出差别但在真实机器上锁竞争导致的缓存一致流量会让系统整体性能大幅下降。因此把一把大锁拆成多把更小的锁不仅是为了让更多 CPU 进入临界区也是为了减少不同 CPU 对同一个缓存行的争用。理解了这一点再看实验里让“拆分锁”的任务就明白它的目标不是玄学优化而是实实在在的核心性能问题。4.2 内存分配器改造per-CPU freelist6.S081 的第八个实验有好几个任务其中一个是优化页面分配器。原始版本里内核维护一个全局的空闲页链表kalloc()和kfree()都要拿同一把锁。在多核跑负载时这把锁会变成严重瓶颈。我当时改造的思路是给每个 CPU 维护一个独立的空闲页链表每个链表配一把自己的锁。这样正常情况下每个 CPU 只需要操作自己的链表完全没有锁竞争。代码如下struct run { struct run *next; }; struct { struct spinlock lock; struct run *freelist; } kmem[NCPU]; void kfree(void *pa) { int cpu cpuid(); struct run *r (struct run*)pa; acquire(kmem[cpu].lock); r-next kmem[cpu].freelist; kmem[cpu].freelist r; release(kmem[cpu].lock); }这里面有几个细节要小心。第一cpuid()依赖当前 CPU id而push_off()已经关闭了抢占和中断所以在kfree和kalloc路径上可以安全调用。第二当一个 CPU 的空闲页用完时它需要从其他 CPU 的链表里“借”一些页。我实现的简单版本是遍历所有 CPU 的链表找到第一个非空的链表并取一页。这里要注意锁顺序确保不会两个 CPU 互相等待否则就会死锁。我的做法是固定按 CPU id 升序取锁借完立即释放不让嵌套持锁的窗口扩大。优化完之后我跑了一个简单的并发 malloc 测试性能提升非常明显。这也验证了一个道理在并发程序里减少共享数据的争用比优化临界区内部的代码更有效。4.3 块缓存改造哈希桶级别实验里另一个任务是把块缓存的单一大锁拆成多把锁。原始 xv6 中bcache有一个全局锁和一个按 LRU 排序的双向链表每次bget()都要遍历整个链表。为了优化我参考了课程提示把缓冲区分成多个哈希桶每个桶维护自己的一把锁和该桶下的节点链表。改造的关键点是哈希后的块号会落到一个具体桶里查找时只需要锁住对应桶即可。哈希桶的数量我选了 13 个课程给的建议是素数可以减少哈希冲突。每个桶是一个双向链表桶内按访问时间粗略排序。这里容易犯的错误是如果你试图同时维护一个跨桶的全局 LRU 顺序那又需要一把全局锁优化效果就打了折扣。xv6 的语义其实并不强依赖严格 LRU所以实验允许牺牲一点 LRU 精度换取并发的提升。我后来查看到课程说明里也提到只要保证“被多次访问的块大概率留在缓存”即可不需要强全局一致性。拆完之后我重新跑了块读写密集测试。在只有单个 CPU 的情况下感觉不到太大差异但在多核并发读写的压力下性能提升非常明显。这也是实验设计的一个很好的教学要点同样的功能不同的锁粒度性能差异巨大。4.4 锁粒度选择的判断标准从实验里我总结了一套判断锁粒度选择的标准。首先是锁竞争的频率如果临界区很少被多核同时访问那把锁大一点无所谓但如果频繁争用就要考虑按资源维度拆锁。其次是临界区的长度临界区里如果只是几行赋值自旋锁完全够用如果可能睡眠必须用 sleep lock。第三是共享数据的结构如果数据天然能按 key 分桶比如块号、桶号、CPU 号那就按这些属性拆锁如果数据本身是一棵大树比如文件系统目录树那只能按树路径层级去设计锁顺序这比按桶拆锁复杂得多。在实际使用中尽量选择“共享冲突较小、实现复杂度可控”的方案。学习操作系统实验不比谁加的锁多而是要比谁能在保证正确性的前提下让锁的粒度恰到好处。为了性能把锁拆得过头只会让代码难维护还会引入新的死锁风险。5. 死锁排查与锁顺序5.1 ABBA 死锁在 xv6 里怎么出现多锁系统最经典的错误就是 ABBA 死锁。想象有锁 A 和锁 BCPU0 持有 A 等待 BCPU1 持有 B 等待 A两边都在互等谁也不会释放手里已有的锁系统就永久卡住。在 xv6 里这种场景并不遥远。比如文件系统操作中一个进程要打开目录/a另一个进程要打开目录/b。如果两个进程都先锁目录 A 的 inode再锁目标 inode那只要它们选择了不同的顺序就可能出现 ABBA。再比如我写 lab 时遇到的一种场景一个函数在持有进程表锁的时候调用了一个会获取文件表锁的函数而另一个 CPU 在持有文件表锁时又试图获取进程表锁两边就撞上了。一开始我总觉得自己写的操作系统不会出死锁直到真实遇到一次只剩下黑屏终端、怎么按都没反应才承认死锁离自己并不远。排除死锁最有效的办法不是事后调试而是在写代码之前就定好锁的获取顺序。5.2 全局锁顺序与一致排序xv6 虽然没有像 Linux 的lockdep那样做动态死锁检测但它的代码风格确保了锁顺序的一致性。总的原则是如果你必须在持有锁 A 的情况下再获取锁 B那么所有代码路径都必须保证“先拿 A再拿 B”绝不允许出现“先拿 B再拿 A”的反向操作。那样两种路径交叉到一起就会死锁。我在写 lab 时还学到一个技巧如果某段代码不需要同时持有两把锁就尽量释放第一把锁再拿第二把锁。把“嵌套持锁”的范围缩到最小死锁风险自然下降。另外睡眠锁和自旋锁混用时也要特别注意。不要在持有自旋锁的时候去获取睡眠锁因为如果睡眠锁需要睡眠你就抱着自旋锁睡过去了其他 CPU 还在等你释放自旋锁场面会非常难看。验证锁顺序的一个实例在自查文件系统的路径解析代码时我总结了一个习惯每次看到inode相关的嵌套锁都会在脑内画一张“锁获取顺序图”。如果发现某个流程要打破既定顺序就直接改代码或者精简嵌套。这种“画图法”虽然土但比盯着代码死看效率高很多。实验之后我还习惯性地在所有acquire后面打印调试信息观察有没有周期性的等待关系。5.3 自查锁状态的几个笨办法死锁发生后怎么定位我的第一反应是使用 qemu 的 monitor 和 gdb 看当前每个 CPU 的 PC 指针。死锁时所有 CPU 通常都卡在acquire的 while 自旋循环里也就是__sync_lock_test_and_set那一行。在 gdb 里执行info threads再逐个线程bt就能看出谁在等哪把锁。如果死锁是偶发的或者你已经 panic 了那就在acquire里临时加一行打印锁名和当前 CPU id再查看当前谁持有这把锁。更系统的做法是在锁结构体里维护一个全局计数器每次 acquire 和 release 的次数都打印出来看看是否出现“一直 acquire 不 release”的锁。这些方法在课程 lab 里足够用比直接盲目加打印和猜来得快。6. 常见问题与自查清单6.1 三个典型翻车现场我在这个章节踩了不少坑挑三个最有代表性的说一说。第一个坑是用自旋锁保护需要睡眠的临界区。当时我写一个文件系统操作直接在持有bcache.lock的情况下调用bread而bread在缓存 miss 时可能触发磁盘读写进而睡眠。结果是整个系统陷入僵死的状态。修正方式是把临界区拆开在锁保护下只做缓存查找找到就返回找不到就释放锁再发起 I/O等 I/O 完成后再回来重新拿锁查缓存。第二个坑是不理解关中断的作用在写定时器驱动时又自己加了一次开中断。结果每次时钟中断一来就出现“CPU 在中断处理函数里尝试获取已经被同一个 CPU 持有的锁”的情况系统直接 panic。后来我重新阅读acquire的注释才明白xv6 的设计里关中断由acquire统一处理驱动代码不要画蛇添足。第三个坑是优化锁粒度时忽略了 per-CPU 结构的初始化。我把空闲页列表改成每 CPU 一个后忘了为每个 CPU 的锁都调用initlock导致某些 CPU 上的锁从未初始化locked是一个随机值系统跑起来后行为完全随机。这个问题花了我快半天时间排查最后是靠把kmem改成数组后逐项打印锁的状态才发现。教训是改结构体数组时初始化函数也必须要循环处理一个都不能漏。6.2 一个锁相关的快速自查清单这个清单是我在写并发内核代码时反复对照的分享出来希望能帮到你锁保护的数据是否所有读写路径都加了同一把锁有没有漏掉某一处持有锁的临界区里有没有调用可能睡眠的函数如果有改成 sleep lock 或拆分临界区。获取锁之前是否确保本地中断是关闭状态如果有任何可能显式检查一下。嵌套获取锁时所有路径的锁获取顺序是否都一致如果不一致立即调整。释放锁之后是否还有代码访问了原来受保护的数据这是最常见的 use-after-free 型 Bug。在 per-CPU 结构中是否每个 CPU 都有独立的锁并且正确初始化如果锁竞争严重是否可以考虑按 hash、按 CPU id 等方式拆分锁来避免缓存行乒乓如果你能把这些问题都回答清楚操作系统部分的并发代码基本就稳了。我个人实际操作下来的体会是锁这个东西概念上非常简单不过“会用锁”和“用对锁”之间隔着一整个系统的设计功力。6.S081 的这章让我真正建立了并发意识现在写任何共享数据结构的代码第一反应都是画出资源获取顺序图而不是先把功能写出来再说。这种习惯一旦养成对以后写多线程程序、看真实操作系统源码都帮助很大。希望这篇学习记录也能让你少走一点弯路。
