就性格而言，人可以分为乐天派和悲观派。对于乐天派来说，他们总是会把事情往好的方面想。他们认为所有事情都不太容易出现问题，出错是小概率的，因此可以大胆地做事。如果真的不幸遇到了问题，则努力解决问题。而对于悲观派来说，他们总是担惊受怕，认为出错是一种常态，所以无论大小事情都考虑得面面俱到，确保万无一失。

对于并发控制而言，锁是一种悲观的策略。它总是假设每一次的临界区操作都会产生冲突，因此必须对每次操作都小心翼翼。如果多个线程同时需要访问临界区资源，则宁可牺牲性能让线程进行等待，所以说锁会阻塞线程执行。而无锁是一种乐观的策略，它会假设对资源的访问是没有冲突的。既然没有冲突，自然不需要等待，所以所有的线程都可以在不停顿的状态下持续执行。那遇到冲突怎么办呢？无锁的策略使用一种叫作比较交换(CAS, Compare And Swap)的技术来鉴别线程冲突，一旦检测到冲突产生，就重试当前操作直到没有冲突为止。

1、与众不同的并发策略：比较交换

与锁相比，使用比较交换会使程序看起来更加复杂一些，但由于其非阻塞性，它对死锁问题天生免疫，并且线程间的相互影响也远远比基于锁的方式要小。更为重要的是，使用无锁的方式完全没有锁竞争带来的系统开销，也没有线程间频繁调度带来的开销，因此，它要比基于锁的方式拥有更优越的性能。

CAS(V, E, N)包含三个参数，其中V表示要更新的变量，E表示预期值，N表示新值。仅当V值等于E值时，才会将V值设为N，如果V值和E值不同，说明已经有其他线程做了更新，则当前线程什么都不做。最后，CAS操作返回当前V的真实值。CAS操作是抱着乐观的态度进行的，它总是认为自己可以成功完成操作。当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败。失败的线程不会被挂起，仅被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作。基于这样的原理，CAS操作即使没有锁，也可以发现其他线程对当前线程的干扰，并进行恰当的处理。

简单地说，CAS操作需要你额外给出一个期望值，也就是你认为这个变量现在应该是什么样子的。如果变量不是你想象的那样，则说明它已经被别人修改过了，此时你需要重新读取，再次尝试修改。

在硬件层面，大部分的现代处理器都已经支持原子化的CAS操作。在JDK 5以后，虚拟机便可以使用这种操作来实现并发操作和并发数据结构，并且这种操作在虚拟机中可以说是无处不在的。

2、无锁的线程安全整数：AtomicInteger

为了让Java程序员能够受益于CAS等CPU指令，JDK并发包中有一个atomic包，里面实现了一些直接使用CAS操作的线程安全的类型。

其中，最常用的一个类就是AtomicInteger，可以把它看作一个整数。与Integer不同，它是可变的，并且是线程安全的。对其进行修改等任何操作都是通过CAS操作实现的。这里简单列举一下AtomicInteger的主要方法，对于其他原子类，操作也是非常类似的。

就内部实现来说，AtomicInteger中保存了一个核心字段：

它就代表了AtomicInteger的当前实际取值。此外还有一个：

它保存着value字段在AtomicInteger对象中的偏移量。后面你会看到，这个偏移量是实现AtomicInteger的关键。

AtomicInteger的使用非常简单，这里给出一个示例：

第6行的AtomicInteger.incrementAndGet()方法会使用CAS操作自增1，同时会返回当前值（这里忽略了当前值）。执行这段代码，你会看到程序输出了100000。这说明程序正常执行，没有错误。如果不是线程安全的，那么i的值应该会小于100000。

使用AtomicInteger会比使用锁具有更好的性能。由于篇幅限制，这里不再给出AtomicInteger和锁性能对比的测试代码，大家自己写一段简单的代码测试两者的性能应该不是难事。这里我们关注一下incrementAndGet()方法的内部实现：

其中getIntVolatile()方法非常简单，就是返回内部数据value。

