到目前为止，我们已经开发了锁的概念，并看到了如何正确地结合硬件和操作系统支持来构建锁。不幸的是，锁并不是构建并发程序所需要的唯一原语。<br />特别是，在许多情况下，线程希望在继续执行之前检查一个**条件（condition）**是否为真。例如，父线程可能希望在继续之前检查子线程是否已经完成(这通常称为join());这种等待应该如何实现?让我们看看图30.1。<br /><br />我们想在这里看到的是以下输出:<br /><br />我们可以尝试使用**共享变量（shared variable）**，如图30.2所示。这个解决方案通常是有效的，但是它的效率非常低，因为父线程自旋并且浪费CPU时间。这里我们想要的是让父线程进入休眠状态，直到我们所等待的条件(例如，子线程执行完毕)变为真。<br />
关键的问题：怎样等到一个条件 在多线程程序中，线程在继续之前等待某个条件为真通常是有用的。简单的方法是一直自旋直到条件变为真，这种方法非常低效，并且浪费CPU周期，在某些情况下可能是不正确的。因此，线程应该如何等待条件?
30.1 定义和例程 Definition and Routines
为了等待条件为真，线程可以使用条件变量（condition variable）。条件变量是一个显式队列（explicit queue），当某个执行状态(即某个条件)不理想时(通过等待条件)，线程可以将自己放入该队列;当其他线程改变状态时，可以唤醒一个(或多个)等待线程，从而允许它们继续(通过在条件下发出信号（signaling）)。这个想法可以追溯到Dijkstra对“私有信号量（private semaphores）”的使用[D68];类似的想法后来被Hoare命名为“条件变量（condition variable）”，在他的监测工作中[H74]。
要声明这样一个条件变量，只需这样写:pthread_cond_t c;，它声明c为条件变量(注意:还需要适当的初始化)。条件变量有两个相关的操作:wait()和signal()。当线程希望让自己进入睡眠状态时，会执行wait()调用;当一个线程在程序中更改了某些内容，因此希望唤醒一个正在等待此条件的沉睡线程时，就会执行signal()调用。具体来说，POSIX调用看起来像这样:
为了简单起见，我们通常将它们称为wait()和signal()。关于wait()调用，您可能注意到一件事:它也接受一个互斥锁作为参数;它假定在调用wait()时这个互斥锁是锁定的。wait()的职责是释放锁并(原子地)使调用线程进入睡眠状态;当线程醒来时(在其他线程通知它之后)，它必须在返回给调用者之前重新获取锁。这种复杂性源于当线程试图让自己进入睡眠状态时，防止某些竞争条件发生的愿望。让我们看看join问题的解决方案(图30.3)，以便更好地理解这一点。
有两种情况需要考虑。在第一种情况下，父线程创建子线程，但继续运行自己(假设我们只有一个处理器)，因此立即调用thr_join()来等待子线程完成。在这种情况下，它将获取锁，检查子进程是否完成(没有完成)，并通过调用wait()使自己进入睡眠状态(因此释放锁)。子线程最终会运行，打印消息”child”，并调用thr_exit()来唤醒父线程;这段代码只是获取锁，设置状态变量done，并向父程序发出信号从而唤醒它。最后，父进程将运行(在持有锁的情况下从wait()返回)，解锁锁，并打印最后的消息“parent: end”。
在第二种情况下，子线程在创建时立即运行，将done设置为1，调用信号来唤醒一个沉睡的线程(但是没有，所以它只是返回)，并完成。然后父进程运行，调用thr_join()，看到done为1，因此不等待并返回。
最后注意:您可能会观察到，当决定是否等待条件时，父程序使用了一个while循环而不是一个if语句。虽然按照程序的逻辑，这似乎不是严格必要的，但它总是一个好主意，正如我们将在下面看到的。
为了确保您理解thr_exit()和thr_join()代码中每一部分的重要性，让我们尝试几个替代实现。首先，你可能想知道我们是否需要状态变量done。如果代码看起来像下面的例子呢?(图30.4)
不幸的是，这种方法被打破了。想象这样一种情况:子进程立即运行并立即调用thr_exit();在这种情况下，子线程将发出信号，但在此条件下没有线程处于睡眠状态。当父程序运行时，它将简单地调用wait并被卡住;没有线能唤醒它。从这个例子中，您应该认识到状态变量done的重要性;它记录线程感兴趣的值。睡眠、醒来和锁都是围绕着它建立的。
这里(图30.5)是另一个糟糕的实现。在本例中，我们假设一个线程不需要持有锁来发出信号和等待。这里会发生什么问题?想想看!
注意，这个例子不是“真正的”代码，因为调用pthread_cond_wait()总是需要一个互斥对象和一个条件变量;在这里，我们只是假设接口没有这样做，因为这个负面的例子。
这里的问题是一个微妙的竞争条件。具体来说，如果父调用 thr_join() 然后检查 done 的值，它将看到它是 0 并因此尝试进入睡眠状态。但是就在它调用wait进入睡眠之前，父进程被打断，子进程运行。子进程将状态变量 done 更改为 1 并发出信号，但没有线程在等待，因此没有线程被唤醒。当父级再次运行时，它会永远沉睡，这是可悲的。
希望通过这个简单的join示例，您可以了解正确使用条件变量的一些基本要求。为了确保您理解，我们现在来看看一个更复杂的例子:生产者/消费者或有界缓冲区问题（producer/consumer or bounded-buffer problem）。
Tip：永远只在持有锁的时候发信号 尽管在所有情况下都不是必须的，但在使用条件变量时，在发出信号时保持锁可能是最简单和最好的方法。上面的例子显示了一种情况，你必须保持锁的正确性;然而，在其他一些情况下，不这样做是可以的，但可能是你应该避免的事情。因此，为了简单起见，在调用信号时保持锁（hold the lock when calling signal）。 交谈的技巧,即当调用wait时持有锁, 不仅是一种技巧, 而是由 wait 的语义强制执行的，因为 wait 总是 (a) 假设当你调用它时锁被持有，(b) 释放当调用者进入睡眠状态时的锁，并且（c）在返回之前重新获取锁。因此，这个技巧的概括是正确的：在调用信号或等待时保持锁定，您将始终处于良好状态。
30.2 生产者/消费者（有界缓冲区）问题 The Producer/Consumer (Bounded Buffer) Problem
我们将在本章中遇到的下一个同步问题称为生产者/消费者（producer/consumer）问题，有时也称为有界缓冲区（bounded buffer）问题，这是Dijkstra [D72]首先提出的。实际上，正是这种生产者/消费者的问题导致Dijkstra和他的同事发明了广义信号量（generalized semaphore）(既可以用作锁，也可以用作条件变量)[D01];稍后我们将学习更多关于信号量的知识。
想象一个或多个生产者线程和一个或多个消费者线程。生产者产生数据项并将其放在缓冲区中;消费者从缓冲区中抓取这些物品，并以某种方式消费它们。
这种安排在许多实际系统中都存在。例如，在多线程web服务器中，生产者将HTTP请求放入工作队列(即有界缓冲区);消费者线程将请求从队列中取出并处理它们。
当你将一个程序的输出管道（pipe）连接到另一个程序时，也会使用有界缓冲区，例如grep foo file.txt | wc -l。这个例子并发地运行两个进程;grep将file.txt中带有字符串foo的行写入它认为是标准输出的内容;UNIX shell将输出重定向到所谓的UNIX管道(由管道（pipe）系统调用创建)。这个管道的另一端连接到进程wc的标准输入，它只是计算输入流中的行数并打印结果。因此，grep进程是生产者;wc进程是消费者;在它们之间是一个内核中有边界的缓冲区;在本例中，您只是一个快乐的用户。
由于有界缓冲区是共享资源，我们当然必须要求对它进行同步访问（synchronized access），以免出现竞争条件。为了更好地理解这个问题，让我们检查一些实际的代码。
这就是我们要讲一些严肃的古英语的地方，还有虚拟语气。
我们首先需要的是一个共享缓冲区，生产者将数据放入其中，消费者从其中获取数据。为了简单起见，让我们只使用一个整数(您当然可以想象将一个指向数据结构的指针放置到这个槽中)，以及两个内部例程来将一个值放入共享缓冲区，并从缓冲区中获取一个值。详见图30.6。<br /><br />很简单,不是吗?put()例程假定缓冲区为空(并使用断言进行检查)，然后简单地将一个值放入共享缓冲区，并通过将count设置为1将其标记为已满。get()例程执行相反的操作，将缓冲区设置为空(即将count设置为0)并返回该值。不要担心这个共享缓冲区只有一个元素;稍后，我们将它普遍化为一个可以容纳多个元素的队列，这将比听起来更有趣。<br />现在我们需要写一些例程，知道什么时候可以访问缓冲区，把数据放进去或从里面取出数据。这样做的条件应该很明显:只在count为0时(即缓冲区为空时)将数据放入缓冲区，只在count为1时(即缓冲区已满时)从缓冲区中获取数据。如果在编写同步代码时，生产者将数据放入一个完整的缓冲区，或者消费者从一个空的缓冲区获取数据，那么我们就做错了(在这段代码中，将触发一个断言（assertion）)。<br />这项工作将由两种类型的线程完成，其中一组我们将称为生产者（producer）线程，另一组我们将称为消费者（consumer）线程。图 30.7 显示了生产者将整数放入共享缓冲区循环次数的代码，以及从共享缓冲区中获取数据（永远）的消费者，每次打印出它从共享缓冲区中提取的数据项的代码。<br />
一个失败的解决方案 A Broken Solution
现在假设我们只有一个生产者和一个消费者。显然，put()和get()例程中有临界区，因为put()更新缓冲区，而get()读取缓冲区。然而，在代码周围设置一个锁是不起作用的;我们需要更多的东西。毫无疑问，更多的是一些条件变量。在这个(中断的)第一次尝试中(图30.8)，我们有一个条件变量cond和关联的互斥锁。
让我们来看看生产者和消费者之间的信号逻辑。当生产者想要填充缓冲区时，它会等待它为空（p1 - p3）。消费者具有完全相同的逻辑，但等待不同的条件：满度 (c1 - c3)。
只有一个生产者和一个消费者，图30.8中的代码可以工作。但是，如果我们有不止一个这样的线程(例如，两个消费者)，那么解决方案就会有两个关键问题。他们是什么?
．．． (停下来思考)．．．
让我们理解第一个问题，它与等待之前的if语句有关。假设有两个消费者(Tc1和Tc2)和一个生产者(Tp)。首先，运行一个消费者(Tc1);它获取锁(c1)，检查是否有缓冲区可以使用(c2)，如果没有，则等待(c3)(释放锁)。
然后生产者（Tp）运行。它获取锁 (p1)，检查所有缓冲区是否已满 (p2)，如果发现并非如此，则继续填充缓冲区 (p4)。然后生产者发出信号表示缓冲区已填充（p5）。至关重要的是，这会将第一个消费者 (Tc1) 从在条件变量上休眠的状态移动到就绪队列；Tc1 现在可以运行（但尚未运行）。然后生产者继续，直到意识到缓冲区已满，此时它会休眠（p6，p1-p3）。
这就是问题发生的地方:另一个消费者(T**c2)潜入并消耗缓冲区中的一个现有值(c1, c2, c4, c5, c6，跳过c3的等待，因为缓冲区已满)。现在假设Tc1**运行;就在从等待返回之前，它重新获取锁，然后返回。然后调用get() (c4)，但是没有缓冲区可以使用!断言触发，代码没有按预期运行。显然，我们应该以某种方式阻止Tc1尝试消费，因为Tc2潜入并消费了缓冲区中已经产生的一个值。图30.9显示了每个线程所采取的操作，以及它的调度器状态(Ready、Running或Sleeping)随时间的变化。
出现问题的原因很简单: 在生成程序唤醒T**c1之后，但在Tc1运行之前，有界缓冲区的状态发生了变化(多亏了Tc2**)。给线程发信号只会唤醒它们;因此，这是一个提示，表明全局的状态已经改变(在这种情况下，一个值已经被放置在缓冲区中)，但不能保证当唤醒的线程运行时，状态仍然是所希望的。这种对信号含义的解释通常被称为Mesa语义（Mesa semantics），这是在以这种方式构建条件变量的第一项研究之后 [LR80]；这种对比被称为 Hoare 语义（Hoare semantics），更难构建，但提供了更强的保证，即被唤醒的线程将在被唤醒后立即运行 [H74]。实际上，几乎所有的系统都使用Mesa语义。
更好，但仍然失败：while，而不是if Better, But Still Broken: While, Not If
幸运的是，这个修复很简单(图30.10):将if改为while。想想为什么会这样;现在，消费者Tc1会被唤醒，并(持有锁)立即重新检查共享变量(c2)的状态。如果缓冲区在那一刻是空的，消费者只是回到睡眠(c3)。推论if也在生产者(p2)中被更改为while。
多亏了Mesa语义，条件变量的一个简单规则就是始终使用while循环（always use while loops）。有时你不需要重新检查条件，但这样做总是安全的;只管去做，快乐地去做。
Tip：为条件使用while(而不是if) 在多线程程序中检查条件时，使用while循环总是正确的;只使用if语句可能是错误的，这取决于语句的语义。因此，始终使用while，您的代码将按照预期运行。 在条件检查周围使用while循环还可以处理出现虚假唤醒（spurious wakeups）的情况。在一些线程包中，由于实现的细节，有可能两个线程被唤醒，尽管只发生了一个信号[L11]。虚假唤醒是重新检查线程正在等待的条件的进一步原因。
然而，这段代码仍然有一个错误，即上面提到的两个问题中的第二个。你能看见它吗？这与只有一个条件变量这一事实有关。在继续阅读之前，尝试找出问题所在。开始！（停下来思考，或者闭上眼睛……）
让我们确认一下你是正确的，或者让我们确认一下你现在是醒着的，正在读这本书的这一部分。当两个消费者(T**c1和Tc2**)先运行，然后都进入睡眠状态(c3)时，就会出现问题。然后，生产者程序运行，在缓冲区中放入一个值，并唤醒一个消费者(比如Tc1)。然后生产者循环返回(在此过程中释放和重新获取锁)，并尝试在缓冲区中放入更多数据;因为缓冲区已满，所以生产者将等待条件(因此处于睡眠状态)。现在，一个消费者已经准备好运行(Tc1)，两个线程在一个条件下(Tc2和Tp)处于睡眠状态。我们即将引发一个问题:事情变得越来越令人兴奋！
消费者Tc1然后通过从wait() (c3)返回来唤醒，重新检查条件(c2)，并发现缓冲区已满，然后消费值(c4)。然后，这个消费者会在条件(c5)上发出信号，只唤醒一个正在休眠的线程。但是，它应该唤醒哪个线程?
因为消费者清空了缓冲区，它显然应该唤醒生产者。然而，如果它唤醒了消费者Tc2(这是绝对可能的，取决于等待队列的管理方式)，我们就有问题了。具体来说，消费者Tc2将唤醒并发现缓冲区为空(c2)，并返回睡眠(c3)。生产者Tp(它有一个值要放到缓冲区中)被保留为睡眠状态。另一个消费者线程Tc1也回到睡眠状态。所有三个线程都处于休眠状态，这是一个明显的漏洞;参见图30.11，了解这场可怕灾难的残酷步骤。
信号显然是必要的，但必须更有指向性。消费者不应该唤醒其他消费者，而应该唤醒生产者，反之亦然。
单一缓冲区生产者/消费者解决方案 The Single Buffer Producer/Consumer Solution
这里的解决方案同样是一个小的:使用两个条件变量，而不是一个，以便正确地通知当系统状态改变时应该唤醒哪种类型的线程。图30.12显示了结果代码。
在代码中，生产者线程等待条件为empty，信号fill。相反，消费者线程等待fill并发出empty信号。通过这样做，上面的第二个问题被设计避免了：消费者永远不会意外唤醒消费者，生产者永远不会意外唤醒生产者。
正确的生产者/消费者解决方案 The Correct Producer/Consumer Solution
我们现在有一个有效的生产者/消费者解决方案，尽管不是一个完全通用的解决方案。我们所做的最后一个更改是实现更高的并发性和效率；具体来说，我们增加了更多的缓冲槽，这样就可以在休眠之前产生多个值，同样可以在休眠之前消耗多个值。由于只有一个生产者和消费者，这种方法更有效，因为它减少了上下文切换；对于多个生产者或消费者（或两者），它甚至允许同时进行生产或消费，从而增加并发性。幸运的是，与我们当前的解决方案相比，这是一个很小的变化。
这个正确的解决方案的第一个更改是缓冲区结构本身以及相应的put()和get()(图30.13)。我们还稍微改变了生产者和消费者为了决定是否睡觉而检查的条件。我们还展示了正确的等待和信号逻辑(图30.14)。只有当所有缓冲区都被填满时，生产者才会休眠(p2);类似地，只有当所有缓冲区当前为空时，消费者才会休眠(c2)。这样我们就解决了生产者/消费者的问题;是时候坐下来喝杯冰啤酒了。
30.3 覆盖条件 Covering Conditions
现在我们再看一个如何使用条件变量的例子。该代码研究来自Lampson和Redell关于Pilot [LR80]的论文，这是第一个实现上面描述的Mesa语义（Mesa semantics）的小组(他们使用的语言是Mesa，因此得名)。
他们遇到的问题最好通过一个简单的例子来说明，在这个例子中是一个简单的多线程内存分配库。图30.15显示了演示该问题的代码片段。
正如您在代码中看到的那样，当一个线程调用内存分配代码时，它可能必须等待更多内存释放出来。相反，当线程释放内存时，它表示有更多内存可用。但是，我们上面的代码有一个问题：应该唤醒哪个等待线程（可以不止一个）？
考虑以下场景。假设有0字节空闲;线程Ta调用allocate(100)，然后是线程Tb，它通过调用allocate(10)请求更少的内存。因此，Ta和Tb都等待条件，去休眠; 没有足够的空闲字节来满足这两个请求。
此时，假设第三个线程Tc调用free(50)。不幸的是，当它调用信号来唤醒一个等待线程时，它可能不会唤醒正确的等待线程Tb，Tb只等待10个字节的释放;Ta应该继续等待，因为还没有足够的内存可用。因此，图中的代码不起作用，因为唤醒其他线程的线程不知道要唤醒哪个线程(或多个线程)。
Lampson和Redell建议的解决方案很简单:将上面代码中的pthread_cond_signal()调用替换为pthread_cond_broadcast()，这将唤醒所有等待的线程。通过这样做，我们保证任何应该被唤醒的线程都被唤醒了。当然，它的缺点可能是对性能的负面影响，因为我们可能会不必要地唤醒许多其他不应该(还)处于唤醒状态的等待线程。这些线程将简单地被唤醒，重新检查条件，然后立即返回睡眠。
Lampson和Redell将这样的条件称为覆盖条件（covering condition），因为它覆盖了线程需要唤醒的所有情况(保守地);代价，正如我们讨论过的，是太多的线程可能被唤醒。精明的读者可能也注意到，我们可以更早地使用这种方法(参见只有一个条件变量的生产者/消费者问题)。然而，在那种情况下，我们可以使用更好的解决方案，因此我们使用了它（而不是broadcasts）。一般来说，如果你发现你的程序只在你把signals改为broadcasts时才能工作(但你认为它不应该这样做)，你可能有一个bug;修复它!但是在类似上面的内存分配器的情况下，broadcasts可能是可用的最简单的解决方案。
30.4 总结 Summary
我们已经看到了锁之外的另一个重要的同步原语的引入:条件变量。通过允许线程在某些程序状态不理想时休眠，CVs使我们能够巧妙地解决许多重要的同步问题，包括著名的(仍然重要的)生产者/消费者问题，以及覆盖条件。一个更富有戏剧性的结语会在这里，比如“He loved Big Brother”[O49]。
References
[D68] “Cooperating sequential processes” by Edsger W. Dijkstra. 1968. Available online here: http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF.
Another classic from Dijkstra; reading his early works on concurrency will teach you much of what you need to know.
[D72] “Information Streams Sharing a Finite Buffer” by E.W. Dijkstra. Information Processing Letters 1: 179–180, 1972.
http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD329.PDF
The famous paper that introduced the producer/consumer problem.
[D01] “My recollections of operating system design” by E.W. Dijkstra. April, 2001. Available: http://www.cs.utexas.edu/users/EWD/ewd13xx/EWD1303.PDF.
A fascinating read for those of you interested in how the pioneers of our field came up with some very basic and fundamental concepts, including ideas like “interrupts” and even “a stack”!
[H74] “Monitors: An Operating System Structuring Concept” by C.A.R. Hoare. Communications of the ACM, 17:10, pages 549–557, October 1974.
Hoare did a fair amount of theoretical work in concurrency. However, he is still probably most known for his work on Quicksort, the coolest sorting
algorithm in the world, at least according to these authors.
[L11] “Pthread cond signal Man Page” by Mysterious author. March, 2011. Available online: http://linux.die.net/man/3/pthread_cond_signal.
The Linux man page shows a nice simple example of why a thread might get a spurious wakeup, due to race conditions within the signal/wakeup code.
[LR80] “Experience with Processes and Monitors in Mesa” by B.W. Lampson, D.R. Redell. Communications of the ACM. 23:2, pages 105-117, February 1980.
A classic paper about how to actually implement signaling and condition variables in a real system, leading to the term “Mesa” semantics for what it means to be woken up; the older semantics, developed by Tony Hoare [H74], then became known as “Hoare” semantics, which is a bit unfortunate of a name.
[O49] “1984” by George Orwell. Secker and Warburg, 1949.
A little heavy-handed, but of course a must read. That said, we kind of gave away the ending by quoting the last sentence. Sorry! And if the government is reading this, let us just say that we think that the government is “double plus good”. Hear that, our pals at the NSA?
Homework (Code)
这个作业让你探索一些使用锁和条件变量来实现本章讨论的生产者/消费者队列的各种形式的真实代码。您将查看实际的代码，在各种配置中运行它，并使用它来了解哪些工作，哪些不工作，以及其他的复杂情况。详细信息请阅读README。
Questions
- 我们的第一个问题侧重于 main-two-cvs-while.c（工作解决方案）。首先，研究代码。您认为您了解运行程序时会发生什么吗？
- 运行一个生产者和一个消费者，并让生产者产生一些值。从一个缓冲区(大小为1)开始，然后增加它。对于较大的缓冲区，代码的行为如何变化?(还是?)当你将消费者睡眠字符串从默认(没有睡眠)更改为-C 0,0,0,0,0,1时，你会预测num full与不同的缓冲区大小(例如，- m10)和不同数量的生产项目(例如，-l 100)吗?
- 如果可能的话，在不同的系统上运行代码(例如，Mac和Linux)。你看到这些系统的不同行为了吗?
- 让我们看看一些时间。您认为下面的执行，一个生产者，三个消费者，一个单条目共享缓冲区，每个消费者在点c3暂停一秒钟，将花费多长时间?
./main-two-cvs-while -p 1 -c 3 -m 1 -C 0,0,0,1,0,0,0:0,0,0,1,0,0,0:0,0,0,1,0,0,0 -l 10 -v -t
- 现在将共享缓冲区的大小改为3 (-m 3)。这会对总时间产生任何影响吗?
- 现在将sleep的位置更改为c6(这个模型是一个消费者从队列中取出一些东西，然后用它做一些事情)，同样使用单条目缓冲区。在这种情况下，你预计什么时间? ./main-two-cvs-while -p 1 -c 3 -m 1 -C 0,0,0,0,0,0,1:0,0,0,0,0,0,1:0,0,0,0,0,0,1 -l 10 -v -t
- 最后，再次将缓冲区大小更改为 3 (-m 3)。你现在预测什么时间？
- 现在让我们看看main-one-cv-while.c。你能配置一个睡眠字符串，假设一个生产者，一个消费者，一个大小为1的缓冲区，从而导致这个代码的问题吗?
- 现在将消费者的数量改为2个。你可以为生产者和消费者构造睡眠字符串以便在代码中引起问题吗?
- 现在检查main-two-cvs-if.c。你能在这个代码中引起一个问题吗?再次考虑只有一个消费者的情况，以及有多个消费者的情况。
- 最后,检查main-two-cvs-while-extra-unlock.c。在执行put或get操作之前释放锁会出现什么问题?给定睡眠字符串，您能可靠地导致这样的问题发生吗?会发生什么坏事呢?
若有收获，就点个赞吧
0 人点赞
