Lock 实现

Lock 的接口看起来很小：进入临界区前 acquire，离开临界区后 release。它真正承诺的是同一时刻至多一个线程持有锁。如果锁已经被别人拿着，当前线程要等待；如果等待时间可能很长，理想行为是睡眠，而不是一直占着 CPU 空转。

实现 lock 时要区分两层 critical section。用户真正想保护的是银行账户、队列、数据库等业务共享状态；lock 实现内部也有自己的共享状态，例如 value、wait queue、ready queue。底层机制只应该短暂保护这些元数据，不能把用户任意长的临界区都放进“关中断”或“自旋”里。

关中断

在单处理器上，调度器获得控制权通常来自内部事件和外部中断。内核修改 lock 元数据时暂时关闭中断，可以避免在“检查锁空闲”和“把锁标为忙”之间被切走。中断只应在内核短路径中关闭，不能覆盖用户临界区。

朴素方案是在 Acquire 中 disable interrupts，在 Release 中 enable interrupts，但这不能开放给普通用户程序。用户若拿锁后死循环，时钟中断也进不来，内核会失去重新调度的机会。实时系统中也不能让中断关闭时间不可控，否则 I/O、timer 和紧急事件响应都会被推迟。

因此只在更新 lock 内部元数据时短暂关闭中断：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int value = FREE;

Acquire() {
    disable interrupts;
    if (value == BUSY) {
        put thread on wait queue;
        go to sleep();
    } else {
        value = BUSY;
    }
    enable interrupts;
}

Release() {
    disable interrupts;
    if (anyone on wait queue) {
        take thread off wait queue;
        place on ready queue;
    } else {
        value = FREE;
    }
    enable interrupts;
}

关中断保护的是 value 与等待队列。多处理器上，关闭当前 CPU 的中断并不能阻止其他 CPU 同时访问同一内存位置，所以还需要硬件原子读改写指令。

Lost Wakeup

线程准备睡眠时，中断最终当然要重新打开，否则系统无法处理时钟和 I/O。危险在于开中断的时机，因为睡眠不是一句孤立的函数调用，而是一段会修改等待队列和线程状态的协议。

如果线程 A 判断锁忙后过早打开中断，线程 B 可能释放锁并检查等待队列；此时 A 还没入队，B 以为没人等，唤醒事件就丢了。之后 A 再把自己放进 wait queue 并睡下去，就可能永远没人叫醒。另一种窗口是 A 已经入队，B 把 A 放进 ready queue，但 A 继续执行旧路径又调用 sleep，把自己重新睡回去。

“加入等待队列、标记 sleeping、释放内部保护、切换到其他线程”必须在 sleep/scheduler 路径中原子衔接。所有阻塞同步都要避免这类 lost wakeup 窗口。

Test-and-Set

更通用的锁实现依赖 atomic read-modify-write 指令。它们把“读旧值、判断、写新值”合成一个不可分割的硬件动作。典型指令包括 test_and_set、swap 和 compare_and_swap，共同点都是让多个 CPU 不能同时基于同一个旧值做出“我拿到锁了”的判断。

1
2
3
4
5

test_and_set(address) {
    result = M[address];
    M[address] = 1;
    return result;
}

用 test_and_set 写最简单的 spinlock：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int value = 0;        // 0 means free, 1 means busy

Acquire() {
    while (test_and_set(&value)) {
        ;             // busy wait
    }
}

Release() {
    value = 0;
}

硬件保证同时执行 test_and_set 的多个 CPU 会排出一个先后顺序，因此不会有两个线程同时看到旧值为 0。这个版本简单、可在用户态使用、也支持多处理器；缺点是锁忙时一直 busy-wait。竞争严重时，等待线程浪费 CPU，甚至可能抢走持锁线程运行机会；在多核上，同一 cache line 还会在多个 cache 间来回迁移。

这些指令只解决锁变量本身的竞争，不自动解决等待效率、优先级反转或 cache ping-pong。

Guard + Wait Queue

直接 spinlock 的问题是等待时间等于用户临界区长度。改进思路是只对 lock 内部元数据短暂自旋；如果真正的锁拿不到，就把线程放进等待队列并睡眠。这样忙等只出现在很短的内部窗口里，长等待交给 scheduler 处理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

int guard = 0;
int value = FREE;

Acquire() {
    while (test_and_set(&guard)) {
        ;
    }

    if (value == BUSY) {
        put thread on wait queue;
        go to sleep and set guard = 0;
    } else {
        value = BUSY;
        guard = 0;
    }
}

Release() {
    while (test_and_set(&guard)) {
        ;
    }

    if (anyone on wait queue) {
        take thread off wait queue;
        place on ready queue;
    } else {
        value = FREE;
    }
    guard = 0;
}

guard 不是用户看到的锁，而是保护 value 和 wait queue 的短锁。go to sleep and set guard = 0 必须作为一条受控调度路径理解：线程已经入队并准备睡眠，同时保证后继线程能看到 guard 被释放。Release 发现有人等待时通常直接唤醒等待者，而不是把 value 改成 FREE，这样可以避免第三个线程趁空插队并造成两个线程都以为自己拥有锁。

Monitor

Condition Variable

Semaphore 很适合资源计数，但大型程序里 P/V 顺序容易写散。Monitor 把共享数据、访问函数、锁和 condition variable 放在一起管理。锁保护 monitor 内部状态，condition variable 让条件不满足的线程睡在对应队列上。程序只需检查条件是否成立，并保证状态在锁内更新。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

lock monitor_lock;
condition cv;
shared_state state;

MonitorOperation() {
    acquire(&monitor_lock);

    while (condition_not_satisfied(state)) {
        cond_wait(&cv, &monitor_lock);
    }

    update_shared_state(state);

    cond_signal(&cv);
    release(&monitor_lock);
}

Condition variable 不是布尔变量，也不是计数器；真正的条件在受锁保护的共享状态里。cond_wait(&cv, &lock) 必须在持有锁时调用，它会原子地释放锁并睡眠，被唤醒返回前重新拿回同一把锁。signal 唤醒一个等待者，broadcast 唤醒所有等待者；如果 signal 发生时没人等待，这次 signal 没有历史可保存。

Semaphore 的 V 会积累许可，未来的 P 可以消耗；condition variable 的 signal 只对当前等待者有效。因此不能简单把 semaP 当作 cond_wait，也不能把 semaV 当作 cond_signal。

Mesa vs Hoare

Hoare monitor 的语义是 signal 后 waiter 立即获得锁并运行，因此被唤醒时条件在语义上成立。但这种实现需要强制上下文切换，成本高，也复杂。

Mesa monitor 更接近真实系统：signaler 继续持锁运行，被唤醒线程只是进入 ready queue。等 waiter 真正运行时，条件可能又被别的线程改变了。所以 Mesa 风格下等待必须写成：

1
2
3

while (!condition) {
    cond_wait(&cv, &lock);
}

while 不是 busy-wait。线程在 cond_wait 里睡眠，醒来后重新检查共享状态。它保护的是“signal 只表示条件可能成立”的现实语义。