让人印象深刻的应该是getIntVolatile()方法的第8行的while循环吧！如果你是初次看到这样的代码，可能会觉得很奇怪，为什么连设置一个值那么简单的操作都需要一个死循环呢？原因就是：CAS操作未必是成功的，对于不成功的情况，我们就需要不断地进行尝试。第9行的getIntVolatile()方法取得当前值，接着加delta后更新value。这里，我们就得到了CAS操作必需的两个参数：期望值及新值。使用weakCompareAndSetInt()方法将新值v+delta写入，成功的条件是在写入的时刻，当前的值等于刚刚取得的v。如果不满足这样的条件，则说明AtomicInteger的值在第8行到第10行代码之间又被其他线程修改了，当前线程看到的状态就是一个过期状态，因此，weakCompareAndSetInt()方法返回失败，需要不断重试，直到成功。

以上就是CAS操作的基本思想，无论程序多么复杂，其基本原理总是不变的。

和AtomicInteger类似的类还有：AtomicLong表示long型数据；AtomicBoolean表示boolean型数据；AtomicReference表示对象引用。

3、Java中的指针：Unsafe类

如果你对技术有追求，应该还会特别在意incrementAndGet()方法中的U.getAndAddInt()。这里的U是什么呢？它正是本节的主题Unsafe类。从名字上看，这个类封装了一些不安全的操作。什么操作是不安全的呢？学习过C或者C++的人应该知道，指针是不安全的，这也是在Java中把指针去除的重要原因。如果指针指错了位置，或者计算指针偏移量时出错，结果可能是灾难性的，很有可能会覆盖别人的内存，导致系统崩溃。

Unsafe类封装了一些类似指针的操作，比如，它提供的一些函数可以根据偏移量获得或者设置对应位置上的数据。

比如，weakCompareAndSetInt()方法的实现如下：

这里的compareAndSetInt()方法是一个native方法，它的几个参数含义如下：

第一个参数o为给定的对象，offset为对象内的偏移量（其实就是一个字段到对象头部的偏移量，通过这个偏移量可以快速定位字段），expected表示期望值，x表示要设置的值。如果指定的字段的值等于expected，那么就把它设置为x。

不难看出，compareAndSetInt()方法内部必然是使用CAS原子指令来完成的。此外，Unsafe类还提供了一些方法，主要有以下几种（以int类型数据操作为例，其他类型数据操作是类似的）：

可以看到，虽然Java抛弃了指针，但是在关键时刻，类似指针的技术还是必不可少的。这里底层的Unsafe类实现就是最好的例子。但是很不幸，JDK的开发人员并不希望大家使用这个类。获得Unsafe类实例的方法是调动其工厂方法getUnsafe()，但是它的实现却是这样的：

注意加粗部分的代码，它会检查调用getUnsafe()方法的类，如果这个类的ClassLoader不为null，就直接抛出异常，拒绝工作。这也使得我们自己的应用程序无法直接使用Unsafe类。它是一个在JDK内部使用的专属类。

注意：根据Java类加载器的工作原理，应用程序的类由App Loader加载。而系统核心类，如rt.jar中的类由Bootstrap类加载器加载。Bootstrap类加载器没有Java对象的对象，因此试图获得这个类加载器会返回null。所以，当一个类的类加载器为null时，说明它是由Bootstrap类加载器加载的，而这个类也极有可能是rt.jar中的类。

4、无锁的对象引用：AtomicReference

AtomicReference和AtomicInteger非常类似，不同之处就在于AtomicInteger是对整数的封装，而AtomicReference则对应普通的对象引用。也就是它可以保证你在修改对象引用时的线程安全性。在介绍AtomicReference的同时，我希望同时提出一个有关原子操作的逻辑上的不足。

之前说过，线程判断被修改的对象是否可以正确写入的条件是对象的当前值和期望值是否一致，这个逻辑从一般意义上来说是正确的。但有可能出现一个小小的例外，就是当你获得对象当前的数据后，在准备将其修改为新值前，对象的值被其他线程连续修改了两次，而经过这两次修改后，对象的值又恢复为旧值。这样，当前线程就无法正确判断这个对象是否被修改过，下图显示了这种情况：

