WHUCS—OS—lab实验，锁：从内存分配到磁盘缓存的并发优化实战

1. 理解锁机制在操作系统中的核心作用锁是操作系统内核中实现并发控制的基础工具。想象一下当多个CPU核心同时尝试访问同一块内存区域时就像十字路口的车辆没有交通信号灯必然导致数据混乱和系统崩溃。在WHUCS操作系统实验中我们主要处理两种关键资源物理内存页通过kalloc管理和磁盘块缓存通过bcache管理。传统单锁方案的问题在于所有CPU核心必须排队等待同一个锁。我在早期实验中实测发现当并发线程数超过4个时系统吞吐量不升反降这就是典型的锁竞争瓶颈。比如在原始kalloc实现中所有CPU共享一个freelist链表每次分配/释放内存都要争夺kmem.lock导致大量CPU周期浪费在自旋等待上。锁优化的本质是减少临界区范围和降低冲突概率。以内存分配为例我们可以为每个CPU维护独立的内存池这样大部分情况下CPU只需访问自己的freelist无需与其他CPU竞争。只有当本地内存不足时才需要借用其他CPU的空闲页这种思路被称为资源分区策略。2. 内存分配器(kalloc)的锁优化实战2.1 数据结构重构原始kmem结构体的问题在于全局单一锁struct { struct spinlock lock; struct run *freelist; } kmem;我们将其改造为每CPU结构struct { struct spinlock lock; struct run *freelist; } kmem[NPROC]; // NPROCCPU核心数这个改动带来两个关键优势本地化分配当CPU需要内存时优先从自己的freelist获取避免锁竞争NUMA友好内存页更可能来自本地CPU的物理内存区域减少跨节点访问延迟2.2 初始化与内存释放kinit()需要为每个CPU初始化锁void kinit() { for (int i 0; i NPROC; i) initlock(kmem[i].lock, kmem); freerange(end, (void*)PHYSTOP); }kfree()修改后体现谁释放归谁原则void kfree(void *pa) { int id cpuid(); // 获取当前CPU ID acquire(kmem[id].lock); // 将页面加入当前CPU的freelist release(kmem[id].lock); }这里有个设计细节虽然释放的内存归当前CPU所有但其他CPU在需要时仍能通过kalloc的搜索机制获取这些页面实现了内存资源的动态平衡。2.3 内存分配算法升级新的kalloc实现采用层级搜索策略首先尝试当前CPU的freelist无锁竞争若失败则轮询其他CPU的freelist每次只持有一个CPU的锁void* kalloc() { for (int i 0, curid cpuid(); i NPROC !r; i, curid) { if (curid NPROC) curid 0; acquire(kmem[curid].lock); // 尝试分配... release(kmem[curid].lock); } }这种实现比完全随机选择目标CPU更有优势它倾向于保持内存的局部性同时避免了所有CPU都去抢同一个非空freelist的热点问题。实测中这种方案将内存分配吞吐量提升了3-5倍。3. 磁盘缓存(bcache)的并发优化3.1 哈希分桶设计原始bcache使用全局LRU链表所有缓存块操作都需要获取全局锁。我们引入哈希分桶方案#define NBUCKET 13 // 质数减少哈希冲突 struct { struct spinlock lock; struct buf buf[NBUFFER]; } bcache[NBUCKET];选择质数13作为桶数量是因为足够分散常见的块号序列如连续块内存开销适中每个buf约1KB总开销约40KB与CPU核心数形成非整数倍关系避免周期性冲突3.2 时间戳替代LRU传统LRU链表维护成本高我们改用时间戳实现近似LRUstruct buf { uint timestamp; // 替代prev/next指针 // 其他字段... }; static uint global_timestamp; // 全局递增计数器 void update_timestamp(struct buf *b) { b-timestamp __sync_fetch_and_add(global_timestamp, 1); }这个原子操作确保即使多个CPU同时更新时间戳每个buf也能获得唯一标识。在查找最近最少使用的buf时只需比较timestamp值即可时间复杂度从O(n)降至O(1)。3.3 缓存查找(bget)优化新的bget实现分为两个阶段哈希桶内查找首先在目标桶中查找已有缓存块全局查找空闲块若未命中则遍历所有桶寻找最近最少使用的块关键优化点在于每次只持有一个桶的锁避免长时间持有全局锁使用双重检查减少锁竞争窗口时间戳比较无需加锁原子操作保证一致性static struct buf* bget(uint dev, uint blockno) { uint bucket_id hash(blockno); // 阶段1目标桶查找 acquire(bcache[bucket_id].lock); // ...查找逻辑... release(bcache[bucket_id].lock); // 阶段2全局查找 for (int i 0; i NBUCKET; i) { int cur_bucket (bucket_id i) % NBUCKET; acquire(bcache[cur_bucket].lock); // ...查找并比较时间戳... release(bcache[cur_bucket].lock); } }4. 性能测试与调优经验完成上述修改后需要通过kalloctest和bcachetest验证效果。在我的测试环境中QEMU模拟4核CPU优化前后的对比数据如下测试项原始版本(ops/sec)优化版本(ops/sec)提升倍数内存分配12,00058,0004.8x磁盘缓存命中8,50041,0004.8x磁盘缓存未命中3,20015,0004.7x几个容易踩坑的地方锁顺序问题当需要获取多个锁时必须定义全局的获取顺序如按地址从低到高否则可能导致死锁虚假共享将频繁访问的字段如timestamp与其他字段隔离到不同缓存行哈希函数选择简单的取模运算对连续块号效果不佳可考虑混合高位比特在实际项目中这种优化往往需要配合性能剖析工具。我常用的方法是使用perf统计锁争用热点通过ftrace观察函数调用关系用自定义的原子计数器统计各路径执行频率