1. 项目概述深入理解并发编程的基石锁对于任何一位从事系统编程或高性能应用开发的工程师来说都是一个既熟悉又令人头疼的概念。熟悉是因为它无处不在是保证多线程/多进程环境下数据一致性的基本工具头疼是因为锁的设计和使用稍有不慎就会引入死锁、性能瓶颈、甚至难以复现的诡异Bug。MIT 6.S081 操作系统课程的 Lab 8: locks正是这样一个旨在让你从“会用锁”到“懂锁”再到“设计高效锁”的硬核实验。它不满足于让你简单地调用acquire和release而是引导你深入操作系统内核亲手剖析和优化真实的锁实现直面高并发场景下的性能挑战。这个实验的核心价值在于它将锁从一个抽象的黑盒API还原为一个具体的数据结构和算法问题。你会看到锁的本质就是一小块内存struct spinlock以及围绕它展开的原子操作、内存屏障和调度策略。通过完成这个实验你将彻底理解自旋锁spinlock在单处理器和多处理器环境下的不同行为学会如何通过拆分锁lock splitting和读写锁等策略来减少锁竞争并最终将这些知识应用于优化一个真实的内核模块——内存分配器kalloc和块缓存buffer cache的性能。这不仅仅是完成几个函数填空而是一次完整的并发问题诊断与性能调优实战其思考方式对你在日常开发中设计高并发服务、数据库或中间件都有着直接的指导意义。2. 实验目标与核心挑战拆解Lab 8 通常被分解为几个循序渐进的子任务每个任务都瞄准并发编程中的一个特定痛点。2.1 任务一内存分配器锁优化第一个任务聚焦于XV6内核的物理内存分配器kalloc。原始的kalloc.c使用了一个全局的自旋锁来保护空闲内存页链表。这意味着无论系统中有多少个CPU核心任何核心在分配或释放物理页时都必须争夺这同一把锁。在单核环境下这或许问题不大但在多核SMP环境下这就成了严重的性能瓶颈。想象一下多个CPU核心频繁地进行内存分配例如创建新进程、扩展用户堆栈它们会在这一把锁上发生激烈的竞争导致大量的CPU周期浪费在空转自旋等待上真正的内存操作吞吐量却上不去。这个任务的目标非常明确将全局锁拆分为每个CPU核心一个的独立锁即实现“每CPU空闲列表”。每个CPU核心维护自己的空闲页链表分配和释放页时优先操作本CPU的链表。这样大部分情况下各CPU互不干扰并行度大幅提升。只有当某个CPU自己的链表空了才需要去“窃取”其他CPU链表中的页此时才涉及跨CPU的锁操作。这个设计完美诠释了“分而治之”的思想是减少锁竞争最经典的模式之一。注意这里的“每CPU”数据结构per-CPU data structure是高性能系统编程中的常见技巧。它不仅用于内存分配器也广泛用于网络栈、统计计数等场景。关键点在于要确保每个CPU访问的是自己独有的数据副本这通常需要利用CPU编号cpuid()作为数组索引。2.2 任务二块缓存锁优化第二个任务的挑战更大目标是块缓存buffer cache。块缓存是内核用于缓存磁盘块disk block的内存区域所有文件系统的读写请求最终都会经过它。原始的XV6实现使用了一个双向链表LRU链表来管理所有缓存块并用一把大锁保护这个链表和所有的缓存块。这里的性能问题比内存分配器更复杂锁粒度问题一把锁保护所有缓存块任何块查找bget或释放都会锁住整个缓存即使在读写不同文件的不同块时也无法并行。查找效率问题每次根据设备号和块号查找缓存块都需要遍历整个链表时间复杂度为O(n)。虚假共享问题即使为每个缓存块加独立的锁如果它们频繁在同一个缓存行cache line上更新也会导致CPU缓存失效损害性能。因此优化策略需要多管齐下使用哈希表替代链表将缓存块组织到多个哈希桶中。查找时先根据设备号和块号计算哈希值定位到某个桶只需遍历该桶内的短链表即可将查找复杂度降至近似O(1)。细化锁粒度为每个哈希桶配备一把锁而不是全局一把锁。这样操作不同哈希桶的请求就可以真正并行。移除缓存块本身的锁一个常见的优化是当使用桶锁保护了桶内链表的完整性后可以移除每个buf结构体上原有的锁进一步减少锁开销。但需要仔细设计确保在持有桶锁的情况下才能修改buf的元数据。2.3 任务三避免死锁与锁排序在所有锁优化实验中一个贯穿始终的幽灵就是死锁。当你引入多个锁比如多个桶锁、每CPU的锁时如果两个线程以不同的顺序获取这些锁就可能形成循环等待导致死锁。例如在块缓存优化中假设线程A持有桶1的锁试图获取桶2的锁同时线程B持有桶2的锁试图获取桶1的锁。这就构成了典型的死锁。解决方案是强制规定一个全局的锁获取顺序。在XV6的bget中这意味着你需要定义一个规则比如总是先获取哈希值较小的桶的锁再获取哈希值较大的桶的锁。当需要同时持有两把锁时必须按照这个固定顺序去获取。在内存分配器的“窃取”场景中也可能出现死锁CPU1试图从CPU2的链表中偷页需要先锁住自己的链表再锁CPU2的链表而CPU2可能正相反。为了避免这种情况可以规定一个基于CPU编号的锁获取顺序或者使用更巧妙的无锁或尝试锁trylock机制。3. 内存分配器锁优化实战让我们深入到代码层面看看如何实现“每CPU空闲列表”。首先你需要修改kernel/kalloc.c中的数据结构。3.1 数据结构改造原始结构只有一个全局的空闲页链表和一把锁struct { struct spinlock lock; struct run *freelist; } kmem;我们需要将其改为一个数组每个元素对应一个CPUstruct { struct spinlock lock; struct run *freelist; } kmem[NCPU]; // NCPU 是内核支持的最大CPU数在param.h中定义同时我们可能还需要一个后备列表或者一个机制来处理所有CPU列表都为空的情况尽管在实验初始状态下所有内存会被分配给某个CPU的列表。3.2 核心函数重写kalloc和kfreekalloc函数调用push_off()关闭中断并获取当前CPU的ID。关闭中断是为了防止在获取当前CPU ID后、操作本CPU列表前被调度到其他CPU上导致数据错乱。根据cpuid()获取当前CPU的索引。获取该CPU对应的kmem[cpuid].lock。从kmem[cpuid].freelist中取出一个空闲页。如果成功释放锁打开中断pop_off()并返回该页。如果当前CPU的列表为空则需要执行“窃取”逻辑 a. 遍历其他所有CPU的列表kmem[i].freelist。 b. 在尝试获取其他CPU的锁之前必须先释放自己CPU的锁否则可能违反锁顺序导致死锁。 c. 尝试获取另一个CPU (i) 的锁。如果获取成功且它的列表非空则“偷走”一个页或者偷走一半这是一种常见的负载均衡策略释放CPU i的锁然后跳回步骤3重新获取自己CPU的锁并将偷来的页放入自己列表或直接分配。 d. 如果遍历完所有其他CPU都没偷到页说明系统内存已耗尽返回0。kfree函数将释放的页清零安全考虑。关闭中断获取当前CPU ID。获取当前CPU对应的锁。将释放的页插入到当前CPU空闲链表头部。释放锁打开中断。3.3 初始化与启动时的分配在kinit函数中你需要初始化所有NCPU个锁。然后在系统启动时所有可用的物理页需要被分配到某个CPU的列表中。一个简单且公平的策略是以轮询round-robin的方式将这些页分配到各个CPU的列表中。这可以在freerange函数中实现每次调用kfree释放一个页范围时实际上就完成了初始分配。由于启动时只有一个CPU在运行我们需要模拟轮询例如使用一个静态变量int next_cpu 0;每次kfree时将页分配给kmem[next_cpu]然后next_cpu (next_cpu 1) % NCPU。实操心得在实现“窃取”逻辑时最容易犯的错误是死锁。你必须严格遵守“先释放自己的锁再去获取别人的锁”的原则。此外在偷页时直接偷走整个链表或者偷走一半是两种策略。偷一半可以避免一次性掏空某个CPU的缓存对长期性能更友好实现上也只需遍历链表找到中间点即可。4. 块缓存锁优化实战块缓存的优化是本次实验的重头戏涉及数据结构和同步机制的双重改造。4.1 从链表到哈希表首先在kernel/bio.c中将全局的bcache.head链表替换为一个哈希桶数组。#define NBUCKET 13 // 选择一个质数作为桶数量可以减少哈希冲突 struct { struct spinlock lock; struct buf head; // 桶内的哑元头节点用于组织双向链表 } bcache.bucket[NBUCKET]; struct buf { // ... 其他字段保持不变 struct buf *next; // 指向桶内链表的下一个buf struct buf *prev; // 指向桶内链表的上一个buf // 注意原来的 struct buf *next; 用于全局LRU链表现在可以移除或复用 };同时移除全局的bcache.lock为每个桶初始化一把锁bcache.bucket[i].lock。哈希函数需要简单高效例如int hash(uint dev, uint blockno) { return (dev ^ (blockno 4)) % NBUCKET; }4.2 重写bget函数bget是块缓存的核心逻辑最复杂。优化后的流程如下计算哈希值bidx hash(dev, blockno)。获取桶锁acquire(bcache.bucket[bidx].lock)。查找缓存遍历bcache.bucket[bidx].head链表查找是否有dev和blockno匹配的缓存块。如果找到增加其引用计数refcnt释放桶锁然后返回该缓存块。未找到缓存需要找一个未被引用的缓存块refcnt 0进行替换。此时不能只在本桶找因为本桶可能没有空闲块。我们需要在所有桶中寻找LRU块。但这里有个死锁陷阱我们正持有桶bidx的锁。如果直接去获取其他桶的锁必须定义一个全局顺序比如桶索引递增顺序并按照这个顺序获取。一个清晰的实现是 a. 首先释放当前桶bidx的锁。 b. 然后按顺序遍历所有桶从0到NBUCKET-1。对于每个桶i i. 获取桶i的锁。 ii. 遍历桶i的链表寻找refcnt 0且“最久未使用”的块可以通过时间戳或类似LRU的算法判断。记录下找到的最佳候选块。 iii. 如果桶i就是我们的目标桶bidx并且找到了候选块那么事情就简单了我们可以直接重用这个块修改其元数据释放桶锁除了bidx的锁因为我们还要用然后跳到步骤5。 iv. 如果候选块在其他桶中情况更复杂我们需要将该块从它所在的桶链表桶i中移除然后插入到目标桶桶bidx的链表中。这意味着我们需要同时持有桶i和桶bidx两把锁。因此在找到候选块后我们需要先释放桶i的锁然后按照锁顺序假设i bidx则先锁i再锁bidx反之亦然重新获取这两把锁再进行移动操作。这个过程必须非常小心确保在释放锁后候选块没有被其他线程抢走。 c. 遍历完所有桶后应该能找到一个候选块。分配与设置找到候选块后如果它来自其他桶将其从原桶链表移除并插入到目标桶bidx的链表头部。然后设置该块的dev,blockno,valid0,refcnt1。最后释放所有持有的桶锁。极端情况如果遍历所有桶都找不到refcnt 0的块理论上不应该发生因为缓存块总数是固定的则需要报错或等待。4.3 简化方案仅使用桶锁保护查找上述完全LRU的方案非常复杂容易出错。XV6实验指南通常允许一个简化不再维护全局的LRU顺序而是直接在目标桶内寻找一个可重用的块。如果目标桶内没有就去“窃取”其他桶的块。判断“最久未使用”可以简化例如直接使用桶链表头或尾的块如果它是双向链表且维护了某种顺序。这大大降低了实现复杂度虽然缓存淘汰策略不是最优的但足以显著提升并行性能并满足实验要求。在简化方案中bget的未命中处理逻辑变为持有目标桶bidx的锁。先在桶bidx内找一个refcnt 0的块。如果找到就用它。如果没找到释放桶bidx的锁。按顺序遍历其他桶i ! bidx获取桶i的锁在其链表中找一个refcnt 0的块。找到后先释放桶i的锁然后按照锁顺序先锁min(i, bidx)再锁max(i, bidx)同时获取两把锁将块移动到桶bidx然后释放锁。4.4 修改brelse、bpin、bunpin这些函数现在都需要根据块的dev和blockno计算哈希值找到对应的桶然后获取该桶的锁再进行操作。brelse中原来维护全局LRU链表的代码可以移除因为我们可能不再需要严格的LRU或者只在桶内部维护一个简单的顺序。5. 锁优化中的常见陷阱与调试技巧在多核环境下调试锁相关的问题极其困难因为问题可能只在特定的时序下出现。以下是一些常见陷阱和应对策略陷阱一忘记关闭中断在kalloc/kfree中操作每CPU数据前必须用push_off()关闭中断。这是因为中断处理程序也可能调用这些函数如果不关中断当前CPU可能在获取自己锁之后、操作列表之前被中断中断处理程序又试图获取同一把锁导致死锁自旋锁在单CPU上不会自旋但重复获取会导致panic。push_off/pop_off必须成对调用。陷阱二锁顺序导致的死锁这是最经典的死锁原因。务必为所有可能同时持有的锁定义一个全序关系。在块缓存实验中一个简单的全序就是桶的索引号。任何需要同时持有两把锁的代码路径都必须先获取序号小的锁再获取序号大的锁。在代码中可以用if (i j) { acquire(lock[i]); acquire(lock[j]); } else { acquire(lock[j]); acquire(lock[i]); }这样的模式来保证。陷阱三在持有锁时调用sleepXV6的锁是自旋锁持有锁时绝对不能调用sleep或任何可能让出CPU的函数否则其他需要该锁的CPU将永远自旋系统死锁。确保在获取锁之前所有可能失败或阻塞的操作如磁盘I/O请求都已经完成。调试技巧使用printf与panic在锁的获取和释放处添加详细的printf打印CPU号、锁地址、函数名等信息。在可疑的地方插入if(condition) panic(“error message”)来主动触发崩溃获取堆栈跟踪。利用CPUS变量在Makefile中你可以通过修改CPUS : 1来指定模拟的CPU数量。调试时先从单核开始确保逻辑正确再切换到多核如CPUS : 3测试并发问题。运行压力测试XV6有一些用户态测试程序如usertests但为了测试锁优化你可能需要编写自己的内核测试在多个CPU上频繁调用kalloc/kfree或文件操作。观察是否出现死锁系统挂起或数据损坏断言失败。检查锁的初始化确保所有锁包括每个桶的锁、每个CPU的kmem锁都在main.c的main函数或各自的初始化函数中被正确初始化调用initlock。6. 性能评估与延伸思考完成代码后如何评估优化效果XV6本身提供了一个简单的计时功能。你可以修改kernel/start.c中的main函数在系统启动后、运行用户程序前插入一段性能测试代码。例如创建多个内核线程让它们并发执行大量的内存分配/释放操作记录总耗时。对比优化前后的时间。也可以使用qemu的-d cpu参数输出CPU执行指令的跟踪但分析起来比较复杂。更重要的不是微基准测试的数字而是理解优化背后的原则减少临界区让锁保护的数据和代码尽可能少。降低锁粒度用多个细粒度锁代替一个粗粒度锁。避免锁使用无锁数据结构、每CPU变量、RCU读-复制-更新等更高阶的并发控制技术。减少锁持有时间在锁内只做必要的操作把耗时操作如磁盘I/O请求、内存拷贝移到锁外。Lab 8 的锁优化只是高性能并发编程的入门。现实世界中的Linux内核其内存分配器SLUB/SLAB和页缓存Page Cache的实现要复杂得多涉及更精巧的锁策略、无锁操作以及针对NUMA架构的优化。但通过这个实验你已经亲手拆解了这些复杂系统中最核心的同步问题并实践了从诊断到优化的完整流程。下次当你在设计一个需要高并发的服务时你会自然而然地思考哪些数据是共享的共享的频次如何能否拆分该用什么样的锁来保护这种思维习惯正是这个实验带给你的最宝贵财富。