写在前面：这是本系列的第十六篇。

在上一讲中，我们发现互斥锁 (mutex) 只能保证代码原子性地执行，却无法控制并发线程的先后次序。为了实现 Happens-before 的顺序关系，我们学习了万能的“条件变量”机制。

本讲内容：我们将学习由计算机科学巨擘 E. W. Dijkstra 发明的另一种共享内存同步神器：信号量 (Semaphore)。并在最经典的“哲学家就餐问题”中，直面并发编程的死锁梦魇。

同步：实现 Happens-before

同步的核心，就是实现“条件达成前等待” $ \rightarrow $ “条件达成后继续”。

• 23:59:59 大活门口不见不散。
  • 存在一个确定的状态：两人同时到达，且都未进行下一步动作。
• 生产 (对象创建) $ \rightarrow $ 消费 (对象释放)。
  • 存在一个状态：对象已经创建，但还未被释放。
• 线程结束 $ \rightarrow $ join 返回。
  • 存在一个状态：线程全部结束，且后续代码还未开始。

条件变量的终极万能模板：

• 等待条件满足：while (!cond) wait(cv, lk);
• 条件可能满足时唤醒：broadcast(cv);

互斥锁也能实现 Happens-before (Release -> Acquire)

其实，哪怕不用条件变量，单靠互斥锁也能强行造出同步。

void lock() {
    std::unique_lock<std::mutex> lk(mtx);
    cv.wait(lk, []{ return !lock_held; });
    lock_held = true;
}
 
void unlock() {
    std::lock_guard<std::mutex> lk(mtx);
    lock_held = false;
    cv.notify_one();  // 或 cv.notify_all()
}

• 在纯互斥的场景下（例如自己写 malloc 分配器），直接用底层的 mutex_lock 效率更高。

---

信号量 (Semaphore)：凭票入场的艺术

有没有想过一个奇妙的 Hack 技巧？

1. 主进程创建一把互斥锁 L，并立即 lock(L) 获取它。
2. 主进程再次调用 lock(L)，由于锁已经被占，主进程被挂起（等待）。
3. 此时，派出一个子进程，在子进程里调用 unlock(L)！
4. 主进程瞬间被唤醒，lock(L) 成功返回，继续执行。

_(注：在 C++ std::mutex 中这是一个 Undefined Behavior，互斥锁通常要求在同一个线程解铃还须系铃人。但这给我们提供了一种绝妙的*_同步思路！)*

这种机制的本质：Release as Synchronization

这种“一个线程上锁，另一个线程解锁”的思想，实现了完美的 Happens-before：

• Acquire (获取): 等待信号。
• Release (释放): 发出信号。

信号量的现实隐喻：“资源许可”与“凭票入场”

不要把信号量想得很神秘，它就是现实生活中的“门票”：

• 游泳馆： 储物柜只有 100 个手环。有手环就能进（Acquire），没有就排队。出来时交还手环（Release）。
• 餐厅： 只有 20 张桌子。有空桌直接进，没有就取号等待。
• 停车场： 只有 50 个车位。有空位抬杆进场，没空位在门口死等。

用条件变量模拟“停车场” (信号量的推导)

在发明信号量之前，如果我们用条件变量来写停车场的逻辑：

void enter_parking() {
    mutex_lock(&lk);
    // 进入 parking lot 的判断：如果车位满了，就睡觉等待
    while (!(in_parking < capacity)) {
        cond_wait(&cv, &lk);
    }
    in_parking++;  // 这个时候我已经拿到车位，“进入”了
    mutex_unlock(&lk);
}

void leave_parking() {
    mutex_lock(&lk);
    in_parking--;         // 腾出车位
    cond_broadcast(&cv);  // 大吼一声：有车位了！唤醒外面排队的车
    mutex_unlock(&lk);
}

发现了吗？“空位” 和 “占用” 其实是相对的！

• 停车 = “吃掉”一个车位资源。
• 离开 = “创造”一个车位资源。

于是，Dijkstra 发明了“信号量”！

