第2章
并发模式初探
在前一章中，我们讨论了竞争问题。其实，在现实生活中也充满着竞争（下面的例子是假设的）。鉴于目前发达的通信技术，人们在日常生活中很少会错过约会。但是，假如没有这些技术，让我们看看又会怎么样。假设今天是星期五，我准备下班回家，然后计划去吃晚饭和看电影。我打电话给我的妻子和女儿，让他们提前到达电影院。然而，在开车回家的路上，我遇上了周五晚上的交通高峰而被堵在路上。由于我未及时赶到，我的妻子决定带着女儿去散步，并去拜访一位住在附近的朋友，和他聊天叙旧。
与此同时，我到达了电影院，停好车并立刻走进电影院。然而，我却没看到我的妻女，所以决定去附近的餐馆找她们。当我在餐馆寻找她们时，她们来到了电影院，却没有发现我在那里。所以，她决定去停车场看看。
这种情况可能会一直持续下去，最终我们可能错过周五的电影和晚餐。但是，由于有了手机，我们可以轻松地同步我们的行程，在电影院及时相遇。
在本章中，我们将研究线程的上下文，理解这个概念对于理解Java的并发工作方式至关重要。我们首先研究单例设计模式（singleton design pattern）和共享状态问题。但在此之前，我们先来看一些背景信息。
https://github.com/PacktPublishing/Concurrent-Patterns-and-Best-Practices 提供完整的代码文件。
2.1 线程及其上下文
正如我们在第1章中所看到的，进程是线程的容器。进程具有可执行代码和全局数据，所有线程与同一进程的其他线程共享这些东西。如图2-1所示，二进制可执行代码是只读的，它可以由线程*共享，因为不存在任何可变性。
但是，全局数据是可变的，如图2-1所示，这正是并发错误的根源！我们将在本书中研究的大多数技术和模式都是为了避免此类错误。
同一进程的线程同时运行，在只有一组寄存器的情况下，这是如何实现的？答案是“线程上下文”，此上下文有助于使线程运行时信息始终独立于另一个线程，线程上下文包含寄存器集和堆栈。
图2-1显示线程上下文的各个部分。
当调度程序抢占正在运行的线程时，它会备份线程上下文，也就是说，它会保存CPU寄存器和堆栈的内容。接下来，它选择另一个可运行的线程并加载其上下文，这意味着它会将线程寄存器的内容还原为与上次一样（它的堆栈也会还原为与上次一样，依此类推），然后继续执行线程。
那么可执行二进制代码呢？运行相同代码的进程可以共享同一块代码，因为代码在运行时不会更改。（例如，共享库的代码在进程间共享。）
图2-2是一些简单的规则，用于理解由各种变量表示的状态的线程安全方面。
如图2-2所示，final变量和局部变量（包括函数参数）始终是线程安全的，你不需要任何锁来保护它们。final变量是不可变的（即只读），因此不存在多个线程同时更改值的问题。
final变量在可见性方面也享有特殊地位，稍后我们将详细介绍这意味着什么。可变静态实例变量是不安全的，如果它们不受保护，我们可以轻松创建竞争条件。
2.2 竞争条件
我们先来研究一些并发错误。下面是一个递增计数器的简单示例：
这个代码不是线程安全的，如果两个正在运行的线程并发地使用同一对象，则每个线程获取的计数器值序列基本上是不可预测的，原因是“++counter”操作，这个看起来很简单的语句实际上由三个不同的操作组成：读取新值、修改新值并保存新值。
如图2-3所示，线程的执行是相互不知道的，因此会在不知情的情况下发生干预，从而造成丢失更新。
以下代码说明单例设计模式（singleton design pattern）。从时间和内存方面来看，创建LazyInitialization实例是很昂贵的，所以，我们接管对象创建。想法是将创建延迟到第一次使用时，然后只创建一个实例并重用它：
当我们想要接管实例创建时，一个常见的设计技巧是使构造函数私有化，从而迫使客户端代码使用我们的public修饰的工厂方法getInstance()。
单例模式和工厂方法模式是著名的“四人组”（GOF）一书中众多创造性设计模式中的两种。这些模式有助于我们强制进行设计决策，例如，在这里确保我们只有一个类实例。对单例的需求非常普遍，单例的典型示例是日志记录服务，线程池也表示为单例（我们将在下一章中介绍线程池）。在树形数据结构中，单例作为哨兵节点，用来表示终端节点。一个树可以有数千个节点来保存各种数据项，但是，终端节点没有任何数据（根据定义），因此终端节点的两个实例完全相同。通过将终端节点设置为单例，可以利用此性质，从而节省大量的内存。在遍历树时，编写条件语句来检查是否命中了哨兵节点是很简单的：只需比较哨兵节点的引用。有关更多信息，请参阅https://sourcemaking.com/design_patterns/null_ object 。Scala的None是一个null对象。
在第一次调用getter方法时，我们创建并返回新实例。对于后续调用，将返回相同的实例，从而避免昂贵的构造过程，如图2-4所示。
为什么我们需要将实例变量声明为volatile？因为这时编译器能优化我们的代码。例如，编译器可以选择将变量存储在寄存器中，当另一个线程初始化实例变量时，第一个线程可能有一个旧副本，如图2-5所示。
通过一个关键字volatile可以解决这个问题。在写入之后，实例引用始终使用内存屏障（Store Barrier）保持最新，并在读取之前使用加载屏障（Load Barrier）。内存屏障使所有CPU（以及在它们上执行的线程）都知道状态的更改，如图2-6所示。
同样，加载屏障（Load Barrier）让所有CPU能读到最新值，从而避免过时状态问题。有关更多信息，请参阅https://dzone.com/articles/memory-barriers-fences 。
该代码中存在竞争条件。两个线程都检查条件，但有时，第一个线程尚未完成对象的初始化。（请记住，初始化对象比较昂贵，这也是我们要先完成这些烦琐手续的原因。）与此同时，第二个线程被调度，获取引用并开始使用它，也就是说，它开始使用部分构造的实例，这将是一个bug。
这个“部分构造的实例”是如何实现的？JVM可以重新排列指令，所以实际结果不会改变，但性能会提高。
当正在执行LazyInitialization()表达式时，它可以首先分配内存，并将已分配内存的位置引用返回给实例变量，然后启动对象的初始化。由于引用是在构造函数已经有机会执行之前返回的，所以它会产生一个其引用不为空的对象，然而，构造函数还没有完成。
由于执行了部分初始化的对象，可能会导致一些神秘的异常，并且它们很难重现！让我们看看图2-7所示的情况。
诸如此类的竞争条件基本上是不可预测的，线程的调度时间取决于外部因素。大多数情况下，代码将按预期工作，然而，偶尔也会出现问题。那么，如前所述，我们应该如何调试呢？
调试器将无济于事，我们需要确保竞争不会因设计而发生。接下来，让我们进入监视器模式学习。
2.2.1 监视器模式
我们之前看到的递增计数器的操作包括以下步骤：
这些步骤应该是原子的，即不可分割，要么线程执行所有这些操作，要么一个都不执行。监视器模式的作用是使这样的操作序列原子化，Java通过其synchronized关键字来提供监视器：
如代码所示，现在，计数器代码是线程安全的。每个Java对象都有一个内置锁，也称为内部锁（intrinsic lock）。进入同步块（synchronized block）的线程将获取此锁，锁一直保持到块执行为止。当线程退出方法时（因为它执行完成或由于异常），锁被释放，如图2-8所示。
同步块是可重入的：持有锁的同一线程可以再次进入块，否则，如图2-8所示，将导致死锁。这种情况下，线程本身不会往下推进，因为它在等待锁（由它自己在第一位持有锁）被释放，显然，其他线程将被锁定，从而使系统停止运行。
2.2.2 线程安全性、正确性和不变性
不变性是了解代码正确性的一个好工具。例如，对于单链表，我们可以说最多有一个非空节点的next指针为空，如图2-9所示。
在图2-9中，第一部分显示带不变性的单链表。我们想在最后一个值为19的节点之前，添加一个值为15的节点。当插入算法在调整指针链的过程中，第二部分显示它已将节点c的next指针设置为null之前的状态。
无论是顺序的单线程模型还是多线程模型，都应该保持代码不变性。
显式同步使得违反不变性的系统状态可能暴露，对于该链表示例，我们必须同步数据结构的所有状态，以确保始终保持不变性。
假设有一个size()方法计算列表节点数。当第一个线程位于第二个快照（处于插入节点过程中间）时，如果另一个线程访问第二个快照并调用size()，我们就会遇到一个讨厌的错误。只是在偶然情况下，size()方法会返回4，而不是预期的5，那可调试性如何呢？
2.2.2.1 顺序一致性
另一个了解并发对象的工具是顺序一致性（Sequential Consistency），请考虑如图2-10所示的执行流程。
如图2-10所示，我们通过假设x的值为1来阅读和理解代码，同时计算p的赋值。我们从顶部开始，向下进行，它是如此直观，明显是正确的。
左侧执行过程是顺序一致的，因为我们在评估后面的步骤时看到了先前步骤的结果。
然而，Java内存模型在后台不是按这种方式工作。虽然对我们隐藏了，但是其实并不是线性的，因为代码针对性能进行了优化。然而，运行时间可以确保满足我们的期望，在单线程世界中一切都很好。
当我们引入线程时，事情并不那么乐观。如图2-10的右侧所示，在计算p时，无法保证线程T2能读取x变量的正确的最新值。
锁定机制（或volatile）保证了正确的可见性语义。
2.2.2.2 可见性和final字段
众所周知，final字段是不可变的，一旦在构造函数中初始化，之后就无法更改。final字段对其他线程是可见的，我们不需要任何机制，如锁定或volatile来实现这一点，如图2-11所示。
如图2-11所示，两个线程共享fv静态字段，a字段声明为final，并在构造函数中初始化为值9。在extractVal()方法中，a的正确值对其他线程可见。
然而，b字段却没有这样的保证。因为它被声明时，修饰符既不是final字段，也不是volatile，并且没有锁定，我们不能明确b的值，其他线程同样如此。
但是有一个问题，final字段不应该从构造函数中泄漏。
如图2-12所示，在构造函数执行完成之前，this引用被泄露给someOther
ServiceObj的构造函数。可能有另一个线程同时使用someOtherServiceObj，这样就会间接使用FinalVisibility类实例。
由于FinalVisibility构造函数尚未完成，因此final字段a的值对于其他线程是不可见的，从而出现海森堡bug。
有关更多信息和有关从构造函数中泄漏引用的讨论，请参阅http://www.javapractices.com/topic/TopicAction.do?Id=252。
2.2.3 双重检查锁定
我们可以使用“内在锁”编写单例的线程安全版本。
请看这里：
由于该方法是同步的，因此任何时候只有一个线程可以执行它。如果多个线程多次调用getInstance()，该方法很快就会成为瓶颈。其他竞争访问此方法的线程将阻塞等待锁，并且在此期间将无法执行任何有效的操作，系统的活力将受到影响，这个瓶颈会对系统的并发性产生不利影响。
这促成双重检查锁定模式技术的开发，如下面的代码片段所示：
这是一种机智的想法：锁可确保安全地创建实际实例。由于volatile关键字，其他线程要么得到空值，要么得到更新的实例值。如图2-13所示，代码仍然是不完整的。
我们暂停一下来研究代码。第一次检查后有一个时间窗口，在这里可以进行上下文切换，另一个线程有机会进入同步块，我们在这里同步一个锁变量：“类锁”。第二次检查是同步的，并且只由一个线程执行，假设它是null。然后，拥有锁的线程向前推进，并创建实例。
一旦它退出块并继续执行，其他线程将依次访问锁。它们应该发现实例已被完全构造，因此它们使用完全构造的对象，我们要做的是安全地发布共享的实例变量。
2.2.3.1 安全发布
当一个线程创建一个共享对象时（如本例所示），其他线程也想使用它。“安全发布”这个术语是指创建者线程将对象作为已可供其他线程使用的状态进行发布。
问题是，只是用volatile修饰该实例变量并不能保证其他线程看到一个完全构造的对象。volatile适用于实例引用发布本身，但如果指称对象（在本例中为LazyInitialization对象）包含可变成员，则不适用。在这种情况下，我们可以得到部分初始化的变量，如图2-14所示。
当LazyInitialization构造函数退出时，所有final字段都被保证对访问它们的其他线程可见。有关final关键字与安全发布之间关系的更多信息，请参阅https://www.javamex.com/tutorials/synchronization_final.shtml 。
使用volatile关键字并不能保证可变对象的安全发布。你可以在这里找到关于这个问题的讨论：
https://wiki.sei.cmu.edu/confluence/display/java/CON50J.+Do+not+assume+that+ declaring+a+reference+volatile+guarantees+safe+publication+of+the+members+of+ the+referenced+object 。
接下来我们将学习一个设计模式，它简化了实例的延迟创建，而不需要所有这些复杂性。
2.2.3.2 初始化Demand Holder模式
我们似乎陷入了困境。一方面，我们不想为不必要的同步付出代价；另一方面，双重检查锁定是断开的，可能会发布一个部分构造的对象。
以下代码段显示了延迟加载的单例。生成的代码很简单，不依赖于细微的同步语义，相反，它利用了JVM的类加载语义：
getInstance()方法使用静态类LazyInitializationHolder，当首次调用getIn-stance()方法时，JVM将加载这个静态类。
现在，Java语言规范（JLS）确保类初始化阶段是按顺序的。所有后续的并发执行都将返回相同且被正确被初始化的实例，而且无须任何同步。
该模式利用了这个功能，以完全避免任何锁定，并且仍然实现了正确的“懒惰”初始化语义。
单例模式经常被批评，因为它表现为全局状态。但是，正如我们所看到的，有时我们仍然需要它们的功能，并且这种模式是一个很好的可重用解决方案，也就是说，它是一个并发设计模式。
你还可以使用枚举来创建单例，有关此设计技术的更多信息，请参阅https://dzone.com/articles/java-singletons-using-enum 。
2.2.4 显式锁定
synchronized关键字是一种内部锁机制，它非常方便，但也有一些限制。例如，我们不能中断等待内部锁的线程，在获取锁时也决不允许超时等待。
有一些用例需要这些功能，在这种情况下，我们使用显式锁。Lock接口允许我们克服这些限制，如图2-15所示。
ReentrantLock具备synchronized关键字的功能。已经持有它的线程可以再次获取它，就像使用同步语义一样。在这两种情况下，内存可见性和互斥保证都是相同的。
此外，ReentrantLock为我们提供了非阻塞tryLock()和可中断锁定。
我们承担使用ReentrantLock的责任，即使是例外情况，我们也需要确保通过所有返回路径释放锁定。
这种显式锁让我们可以控制锁的粒度，在这里，我们可以看到一个使用排序链表实现的并发集合数据结构的示例：
其中，该并发集合持有一个节点链表（节点类型是Node），它的定义如下：
Node类表示链表的一个节点类型，下面是构造函数：
图2-16显示构造函数执行完成后的状态。
如图2-16所示，默认构造函数初始化一个空的集合，这是一个由两个节点组成的链表。头节点始终保持最小值（Integer.MIN_VALUE），最后一个节点包含最大值（Integer.MAX_VALUE）。使用这样的哨兵节点是一种常见的算法设计技术，它简化了其余的代码，如下所示：
ConcurrentSet也有一个名为lck的字段，它被初始化为ReentrantLock。下面是我们的add方法：
add(int)方法从获取锁开始。由于列表是一个集合，因此所有元素都是唯一的，并且元素按升序存储。
接下来是lookUp(int)方法：
lookUp(int)方法搜索集合，如果找到参数元素，则返回true，否则返回false。最后，下面是remove(int)方法，它调整下一个指针，以便删除包含该元素的节点：
问题是我们正在使用粗粒度同步：我们持有全局锁。如果集合中包含大量元素，则一次只能有一个线程执行添加、删除或查找。执行基本上是顺序的，如图2-17所示。
同步显然是正确的，代码更容易理解。但是，由于它是粗粒度的，如果许多线程争夺锁，它们最终会等待锁。原本可以用来做有成效工作的时间却花在等待上，所以说锁是瓶颈。
2.2.4.1 手拉手模式
上一节中解释的粗粒度同步会损害并发性，因此我们可以不锁定整个列表，而是将前一个节点和当前节点都锁定来加以改进。如果线程在遍历列表时这样做（称为手拉手锁定），则允许其他线程同时处理列表，如下所示：
注意，我们讨论的是锁定节点，而这需要删除我们的全局锁，并且不是在节点本身中创建锁字段。为了提高代码的可读性，我们提供了两个原语：lock()和unlock()，如图2-18所示。
为了使用这种模式，我们重写了add(int)方法，如下所示：
与前面一样，我们需要用try或finally来保护锁。因此，在异常的情况下，能够保证释放锁，如图2-19所示。
前面的代码片段解释了各种并发方案。下面是remove(int)方法：
remove(int)方法移除相同行。代码对需要权衡的状况进行了平衡：它尽快解锁，但确保它同时持有prev节点锁和curr节点锁，以消除出现任何竞争条件的可能性：
这段代码是一个测试驱动器，请注意，它是单线程的。通过编写一个多线程的驱动器，并产生两个或更多个共享并发集合的线程，将有助于更好地理解代码。编写的lookUp(int)方法类似于add方法和remove方法，留给读者自己练习。
2.2.4.2 观察后判断这是正确的吗？
为什么这段代码和手拉手模式都有效呢？这里有一些推理可以帮助我们建立对代码的信心。例如，在管理多个锁时，避免死锁是一项挑战。前面的代码是如何帮助我们避免死锁的呢？
假设线程T1调用add()方法，同时线程T2调用remove()。可能出现图2-20中显示的情况吗？
这段代码保证不可能出现死锁情况。我们确保始终从头节点开始按顺序获取锁，因此，图2-20中的锁定顺序不可能发生。
那么如果发生两个并发add(int)调用呢？假设该集合的内容为{9,22,35}，并且T1向集合加入10，同时T2向集合加入25。
如图2-21所示，总是有一个公共节点（因此总是有一个公共锁）需要被两个（或多个）线程获取，因为根据定义，只有一个线程可以获胜，从而迫使其他线程等待。
很难看出我们是如何使用Java的内部锁（synchronized关键字）来实现手拉手模式。显式锁为我们提供了更多控制权，并允许我们轻松地实现该模式。
2.2.5 生产者/消费者模式
在上一章中，我们看到线程需要相互协作才能实现重要功能。当然，协作离不开通信，ReentrantLock允许线程向其他线程发送信号，我们使用这种机制来实现一个并发FIFO队列：
该类在其lck字段中持有可重入锁。当然，它还有两个Condition类型的字段：need-Space和needElem。在这里，我们将看到如何使用它们，队列元素存储在名为items的数组中，如图2-22所示。
head指向要消费的下一个元素，同样，tail指向一个将存储新元素的空槽。构造函数分配一个容量为cap的数组：
这里有一些微妙之处，让我们先理解一下简单的东西。生产者线程尝试将这些条目（items）压入队列，它首先获取lck锁，该方法代码的其余部分在这个锁下执行。tail变量持有下一个槽的索引，我们可以在那里存储新的数字。下面的代码将新元素压入队列：
如果我们已经用完所有数组槽，那么tail将回到0：
count变量表示当前可供消费的元素个数。当我们再生成一个元素时，count会递增。
接下来，让我们看一下并发方面，如图2-23所示。
由于items数组具有有限的容量（它最多可以容纳cap个元素），因此我们需要处理队列已满的情况，此时，生产者需要等待消费者从队列中取得一个或多个元素。
此等待通过调用needSpace条件变量的await()来完成。重要的是要意识到，线程被设置为等待和锁lck被释放，这是两个原子操作。
假设有线程已从队列中消费了一个或多个条目（我们很快就会在pop()方法中看到这是如何做的），此时，生产者线程在获取锁后醒来，获取锁对于让其余代码正常工作是前提条件：
pop方法的工作原理与此类似，除了弹出逻辑外，它是push方法的镜像，如图2-24所示。
消费者线程使用以下代码从队列中弹出一个元素：
head移动到下一个可用元素（如果有）：
请注意，就像tail 变量一样，我们不断回到开头。当可用元素个数减少一个时，count则减1。
虚假和丢失的唤醒
为什么我们需要先获得锁？当然，count变量是生产者和消费者二者共享的状态。
还有一个原因是，我们需要在获取lck锁之后调用await。如https://docs.oracle.com/cd/E19455-01/806-5257/sync-30/index.html 所述，可能会出现图2-25所示的情况。
如图2-25所示，没有被锁定，因此信号丢失；没有线程被唤醒，因此信号丢失。对于正确的信号语义来说，需要锁定await()。
在循环中检查条件也是必需的，换句话说，线程唤醒后，必须重新测试该条件，然后再继续。这是处理“虚拟和丢失的唤醒”所必需的：
如果我们使用if条件，就会有一个潜在的bug。由于arcane平台效率的原因，await()方法可以虚假地返回（没有任何理由）。
在等到某个条件时，通常允许出现虚假唤醒，作为对底层平台语义的让步。这对大多数应用程序几乎没有实际影响，因为循环中应该始终等待一个条件，从而测试正在等待的状态谓词。*地消除虚假唤醒的可能性是可以实现的，但建议应用程序程序员始终假设它们可以发生，因此始终在循环中等待。
上一段话引用自相关Java文档，其链接如下：https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Condition.html 。
图2-26是可能发生的错误情景。
如图2-26所示，如果在一个循环中测试条件，生产者线程总是会醒来、再次检查并继续执行正确的语义。
2.2.6 比较和交换
锁是昂贵的，试图获取锁时被阻塞的线程会被挂起，挂起和恢复线程也是非常昂贵的。作为替代方案，我们可以使用CAS（比较和设置）指令来更新并发计数器。
CAS操作将处理如下项：
- 变量的内存位置（x）
- 变量的期望值（v）
- 需要设置的新值（nv）
CAS操作会自动将x中的值更新为nv，但前提是x中的现有值与v匹配，否则，不采取任何行动。
在这两种情况下，都返回x的现有值。对于每个CAS操作，执行以下三个操作：
1.获得值
2.比较值
3.更新值
所指定的三个操作均作为单个原子机器指令执行。
当多个线程尝试执行CAS操作时，只有一个线程获胜并更新该值，但是，其他线程不会被挂起，CAS操作失败的线程可以重新尝试更新。
CAS的最大的优点是完全避免了上下文切换，如图2-27所示。
如图2-27所示，线程不断循环并试图通过尝试执行CAS操作来获胜。该调用采用当前值和新值，仅在更新成功时返回true。如果其他某个线程赢了，循环就会重复，从而一次又一次地尝试。
CAS更新操作是原子操作，更重要的是它避免了线程的挂起（以及随后的恢复）。在这里，我们使用CAS来实现我们自己的锁，如图2-28所示。
getAndSet()方法尝试设置新值并返回前一个值。因此，如果前一个值为false，并且我们设法将其设置为true（请记住compare和set是原子的），那么我们已经获得锁。
在使用CAS操作的情况下，通过扩展锁接口而不阻塞任何线程来实现锁定！但是，当多个线程争用锁时，会导致更激烈的争用，性能就会下降。
这就是为什么线程运行在内核上的原因。每个内核都有一个缓存，这个缓存会存储锁变量的副本。getAndSet()调用会导致所有内核使锁的缓存副本失效，因此，当我们有更多线程和更多这样的循环锁时，会存在太多不必要的缓存失效，如图2-29所示。
之前的代码通过使用缓存变量b进行循环（也就是说，等待锁定）来提高性能。当b的值变为false（从而意味着解锁）时，while循环中断。现在，执行getAndSet()调用以获取锁。
2.3 本章小结
在这一章中，我们从竞争条件入手，无论是在实际环境中还是在并发代码中，我们看到了同步的必要性。我们还详细了解了竞争条件，并了解了volatile关键字的作用。
接下来，我们研究了表示程序全局状态的单例模式，也了解了如何使用监视器安全地共享状态。我们还纠正了可见性语义，并研究了称为双重检查锁定的优化。
我们研究了一个使用排序链表的并发集合实现的用例，使用锁可能导致粗粒度锁定，虽然语义上是正确的，但此方案只允许单个线程，这可能会损害并发性。
解决方案是使用手拉手设计模式，我们对它进行了深入的研究，了解到显式锁如何为我们提供更好的解决方案，从而既保持正确性，又提高并发性。
最后，我们介绍了生产者/消费者设计模式，我们了解了线程如何使用条件进行通信，我们还讨论了正确使用条件所涉及的微妙之处。
所以，亲爱的读者们，我们在这里已经讲了很多。现在，请看下一章中的更多设计模式。