30. Condition Variables

之前介绍了lock，以及使用lock构建的一些线程安全的数据结构。但是那并不是所有并发的内容，说到并发，怎么能不谈谈同步呢？并发中，一个线程等待另一个线程是很常见的事情。举个栗子，父线程要等待子线程结束才能结束：

我们希望看到的结果是这样：

那要怎么做才能实现上述目的呢？首先尝试使用一个共享变量：

这种做法基本可以达到我们的目的，但是效率很低，因为父线程一直在spin。实际上，我们应该将父线程sleep，当子线程结束时，再awake父线程。那么问题来了：在多线程程序中，经常出现一个线程要等待另一个线程的。简单的做法就像上面这样，在条件满足前一直spin，但是很低效。那应该用什么方法来代替呢？

30.1 Definition and Routines

为了实现同步等待的目的，线程用到的叫做condition variable。condition variable是一个队列，当一些条件不满足时线程可以将自己放到这个队列中（wait）。当由于其他线程的操作使得其他该条件成立时，可以将在队列中的一个或多个线程唤醒（signal），允许他们继续运行。
声明condition variable，简单点可以直接pthread_cond_t c，每个condition variable都有两个原语：wait()和signal()。wait()原语将线程自己sleep；signal()原语可以将一个sleeping的线程唤醒，一般用于某个线程改变了某个条件后。特别的。POSIX库中长这样：

你可能发现，在wait()中还传入了lock作为参数，wait()的作用就是原子地先将锁释放，然后将线程sleep。当线程被唤醒时，在wait()中必须重新申请占用lock，才能进行接下来的操作。这样可以避免race condition。

这样有两种情况：

第一种是父线程需要等待子线程，那么父线程就会被sleep。当子线程结束时，由于done=1，父线程会从wait()处被唤醒，这时父线程需要先的申请lock，如果子线程还没有释放lock，父线程无法进行下面的操作。

第二种情况，父线程无须等待子线程，那就没什么好说的了，按照流程进行下去。

下面来看一种更复杂的情况：生产者消费者模型。

30.2 The Producer/Consumer (Bounded Buffer) Problem

一个或多个生产者以及一个或多个消费者，生产者向buffer中生产数据，消费者从buffer中取出数据消费。这种模型在实际系统中很常见，比如多线程的web服务器，生产者线程生产HTTP请求，消费者线程处理HTTP请求。等等。
因为有界buffer是共享资源，因此必须保证对其的同步操作，要避免race condition。

首先来看简单的生产者和消费者，这里简单起见buffer只是一个整数值，后面会扩展的：

生产者不停的生产数据，消费者不停的取出数据。其中put()，假设buffer是空的，然后将数据放进去后通过将count设置为1表明buffer已满；get()从buffer中取数据，然后将count设置为0，返回数据值。

对于这个模型，条件是这样：只有当count是0时，才能put()；只有count是1时，才能get()。因为你不能向已经满了的buffer在放数据，也不能从空的buffer中取数据。

A Broken Solution

现在假设只有一个生产者和一个消费者，现在要想实现生产者和消费者的同步该怎么做呢？也就是说实现，只有在生产者向buffer中生产数据后，消费者才能从buffer中取数据？只有lock是不够的，还需要用到condition variable。先来看一次失败的尝试：

这种做法在只有一个生产者和一个消费者的时候是可行的，如果是多线程时，就会有两个问题。

第一，在判断count状态时使用了if语句。假设有两个消费者 $T_{c1}、T_{c2}$ ，一个生产者 $T_{p}$ 。考虑下面这种情况：

问题在于，当 $T_{p}$ 向buffer中put数据后，本应该让Ready的 $T_{c1}$ 运行，但是被 $T_{c2}$ 抢占了先机，当 $T_{c2}$ 把数据取完之后， $T_{c1}$ 开始运行了，但这是已经没有数据了，ops。

问题的原因在于，当 $T_{c1}$ 被唤醒成Ready状态后，没有立刻运行使其成为Run，在其真正Run之前，buffer的状态又发生了改变。

对于这种情况，可以将if改为while，那么可以解决第一个问题。变成这样：

当判断语句是while时，现在 $T_{c1}$ 被唤醒，然后由于while循环立即检查count的状态。如果Buffer为空， $T_{c1}$ 又会sleep。记住，在condition varivable中永远使用while循环，可能并不一定真的要重新检查条件，但是加上总没错的。

这虽然解决了第一个问题，但是第二个问题还没有解决。考虑下面这种情况：

问题在于，一开始 $T_{c1}、T_{c2}$ 都在sleep，接着 $T_{p}$ 放入数据，接着 $T_{p}$ 也sleep。 $T_{c1}$ 被唤醒消费数据，然后试图去唤醒 $T_{p}$ ，但是由于并不能控制唤醒哪个进程，完全有可能唤醒 $T_{c2}$ ，ops，搞错了， $T_{c2}$ 醒来一看没有数据于是接着睡， $T_{c1}$ 认为自己唤醒了 $T_{p}$ ，也开始睡， $T_{p}$ 自始至终都在睡，好嘛大家都在睡！

要想解决这个问题，就要让signal唤醒的线程正确。所以在这里要使用两个condition variable，代码长这样：

对于生产者和消费者各分配一个condition variable，生产者生产数据后唤醒消费者的cv，消费者消费数据后唤醒生产者的cv。

The Correct Producer/Consumer Solution

上面的做法已经可以基本满足需求了，现在要做最后一点改变，将Buffer的大小扩大，这样就能够减小context switch以减少开销：

30.3 Covering Conditions

还有一个问题：唤醒线程的时候，应该唤醒哪一个？

考虑这种情况，线程A申请100字节空间，线程B申请10字节空间，但是由于内存空间不足，两个线程依次sleep。不久后有线程释放了50字节空间，那么这时应该唤醒哪一个线程呢？很明显时线程B因为B只要求10字节的空间，唤醒它可能让他运行。但是往往很有可能就唤醒了A，A被唤醒后还是没有足够的内存空间。

因此解决方法是：不要pthread_cond_signal()，用pthread_cond_broadcast()。signal只是唤醒单个线程，而broadcast唤醒所有线程。那么这种做法是可以满足需求的，所有应该被唤醒的线程都被唤醒了，但是缺点是可能会唤醒那些不该被唤醒的线程，因此性能会变差。这种情况叫做covering condition。