第9讲：锁 | XV6 中文文档

6.1810 2024 第10讲：锁

为什么要讨论锁？

如果没有锁会出什么问题？

糟糕的是：

锁的抽象：

lock l
acquire(l)
  x = x + 1 -- "临界区"
release(l)

一个保守的规则来决定何时需要锁：

锁可以是自动的吗？

这个想法通常太僵化了：

if present(table1, key1):
  add(table2, key1)

我们需要：

lock table1
lock table2
  present(..)
  add()
unlock table1; unlock table2

思考锁实现了什么的方式

问题：死锁

如果：

核心 A              核心 B
rename(d1/x, d2/y)  rename(d2/a, d1/b)
  lock d1             lock d2
  lock d2 ...         lock d1 ...

锁与模块化

锁与并行性

锁粒度建议

让我们看看 xv6 中的锁。

一个典型的锁使用：uart.c

许多操作系统设备驱动程序安排的典型
图示：
- 用户进程、内核、UART、uartputc、从 uart_tx_buf 中移除、uartintr()
并发源：进程、中断
uart.c 中只有一个锁：uart_tx_lock —— 相当粗粒度
uartputc() —— uart_tx_lock 保护什么？
1. uart_tx_buf 操作中没有竞争
2. 如果队列不为空，UART 硬件正在执行队列的头部
3. 没有对 UART 写入寄存器的并发访问
uartintr() —— 中断处理程序
- 获取锁 —— 可能必须在中断级别等待！
- 从 uart_tx_buf 中移除字符
- 将下一个排队的字符交给 UART 硬件 (2)
- 接触 UART 硬件寄存器 (3)

如何实现锁？

为什么不这样：

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

原子交换指令：

assembly

a5 = 1
s1 = &lk->locked
amoswap.w.aq a5, a5, (s1)

这在硬件中执行：
- 全局锁定地址（其他核心不能使用它）
- temp = *s1
- *addr = a5
- a5 = temp
- 解锁地址
RISC-V 硬件提供了一种锁定内存位置的概念
- 不同的 CPU 有不同的实现
- 图示：核心、总线、RAM、锁的东西
- 所以我们实际上是将问题推给了硬件
- 硬件在缓存行或整个总线的粒度上实现
内存锁强制并发交换一个接一个地运行，而不是交错进行

看看 xv6 的自旋锁实现

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

如果 l->locked 已经是 1，sync_lock_test_and_set 将其（再次）设置为 1，返回 1，
- 并且循环继续“自旋”
如果 l->locked 是 0，最多只有一个 lock_test_and_set 会看到 0；它会将其设置
- 为 1 并返回 0；其他的 test_and_set 将返回 1
这是一个“自旋锁”，因为等待的核心在 acquire 循环中“自旋”
push_off() 是关于什么的？
- 为什么要禁用中断？
release():
- 设置 lk->locked = 0
- 并重新启用中断

细节：内存读/写顺序

核心 A: 核心 B:

locked = 1
x = x + 1      while(locked == 1)
locked = 0       ...
               locked = 1
               x = x + 1
               locked = 0

编译器和 CPU 会重新排序内存访问
- 即它们不遵守源程序的内存引用顺序
- 例如，编译器可能会为核心 A 生成此代码：
```
locked = 1
locked = 0
x = x + 1
```
  - 即将增量移出临界区！
合法的行为称为“内存模型”
release() 对 __sync_synchronize() 的调用可防止重排序
- 编译器不会将内存引用移动到 __sync_synchronize() 之后
- 并且（可能）发出“内存屏障”指令来告诉 CPU
acquire() 对 __sync_synchronize() 的调用具有类似的效果：
如果你使用锁，你不需要理解内存排序规则
- 如果你想编写奇特的“无锁”代码，你需要它们

为什么是自旋锁？

建议：