xv6 锁与并发 / xv6 Locks And Concurrency

1. 这篇文章解决什么问题

xv6 是多核内核。

多个 hart 可以同时执行内核代码。

如果它们同时访问共享数据，就可能出错。

典型共享对象：

proc table
free page list
file table
inode cache
buffer cache
pipe buffer
console buffer

锁的作用不是让代码看起来更严肃。

锁保护共享对象的不变量。

本篇重点：

• 什么是竞态。
• spinlock 解决什么问题。
• sleeplock 解决什么问题。
• 为什么有些锁要关闭中断。
• sleep/wakeup 为什么必须配合锁。
• 如何思考死锁。

1.1 本文基础词小注释

并发 concurrency：并发表示多条执行路径在时间上交错推进。它不一定要求同一瞬间真的同时执行。单核上可以靠中断和切换形成并发，多核上则可能真的同时执行。

共享数据 shared data：被多个 CPU、多个进程路径、或者中断处理路径共同访问的数据。比如进程表、空闲页链表、buffer cache。只要共享，就要问：谁能改？什么时候改？改到一半会不会被别人看见？

竞态 race condition：程序结果取决于“谁先执行、谁后执行”的微妙时序，而且这种时序没有被锁或其他同步机制约束。竞态常常不是每次都出现，所以很难调试。

------- CPU 0 -------+     +------- CPU 1 -------+
read old value       |     | read old value       |
compute new value    |     | compute new value    |
write back           |     | write back           |
          \          |     |          /
           +---- lost update ----+

锁 lock：锁是一种同步工具。拿到锁的路径可以进入临界区，其他路径必须等待。锁的目的不是“让代码串行得更慢”，而是保护共享对象在修改过程中不被别人破坏。

临界区 critical section：从拿锁到放锁之间的代码区域。这个区域通常会读写共享数据。临界区应尽量短，但不能短到破坏正确性。

不变量 invariant：对象必须一直满足的正确条件。例如“一个空闲物理页只能在 free list 里出现一次”。锁通常保护的不是某一行代码，而是这个条件。

死锁 deadlock：多个执行路径互相等待对方释放资源，导致谁也走不下去。最常见原因是锁顺序不一致。

2. 什么是共享不变量

不变量是某个对象必须一直满足的正确条件。

例如进程状态：

one process cannot be RUNNING on two CPUs at same time

例如 free list：

each free physical page appears exactly once in free list

例如 file ref：

file object can be reused only when ref == 0

锁保护这些条件。

shared object
  |
  v
lock
  |
  v
temporarily modify fields safely
  |
  v
restore invariant before unlock

所以读锁时，不要只问“为什么加锁”。

要问：

which invariant is protected?

3. spinlock

自旋锁用于短临界区。

拿不到锁时，CPU 会循环等待。

try acquire
  |
  +-- success -> enter critical section
  |
  +-- fail -> keep spinning

xv6 spinlock 相关文件：

kernel/spinlock.h
kernel/spinlock.c

典型 API：

initlock
acquire
release
holding

适合保护：

• 进程状态。
• free page list。
• file table。
• buffer cache metadata。

不适合长期持有。

因为自旋时 CPU 没有做有用工作。

4. sleeplock

sleeplock 允许等待者睡眠。

适合可能等待较久的资源。

相关文件：

kernel/sleeplock.h
kernel/sleeplock.c

典型 API：

initsleeplock
acquiresleep
releasesleep
holdingsleep

常见用途：

inode 内容保护。

为什么 inode 适合 sleeplock？

因为文件系统操作可能涉及磁盘 I/O。

等待磁盘时不应该一直自旋浪费 CPU。

short metadata update
  |
  v
spinlock

long operation may sleep
  |
  v
sleeplock

5. 为什么 spinlock 会关中断

xv6 获取 spinlock 时会配合 push_off()。

释放时配合 pop_off()。

它们管理当前 CPU 的中断开关嵌套。

为什么？

避免同一 CPU 上中断处理程序再次尝试获取同一把锁，造成死锁。

错误情况：

kernel code acquires lock L
  |
  v
interrupt arrives on same CPU
  |
  v
interrupt handler tries acquire L
  |
  v
deadlock

关中断可以避免这类本地中断重入。

注意：

关中断不是为了阻止其他 CPU。

其他 CPU 仍然可能运行。

阻止其他 CPU 同时进入临界区的是锁本身。

spinlock
  |
  +-- protects against other CPUs

push_off
  |
  +-- protects against interrupt reentry on same CPU

6. proc lock

每个进程有 p->lock。

它保护进程状态。

p->lock protects
  |
  +-- state
  +-- chan
  +-- killed
  +-- xstate
  +-- scheduling transitions

