Lecture 6: 锁的实现（Implementing Locks）
Lecture 6: 锁的实现（Implementing Locks）
概述
前几讲使用锁，本讲在操作系统内部实现锁：单核上通过关中断（disable interrupts）获得原子性；多核上必须借助硬件的原子读改写指令（如 xchg）。我们从朴素实现出发，逐版本发现竞态窗口，最终得到 Linux 风格的正确实现，并理解”为什么多核上一定程度的忙等不可避免”。
核心概念与系统机制图解
单核（Uniprocessor）锁：关中断
- 关键事实：单核上，只有陷阱（trap）或中断（interrupt）能把当前线程切走。因此关中断 = 获得临界区。
- 实现： ``` class Lock { bool locked = false; ThreadQueue q; // 等待该锁的线程队列 };
void Lock::lock() { intrDisable(); // 原子地: 关中断 if (!locked) { locked = true; } else { q.add(currentThread); // 加入等待队列 blockThread(); // 阻塞自己(必须保持中断关闭!) } intrEnable(); // 重新开中断 }
void Lock::unlock() { intrDisable(); if (q.empty()) { locked = false; // 无人等待, 直接释放 } else { unblockThread(q.remove()); // 唤醒队首线程(把锁”移交”给它) } intrEnable(); }
- **为什么 `blockThread()` 必须在关中断状态下调用**：若先开中断再阻塞，开中断与阻塞之间可能来一个中断把另一线程调度进来，而该线程可能调用 `unlock`/`lock`，破坏队列一致性——"加进队列"与"变成阻塞"必须原子。
#### 多核（Multiprocessor）锁：原子读改写
- **问题**：关中断只对当前核有效，其它核上的线程照常访问共享锁变量 → 需要**硬件原子指令**。
- **原子交换 `xchg`**：把变量的旧值取回并同时写入新值，一步完成（Intel x86 指令）。
#### 多核锁实现演化（Lecture 6 逐版本）
v1: 自旋锁(spinlock)——忙等: void lock() { while (locked.exchange(true)) { /* 空转 */ } } void unlock(){ locked = false; } → 简单但忙等; 而且锁竞争激烈时大量缓存一致性流量
v2: 尝试加原子交换+阻塞: if (locked.exchange(true)) { q.add(currentThread); blockThread(); } → 竞态: 两个核可能同时操作线程队列 q!
v3: 用自旋锁保护队列(二阶段锁): 自旋锁保护 locked 标志与线程队列; 队列操作在自旋锁内完成 → 仍有竞态: 持锁者正在运行, 等待者被阻塞后, 谁来唤醒它? (unlock 由另一个核执行时与 blockThread 交错的问题)
v4: 显式设置 BLOCKED 状态 + redispatch: q.add(currentThread); currentThread->state = BLOCKED; // 先标记阻塞 spinlock = false; // 释放自旋锁 redispatch(); // 再调度其它线程 → Linux 的做法: 让调度器看到”我已阻塞”, 避免调度器把我又调度回来
v5: 加上关中断, 防止本核中断打断上述序列 → 最终版(见代码示例)
- **为什么多核上忙等不可避免**：等待一个由**其它核**持有的锁时，你无法通过"关本核中断"获得原子性，只能自旋；目标是**尽量缩短忙等时间**（只保护极短的临界区，如队列操作），而不是完全消除。
### 代码示例与系统调用解说
#### 示例：多核锁的最终实现（v5，Linux 风格）
```cpp
#include <atomic>
class Lock {
public:
void lock() {
intrDisable(); // 1. 关本核中断
while (spinlock.exchange(true)) { } // 2. 自旋获取自旋锁(保护内部状态)
if (!locked) {
locked = true;
spinlock = false; // 3a. 拿到锁, 释放自旋锁
} else {
q.add(currentThread); // 3b. 加入等待队列
currentThread->state = BLOCKED; // 4. 显式标记阻塞
spinlock = false; // 5. 释放自旋锁
redispatch(); // 6. 让出 CPU, 调度器运行其它线程
}
intrEnable();
}
void unlock() {
intrDisable();
while (spinlock.exchange(true)) { }
if (q.empty()) {
locked = false; // 无人等待 → 释放锁
} else {
unblockThread(q.remove()); // 有人等待 → 把锁移交给队首线程
}
spinlock = false;
intrEnable();
}
private:
bool locked = false;
ThreadQueue q; // 阻塞在该锁上的线程队列
std::atomic<bool> spinlock; // 保护 locked 与 q 的自旋锁
};
【代码做了什么？】 lock() 先关中断（防本核中断），再用自旋锁保护内部状态：锁空闲则直接占有；否则入队、标记阻塞、释放自旋锁并让出 CPU。unlock() 对称地移交锁或释放锁。
【系统机制透视】
- 为什么需要两级同步：
locked标志与线程队列q是共享状态，任何核上的线程都能操作它们，必须用硬件原子指令（exchange）保护；而”入队→标记 BLOCKED→redispatch”序列必须对调度器原子可见，否则调度器可能把一个已阻塞的线程又调度到核上运行（它却在等待锁）——这就是 v4 中”先设 BLOCKED 再 redispatch”的意义。 xchg的硬件行为：一条指令同时”读取旧值并写入新值”，总线/缓存一致性协议保证所有核看到一致的顺序——这是软件无法模拟的原子性来源。- 用户态对应物：Assign4 在用户态实现单核锁/条件变量时，由于没有中断开关，用”关闭抢占/单线程调度器配合”的技巧；而 C++ 的
std::mutex在用户态通常用 futex（fast user-space mutex）：先试自旋，失败则通过系统调用睡眠，把”忙等+阻塞”结合。
关键要点
- 单核上”关中断”即可构造临界区；多核上必须依赖硬件原子读改写指令。
- 阻塞线程必须在关中断/持自旋锁状态下完成”入队 + 标记阻塞 + 让出”，避免调度器竞态。
- 多核系统中忙等不可避免，但应把忙等限制在极短临界区内。
- 硬件原子原语（如
xchg）是构建一切高层同步（锁、信号量、futex）的基石。 - 一个”看起来正确”的锁实现往往藏有竞态窗口——需要逐版本推敲中断与调度器的交错。
常见陷阱与注意事项
- 在关中断时调用可能阻塞的函数 → 中断长时间关闭，系统失去响应（时钟中断进不来）。
- 先释放自旋锁再 redispatch：顺序颠倒会导致另一核的线程在队列操作进行中修改队列。
- 忘记处理”锁被移交”的情形：
unlock若直接locked=false而不唤醒，可能出现”锁空闲但无人知道”。 - 自旋锁持锁时间过长：其它核自旋浪费 CPU，缓存行 bouncing 严重。
思考题
- 问题：为什么单核锁可以只用关中断实现，而多核不行？
- 答案：单核上只有中断/陷阱能切换线程，关中断即独占 CPU；多核上其它核的线程可并发访问共享锁变量，关本核中断管不住别的核，必须用跨核一致的原子指令。
- 问题：v4 中
currentThread->state = BLOCKED;为什么必须发生在redispatch()之前？- 答案：若先 redispatch 再设状态，调度器可能在状态仍为 RUNNING/READY 时把该线程重新调度到核上，而它正等着锁——出现”阻塞线程还在跑”的不一致；先标记 BLOCKED 保证调度器不会再选它。