本节书摘来自华章出版社《多核与GPU编程：工具、方法及实践》一书中的第3章，第3.5节， 作 者 Multicore and GPU Programming: An Integrated Approach［阿联酋］杰拉西莫斯·巴拉斯（Gerassimos Barlas） 著，张云泉 贾海鹏 李士刚 袁良 等译， 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.5 经典问题中的信号量
下面几节将介绍一组问题，有两重目的。
这些问题代表了实际应用中常见的场景。
这些问题引入了日常中常见的一些特殊条件。
3.5.1 生产者–消费者
生产者–消费者问题是通过一个共享缓冲区对两类不同进程进行同步的问题，共享缓冲区用来存放生产者线程产生的资源，消费者线程从中获取资源。一般情况下问题包含n个生产者和m个消费者。
代码清单3-8中的伪码展示了两种类型的线程如何进行互操作。
首先罗列出两类线程必须满足的需求，共享缓冲区边界特征以及安全访问共享变量的需求。
当一个生产者在共享缓冲区中存储一个资源时，必须对in参数加锁。表3-2中的相关模式是S1。
当一个消费者在共享缓冲区中移除一个资源时，必须对out参数加锁。表3-2中的相关模式是S1。
如果共享缓冲区为空，则消费者线程必须等待生产者产生资源。表3-2中的相关模式是S2。
如果共享缓冲区已满，则生产者线程必须等待消费者移除资源。表3-2中的相关模式是S2。
以上讨论可以归纳为，需要两个二元信号量作为in和out参数的加锁操作，需要两个计数信号量来指示线程对共享缓冲区的操作。代码清单3-9中的解决方案克服了代码清单3-8中效率低下的缺点，即第13行和第25行的空循环。这是由于信号量可以阻塞调用线程，直到资源可用时才恢复执行，因此while循环可以删除。
比较代码清单3-8和代码清单3-9可以引出如下几个问题。
Q：resCount计数器为何删除？这是一个共享变量，但是没有被互斥量保护，并且被完全删除。
A：删除这一变量是由于使用它的空循环被删除。如果依然在代码中保留这一计数器，则需要一个互斥量进行保护。
Q：是否可以将resAvail和slotsAvail两个计数信号量合并为一个计数信号量？这是由于resAvail+slotsAvail=BUFFSIZE。
A：在串行程序中resAvail+slotsAvail永远等于BUFFSIZE，但是当访问共享缓冲区的每种类型的线程个数多于一个时，可能产生：
另一个不允许合并这些信号量的原因在于其扮演一个信号通知角色，用于唤醒等待一个资源或者一个空位的线程。
Q：是否可以替换两个互斥量为一个？两个互斥量的作用看上去都是锁定共享缓冲区。
A：可以，但是这样会降低程序效率。这会强制一个生产者等待消费者完成资源移除操作以及更新out变量，反之也是如此。但是，当每个类型的线程数目为1时可以消除一个或者两个互斥量。因此，如果仅存在一个生产者，l1（及其相关逻辑）可以删除，如果只有一个消费者，l2（及其相关逻辑）可以删除。表3-3总结了这些不同情况。
Q：对in和out的锁的释放操作位于资源被存储和移除以前，这是否会导致资源竞争？
A：在resAvail和slotsAvail信号量被正确更新之前，由in和out（在更新之前）索引的共享缓冲区位置是不会被另一个线程（无论何种类型）访问的。第18行和第33行的临时指针也保证关键区的执行时间以及对并发性的影响程度为最小。
代码清单3-8中的代码可以通过将共享缓冲区变为一个合适的类（提供配置互斥量的方法）来进一步优化其简洁性。这将同步问题交给共享缓冲区本身，使得线程完全不用考虑任何并发问题。3.6节将会进一步讨论该问题。
3.5.2 终止处理
共享内存和分布式应用中的一个重要问题是处理程序终止。经常会出现需要对复杂条件进行判断以便执行程序终止。这些条件通常在本地进行判断（例如，在密码破解程序中查找一个合适的哈希值，或者一个GUI线程对于单击一个Exit按钮的响应），这些条件被传播给其他线程。本节将会介绍两种用于适当终止多线程程序的方法。
在这两种方法中都有两个需要注意的关键之处：
无论何种形式的终止信号都需要到达所有线程。
线程应该可以在合理的时间范围内检测到这一信号。
这两个解决方案在生产者-消费者问题中介绍，但是也可应用到其他情况中。唯一的限制是每个线程都应该周期地检查终止条件是否已满足。
3.5.2.1 利用共享数据状态终止运行
利用共享数据状态终止运行看上去是一个一般的解决方案，但是其实现有许多注意事项。现代CPU都包含多层共享缓存，以便加速内存数据访问。这些缓存所依赖的一致性模型可能并非十分严格，即一个共享变量可能在多个共享缓存中存在副本，但其中一个改变时，其他位置的值并不是立即更新。大部分共享缓存一致性实现遵循弱一致性模型，即同步变量（例如信号量）有一个全局一致性状态，但是普通数据的读写操作可以按照不同顺序执行。
因此为了恰当地通过一个共享标志来支持程序终止，必须使用原子数据类型（例如Qt中的QAtomicInt或者信号量）或者强制编译器设置volatile关键字来禁止对这些共享标志进行缓存操作。
在生产者–消费者问题中，根据线程执行迭代的次数是固定还是可变的，可以有两种不同的设计方案。具体情况区分如下：
1.已知迭代次数是先验知识。
一个计数信号量可以被所有类型的线程访问，并把无限的whlie（1）循环替换为while（sem.tryAcquire()）。tryAcquire方法是acquire的非阻塞版本，当成功对信号量减一时返回真，否则返回假。这一代码如代码清单3-10所示，其中包含生产者和消费者线程模板类的工作代码。
代码清单3-10中展示的程序需要生产者数目、消费者数目和迭代次数信息来执行，具体实例如下：
程序的关键点包括：
所有Producer和Consumer类都定义为一般类型（模板），可以支持任意资源类型。
类不变量，例如信号量、缓冲区引用以及in/out索引都另存为类的静态变量（第9～14行以及第52～56行），并在initClass静态方法中初始化。初始化操作在所有线程生成（第112行和第113行）前以及main函数已完成所需数据分配后执行。
资源相关部分（即被处理的资源的产生和消费部分）由两个函数处理。这两个函数作为参数传递给initClass方法。代码中用到的真实函数仅包含存根（stub）。
avail和buffslots信号量被两种类同时共享，这也是要在类外面进行声明的原因，相反，l1和l2互斥量是类私有的，分别在第11行和第54行声明。
C++中的静态模板函数指针语法格式如第89行和第90行所示。如果想要使用其他具体数据类型T，则需要将int说明符替换为T。
2.迭代执行次数在运行时确定。
这种情况下的代码如下：
但是这导致了另一个问题：除非能检查共享的exitFlag标志状态，否则线程无法终止。当检测到终止状态时，如何唤醒可能在信号量队列中被阻塞的线程？唤醒线程需要增加相应的信号量，运行线程重新开始运行。
一种显而易见的方法是令第一个检测到执行终止状态的线程执行该任务。代码清
单3-11展示了这一实现（出于简洁性，仅展示了部分代码），consume函数触发终止信号，某个Consumer线程检测到这一信号，并将终止标志设为真（第66行）。
代码清单3-10和代码清单3-11的其他关键不同之处在于：
检测到程序终止的线程（第62行）确保所有其他类型的线程都能通过适当地增加resAvail和slotsAvail来终止运行（第67行和第68行）。
由于借助一个Consumer线程执行终止，因此在类中要包含Consumer和Producer两种类型线程的个数（第86行）。
声明为volatileexitFlag的布尔变量在所有类型的线程间共享，允许通过一个简单的while（exitFlag == false）循环控制语句来完成终止操作（第20行和第50行）。
被唤醒的线程在与共享缓冲区交互（第24行和第53行）之前，首先要立即检测终止条件，这就防止了某些副作用和开销。
3.5.2.2 通过消息完成程序终止
另一个可以适用于分布式内存应用的解决方案是传递终止消息。在这种生产者-消费者方案中，可以通过共享缓冲区将交换的资源视为隐式消息。一个特殊的（在程序环境中无效的）资源（例如传递给一个只接受正整数的程序负数值）可以用来表示程序终止。例如，可以假定生产者线程生成并存储在类的共享缓冲区实例中：
一个Triangle3D实例有两个相同的顶点时可以被消费者线程看成终止信号。
由于资源流是无向的，因此唯一的限制是终止必须由生产者处理。如果消费者线程用来完成这一目的，则必须使用上一节提到的方法来实现。
为了说明这一概念，代码清单3-12中展示了一个示例，即一个多线程积分函数。生产者线程在共享缓存中放入计算说明，消费者线程取出并对一个特定的区间进行计算，即包含一个区间范围以及划分的子区间个数。这一个程序基本上遵循2.4.4节介绍的map-reduce计算模式。
具体的积分实现利用梯形法则，即整个积分区间[a，b]被划分为n个等宽的子区间，每个子区间长度为h，如图3-10所示。位于xi和xi+1间的每个子区间的函数面积通过h[f（xi）+f（xi+1）]/2来近似。[a，b]区间的整个面积是：
这里x0=a，xn=b，xi=a+i*h，h=（b-a）/n。
上面程序的关键之处如下。
第18～34行的IntegerCalc类作为一个消费者，从程序主线程中接收Slice结构（第7～11行）作为分配的计算任务。
主线程转变Slice结构并设置其可用性，然后依靠生产者执行（第111～116行）。
在InitClass方法中初始化的类不变量，也作为参数传递进来，指向在主线程和消费者线程间共享的信号量（第94行）。
run方法运行一个无限循环（第47行），当一个Slice结构中的div等于零时终止（第61行）。
程序的终止由主线程负责。在所有Slice结构都被放入共享缓冲区中后，主线程生成与生成线程数目一样多的信号结构（第120～125行）。注意，终止循环组织为与生成Slice任务同样的结构，在给定的共享缓冲区结构中只能这样处理。
integrCalc线程从Slice结构中抽取需要的计算参数并根据梯形法则计算面积。计算的部分结果被累加存入*result中。后者被所有IntegrCalc线程共享，并在关键区中执行累加操作（第78～80行）。
3.5.3 理发师问题?：引入公平性
理发师问题是一个线程/进程同步问题，在不同的文献中都有介绍，其最简单的情形如下：
假设有一个理发店，只有一个理发师和一个理发椅，还有一间等待房屋（可容纳固定数量的椅子）。每个进入理发店的客户都必须先坐在等待房间的椅子上，然后等待理发师的邀请才能坐在理发椅上。当理发师服务完一个客户之后，就将客户送出理发店并从等待房间中邀请另一名客户。
基于理发师和客户的上述行为方式，以及相应数目的线程，这个问题有许多种解决方案。这里将介绍一个特殊的问题，其中引入了公平性。公平性常常应用于调度算法的评价中，例如，如果一个调度程序是公平的，则所有具有相同优先级且等待运行的进程都将获得相同的处理器时间。在这种上下文中，公平性意味着发送给某个线程的信号终将到达。
为了描述这一问题，假定理发店中有两个理发师，每个理发师使用两个可用的理发椅中的一个为服务客户。代码清单3-13展示了解决方案的伪码实现。
代码清单3-13中的解决方案能够正确工作，但是存在一个致命缺陷。图3-11中的时序图说明了一个场景，其中一个理发师将一个客户的理发信号截断，导致另一个理发椅上的客户起身离开。当两个理发师线程的运行速度不同时就有可能发生这种情况。一旦Cust1增加customerReady并从相应队列中释放Barb1，这两个线程就已经隐式关联在一起。Barb1如果运行太慢而不能及时完成任务，则Barb2增加了barberDone，Cust1就会离开理发椅。这显然不是一个合适的解决方案。
解决这一问题的唯一方法是在客户和理发师之间建立联系，有两种实现方法：
1.客户获得将要对其服务的理发师线程的ID。
2.理发师获得其将要服务的客户的ID。
两种解决方案都要求把原始解决方案中的信号量替换为信号量队列，数目与需要进行标识的线程数目一样多。显然应用第一种解决方案更为高效，因为只需要为两个理发师分配两个元素。
对于一个可以获得理发师ID的客户而言，必须建立一个存放可用理发师ID的缓冲区。这一缓冲区的实现必须利用生产者–消费者模式。具体如何配置需要仔细考虑：如果存放ID的缓冲区大小跟ID的数目一样多，理发师（生产者）就无须等待缓存中的可用位置。从理发师视角看，缓冲区大小相当于是无限的，因此相关联的信号量可以删除。代码清单3-14展示了这一解决方案的关键之处。
代码清单3-14解决方案的关键之处如下。
每个理发师都通过customerReady和barberDone两个信号量队列与一个元素相联，分别在第101行、第102行定义。
与本章介绍的上一个解决方案一样，在两种类型的线程间共享的数据在main()中分配，并作为参数传递给对两个类的数据成员初始化的方法（第98～105行）。
一个缓冲区用于存放可用的理发师ID。消费者线程通过生产者–消费者模式抽取ID。唯一删除的内容是slotsAvail信号量，这是由于缓冲区大小足够容纳所有理发师ID，因此总会有一个空闲的可用位置。生产者部分的代码如第43～47行所示，消费者部分的代码如第81～84行所示。
Customer线程并不执行任何循环，因此程序终止由Barber线程负责。为了完成这一功能，customerLeft信号量在第32行被初始化为客户数目，在第42行Barber::run方法内进行递减/测试操作。
最后，第3～7行定义的concurPrint函数用于生成非错误控制台输出，限制在关键区内使用cout对象。
3.5.4 读者–写者问题
读者–写者问题发生在多个线程尝试更新一个共享资源并且多个线程尝试读取同一共享资源时。在最简单的场景中，如下两个条件控制这整个问题的运行：
每个写者必须对资源进行互斥更新。所有其他线程（包括所有读线程）都必须被阻塞。
如果一个读者访问资源，其他读者也可以同时访问。显然，与前一条件一致，写者必须等待读者完成操作后才能访问资源。
这两个规则可以防止资源进入不一致状态，避免竞争条件以及错误的改变。但是这些条件没有定义线程访问资源的顺序。
是否应该赋予某种类型的线程优先级？优先级的引入可能会导致饿死情况的发生，但是在某些情况下，优先级是程序所必需的。解决该问题的关键是对尝试访问资源的线程队列的管理。
这三个不同的可能性（包括线程顺序问题）将会在下一节的分析中解决。
3.5.4.1 优先考虑读者的解决方案
优先考虑读线程意味着，当一个读线程尝试访问资源并且该资源当前正在被其他读线程访问时，无论是否存在等待的写线程，该读线程都允许继续执行。
代码清单3-15展示了这一解决方案的核心部分伪码。
这一解决方案的设计十分简单。
写线程共享一个互斥量（writerLock），用于控制写线程进入关键区。
读线程也共享一个互斥量（countLock），用于控制读线程访问共享计数器（numReaders）。在第8行和第16行中改变这一计数器之前，一个线程必须锁定这一互斥量。
第一个获得countLock的读线程也尝试获得writerLock互斥量。如果已经有一个写线程在关键区中执行，该读线程进行等待（其他进入的读线程也将会被阻塞在这一等待处）。否则，读线程将会继续执行，并阻止其他写线程进入关键区。
在最后一个读线程退出关键区后，写线程的互斥量将被释放（第18行）。
这一解决方案优先考虑读线程，这是因为一旦一个读线程进入其关键区，所有其他尝试进入的读线程都将成功进入，并阻塞所有等待中的写线程。
3.5.4.2 为写线程赋予优先级
优先考虑写线程意味着，在等待队列中的任意写线程都将绕过所有读线程进入关键区。尽管看上去更为复杂，但是这一解决方案十分类似前一节介绍的方案。代码清单3-16展示了这一解决方案的关键核心伪码。
初步看上去，读线程部分等价于代码清单3-15中的代码，仅仅增加了对readersLock看上去无效的
加锁解锁对，更多的细节包括：
除了阻止读线程进入关键区外，readerLock锁并没有其他作用。这就是读线程要立即对其进行释放的原因（第16行）。写线程在其第一次运行时执行这一控制（第32行）。
第31行中，只有第一个写线程阻塞其他读线程。最后一个写线程离开时释放所有读线程的锁（第41行和第42行）。
通过numWriters枚举所有等待的写线程需要使用互斥量（writerCountLock）来避免竞争条件。
在第一个写线程尝试更新数据之前，读线程的执行过程与前一节的介绍一致。
3.5.4.3 公平方案
一个公平的方案是对于等待的线程队列应用一个严格先入先出策略。这意味着所有线程将按照其排队的顺序进入关键区，也遵循3.5.4节介绍的两个规则。
公平解决这一问题的一个可用技巧是使用另一个信号量，使得所有线程在执行之前只访问一次。一旦允许两种类型的线程进入其关键区，二者就应释放该信号量。只要利用一个强信号量，其执行顺序就是先入先出的，因此没有饿死的危险。
代码清单3-17展示了这一公平解决方案的伪码：
这一公平解决方案的一些关键点包括：
读者线程的代码与优先考虑读线程的解决方案一致。然而，fairLock互斥量的引入强制所有类型的线程进入相同队列中。
当一个读者线程获得fairLock时，它将对numReaders计数器加一，并获得writerLock锁。它将在进入其关键区之前释放fairLock，允许其他读者线程也进入。
如果一个写者线程跟随一个读线程进入fairLock线程，将会在第29行阻塞它，并阻止所有其他线程访问fairLock锁。
Qt提供一个方便的QReadWriteLock类，以便解决读者–写者问题。这一类支持如下方法：
lockForRead：这一锁用于资源的只读访问。只要没有写线程在之前进入过等待队列，其他读者线程就仍然允许进入。
lockForWrite：这一锁用于修改资源的访问。所有其他线程都将被阻塞。
unlock：释放锁。
同时也支持一类非阻塞的try*类型方法（例如tryLockForRead）。QReadWriteLock的解决方案中优先考虑写者线程。因此它更适用于写者线程不如读者线程频繁的情形。