一般来说，出现这种情况的概率很小，即使发生了，可能也不是什么大问题。比如，我们只是简单地要做一个数值加法，即使在取得期望值后，这个数字被不断地修改，只要它最终被改回了我的期望值，我的加法计算就不会出错。也就是说，当你修改的对象没有过程的状态信息时，所有的信息都只保存于对象的数值本身。

但是，在现实中还可能存在另外一种场景，就是我们是否能修改对象的值，不仅取决于当前值，还和对象的过程变化有关，这时AtomicReference就无能为力了。

打一个比方，有一家蛋糕店，为了挽留客户，决定为贵宾卡里余额小于20元的客户一次性赠送20元，刺激客户充值和消费，但条件是，每一位客户只能被赠送一次。

现在，我们就来模拟这个场景，在这里使用AtomicReference实现这个功能。首先，我们模拟客户账户余额。

定义客户账户余额如下：

接着，我们需要若干个后台线程，它们不断扫描数据，并为满足条件的客户充值：

上述代码第8行，判断账户余额并给予赠送金额。如果已经被其他用户处理，那么当前线程就会失败。因此，可以确保用户只会被充值一次。

如果在赠予金额到账的同时，客户进行了一次消费，使得余额又小于20元，并且正好累计消费了20元使得消费、赠予后的余额等于消费、赠予前的余额，那么后台的赠予进程就会误以为这个账户还没有被赠予，所以，存在被多次赠予的可能。以下代码模拟了这个消费线程：

在上述代码中，只要贵宾卡里的余额大于10元，就会立即进行一次10元的消费。执行上述程序，得到的输出如下：

从输出中可以看到，这个账户被先后反复多次充值。其原因正是账户余额被反复修改，修改后的值等于原有的数值，使得CAS操作无法正确判断当前数据的状态。

虽然这种情况出现的概率不大，但是依然是有可能出现的。当业务上确实可能出现这种情况时，我们必须多加防范。JDK已经为我们考虑到了这种情况，使用AtomicStampedReference就可以很好地解决这个问题。

5、带有时间戳的对象引用：AtomicStampedReference

AtomicReference无法解决上述问题的根本原因是，对象在修改过程中丢失了状态信息，对象值本身与状态被画上了等号。因此，我们只要能够记录对象在修改过程中的状态值，就可以很好地解决对象被反复修改导致线程无法正确判断对象状态的问题。

AtomicStampedReference正是这么做的。它内部不仅维护了对象值，还维护了一个时间戳（我这里把它称为时间戳，实际上它可以使用任何一个整数来表示状态值）。当AtomicStampedReference对应的数值被修改时，除更新数据本身外，还必须更新时间戳。当AtomicStampedReference设置对象值时，对象值及时间戳都必须满足期望值，写入才会成功。因此，即使对象值被反复读写，写回原值，只要时间戳发生变化，就能防止不恰当地写入。

AtomicStampedReference的几个API在AtomicReference的基础上新增了有关时间戳的信息：

有了AtomicStampedReference这个法宝，我们再也不用担心对象被写坏啦！现在，我们使用AtomicStampedReference来修正贵宾卡充值的问题：


在第2行中，我们使用AtomicStampedReference代替原来的AtomicReference。第6行获得账户的时间戳，后续的赠予操作以这个时间戳为依据。如果赠予成功（第13行），则修改时间戳，使得系统不可能发生二次赠予的情况。消费线程也是类似的，每次操作都使时间戳加1（第36行），使之不可能重复。

执行上述代码，可以得到如下输出：

可以看到，账户只被赠予了一次。

6、数组也能无锁：AtomicIntegerArray

除提供基本数据类型外，JDK还为我们准备了数组等复合结构。当前可用的原子数组有：AtomicIntegerArray、AtomicLongArray和AtomicReferenceArray，分别表示整数数组、long型数组和普通的对象数组。

这里以AtomicIntegerArray为例，展示原子数组的使用方式。

AtomicIntegerArray本质上是对int[]类型的封装，使用Unsafe类通过CAS方式保障int[]在多线程下的安全性。它提供了以下几个核心API：

下面给出一个简单的示例，展示AtomicIntegerArray的使用方法：

