十五年前，多处理器系统是高度专业化的系统，耗资数十万美元（其中大多数具有两到四个处理器）。 如今，多处理器系统既便宜又丰富，几乎每个主要的微处理器都内置了对多处理的支持，许多处理器支持数十或数百个处理器。
为了利用多处理器系统的功能，通常使用多个线程来构建应用程序。 但是，正如编写并发应用程序的任何人都可以告诉您的那样，仅将工作分散在多个线程中不足以实现良好的硬件利用率-您必须确保您的线程将大部分时间都花在了实际工作上，而不是等待还有更多工作要做，或者等待共享数据结构上的锁。
几个任务可以以这样的方式来真正的并行，以要求线程之间没有协调。 考虑一个线程池，其中正在执行的任务通常彼此独立。 如果线程池产生了公共工作队列，那么从工作队列中删除元素或向其中添加元素的过程必须是线程安全的，这意味着需要协调对头，尾或节点间链接指针的访问。 而正是这种协调导致了所有麻烦。
协调Java语言中对共享字段的访问的传统方法是使用同步，以确保对共享字段的所有访问都持有适当的锁。 通过同步，可以确保（假设您的类已正确编写）确保拥有保护给定变量集的锁的线程将对这些变量具有独占访问权，并且在其他线程随后获取这些变量时，对这些变量的更改将变为可见锁。 不利的一面是，如果锁竞争激烈（当线程已被另一个线程持有时，线程经常要求获取该锁），则吞吐量可能会受到影响，因为竞争同步可能会非常昂贵。 （公共服务公告：无竞争的同步现在在现代JVM上非常便宜。）
基于锁的算法的另一个问题是，如果持有锁的线程被延迟（由于页面错误，调度延迟或其他意外的延迟），那么任何需要该锁的线程都不会取得进展。
易变变量还可以用于存储共享变量，其成本低于同步存储的成本，但是它们有局限性。 虽然对volatile变量的写入保证可以立即对其他线程可见，但是无法呈现原子操作的read-modify-write操作序列，这意味着，例如，volatile变量不能用于可靠地实现互斥体（互斥锁）或计数器。
考虑开发一个线程安全的计数器类，该类公开get() ， increment()和decrement()操作。 清单1显示了如何使用锁（同步）实现此类的示例。 请注意，所有方法，甚至是get() ，都必须进行同步，以使该类具有线程安全性，以确保不会丢失任何更新，并且所有线程都可以看到该计数器的最新值。
increment()和decrement()操作是原子的读取，修改，写入操作-为了安全地递增计数器，您必须采用当前值，向其添加一个值，然后将新值写出，所有操作都作为一个单独的操作不能被另一个线程中断。 否则，如果两个线程试图同时执行递增操作，那么不幸的操作交错将导致计数器仅递增一次，而不是两次。 （请注意，通过将值实例变量设置为volatile不能可靠地实现此操作。）
原子的读取-修改-写入组合出现在许多并发算法中。 清单2中的代码实现了一个简单的互斥体，并且acquire()方法也是原子的读取-修改-写入操作。 要获取互斥锁，您必须确保没有其他人持有该互斥锁（ curOwner == null ），然后记录您拥有它的事实（ curOwner = Thread.currentThread() ），所有curOwner = Thread.currentThread()都没有另一个线程可以进入中间并修改curOwner field 。
清单1中的计数器类工作可靠，并且在几乎没有竞争或没有竞争的情况下都可以正常工作。 但是，在激烈的争用中，性能将受到严重影响，因为JVM将花费更多的时间来处理调度线程和管理争用以及等待线程的队列，而花费较少的时间来进行实际工作（例如增加计数器）。 您可能还记得上个月专栏中的图表，该图表显示了当多个线程争用内置同步器锁定时，吞吐量如何急剧下降。 该专栏文章介绍了新的ReentrantLock类如何更可扩展地替代同步，但是对于某些问题，还有更好的方法。
使用锁定时，如果一个线程尝试获取另一线程已经持有的锁，则该线程将阻塞，直到该锁可用为止。 这种方法有一些明显的缺点，包括以下事实：线程在等待锁定时被阻塞，但无法执行其他任何操作。 如果阻塞的线程是高优先级任务（这种危险称为优先级倒置 ），则这种情况可能是灾难。
使用锁还有其他一些危险，例如死锁（当以不一致的顺序获取多个锁时可能会发生死锁）。 即使没有这样的危险，锁也只是相对粗粒度的协调机制，因此，对于管理简单的操作（例如增加计数器或更新谁拥有互斥体）来说，锁是相当“重的”。 如果有一个更细粒度的机制可以可靠地管理对单个变量的并发更新，那将是很好的； 在大多数现代处理器上都有。
如前所述，大多数现代处理器都支持多处理。 尽管这种支持当然包括多个处理器共享外围设备和主存储器的能力，但它通常还包括对指令集的增强，以支持多处理的特殊要求。 特别是，几乎每个现代处理器都具有用于更新共享变量的指令，该指令可以检测或阻止其他处理器的并发访问。
支持并发的第一批处理器提供了原子测试和设置操作，这些操作通常只在单个位上进行。 当前的处理器（包括Intel和Sparc处理器）最常用的方法是实现一种称为比较和交换 （CAS）的原语。 （在Intel处理器上，比较和交换是通过cmpxchg指令系列实现的。PowerPC处理器具有一对称为“加载和保留”和“条件存储”的指令，它们可以实现相同的目标；对于MIPS而言，类似，除了第一个称为“负载链接”。）
CAS操作包括三个操作数-内存位置（V），预期的旧值（A）和新的值（B）。 如果该位置的值与预期的旧值匹配，则处理器将自动将该位置更新为新值，否则它将不执行任何操作。 无论哪种情况，它都返回CAS指令之前该位置的值。 （CAS的某些版本会简单地返回CAS是否成功，而不是获取当前值。）CAS有效地表示：“我认为位置V应该具有值A；如果有，则将B放入其中，否则，不要不要改变它，但告诉我现在有什么价值。”
使用CAS进行同步的自然方法是从地址V读取值A，执行多步计算以得出新值B，然后使用CAS将V的值从A更改为B。同时，V处的值未更改。
像CAS这样的指令允许算法执行读-修改-写序列，而不必担心与此同时另一个线程修改变量，因为如果另一个线程确实修改了变量，则CAS会检测到该变量（并失败），并且算法可以重试操作。 清单3展示了CAS操作的行为（但不是性能特征），但是CAS的价值在于它是在硬件中实现的，并且非常轻巧（在大多数处理器上）：
基于CAS的并发算法称为无锁 ，因为线程不必等待锁（有时称为互斥锁或关键部分，具体取决于线程平台的术语）。 CAS操作成功还是失败，但是无论哪种情况，它都可以在可预测的时间内完成。 如果CAS失败，则呼叫者可以重试CAS操作或采取其认为合适的其他措施。 清单4显示了重写计数器类以使用CAS而不是锁定：
如果每个线程都将面对其他线程的任意延迟（甚至失败）而继续取得进展，则该算法被称为无需等待 。 相比之下，无锁算法仅要求某些线程始终取得进展。 （定义免等待时间的另一种方法是，保证每个线程都可以在一定数量的自身步骤中正确地计算其操作，而与其他线程的动作，定时，交织或速度无关。此绑定可能是一个函数（例如，如果十个线程每个执行一次CasCounter.increment()操作，则在最坏的情况下，每个线程最多必须重试九次才能完成增量操作。）
在过去的15年中，对无等待和无锁算法（也称为非阻塞算法 ）进行了大量研究，并且发现了许多常见数据结构的非阻塞算法。 非阻塞算法在操作系统和JVM级别广泛用于诸如线程和进程调度之类的任务。 尽管实现起来较为复杂，但与基于锁的替代方法相比，它们具有许多优点-避免了诸如优先级反转和死锁之类的风险，争用的成本更低，并且协调发生在更精细的粒度级别，从而实现了更高程度的安全性。并行性。
在JDK 5.0之前，如果不使用本机代码，就不可能用Java语言编写无等待，无锁的算法。 在java.util.concurrent.atomic包中添加了原子变量类之后，情况发生了变化。 原子变量类都公开了一个“比较设置”原语（类似于“比较并交换”），该原语是使用平台上可用的最快本机结构（“比较并交换”，“加载链接/存储条件的”或“在最坏的情况下，旋转锁）。 java.util.concurrent.atomic包中提供了9种类型的原子变量（ AtomicInteger ； AtomicLong ； AtomicReference ； AtomicBoolean ；原子整数的数组形式； long；引用；以及原子标记的引用和标记的引用类，它们分别对一对进行原子更新。值）。
可以将原子变量类视为volatile变量的泛化，扩展了易失性变量的概念以支持原子条件条件比较和设置更新。 原子变量的读取和写入与对易失性变量的读取和写入访问具有相同的内存语义。
尽管原子变量类在表面上看起来像清单1中的SynchronizedCounter示例，但相似之处只是表面上的。 在幕后，对原子变量的操作变成了平台提供的并发访问的硬件原语，例如比较和交换。
调整正在争用的并发应用程序的可伸缩性的一种常用技术是减小使用的锁对象的粒度，以希望更多的锁获取将从竞争的竞争变为无竞争的。 从锁定到原子变量的转换达到了相同的目的-通过切换到更细粒度的协调机制，竞争更少的操作，从而提高了吞吐量。
由于CAS基本上在更改V之前会询问“ V的值是否仍为A”，因此基于CAS的算法可能会因从第一次读取V到读取V之间的值从A到B再回到A的值而感到困惑。在V上执行CAS的时间。 在这种情况下，CAS操作将成功，但是在某些情况下，结果可能不是所希望的。 （请注意， 清单1和清单2中的counter和互斥体示例不受此问题的影响，但并非所有算法都可以。）此问题称为ABA问题 ，通常通过将标记或版本号与每个要进行CAS的值，并自动更新值和标记。 AtomicStampedReference类为这种方法提供支持。
java.util.concurrent包中的几乎所有类都直接或间接使用原子变量而不是同步。 诸如ConcurrentLinkedQueue类的类使用原子变量直接实现免等待算法，而诸如ConcurrentHashMap类的类在需要的地方使用ReentrantLock进行锁定。 反过来， ReentrantLock使用原子变量来维护等待锁定的线程队列。
如果没有JDK 5.0中的JVM改进，就无法构建这些类，因为JDK 5.0公开了（访问类库，但没有显示给用户类）访问硬件级同步原语的接口。 原子变量类以及java.util.concurrent中的其他类又将这些功能提供给用户类。
上个月 ，我研究了ReentrantLock类如何提供优于同步性的可伸缩性优点，并构建了一个简单的，竞争激烈的示例基准，该基准使用伪随机数生成器来模拟滚动骰子。 我向您展示了通过同步， ReentrantLock和公平的ReentrantLock进行协调的实现，并给出了结果。 本月，我将在该基准测试中添加另一种实现，该实现使用AtomicLong更新PRNG状态。
清单5显示了使用同步的PRNG实现，以及使用CAS的替代实现。 请注意，CAS必须循环执行，因为它可能在成功之前失败一次或多次，而使用CAS的代码通常都是这种情况。
下面的图1和图2中的图形与上个月显示的图形相似，并为基于原子的方法添加了另一条线。 这些图显示了在8路Ultrasparc3盒和单处理器Pentium 4盒上使用各种线程数生成随机数时的吞吐量（以每秒滚动数为单位）。 测试中的线程数具有欺骗性； 这些线程比一般线程具有更多的争用，因此与更现实的程序相比，它们在更少的线程数量下显示了ReentrantLock和原子变量之间的收支平衡。 您将看到，原子变量相对于ReentrantLock有了进一步的改进，后者在同步方面已经有了很大的优势。 （由于每个工作单元所做的工作很少，因此下面的图形可能低估了与ReentrantLock相比原子变量在可伸缩性方面的优势。）
大多数用户不太可能自己开发使用原子变量的非阻塞算法-他们更有可能使用java.util.concurrent提供的版本，例如ConcurrentLinkedQueue 。 但是，如果您想知道这些类的性能提升来自何处（与以前的JDK中的类似物相比），则使用了通过原子变量类公开的细粒度，硬件级并发原语。
开发人员可以直接将原子变量用作共享计数器，序列号生成器和其他独立共享变量的高性能替代品，否则必须通过同步来保护它们。
JDK 5.0在高性能并发类的开发方面迈出了一大步。 通过在内部公开新的低层协调原语，并提供一组公共原子变量类，现在第一次可以使用Java语言开发免等待，无锁算法。 反过来， java.util.concurrent中的类是基于这些低级原子变量工具构建的，从而使其具有比以前执行类似功能的类显着的可伸缩性优势。 尽管您可能永远不会在类中直接使用原子变量，但是有充分的理由为它们的存在欢呼。
翻译自: https://www.ibm.com/developerworks/java/library/j-jtp11234/index.html