如果把上面的代码封装一下，把车位数量抽象成 count，我们就得到了大名鼎鼎的 P / V 操作：

void P(sem_t *sem) {
    // Prolaag (荷兰语：尝试降低) - wait / acquire / down
    mutex_lock(&sem->lk);
    while (!(sem->count > 0)) {
        cond_wait(&sem->cv, &sem->lk);
    }
    sem->count--;  // 消耗一个信号 (吃掉一个车位/手环)
    mutex_unlock(&sem->lk);
}

void V(sem_t *sem) {
    // Verhoog (荷兰语：增加) - signal / release / up
    mutex_lock(&sem->lk);
    sem->count++;  // 凭空创造一个信号 (还回一个车位/手环)
    cond_broadcast(&sem->cv);
    mutex_unlock(&sem->lk);
}

极客提示：把信号量当互斥锁用！
如果我们把信号量的初始资源设为 1：
sem_t sem = SEM_INIT(1);
那么 P(&sem) 就是 lock，V(&sem) 就是 unlock。
因此：“信号量本质上是互斥锁的一种数学推广！”

---

信号量的实战应用

1. 实现一次临时的 Happens-before ($ A \rightarrow B $)

线程 1 执行完 $ A $ 后调用 V(s)。
线程 2 在执行 $ B $ 之前调用 P(s)。
这样就强行锁死了 $ A $ 必然在 $ B $ 之前执行！

2. 优雅实现：生产者-消费者模型

告别复杂的条件变量 while 循环，用信号量写生产者-消费者简直是艺术：

// 固定大小的缓冲区
sem_t empty = SEM_INIT(depth); // 初始时，有 depth 个空位
sem_t fill  = SEM_INIT(0);     // 初始时，有 0 个数据

void T_produce() {
    P(&empty);      // 消耗一个空位袋子，如果没有空位就死等
    printf("(");    // 生产数据放入
    V(&fill);       // 创造一个有数据的袋子，叫醒消费者！
}

void T_consume() {
    P(&fill);       // 消耗一个有数据的袋子，如果没有数据就死等
    printf(")");    // 取出数据消费
    V(&empty);      // 创造一个空位袋子，叫醒生产者！
}

---

难度暴增：哲学家就餐问题 (Dining Philosophers)

信号量非常优雅，但当多个资源交织在一起时，致命的危机就潜伏在代码中。

哲学家吃饭问题 (E. W. Dijkstra, 1960)

• 5 个哲学家围坐在一张圆桌旁，平时思考，饿了就吃饭。
• 桌上只有 5 把叉子。
• 规则：吃饭必须同时拿到左手和右手两把叉子。

灾难发生：死锁 (Deadlock)

我们顺理成章地用信号量来实现：把每把叉子看作初始值为 1 的信号量。哲学家饿了，就依次 P 左手，再 P 右手。

#include <thread.h>
#include <thread-sync.h>

#define N 5
sem_t avail[N]; // 5把叉子

void Tphilosopher(int id) {
    int lhs = (id + N - 1) % N; // 左手叉子编号
    int rhs = id % N;           // 右手叉子编号

    while (1) {
        P(&avail[lhs]);  // 拿起左手叉子
        printf("+ %d by T%d\n", lhs, id);
        
        P(&avail[rhs]);  // 拿起右手叉子
        printf("+ %d by T%d\n", rhs, id);

        // 吃饭 (Eat)

        printf("- %d by T%d\n", lhs, id);
        printf("- %d by T%d\n", rhs, id);
        
        V(&avail[lhs]);  // 放下左手
        V(&avail[rhs]);  // 放下右手
    }
}

运行结果：代码卡死了！

......
+ 3 by T4
+ 4 by T4
- 3 by T4
- 4 by T4
+ 2 by T3
+ 4 by T5
+ 3 by T4
+ 1 by T2
^C   # 程序彻底挂起，无响应，被迫强制中断