上述代码第2行声明了一个内含10个元素的数组。第3行定义的线程对数组内10个元素进行累加操作，每个元素各加1000次。第11行，开启了10个这样的线程。因此，可以预测，如果线程安全，则数组内10个元素的值必然都是10000；如果线程不安全，则部分或者全部数值会小于10000。

程序的输出结果如下：

这说明AtomicIntegerArray确实合理地保证了数组的线程安全性。

7、让普通变量也享受原子操作：AtomicIntegerFieldUpdater

有时候，由于初期考虑不周，或者后期的需求变化，一些普通变量可能也会有线程安全的需求。如果改动不大，则可以简单地修改程序中每一个使用或者读取这个变量的地方。显然，这并不符合软件设计中的一条重要原则——开闭原则。也就是系统对功能的增加应该是开放的，而对修改应该是相对保守的。而且，如果系统里用到这个变量的地方特别多，一个一个修改也是一件令人厌烦的事情（况且在很多使用场景下变量可能是只读的，并无线程安全的强烈要求，完全可以保持原样）。

如果你有这种困扰，根本不需要担心，因为在原子包里还有一个实用的工具类AtomicIntegerFieldUpdater。它可以让你在不改动（或者极少改动）原有代码的基础上，让普通的变量也享受CAS操作带来的线程安全性，这样你可以通过修改极少的代码来保证线程安全。这听起来是不是让人很激动呢？

根据数据类型不同，Updater有三种，分别是AtomicIntegerFieldUpdater、AtomicLong-FieldUpdater和AtomicReferenceFieldUpdater。顾名思义，它们分别可以对int类型数据、long类型数据和普通对象进行CAS修改。

现在来思考这么一个场景：假设某地要进行一次选举，如果选民投了候选人一票，就记为1，否则记为0，最终的选票显然就是所有数据的简单求和。下面用代码模拟这个场景：

上述代码中，候选人的得票数量记录在Candidate.score中。注意，它是一个普通的volatile变量，而volatile变量并不是线程安全的。第6～7行定义了AtomicIntegerFieldUpdater实例，用来对Candidate.score进行写入。后续的allScore用来检查AtomicIntegerFieldUpdater的正确性。如果AtomicIntegerFieldUpdater真的保证了线程安全，那么最终Candidate.score和allScore的值必然是相等的。否则，就说明AtomicIntegerFieldUpdater根本没有确保线程安全写入。第12～21行模拟了计票过程，这里假设有大约60%的人投赞成票，并且投票是随机的。第17行使用Updater修改Candidate.score（这里应该是线程安全的），第18行使用AtomicInteger计数，作为参考基准。

运行这段程序，不难发现，最终的Candidate.score总是和allScore绝对相等。这说明AtomicIntegerFieldUpdater很好地保证了Candidate.score的线程安全性。

虽然AtomicIntegerFieldUpdater很好用，但是有几个注意事项：

• 第一，Updater只能修改它可见范围内的变量，因为Updater使用反射得到这个变量。如果变量不可见，就会出错。比如score声明为private的，就是不可行的。
• 第二，为了确保变量被正确的读取，它必须是volatile类型的。如果我们原有代码中未声明这个类型，那么简单地声明一下就行，这不会引起什么问题。
• 第三，由于CAS操作会通过对象实例中的偏移量直接赋值，因此，它不支持static字段（Unsafe.objectFieldOffset()方法不支持静态变量）。

通过AtomicIntegerFieldUpdater，我们可以更加随心所欲地对系统关键数据进行线程安全保护。

8、挑战无锁算法：无锁的Vector实现

我们已经比较完整地介绍了有关无锁的概念和使用方法。相对于有锁的方法，使用无锁的方式编程更加考验一个程序员的耐心和智力。无锁带来的好处是显而易见的：第一，在高并发的情况下，它比有锁的程序拥有更好的性能；第二，它天生就是死锁免疫的。就凭借这两个优势，就值得我们冒险尝试使用无锁并发。

这里向大家介绍一种使用无锁方式实现的Vector。通过这个案例，我们可以更加深刻地认识无锁的算法，同时可以学习一下有关Vector实现的细节和算法技巧（本例讲述的无锁Vector来自amino并发包）。

