6.1810 / 6.1810 · 第 12 课 · nz

锁与并发

应用希望利用多核处理器获得并行加速，因此内核必须处理并发的系统调用，以及并发的内核数据访问（缓冲区缓存、进程表等）。锁帮助正确共享数据，但也可能限制并行加速。

为什么需要锁？

案例研究：xv6 kfree() 中的竞态条件

如果删除 kfree() 中的 acquire/release 会发生什么？

// kfree() 简化
r->next = freelist;   // ①
freelist = r;         // ②

同时 kfree() → 丢失页面

Core 1	Core 2
r1->next = freelist	r2->next = freelist
freelist = r1	freelist = r2

结果：r1 仍在 freelist 中（r2->next = r1），但 freelist 现在指向 r2。r1 之后会被分配出去——但某个进程可能仍在使用它！

---

锁的抽象

lock l;
acquire(l);
x = x + 1;  // 临界区
release(l);

• 锁本身是一个对象
• 多个线程调用 acquire(l) 时，只有一个立即返回，其余等待（阻塞）
• 一个程序通常有很多数据和很多锁
• 如果不同线程使用不同数据，它们可能持有不同锁，可以在多核上并行执行
• 锁 l 并不绑定于数据 x——程序员必须设计对应关系

何时需要锁的保守规则

如果两个线程可能使用同一内存位置，且至少一个是写操作，就需要锁。

锁能实现什么？

• 原子多步操作——隐藏中间状态（读-修改-写）
• 避免丢失更新——如 x = x + 1 或链表插入
• 维护不变量——假设不变量在操作开始时为真，操作使用锁隐藏暂时违反，在释放锁前恢复

---

锁的问题

死锁（Deadlock）

rename(f1, f2) 必须持有两个目录的锁：

Core A	Core B
rename(d1/x, d2/y)	rename(d2/a, d1/b)
lock d1 ✓	lock d2 ✓
lock d2 ...（等待）	lock d1 ...（等待）

解决方案：程序员确定所有锁的全序，所有代码必须按该顺序获取锁。即预测锁、排序、获取——复杂！

锁与模块化

锁使得难以在模块内部隐藏细节。为避免死锁，我需要知道被调用函数获取了哪些锁，甚至可能需要在调用前就获取它们。锁通常不是个体的私有事务。

锁与并行

锁阻止并行执行。为获得并行，通常需要拆分数据和锁，使每个核心通常使用不同数据和锁——"细粒度锁"。

---

xv6 中的锁实例：UART 输出

并发源	tx_lock 保护什么
进程/进程	不交错输出；原子 write(THR) + tx_busy=1
进程/中断	不变量 tx_busy=1 ⇒ 中断会来；原子 read(LSR) + tx_busy=0

---

如何实现锁？

错误实现：非原子 test-and-set

struct lock { int locked; }
acquire(l) {
  while (1) {
    if (l->locked == 0) {  // A
      l->locked = 1;       // B
      return;
    }
  }
}

问题：两个 acquire() 都看到 locked==0，都设置 locked=1。一个释放时设置 locked=0；第二个释放时看到已释放，触发 panic。

RISC-V 原子交换指令

// acquire() in kernel/kernel.asm
a5 = 1
s1 = &lk->locked
amoswap.w.aq a5, a5, (s1)
// 硬件完成：
//   lock *s1 in memory system
//   temp = *s1
//   *s1 = a5
//   a5 = temp
//   unlock *s1

xv6 spinlock 实现

acquire(l) {
  while (__sync_lock_test_and_set(&lk->locked, 1) != 0)
    ;
}

• 如果 lk->locked 已是 1，sync_lock_test_and_set 再设为 1，返回 1，循环继续自旋
• 如果是 0，最多一个 test_and_set 会看到 0；它设为 1 并返回 0；其他返回 1

push_off() 的作用

为什么在 acquire 中禁用中断？如果设备中断，中断处理程序需要同一锁（如 UART 代码），会死锁。

内存读写排序

// 这段代码可能被编译器或 CPU 重排！
locked = 1   (aquire)
x = x + 1
locked = 0   (release)
// 可能生成：
locked = 1
locked = 0      // 编译器把增量移出临界区！
x = x + 1

__sync_synchronize() 防止重排：编译器不会跨越它移动内存引用，并可能发出"内存屏障"指令告诉 CPU。使用锁时，你无需理解内存排序规则。

---

锁设计建议

• 尽可能避免共享
• 从少量粗粒度锁开始
• 测量——哪些锁在阻止并行？
• 仅在需要并行性能时使用细粒度锁
• 使用自动竞态检测器

---

测验

要点总结

延伸阅读

• xv6 手册 —— 第 6 章（锁）
• RISC-V Unprivileged Spec —— amoswap 指令
• 原始讲义