目录
第三章 基本同步模式
3.1 信令（发送信号）（Signaling）
3.2 Sync.py
3.3 会合（Rendezvous）
3.3.1 关于“会合”的提示
3.3.2 “会合”的解决方案
3.3.3 死锁-1#
3.4 互斥（Mutex）
3.4.1 互斥的提示
3.4.2 互斥的解决方案
3.5 多路复用（Multiplex）
3.5.1 多路复用方案
3.6 屏障（Barrier）
3.6.1 关于屏障的提示
3.6.2 关于屏障的非解决方案
3.6.3 死锁-2#
3.6.4 屏障的解决方案
3.6.5 死锁-3#
3.7 可重复使用的屏障(Reusable barrier)
3.7.1 可重复使用屏障的非解决方案
3.7.2 可重复使用屏障的问题-1#
3.7.3 可重复使用屏障的非解决方案-2#
3.7.4 可重复使用屏障的提示
3.7.5 可重复使用屏障的解决方案
3.7.6 预装旋转栅门（Preloaded turnstile）
3.7.7屏障对象（Barrier objects）
3.8 队列(Queue)
3.8.1 队列提示(Queue hint)
3.8.2 队列方案(Queue solution)
3.8.3 独占队列提示(Exclusive queue hint)
3.8.4 独占队列方案(Exclusive queue solution)
本章介绍了一系列基本的同步问题，并展示了使用信号量来解决这些问题的方法。 这些问题包括我们已经看到的序列化和互斥，以及其他问题。
信号量最简单的用途大概就是发送信令，这意味着一个线程向另一个线程发送信号以通知它发生了某些事情。
信令可以保证一个线程中的一段代码将在另一个线程中的一段代码之前运行; 换句话说，它解决了序列化问题。
假设我们有一个名为sem的信号量，初始值为0，并且线程A和B具有对它的共享访问权。
statement语句代表任意程序语句。 为了让例子更具体一点，假设a1从文件中读取一行，并且b1在屏幕上显示该行。 此程序中的信号量保证在线程B开始执行b1之前，线程A已完成a1的执行。
以下是它的工作原理：如果线程B首先进入wait语句，它会查到sem的初始值为零，并且它将被阻塞执行。 然后当线程A执行signal()发出信号时，线程B才能继续执行。
类似地，如果线程A首先发送信号，那么信号量的值将递增，并且当线程B进入等待时，它将立即进行。无论哪种方式，都可以保证a1和b1的执行顺序。
信号量的这种使用是signal操作和wait操作来由的基础，在这种情况下，名称是很方便的助记符。不幸的是，我们会看到其他不太有帮助的名称的情况。
说到有意义的名字，sem并不算一个。如果可能，最好给信号量取一个能表明它的准确含义的名称。在这种情况下，像a1Done这样的名称可能就挺好的，因此a1done.signal（）表示“表示a1已完成”，而a1done.wait（）表示“等到a1完成”。
练习： 从signal.py开始，写一下如何使用sync同步。
为什么线程B发出initComplete信号？
思考：推广信号量模式，使其在两种情况下都有效。 线程A必须等待线程B，反之亦然。 换句话说，给定以下代码
我们要保证a1在b2之前发生而b1在a2之前发生。 在编写解决方案时，请务必指定信号量的名称和初始值（稍有提示）。
您的解决方案不应强制执行太多限制。 例如，我们不关心a1和b1的顺序。 在您的解决方案中，任何一个可能的顺序都应该可以得到执行。
这个同步问题有一个名字; 这是一个“约会”。 这个想法是两个线程在执行点会合，并且这两个线程只有在都到达之后，才能继续往下执行。
您能够找到解决方案的机会很大，但如果没有，这里有一个提示。创建两个名为aArrived和bArrived的信号量，并将它们初始化为零。
顾名思义，aArrived表示线程A是否已到达集合点，bArrived也是类似的意思。
基于上述提示，下面是我的方案：
在解决上述问题时，你可能会想出下面这个方案：
这个解决方案也可以工作，虽然效率可能较低，因为它可能会导致线程A和线程B进行一次不必要的切换。
如果A首先到达，它要等待B。当B到达时，它首先唤醒A，并可能立即进入等待，在这种情况下它会阻塞，直到A到达并发送信号，然后两个线程都可以继续往下执行。
想想这段代码的其他可能执行的路径，并自己证明，在任何情况下，只有在两个线程都到达后，才可能继续执行。
同样，在处理上一个问题时，您可能尝试过这样的事情：
如果是这样，我希望你尽快抛弃它，因为这样有一个严重的问题。 假设A首先到达，它将在等待时阻止。 当B到达时，它也会阻塞，因为A无法发出信号。 此时，两个线程就都不能继续执行了，一直到永远，都不会往下执行。
这种情况称为死锁，显然，它不是解决同步问题的成功方案。在这种情况下，错误是显而易见的，但通常死锁的可能性更微妙。 我们稍后会看到更多的例子。
信号量的第二个常见用途是强制互斥。 我们已经看到了一种用于互斥的用法，即控制对共享变量的并发访问。互斥锁保证一次只有一个线程访问共享变量。
互斥就像是从一个线程传递到另一个线程的令牌，同一时刻只允许一个线程继续进行。例如，在“蝇王”中，一群孩子使用海螺作为互斥体。为了说话，你必须先握住海螺。只有一个孩子能握住海螺，这样就只有一个人能说话。【虽然这个比喻对现在有帮助，但它也会误导人，正如你在第5.6节中所看到的。】
同样，为了让线程访问共享变量，它必须先“获取”互斥锁；当它执行完成后，再“释放”互斥锁。一次只能有一个线程可以拿到互斥锁。
思考：将信号量添加到以下示例中，以强制互斥共享变量计数。
创建一个名为mutex的信号量，该信号量初始化为1。值为1表示线程可以继续并访问共享变量; 值为零意味着它必须等待另一个线程释放互斥锁。
下面是解决方案：
由于互斥锁最初为1，因此无论哪个线程首先进入wait函数都可以继续进行。当然，等待信号量(wait)的行为具有递减它的效果，因此到达的第二个线程必须先等第一个线程发出信号。
编排时我缩进了更新操作，以显示它被包含在互斥锁中。
在此示例中，两个线程都运行相同的代码。这有时被称为对称解决方案。如果线程必须运行不同的代码，则解决方案是非对称的。 对称解决方案通常更容易一般化推广。在这种情况下，互斥解决方案可以处理任意数量的并发线程而无需修改。只要每个线程在执行更新之前等待并在之后发出信号，那么没有两个线程将同时访问计数。
通常，需要保护的代码称为临界区，我想是因为防止并发访问至关重要。
在计算机科学和混合隐喻的传统中，人们有时会谈论互斥体的其他几种方式。 在我们到目前为止使用的比喻中，互斥锁是从一个线程传递到另一个线程的令牌。
在另一个比喻中，我们将临界区视为一个房间，并且一次只允许一个线程进入房间。 在这个比喻中，互斥体被称为锁，一个线程进入房间时，被称为加锁，并在退出时将其解锁。 然而，偶尔，人们会混淆隐喻并谈论“获取”或“释放”锁，这没有多大意义。
这两个比喻都有潜在的用途，可能会产生误导。 当您处理下一个问题时，请尝试两种思维方式，并查看哪种方法可以帮助您找到解决方案。
思考： 再推广前面的解决方案，以便它允许多个线程同时在临界区运行，但它强行限制并发线程数的上限。换句话说，在临界区中不能同时运行n个线程。
该模式称为多路复用。 在现实生活中，多元化问题发生在繁忙的夜总会，在这些夜总会中，允许同时进入建筑物的人数是有上限的，以维持消防安全或创造排他性的幻觉。
在这些地方，保安通常追踪建筑物内部的人数，在房屋人数达到容量时阻止新来的人进入，来强制执行同步约束。 这样，只有一个人离开，才允许另一个人进入。
使用信号量强制执行此约束，听起来可能很困难，但这几乎是微不足道的。
要允许多个线程在临界区中运行，只需将信号量初始化为n，这是应该允许的最大线程数。
在任何时候，信号量的值表示可以进入的其他线程的数量。 如果该值为零，则下一个线程将阻塞，直到其中一个线程退出并发出信号。 当所有线程都退出时，信号量的值将恢复为n。
由于解决方案是对称的，因此通常只显示代码的一个副本，但您应该想象有多个线程在并发运行着的多个代码副本。
多路复用解决方案
如果临界区被占用，且多个线程到达会发生什么？当然，我们想要的是所有到达的线程都要等待。这个解决方案确实如此。每次线程到达并排队等待时，信号量都会递减，因此信号量（负数）的值表示等待队列中的线程数。
线程离开时，它会向信号量发出信号，递增其值并允许某一个等待线程继续执行。
再考虑一下隐喻，在这种情况下，我发现将信号量视为一组标记（而不是锁定）是有用的。当每个线程调用wait时，它会获取一个令牌;当它调用signal时就释放一个。只有持有令牌的线程才能进入房间。如果线程到达时没有可用的令牌，则等待直到另一个线程释放一个令牌。
在现实生活中，售票窗口有时会使用这样的系统。他们将令牌（有时是扑克筹码）分发给客户。每个令牌都允许持有者购买车票。
再次考虑3.3节中的“会合”问题。 我们提出的解决方案的局限性在于它不适用于两个以上的线程。
思考： 进一步推广会合解决方案。 每个线程都应该运行以下代码：
同步的要求是，在所有线程执行完会合（rendezvous）之前，没有线程执行临界点(critical point)。
您可以假设有n个线程，并且该值存储在可从所有线程访问的变量n中。
当前n - 1个线程到达时，它们应该阻塞直到第n个线程到达，然后所有线程才可以继续执行。
对于本书中的许多问题，我将通过介绍我在解决方案中使用的变量并解释其含义来提供提示。
提示
count 跟踪记录已到达的线程数。 mutex提供对count的独占访问，以便多个线程可以安全地递增它。
barrier 被锁定（零或者负数），直到所有线程到达；然后它应该解锁（大于等于1）。
首先，我将提出一个不太正确的解决方案，这有助于检查错误的解决方案并找出问题所在。
由于count被mutex互斥锁保护，因此它计算通过的线程数。前n-1个线程在到达barrier屏障时会等待，而该barrier屏障最初是被锁定的【注：初值为0】。 当第n个线程到达时，它会解锁屏障。
思考： 这个解决方案有什么问题？
问题是会导致死锁。
举一个例子，假设n = 5并且有4个线程在barrier.wait()处等待。 信号量的值（负数）是排队的线程数，即-4。
当第5个线程执行barrier.signal()时，允许其中一个等待线程继续，并且信号量增加到-3。【译注：只有第n个线程满足couont == n的条件，只有它才会执行barrier.signal()函数；其他的都会跳过去，在barrier.wait()处等待。】
但是再也没有线程会再次执行barrier.signal()，给信号量barrier发送信号，其他线程都不能通过屏障。 这是死锁的第二个例子。
思考：这段代码总是会造成死锁吗？ 你能找到一个不会导致死锁的代码执行路径吗？
思考：解决问题。
最后，给出一个可以正常工作的屏障方案：
唯一的变化是在barrier.wait()后面加上一行barrier.signal()。现在，当每个线程通过时，它会发信号通知信号量，以便下一个线程可以通过。
这种模式经常发生，即一对快速连续的wait()和signal()函数，它有一个名字，被称为旋转栅门（十字转门）(turnstile)，因为它允许一次通过一个线程，并且可以锁定以阻止所有线程。
在其初始状态（零），旋转栅门被锁定。 第n个线程解锁它，然后所有n个线程都通过。
读取互斥锁之外的count值似乎很危险。 在这种情况下，这不是问题，但一般来说，这可能不是一个好主意。 我们将在几页内对其进行清理，但与此同时，您可能需要考虑以下问题：在第n个线程之后，旋转门处于什么状态？barrier屏障可能发出多于一次的信号吗？
由于一次只有一个线程可以通过互斥锁mutex，并且一次只有一个线程可以通过旋转栅门，因此将旋转栅门放入互斥锁可能是合理的，如下所示：
事实证明这是一个坏主意，因为它也可能导致死锁。
想象一下，第一个线程进入互斥锁mutex，然后在它到达旋转栅门时阻塞。 由于互斥锁被锁定，因此没有其他线程可以进入，因此条件count == n将永远不会成立，并且没有人会解锁旋转栅门。
在这种情况下，死锁是相当明显的，但它演示了死锁的常见原因：在持有互斥锁时阻塞信号量。
通常，一组协作线程将在循环中执行一系列步骤，完成每个步骤之后在屏障处同步。 对于这个应用程序，我们需要一个可重复使用的屏障，在所有线程通过后锁定自身。
思考：重写屏障解决方案，以便在所有线程都通过之后，再次锁定旋转栅门。
再一次，我们尝试从一个简单的方案开始，并逐步改进：
请注意，旋转栅门( turnstile.wait()和turnstile.signal() )之后的代码与之前的代码几乎相同。同样，我们必须使用互斥锁mutex来保护对共享变量count的访问。但可悲的是，这段代码并不完全正确。
思考：问题是什么？
上一代码的第7行有一个问题点。
如果此时第n-1个线程被中断，然后第n个线程通过互斥锁，则两个线程都会发现count == n，并且两个线程都将发出旋转栅门信号（turnstile.signal()）。 实际上，甚至可能所有线程都会发送旋转栅门信号（执行turnstile.signal()）。
类似地，在第18行，多个线程可能会等待，这将导致死锁。
思考：解决问题。
这一次修复了先前的错误，但仍存在一个微妙的问题。
在这两种情况下，检查（判断count计数）都在互斥锁内部，这样在更改计数器之后和检查之前线程不能被中断。
可悲的是，这段代码仍然不正确。 请记住，此屏障代码块可能位于循环内。 因此，在执行最后一行之后，每个线程将返回到rendezvous。
思考：识别并解决问题。
正如目前所写，这段代码允许一个早熟的线程通过第二个互斥锁，然后循环并通过第一个互斥锁和旋转栅门，有效地超过其他线程一圈。
为了解决这个问题，我们可以使用两个旋转栅门。
最初第一个被锁定，第二个被打开。当所有线程到达第一个时，我们锁定第二个并解锁第一个。当所有线程到达第二个时，我们重新锁定第一个，这使得线程可以安全地循环到开头，然后打开第二个。
此解决方案有时被称为两阶段屏障（two-phase barrier），因为它强制所有线程等待两次：一次是所有线程到达，另一次是所有线程执行临界区。
不幸的是，这种解决方案是大多数不平凡的(non-trivial)同步代码的典型解决方案：很难确定解决方案是否正确。通常有一种微妙的方式，通过程序的特定路径可能会导致错误。
更糟糕的是，针对解决方案的实现的测试并没有多大帮助。错误可能很少发生，因为导致错误的特定路径可能需要非常不幸的情况组合。通过常规手段几乎不可能再现和调试这些错误。
唯一的选择是仔细检查代码并“证明”它是正确的。我把“证明”放在引号中，因为我不是说要你必须写一个正式的证据（虽然有狂热者鼓励这种疯狂的做法）。
我想到的那种证据更加非正式。我们可以利用代码的结构和开发的习语来推断并演示关于该程序的一些中间层的声明。
例如：
通过找到正确的语句来推断和证明，你有时可以找到一种简洁的方式来说服自己（或持怀疑态度的同事）你的代码是经得起考验的。
旋转栅门的一个好处是，它是一个多功能组件，可以用于各种解决方案。 但是一个缺点是它迫使线程顺序执行，这可能导致更多的不必要的上下文切换。
在可重复使用的屏障解决方案中，如果解锁旋转栅门的线程预先加载旋转栅门，并且有足够的信号让正确数量的线程通过，就可以简化解决方案。【感谢Matt Tesch提供此解决方案！】
我在这里使用的语法假定signal函数可以用特定的信号数量作为参数。 这是一个非标准功能，但很容易使用循环来实现。 唯一要记住的是多个信号不是原子的; 也就是说，发送信号的线程可能在循环中被中断。 但在这种情况下，这不是问题。
当第n个线程到达时，它用一个信号为每个线程预加载第一个旋转栅门。当第n个线程通过旋转栅门时，它“取最后一个令牌”并再次锁定旋转栅门。
同样的事情发生在第二个旋转栅门，当最后一个线程通过互斥锁mutex时它被解锁。
将屏障(Barrier)封装在对象中是很自然的。 我将借用Python语法来定义一个类：
__init__方法在我们创建一个新的Barrier对象时运行，并初始化变量实例。 参数n是在Barrier打开之前必须调用wait()的线程数。
变量self指的是正在操作的对象。 由于每个Barrier对象都有自己的互斥锁和旋转栅门，因此self.mutex指的是当前对象的特定互斥锁。
这是一个创建Barrier对象并等待它的示例：
Barrier接口
另外，也可以分别调用Barrier的phase1和phase2函数，并在它们之间处理其他需要完成的事情。
信号量也可用于表示队列。在这种情况下，初始值为0，并且通常编写代码以确保不会发出信号，除非有线程在等待。因此信号量的值永远不会为正数。
例如，假设线程代表舞厅舞者，并且有两种舞者：领舞（leaders）和伴舞（followers），在进入舞池之前排队等候。 当领舞到达时，它会检查是否有伴舞在等待。如果是，他们就都可以进去。 否则就要等待。
类似地，当伴舞到达时，它会检查是否有领舞，相应地，选择继续或等待。
思考： 为强制执行这些约束的领舞和伴舞编写代码。
以下是我在解决方案中使用的变量：
队列提示
leaderQueue是领导者（领舞）等待的队列，followerQueue是追随者（伴舞）等待的队列。
这是领导者（leaders）的代码：
这是追随者（followers）的代码：
这个解决方案就像它得到的一样简单; 它只是一个集合点。 每个leader只发出一个follower的信号，每个follower发出一个leader的信号，由此保证leader和follower成对出发。但他们是否真的成对出发并不清楚。在执行dance()之前，可以积累任意数量的线程，因此可以让任意数量的leader在任何follower之前跳舞【译者注：就是说可能会有N个领舞已经开始跳舞，但却没有一个伴舞的。】。 根据舞蹈dance的语义，这种行为可能有问题，也可能没有问题。
为了使事情变得更有趣，让我们添加额外的约束条件，每个leader只能与一个follower同时调用dance()，反之亦然。换句话说，你必须和带你的那个人一起跳舞【仙妮亚·唐恩演唱的抒情歌曲 】。
思考： 为这个“独占队列”问题写一个解决方案。
以下是我在解决方案中使用的变量：
leaders和followers是计数器，记录每种等待的舞者的数量。 mutex保证对计数器的独占访问。
leaderQueue和followerQueue是舞者等待的队列。 rendezvous用于检查两个线程是否已完成跳舞。
下面是leaders的代码：
当领导者leader到达时，它会获得保护leaders和followers变量的互斥体mutex。 如果有追随者follower在等待，领导者会减少followers计数，给追随者发送信号，然后在释放互斥锁mutex之前调用dance()。 这保证了只有一个追随者线程同时运行dance()。
如果没有追随者在等待，领导者必须在等待leaderQueue之前释放互斥锁。
追随者followers的代码类似：
当追随者到达时，它会检查等待的领导者。 如果有一个，那么追随者会减少领导者计数leaders，向领导者发出信号并执行dance，而不释放互斥体mutex。 实际上，在这种情况下，追随者永远不会释放互斥锁; 而领导者会。 我们不必跟踪哪个线程具有互斥锁，因为我们知道其中有一个有，并且其中任何一个都可以释放它。 在我的解决方案中，它始终是领导者。
当一个信号量被用作队列时【用作队列的信号量与条件变量非常相似。 主要区别在于线程必须在等待之前显式释放互斥锁，并在之后显式重新获取它（但仅在它们需要时才重新获取）。】，我发现这样很有用：将“等待”看作“等待这个队列”，“发送信号”看作“让这个队列中有人离开”。
在这段代码中，除非有人在等待，否则我们永远不会发出队列信号，因此队列信号量的值很少是正数。 但是有可能。 看看你是否能弄明白。