我们将这个无锁的Vector称为LockFreeVector。它的特点是可以根据需求动态扩展其内部空间。在这里，我们使用二维数组来表示LockFreeVector的内部存储。

变量buckets存放所有的内部元素。从定义上看，它是一个保存着数组的数组，也就是通常所说的二维数组。特别之处在于，这些数组都是使用CAS的原子数组。为什么使用二维数组去实现一个一维的Vector呢？这是为了将来Vector进行动态扩展时可以更加方便。我们知道，AtomicReferenceArray内部使用Object[]来存储数据，这使得动态空间增加特别麻烦，因此使用二维数组的好处就是将来可以方便地增加新的元素。

此外，为了更有序地读写数组，可以定义一个Descriptor的元素，它的作用是使用CAS操作写入新数据：

上述代码第4行定义的Descriptor构造函数接收两个参数，第一个表示整个Vector的长度，第二个为一个writer。最终，写入数据是通过writer实现的（通过completeWrite()方法）。

第24行WriteDescriptor的构造函数接收四个参数：第一个参数addr表示要修改的原子数组，第二个参数为要写入的数组索引位置，第三个参数oldV为期望值，第四个参数newV为需要写入的值。

在构造LockFreeVector时，显然需要对buckets和descriptor进行初始化：

在这里N_BUCKET为30，也就是说这个buckets里面一共可以存放30个数组（由于数组无法动态增长，因此数组总数也就不能超过30）。并且将第一个数组的大小FIRST_BUCKET_SIZE设为8。到这里，大家可能会有一个疑问，如果每个数组有8个元素，一共30个数组，那么岂不是一共只能存放240个元素吗？

如果大家了解JDK内的Vector实现，应该知道，Vector在扩容时，在默认情况下，每次都会将总容量翻倍。因此，这里也借鉴类似的思想，每次扩容，新的数组的大小为原来的两倍（即每次扩容都启用一个新的数组），因此，第一个数组的大小为8，第二个就是16，第三个就是32，以此类推。
这个数值已经超过了2^33，即它在80亿以上。因此，可以满足一般的应用需求。当有元素需要加入LockFreeVector时，会使用一个名为push_back()的方法，将元素压入Vector的最后一个位置。这个操作显然就是LockFreeVector最核心的方法，也是最能体现CAS使用特点的方法，它的实现如下：

可以看到，方法主体部分是一个do-while循环，用来不断尝试对descriptor的设置，也就是通过CAS操作保证descriptor的一致性和安全性。第23行使用descriptor将数据真正地写入数组中。这个descriptor写入的数据由第20～21行构造的WriteDescriptor决定。

在循环最开始（第5行），使用descriptor先将数据写入数组，是为了防止上一个线程设置完descriptor后（第22行），还没来得及执行第23行的写入，相当于做一次预防性操作。

因为限制要将元素e压入Vector，所以我们必须首先知道这个e应该放在哪个位置。由于目前使用了二维数组，我们自然需要知道e所在的数组（buckets中的下标位置）和数组中的下标。

第8～10行通过当前Vector的大小(desc.size)，计算新的元素应该落入哪个数组。这里使用了位运算进行计算。也许你会觉得这几行代码看起来有些奇怪，我的解释如下：LockFreeVector每次都会成倍地扩容，它的第一个数组长度为8，第二个是16，第三个是32，以此类推。它们的二进制表示如下：

它们之和就是LockFreeVector的总大小，因此，如果每一个数组都恰好被填满，那么总大小应该是类似这样的数值（以4个数组填满为例）：

导致这个数字进位的条件，就是至少加上二进制的1000，而这个数字正好是8（FIRST_BUCKET_SIZE就是8），这就是第8行代码的意义。它可以使得数组大小发生一次二进制的进位（如果不进位说明还在第一个数组中），进位后前导零的数量就会发生变化。而元素所在的数组，和pos（第8行定义的变量）前导零数量直接相关，每进行一次数组扩容，它的前导零数量就会减1。如果从来没有扩容过，那么它的前导零就是28个，以后逐级减1个，这就是第9行获得pos前导零数量的原因。第10行通过pos前导零数量可以立即定位使用哪个数组（也就是得到了bucketInd的值）。

