关于并发中锁、条件变量和信号量的一些随想

锁——原子性的开始

众所周知，在并发中，锁是最简单的并发源语，也是最简单的消除数据竞争维护原子性的方法，你甚至只需要使用一对语句：

1
2
3
pthread_mutex_lock(&lock);
//CS
pthread_mutex_unlock(&lock);

就可以维护中间的代码的原子性了。

但是如果是朴素的自旋锁的实现会带来一些问题：

  1. 如果多个进程同时尝试抢占一把锁，那么会让多个CPU进入自旋状态，浪费CPU资源
  2. 某些线程被阻塞，继续运行的条件可能需要其它很多线程共同达成，只使用自旋锁这个CPU在很长时间内都不能得到利用
    那么如何解决第一个问题呢？

最朴素的思路就是，先尝试获取这个锁，如果获取成功了，就直接进入临界区，如果不成功，就sleep 一段时间，这段时间甚至可以是在不超过上限的情况下指数递增的，如果超过上限就重置为1。这个自旋锁的改进版本在某种意义上可以提高CPU的运行效率，但是仍然是不够的。比如某个线程有明确的唤醒条件，那么可不可以直接让他睡到这个条件达成再唤醒呢？

答案是可以的，我们可以引入条件变量这个并发源语

条件变量——让线程在特定条件达成时唤醒

为了了解条件变量的语义，先看看条件变量在 pthread 库中的API

条件变量的API

与条件变量交互主要使用这两个函数：

1
2
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);  
int pthread_cond_signal(pthread_cond_t *cond);

而正确的等待线程的写法是：

1
2
3
4
5
Pthread_mutex_lock(&lock);  
while (ready == 0) 
    Pthread_cond_wait(&cond, &lock);  
//CS
Pthread_mutex_unlock(&lock);

正确的唤醒写法是：

1
2
3
4
Pthread_mutex_lock(&lock);  
ready = 1;  
Pthread_cond_signal(&cond);  
Pthread_mutex_unlock(&lock);

条件变量的语义

条件变量API中函数 pthread_cond_wait 提供的语义是：

  1. 释放当前线程占有的锁 mutex
  2. 在条件 cond 上进入睡眠，释放CPU
  3. 等待条件 cond 发生改变（有别的线程调用 Pthread_cond_signal ）再被唤醒
  4. 尝试重新获取锁 mutex
    而函数 pthread_cond_signal 的语义则是，唤醒所有睡在条件 cond 上的线程

    关于条件变量语义的注意事项：

    1. wait 的语义只是释放锁，等待唤醒并重新拿锁，在被唤醒和拿到锁之间没有原子性保证
    2. signal 提供的语义只是唤醒所有睡在 cond 上的线程，没有提供别的保证，例如唤醒的先后顺序

条件变量的规范用法

理解了上面的语义，就可以看看为什么条件变量的规范用法这么复杂了

对于在等待的线程来说，由于唤醒和拿锁之间没有原子性保证，所以有可能该线程被唤醒后，有其它的线程先一步获取了锁并对条件（此例中的ready）进行了修改，所以必须使用 while 不停地进行检查，直到当前的线程既持有锁，又满足了唤醒条件。

Look Deeper into 条件变量

更深入的理解条件变量，就要理解这个例子中的 ready 到底代表了什么。笔者认为，这里的ready可以是任何的条件，换句话说，你可以把这里换成任何一个复杂的表达式。而广播只需要在你认为可能使这个表达式满足的地方进行广播就可以了。

需要注意的是，这里的锁不是随便的一把锁，这把锁是用来保护你的表达式的。即，这把锁保护了表达式的真值不会被修改，维护不变式“只有拿到锁的线程才能对表达式的任意部分做出改变”。否则会出现原子性破坏的并发问题。

结语

条件变量可以看做是自旋锁的拓展，实现了线程在特定条件下的休眠与唤醒。

信号量——专为朴素生产者消费者问题打造

有一类并发问题被称之为生产者——消费者问题，即生产者的线程产生某些资源，放到有容量上限的缓冲区中，而消费者从缓冲区中取出资源进行消耗。生产者只在有空余的情况下能够放入资源，而消费者只能在有资源的情况下获取资源。

生产者消费者模型因为太过常用，所以这里有一组非常适合解决该问题的API：

1
2
3
4
5
6
7
8
9
int sem_wait(sem_t *s) { 
  decrement the value of semaphore s by one 
  wait if value of semaphore s is negative 
} 

int sem_post(sem_t *s) { 
   increment the value of semaphore s by one 
   if there are one or more threads waiting, wake one
 }

当然也一般用 p 表示获取一个资源， v 表示放入一个资源

这套API的语义十分显然，用于处理生产者和消费者问题也十分自然。

信号量的缺陷

信号量笔者认为并没有那么好用，在非朴素生产者消费者问题者，甚至可能导致隐式的死锁问题，例如jyy2024年春季学期的操作系统期中测试最后一题，打印合法的括号序列：

每个线程可能打印[ ] ( ) 这四种字符，要求每时每刻的括号序列是合法的，即括号必须匹配且小括号中不得有中括号，([]) 是不合法序列

如果使用信号量，朴素的想法是用两个信号量分别表示左小括号未被匹配的数量和中括号未被匹配的数量，但是，遇到括号序列 [( 时，如果此时下一个运行的线程是 ] 那么根据信号量它前面已经有一个 [ 了，是可以打印的，但是 ( 这个括号序列让他无法打印。这个时候很难 只 用信号量处理。

计算图+条件变量=无敌

根据jyy的理论，如果一个并发问题能够构建出计算图，那么只需要在计算图的每条边上建立一个条件变量，然后让前序节点广播对应的条件变量，后续节点cond_wait 就可以了