(转)Java 理论与实践: 非阻塞算法简介
平均分 （共 8 个评分 ）

在不只一个线程访问一个互斥的变量时，所有线程都必须使用同步，否则就可能会发生一些非常糟糕的事情。Java 语言中主要的同步手段就是 synchronized 关键字（也称为内在锁），它强制实行互斥，确保执行 synchronized 块的线程的动作，能够被后来执行受相同锁保护的 synchronized 块的其他线程看到。在使用得当的时候，内在锁可以让程序做到线程安全，但是在使用锁定保护短的代码路径，而且线程频繁地争用锁的时候，锁定可能成为相当繁重的操作。

在 “流行的原子” 一文中，我们研究了原子变量，原子变量提供了原子性的读-写-修改操作，可以在不使用锁的情况下安全地更新共享变量。原子变量的内存语义与 volatile 变量类似，但是因为它们也可以被原子性地修改，所以可以把它们用作不使用锁的并发算法的基础。

如 清单 4 所示，插入一个元素涉及两个指针更新，这两个更新都是通过 CAS 进行的：从队列当前的最后节点（C）链接到新节点，并把尾指针移动到新的最后一个节点—）。如果第一步失败，那么队列的状态不变，插入线程会继续重试，直到成功。一旦操作成功，插入被当成生效，其他线程就可以看到修改。还需要把尾指针移动到新节点的位置上，但是这项工作可以看成是 “清理工作”，因为任何处在这种情况下的线程都可以判断出是否需要这种清理，也知道如何进行清理。

队列总是处于两种状态之一：正常状态（或称静止状态，图 1 和 图 3）或中间状态（图 2）。在插入操作之前和第二个 CAS—）成功之后，队列处在静止状态；在第一个 CAS（C）成功之后，队列处在中间状态。在静止状态时，尾指针指向的链接节点的 next 字段总为 null，而在中间状态时，这个字段为非 null。任何线程通过比较 tail.next 是否为 null，就可以判断出队列的状态，这是让线程可以帮助其他线程 “完成” 操作的关键。

图 2. 处在插入中间状态的队列，在新元素插入之后，尾指针更新之前

插入操作在插入新元素（A）之前，先检查队列是否处在中间状态，如 清单 4 所示。如果是在中间状态，那么肯定有其他线程已经处在元素插入的中途，在步骤（C）和—）之间。不必等候其他线程完成，当前线程就可以 “帮助” 它完成操作，把尾指针向前移动（B）。如果有必要，它还会继续检查尾指针并向前移动指针，直到队列处于静止状态，这时它就可以开始自己的插入了。

第一个 CAS（C）可能因为两个线程竞争访问队列当前的最后一个元素而失败；在这种情况下，没有发生修改，失去 CAS 的线程会重新装入尾指针并再次尝试。如果第二个 CAS—）失败，插入线程不需要重试 —— 因为其他线程已经在步骤（B）中替它完成了这个操作！

图 3. 在尾指针更新后，队列重新处在静止状态

幕后的非阻塞算法

如果深入 JVM 和操作系统，会发现非阻塞算法无处不在。垃圾收集器使用非阻塞算法加快并发和平行的垃圾搜集；调度器使用非阻塞算法有效地调度线程和进程，实现内在锁。在 Mustang（Java 6.0）中，基于锁的 SynchronousQueue 算法被新的非阻塞版本代替。很少有开发人员会直接使用 SynchronousQueue，但是通过 Executors.newCachedThreadPool() 工厂构建的线程池用它作为工作队列。比较缓存线程池性能的对比测试显示，新的非阻塞同步队列实现提供了几乎是当前实现 3 倍的速度。在 Mustang 的后续版本（代码名称为 Dolphin）中，已经规划了进一步的改进。

回页首

结束语

非阻塞算法要比基于锁的算法复杂得多。开发非阻塞算法是相当专业的训练，而且要证明算法的正确也极为困难。但是在 Java 版本之间并发性能上的众多改进来自对非阻塞算法的采用，而且随着并发性能变得越来越重要，可以预见在 Java 平台的未来发行版中，会使用更多的非阻塞算法。

?

参考资料

学习

您可以参阅本文在 developerWorks 全球站点上的 英文原文 。

“流行的原子” （developerWorks，Brian Goetz，2004 年 11 月）：描述了 Java 5.0 中加入的原子变量类，以及比较-交换操作。

“Scalable Synchronous Queues”（ACM SIGPLAN 关于并行编程的原则与实践的讨论会，William N. Scherer III、Doug Lea 和 Michael L. Scott，2006 年 3 月）：描述了 Java 6 中新增的 SynchronousQueue 实现的构建和性能优势。

“Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queues”（Maged M. Michael 和 Michael L. Scott，关于分布式计算原则的讨论会，1996）：详细介绍了本文的 清单 4 中演示的非阻塞链接队列的构建。

Java Concurrency in Practice （Addison-Wesley Professional，Brian Goetz、Tim Peierls、Joshua Bloch、Joseph Bowbeer、David Holmes 和 Doug Lea，2006 年 6 月）：一份用 Java 语言开发并发程序的 how-to 手册，包括构建和编辑线程安全的类和程序，避免生存风险，管理性能和测试并发应用程序。

Java 技术专区：数百篇关于 Java 编程各方面的文章。

获得产品和技术

JDK 5.0 Update 6：得到 JDK 5.0 的最新更新。

讨论

参与论坛讨论。

developerWorks blog：加入 developerWorks 社区。

关于作者

Brian Goetz 作为专业的软件开发人员已经超过 18 年了。他是 Quiotix 的首席顾问，这是家软件开发和咨询公司，位于加州 Los Altos，他还效力于多个 JCP 专家组。Brian 的力作 Java Concurrency In Practice 将于 2006 年初由 Addison-Wesley 出版。请参阅 Brian 在流行的行业出版物上 已经发表和即将发表的文章。

建议

?

原文地址：http://www.ibm.com/developerworks/cn/java/j-jtp04186/