调度器使用它。

sleep/wakeup 使用它。

exit/wait 使用它。

状态变化通常要持锁。

acquire p->lock
  |
  v
change p->state
  |
  v
release p->lock

没有锁，两个 CPU 可能同时把同一进程状态改坏。

7. kalloc lock

物理页分配器维护 free list。

free list 是共享结构。

free list
  |
  +-- page A -> page B -> page C

kalloc() 和 kfree() 都会修改它。

所以需要锁。

kalloc
  |
  +-- acquire lock
  +-- remove page from free list
  +-- release lock

kfree
  |
  +-- acquire lock
  +-- add page to free list
  +-- release lock

不变量：

free pages form a valid list
no allocated page remains on free list
no free page appears twice

8. file table lock

全局文件表也需要锁。

文件对象有引用计数。

struct file
  |
  +-- ref

filealloc() 找空闲槽位。

filedup() 增加引用。

fileclose() 减少引用。

这些都不能并发乱改。

file ref invariant
  |
  +-- ref > 0 means in use
  +-- ref == 0 means reusable

如果两个 CPU 同时操作 ref，可能提前释放或重复释放。

所以要锁保护。

9. buffer cache lock

buffer cache 既有全局元数据，又有每个 buffer 的内容锁。

简化：

buffer cache metadata
  |
  +-- spinlock

individual buffer content
  |
  +-- sleeplock

为什么两层？

查找缓存块、维护 LRU 链表是短操作。

适合 spinlock。

读写某个块内容可能涉及磁盘等待。

适合 sleeplock。

find buffer
  |
  v
spinlock protected metadata
  |
  v
lock buffer content
  |
  v
release metadata lock

这是锁粒度设计的例子。

10. sleep/wakeup 中的锁

sleep/wakeup 最容易出现 lost wakeup。

锁用于保护条件检查和睡眠状态转换。

acquire condition lock
  |
  v
while condition not true
  |
  v
sleep(chan, lock)

sleep 内部会：

acquire p->lock
release external lock
set p->chan
set p->state = SLEEPING
sched
...
reacquire external lock before return

这个过程复杂，是为了不丢唤醒。

不要把 sleep 看成普通阻塞函数。

它是调度、锁、状态机三者配合。

11. 死锁

死锁是多个执行流互相等待。

典型：

CPU 0 holds A, waits B
CPU 1 holds B, waits A

图：

CPU 0 ----holds----> Lock A
CPU 0 ----waits----> Lock B

CPU 1 ----holds----> Lock B
CPU 1 ----waits----> Lock A

避免死锁的方法：

• 固定锁顺序。
• 不在持有不该持有的锁时 sleep。
• 缩短临界区。
• 区分 spinlock 和 sleeplock。
• 明确每把锁保护什么。

xv6 代码简单，但锁顺序仍然要注意。

12. 读锁代码的方法

读到锁时按这个模板。

lock name:

protected object:

protected fields:

invariant:

who acquires it:

can code sleep while holding it:

lock ordering:

例如：

lock name:
  p->lock

protected object:
  struct proc

protected fields:
  state, chan, killed, xstate

invariant:
  scheduler and wakeup see consistent process state

这比只写“这里加锁保证线程安全”好得多。

13. 锁粒度：一把大锁还是多把小锁

锁粒度描述一把锁保护的数据范围有多大。

粗粒度锁保护很多数据。

细粒度锁保护较小对象。

coarse-grained lock
  |
  +-- simpler
  +-- less parallelism
  +-- easier to reason initially

fine-grained locks
  |
  +-- more parallelism
  +-- more complex
  +-- higher deadlock risk

xv6 同时使用两种思路。

进程是每个 struct proc 一把锁。

这比整个进程表一把锁更细。

物理页分配器有一把锁保护 free list。

文件表有一把锁保护全局文件表。

buffer cache 既有全局锁，又有每个 buffer 的 sleeplock。

proc table
  |
  +-- proc[0].lock
  +-- proc[1].lock
  +-- proc[2].lock

buffer cache
  |
  +-- global metadata lock
  +-- buf[0].sleeplock
  +-- buf[1].sleeplock

读代码时要问：

这把锁保护一个对象，还是一组对象？

如果保护一组对象，是否会限制并发？

如果拆成多把锁，是否会增加锁顺序问题？

14. 原子操作和锁的关系

自旋锁底层通常需要原子操作。

原子操作保证某个读改写过程不可被其他 CPU 插入。

例如获取锁时，需要从“未锁定”变成“已锁定”。

CPU 0 tries acquire
CPU 1 tries acquire
  |
  v
atomic operation ensures only one succeeds

如果没有原子操作，两个 CPU 可能同时认为自己拿到锁。