第11行，判断这个数组是否存在。如果不存在，则创建数组，大小为前一个数组的两倍，并把它设置到buckets中。

再看一下元素没有恰好填满的情况：

那么总大小就是：

总个数加上二进制数1000后，得到：

显然，通过前导零数量可以定位到第4个数组。而剩余位，显然就表示元素在当前数组内的偏移量（也就是数组下标）。根据这个理论，我们就可以通过pos计算这个元素应该放在给定数组的哪个位置。通过第19行代码，获得pos的除第一位数字1以外的其他位的数值。因此，pos的前导零可以表示元素所在的数组，而pos的后面几位，则表示元素在这个数组中的位置。由此，第19行代码就取得了元素的所在位置idx。

到此，我们就已经得到新元素位置的全部信息，剩下的就是将这些信息传递给descriptor，让它在给定的位置把元素e安置上去即可。这里通过CAS操作保证写入的正确性。

下面来看一下get()方法的实现：

在get()方法的实现中，第3～6行使用了相同的算法获得所需元素的数组，以及数组中的索引下标。这里通过buckets定位到对应的元素即可。

对于Vector来说两个重要的方法就讲完了，其他方法非常类似，这里就不再详细讨论了。

9、　让线程之间互相帮助：细看SynchronousQueue的实现

在对线程池的介绍中，提到了一个非常特殊的等待队列SynchronousQueue。SynchronousQueue的容量为0，任何一个对SynchronousQueue的写操作都需要等待一个对SynchronousQueue的读操作，反之亦然。因此，与其说SynchronousQueue是一个队列，不如说它是一个数据交换通道。那么SynchronousQueue的奇妙功能是如何实现的呢？

SynchronousQueue和无锁操作脱离不了关系，实际上SynchronousQueue内部也大量使用了无锁工具。

对SynchronousQueue来说，它将put()和take()两种功能截然不同的方法抽象为一个共同的方法Transferer.transfer()。从字面上看，这就是数据传递的意思。它的完整签名如下：

当参数e为非空时，表示当前操作传递给一个消费者，如果为空，则表示当前操作需要请求一个数据。timed参数决定是否存在timeout时间，nanos决定了timeout的时长。如果返回值非空，则表示数据已经被接收或者正常提供；如果为空，则表示失败（超时或者中断）。

SynchronousQueue内部会维护一个线程等待队列。等待队列中会保存等待线程及相关数据的信息。比如，生产者将数据放入SynchronousQueue时，如果没有消费者接收，那么数据本身和线程对象都会打包在队列中等待（因为SynchronousQueue容积为0，没有数据可以正常放入）。

Transferer.transfer()方法的实现是SynchronousQueue的核心，它大体上分为三个步骤。

• (1)如果等待队列为空，或者队列中节点的类型和本次操作是一致的，那么将当前操作压入队列进行等待。比如，等待队列中是读线程等待，本次操作也是读，因此这两个读都需要等待。进入等待队列的线程可能会被挂起，它们会等待一个“匹配”操作。
• (2)如果等待队列中的元素和本次操作是互补的（比如等待操作是读，而本次操作是写），那么就插入一个“完成”状态节点，并且让它“匹配”到一个等待节点上。接着弹出这两个节点，并且继续执行对应的两个线程。
• (3)如果线程发现等待队列的节点就是“完成”节点，那么帮助这个节点完成任务，其流程和步骤(2)是一致的。

步骤(1)的实现如下：

在上述代码中，第1行SNode表示等待队列中的节点。内部封装了当前线程、next节点、匹配节点、数据内容等信息。第2行，判断当前等待队列为空，或者队列中元素的模式与本次操作相同（比如，如果都是读操作，那么都必须要等待）。第8行，生成一个新的节点并置于队列头部，这个节点就代表当前线程。如果入队成功，则执行第9行的awaitFulfill()方法。该方法会进行自旋等待，并最终挂起当前线程。直到一个与之对应的操作产生，将其唤醒。线程被唤醒后（表示已经读取到数据或者自己产生的数据已经被别的线程读取），在第14～15行尝试帮助对应的线程完成两个头部节点的出队操作（这仅仅是友情帮助），并在最后返回读取或者写入的数据（第16行）。

