16. 并发控制：同步信号量

信号量

互斥锁在某种意义上也可以认为实现了 “happens-before” 的依赖关系—— release 必然发生在 acquire 之前。我们可以试着利用这种依赖关系来实现计算图的调度：为每条边分配一个互斥锁，代表数据或前置任务的完成；一个节点必须获得所有入边对应的互斥锁才能开始计算，计算完成后，就释放所有出边对应的互斥锁，通知下游节点输出就绪（但是这种直接使用互斥锁作为边状态信号的方式是 undefined behavior，因为互斥锁主要用于保护临界区，其释放通常要求由持有它的线程完成，若释放未曾获取的锁，则行为未定义）

我们可以从这种想法中抽象出其本质，也就是用一个“信号”去获取资源的许可，类似餐厅的取号吃饭

这种信号的思想很适合用来管理计数类型的同类资源，比如停车场的空位，为了实现这种 producer-customer 的问题，用条件变量可以轻易解决，进入的条件就是存在空位 count < capacity ，那我们从减少变量的角度出发，这实际上也就是剩余空位的数量大于零，我们停车相当于消耗了一个车位，离开相当于创造了一个车位，这也就得到了所谓“信号量”的机制

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void P(sem_t *sem) {
    // Prolaag - try + decrease/down/wait/acquire
    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 - increase/up/post/signal/release
    mutex_lock(&sem->lk);
    sem->count++;  // 创建一个信号 (车位)
    cond_broadcast(&sem->cv);
    mutex_unlock(&sem->lk);
}

根据这个一路推出信号量的思路，或许可以认为这是互斥锁的扩展

信号量：应用

信号量有两种典型的应用：

实现一个临时的 happens-before：$ A\to V(s)\to P(s)\to B $
管理计数资源：停车场、餐厅……

可以利用信号量优雅地实现 producer-customer 的模型：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
sem_t empty = SEM_INIT(depth);
sem_t fill = SEM_INIT(0);

void T_produce() {
    P(&empty);
    printf("(");
    V(&fill);
}

void T_consume() {
    P(&fill);
    printf(")");
    V(&empty);
}

信号量、条件变量与同步

信号量对比条件变量：

信号量：更加干净优雅，但是不一定能很好地表示同步条件（用更 hack 的方式解决问题）
条件变量：更加万能，但是代码比较丑陋（用更标准化的方式解决问题）

尝试用信号量解决更复杂的同步问题：哲学家吃饭，一张圆桌围坐 $ n $ 个哲学家，每两个人之间有一把叉子（筷子更加合适？？），每个哲学家（线程）有时思考有时吃饭，思考时什么也不用做，吃饭时同时需要左手右手的叉子

用条件变量解决这个问题只需要无脑设置同步条件即可，用信号量解决这个问题有一个初步的想法是 P(&sem[lhs]) && P(&sem[rhs]) ，乍一看没什么问题，但是实际上这个条件在所有人都同时举起了同一边的叉子时会陷入死锁（所以并发编程一定要仔细再仔细！），所以为了排除这种方案，有两种解决方案：

从桌子赶走一个人：为上桌吃饭人数设置一个信号量，限制不让所有人同时上桌即可（显然不可能所有人同时吃上饭）
为叉子编号，总是先拿起编号小的一把（最后一个人的顺序会和其他人反过来）

但是这样的解决方案是不够优雅不够通用的，因此更多时候条件变量是一个更好的选择，可以总结为信号量在适合的适合很好用，但不总是很好用

信号量#

信号量：应用#

信号量、条件变量与同步#

信号量

信号量：应用

信号量、条件变量与同步