发生了什么？
想象一个极端的并发情况：5 个哲学家同时饿了，同时举起了左手的叉子！
此时桌上 5 把叉子全被拿光了。然后他们每个人都在等待右手的叉子，但右手的叉子都在旁边那个人的左手上！
没有人愿意放下左手的叉子。死锁诞生。

破解死锁的 Workaround

解法 1：从桌子上赶走一个人 (引入门卫)

• 在桌子外加一个容量为 4 的信号量（餐厅只发 4 张进场就餐卡）。
• 拿到卡的人才能上桌。这样桌上最多只有 4 个人，必然有 1 个人能同时拿到左右两把叉子，吃完后释放资源，打破死锁循环。

解法 2：Lock Ordering (全局锁排序)

• 给叉子强行编号（0 到 4）。
• 强行规定：所有哲学家必须先拿编号小的叉子，再拿编号大的叉子。
• 这样，坐在 0 号和 4 号之间的哲学家，会去抢 0 号叉子，而不是像其他人一样先拿左手。这就破坏了死锁形成的“环形等待”条件！

---

信号量 vs 条件变量：谁才是王者？

• 信号量： 干净、优雅，完美解决了类似于生产者-消费者这种“资源计数型”问题。
• 局限性： 但如果同步条件变成了“二选一”（比如鱼序列 <><_ 只要匹配任意一边的鱼头鱼尾即可），单纯的资源加减就显得极其无力。信号量很难表达复杂的逻辑决策。
• 条件变量： 万能！ 适用于任何同步条件。配合 while(!cond) 模板，只要你能用 C 语言写出来的条件，它都能同步。缺点是代码显得臃肿，有循环空转的味道。

终极魔法挑战：用信号量实现条件变量 (Spicy 🌶️)

既然两者都是同步原语，能不能用信号量把条件变量给手搓出来？
来自 2003 年的技术报告：Implementing condition variables out of a simple primitive like semaphores is surprisingly tricky.

void wait(cond_t *cv, mutex_t *mutex) {
    atomic_inc(&cv->nwait); // 原子增加等待线程计数
    mutex_unlock(mutex);    // ⚠️ 释放互斥锁！允许其他线程进入临界区

    // ⛔ 致命漏洞窗口：这里可能会发生线程切换，恰好另一个线程执行了 broadcast！
    
    P(&cv->sleep);          // 挂起自己
    mutex_lock(mutex);      // 醒来后重新抢锁
}

void broadcast(cond_t *cv) {
    mutex_lock(&cv->lock);  
    for (int i = 0; i < cv->nwait; i++)
        V(&cv->sleep);      // 唤醒所有等待的线程
    cv->nwait = 0;          
    mutex_unlock(&cv->lock); 
}

实现困难的本质原因：唤醒丢失 (Lost Wakeup)！

在 wait 函数中，当你 mutex_unlock(mutex) 释放锁的一瞬间，到你真正执行 P(&cv->sleep) 睡下去之前，存在一个极小的时间差。
如果此时另一个线程飞速冲进来，发现条件满足，执行了 broadcast（连续执行了 $ n $ 次 V），但此时你还没开始睡！
等你磨磨蹭蹭执行 P 的时候，之前那个 V 信号要么被别人抢走，要么早已错过。你将面临永久睡眠！

那怎么办？
必须在底层将 Release (释放锁) 和 Wait (进入睡眠) 实现为“不可分割的绝对原子操作”。软件层面根本解决不了这个问题，最后必须求助于操作系统内核（实际靠的是 futex 系统调用）。

---

总结

Take-away messages:

信号量可以看作是互斥锁的一个伟大“推广”。我们可以把信号量具象化地理解成：游泳馆的手环、停车场的车位、或者袋子里的球。

通过计数的方式，它极具美感地实现了线程间的先后顺序控制（Happens-before）。在处理同质化资源共享时，信号量能带来极其优雅的代码。

但信号量绝不是万能的。在复杂的资源依赖图（如哲学家就餐）中，滥用信号量极易招致死锁；在面对复杂的逻辑条件时，老老实实回到“条件变量”的模板才是 System 程序员最安稳的归宿。