步骤(2)的实现如下：

在上述代码中，首先判断头部节点是否处于fulfill状态。如果是，则需要进入步骤(3)。否则，将视自己为对应的fulfill线程。第4行生成一个SNode元素，设置为fulfill模式并将其压入队列头部。接着，设置m（原始的队列头部）为s的匹配节点（第13行），tryMatch()方法将会激活一个等待线程，并将m传递给那个线程。如果设置成功，则表示数据投递完成，将s和m两个节点弹出即可（第14行）。如果tryMatch()方法失败，则表示已经有其他线程帮助完成了操作，那么删除m节点即可（第17行），因为这个节点的数据已经被投递，不需要再次处理，再次跳转到第5行的循环体，进行下一个等待线程的匹配和数据投递，直到队列中没有等待线程为止。

步骤(3)的实现如下，如果在执行线程时，发现头部节点恰好处于fulfill状态，它就会帮助fulfill节点尽快执行：

上述代码的执行原理和步骤(2)完全一致。唯一的不同是步骤(3)不会返回，因为步骤(3)所进行的工作是帮助其他线程尽快投递它们的数据，而自己并没有完成对应的操作。因此，线程进入步骤(3)后，再次进入大循环体（代码中没有给出），从步骤(1)开始重新判断条件和投递数据。

从整个数据投递的过程中可以看到，在SynchronousQueue中，参与工作的所有线程不仅仅是竞争资源的关系，更重要的是，它们彼此之间还会互相帮助。在一个线程内部，可能会帮助其他线程完成它们的工作。这种模式可以减小饥饿出现的概率，提高系统整体的并行度。

10、有关死锁的问题

在众多的应用程序中，使用锁的情况一般要多于无锁。因为对于应用来说，如果业务逻辑很复杂，会极大增加无锁的编程难度。但如果使用锁，我们就不得不对一个新的问题引起重视——死锁。

什么是死锁呢？通俗地说，死锁就是两个或者多个线程相互占用对方需要的资源，导致彼此之间相互等待对方释放资源，产生了无限制等待的现象。死锁一旦发生，如果没有外力介入，这种等待将永远存在，从而对程序产生严重的影响。

用来描述死锁问题的一个有名的场景是哲学家就餐问题，如下图所示：

哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆桌旁，做以下两件事情之一：吃饭和思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只叉子。因为用一只叉子很难吃到意大利面，所以假设哲学家必须用两只叉子吃东西。他们只能使用自己左右手边的那两只叉子。哲学家就餐问题有时也用米饭和筷子而不是意大利面和叉子来描述，因为很明显，吃米饭必须用两只筷子。

哲学家从来不交谈，这就很危险，可能产生死锁。每个哲学家都拿着左边的叉子，永远都在等右边的叉子（或者相反）。

最简单的情况就是只有两个哲学家，假设是A和B，桌面也只有两个叉子。A左手拿着其中一只叉子，B也一样。这样他们的右手都会等待对方的叉子，并且这种等待会一直持续，程序出现这种情况时就会永远无法正常执行。

下面用一个简单的例子来模拟这个过程：


上述代码模拟了两个哲学家互相等待对方的叉子的情景。哲学家A先占用叉子1，哲学家B占用叉子2，接着他们就相互等待，都没有办法同时获得两只叉子进而用餐。

在实际环境中，遇到了这种情况，通常的表现就是相关的进程不再工作，并且CPU占用率为0（因为死锁的线程不占用CPU）。不过这种表面现象只能用来猜测问题，如果想要确认问题，还需要使用JDK提供的一套专业工具。

首先，我们可以使用jps命令得到Java进程的进程ID，接着使用jstack命令得到线程的线程堆栈：


上面显示了jstack的部分输出。可以看到，哲学家A和哲学家B两个线程发生了死锁。并且可以看到两者相互等待的锁的ID。同时，死锁的两个线程均处于BLOCK状态。

如果想避免死锁，除使用无锁的函数之外，还有一种有效的做法是使用重入锁，通过重入锁的中断或者限时等待可以有效规避死锁带来的问题。