CPU 0 sees locked = 0
CPU 1 sees locked = 0
CPU 0 sets locked = 1
CPU 1 sets locked = 1

both enter critical section

锁是更高层语义。

原子操作是实现锁的硬件基础之一。

初学 xv6 不需要深入所有内存模型细节。

但要知道：

自旋锁不是普通变量判断。

它依赖硬件提供的原子性。

15. 内存可见性：为什么 release 不只是清零

释放锁不只是把 locked 设回 0。

它还要保证临界区内的写入对后续拿锁者可见。

抽象模型：

CPU 0 inside lock
  |
  +-- writes shared data
  |
  v
release lock
  |
  v
CPU 1 acquire lock
  |
  v
must see CPU 0's shared data writes

如果没有合适的内存顺序，CPU 或编译器可能重排访问。

这会让另一个 CPU 看到奇怪状态。

xv6 的锁实现会使用原子和内存同步机制。

读源码时先把目标记住：

acquire
  |
  +-- after acquire, protected data can be read consistently

release
  |
  +-- before release, protected writes become visible

这就是锁的“可见性”作用。

它不只是互斥。

16. 中断上下文和普通内核上下文

内核代码可能在不同上下文运行。

process kernel context
  |
  +-- executing syscall
  +-- can sleep in some paths

interrupt context
  |
  +-- handling device/timer interrupt
  +-- must be careful

如果普通内核代码持有某把锁时被中断打断，而中断处理也要拿同一把锁，就会死锁。

这就是 spinlock 结合关中断的原因之一。

same CPU:

normal kernel code holds lock L
  |
  v
interrupt arrives
  |
  v
interrupt handler wants L
  |
  v
deadlock

所以分析锁时，要问：

这把锁会不会在中断处理里使用？

持有这把锁时是否需要禁止本 CPU 中断？

17. sleep 时不能随便持有 spinlock

睡眠意味着当前进程让出 CPU。

如果睡眠时持有不该持有的 spinlock，其他 CPU 或进程可能永远等不到锁。

process holds spinlock L
  |
  v
process sleeps
  |
  v
other code needs L to wake it
  |
  v
deadlock

xv6 的 sleep(chan, lock) 有明确规则。

它会释放传入的外部锁，并在醒来后重新获取。

但这并不意味着可以随便在任何锁下睡眠。

你必须知道：

• 当前持有什么锁。
• sleep 会释放哪把锁。
• 是否还持有其他锁。
• wakeup 路径是否需要这些锁。

这也是为什么锁分析必须和调用路径一起看。

18. 本篇源码阅读清单

按这个顺序读锁相关源码：

spinlock.h
  |
  +-- struct spinlock

spinlock.c
  |
  +-- initlock
  +-- acquire
  +-- release
  +-- push_off
  +-- pop_off

sleeplock.h
  |
  +-- struct sleeplock

sleeplock.c
  |
  +-- acquiresleep
  +-- releasesleep

proc.c
  |
  +-- sleep
  +-- wakeup
  +-- scheduler

bio.c / fs.c / file.c / kalloc.c
  |
  +-- concrete lock users

每读一把锁，写下：

lock:
protected fields:
critical section:
can sleep:
interrupt concern:
lock order:

这会让锁从“看不见的魔法”变成可分析对象。

19. 常见误解

误解一：锁保护代码。

更准确地说，锁保护数据和不变量。

误解二：关中断能阻止其他 CPU。

不能。

关中断只影响当前 CPU。

误解三：spinlock 和 sleeplock 可以随便替换。

不能。

spinlock 适合短临界区。

sleeplock 适合可能睡眠的长等待。

误解四：拿锁越多越安全。

不是。

锁过多可能死锁，也可能降低并发。

误解五：sleep 只是暂停。

在 xv6 中，sleep 和锁、调度、wakeup 紧密相关。

20. 小实验：观察 kalloc 锁

在 kalloc() 和 kfree() 周围加少量打印。

观察：

kalloc acquire
kalloc got page
kfree return page

不要在高频路径长期保留。

目标是理解 free list 修改必须受锁保护。

21. 小实验：构造 lost wakeup 思考实验

不建议真的破坏源码。

可以画时序图。

reader checks condition
writer changes condition
writer wakeup
reader sleeps

然后解释为什么正确的 sleep(chan, lock) 避免它。

这是理解并发比跑代码更重要的一类实验。

22. 本篇总结

xv6 锁学习的核心不是 API。

而是共享不变量。

shared object
  |
  v
invariant
  |
  v
lock
  |
  v
safe state transition

下一篇进入：

12-file-descriptor-and-inode.md

文件系统会把进程资源、引用计数、锁和 inode 对象连接起来。