Java语言中非阻塞算法的实现

摘要：在多线程的程序中很重要的是要保证数据的同步和安全。为了保证线程间的协调和数据安全，不同线程访问相同数据需要实行互斥。如果强制实行互斥，即一个线程使用数据时就锁定该数据，则不同线程可能会频繁地把自己阻塞起来，等共享资源被释放时再恢复。非阻塞算法即无等待且无锁定的算法。我们可以使用Java的原子变量类来开发非阻塞算法程序。该类可以实现对数据进行原子性的读、写和修改操作，不同线程在不锁定数据的情况下也能安全地共享变量。

关键词：非阻塞算法；并发；原子变量

中图法分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）20-0224-02

Realization of Nonblocking Algorithms in Java

ZHU Yun

（College of Information Mechanical and Electrical Engineering， Shanghai Normal University， Shanghai 200234， China）

Abstract： Multi-threads programs should promise the synchronization and security of data. We usually lock a data for a thread while other threads have to block waiting for the data. The traditional synchronization technique may be expensive if the lock is heavily contended. In the realization of lock-free concurrent algorithms， we use atomic variables， which provide atomic read-modify-write operations for safely updating shared variables without locks.

Key words： nonblocking algorithms；concurrency； atomic variables

1 背景

在多线程构造的应用程序中，如果只是把工作分割在多个线程中，希望能够高效率的使用硬件，其实是无法实现高效率的。因为多数线程需要共享一些数据，当一个线程工作时，其他线程都在等待同步的数据。要确保线程大部分时间都在工作，这给多线程程序设计带来更高的要求。

1.1 同步的计数器类

图1的代码实现了一个计数器类。该类保存了一个值，在多线程的程序中，要保持该值在各线程中的同步。

图1 计数器类代码

代码中对计数值v的获取、增加和减少的操作都使用了synchronized关键字来同步。get（）、inc（）和dec（） 操作都是使用当前值，并写出新值。这是传统的Java同步方式。当一个线程进入synchronized定义的方法操作v值，则其他线程要进入该同步方法需要先阻塞等待。我们可以把这些操作看成是原子的读、修改和写操作，即同步方法中的各项操作在进行时不能被其他线程打断，一个方法可被视为一项完整的操作。

1.2 锁定的优缺点

我们可以通过锁定资源在多线程中协调共享资源的使用。通过同步，保证一个线程独占一些变量的访问权，而其他线程在最终获得变量访问权时可以看到之前线程对变量所做的修改，如此有效地保护数据的一致性和安全。

但这种方案有它的缺点。那些被阻塞来等待的线程，它们无法进行其他任何操作，导致硬件资源浪费，更糟糕是带来死锁的风险。另外，频繁地获得和等待资源将呈现争用的状态，线程频繁运行和阻塞给程序带来额外的开销。最后，如果阻塞了高优先级的线程，可能造成低优先级的线程优先运行而高优先级的线程被阻塞的情况。

2 非阻塞算法

无等待且无锁定算法，也称为非阻塞算法。一个算法在其他线程发生延迟和失败时都能够继续运行，或者每个线程能在有限步骤中正确计算自己的操作，这样的算法称为无等待算法。而无锁定算法只是要求仅某个线程总是执行其操作。

非阻塞算法虽然实现起来更为复杂，但具有如下优点：不阻塞高优先级的线程，没有线程因争用资源频繁地阻塞和运行，避免死锁，帮助降低运行成本提高程序效率。

3 非阻塞算法在Java中的实现

3.1 原子变量类

JDK 5.0之后，java.util.concurrent.atomic包中提供了原子变量类AtomicXXX，分别有对应不同数据类型的原子变量类。这些类支持原子条件的比较并设置更新。在把原子变量更新为新值时能够观察其他线程对原子变量的修改，如果其他线程在本次更新完成之前就对变量做了修改，那么本次更新尝试失败，可以继续下一次尝试。虽然原子变量类完成的更新功能与前文所述的同步计数器类例子类似，但原子变量的操作最终是转成硬件原语来实现的。使用原子变量类可以减少对共享资源的竞争操作，从而提高了程序的吞吐量。

3.2 非阻塞计数器

我们使用原子变量类来实现简单的非阻塞算法NonblockingCounter类（代码如图2）。

图2 非阻塞计数器代码

这是一个使用 AtomicInteger类的计数器。其中AtomicInteger类的compareAndSet（）方法负责将参数变量更新为新值。这个方法在完成操作时能观察参数变量，如果更新完成前其他线程修改了它的值，那么更新就失败。这一过程实际是依靠硬件原语来实现的。程序把compareAndSet（）方法放在循环条件中，即本次比较更新操作失败，就进入下一次尝试。这样完成了非阻塞的计数器，不需要使用锁定。

3.3 非阻塞堆栈

原子变量类也可以用来构造复杂一些的程序，如图3程序中的ConcurrentStack类。堆栈类需要压入或弹出节点，这个操作也需要在多线程程序中成为原子操作。

图3 非阻塞堆栈代码

使用AtomicReference< >类建立对堆栈节点的引用。push（）方法获得当前的头节点head，构建一个新节点安装在头节点之前，并更新head指向新的头节点。如果头节点在初始观察之后没有变化，那么就完成入栈操作；如果另一个线程已经修改了堆栈，那么过程就会重新开始。pop（）方法在弹出节点完成新的head头节点引用时，也使用compareAndSet方法来观察原来的头节点，如没有被其他线程修改说明堆栈结构未变化，则完成此次出栈过程，将head指向新的头节点，方法返回弹出的节点。

4 结束语

文中通过例子说明了使用Java提供的原子变量类在开发非阻塞算法方面的应用。这些原子变量类比较并更新的操作由硬件原语来实现，一边观察其他线程对变量的修改一边完成更新。使用原子变量类开发非阻塞算法，不通过锁定派生线程，能开发出具有更好吞吐率，更能防御死锁和优先级倒置分发生的并发程序。

参考文献：

[1] Brian Goetz .Java theory and practice： Going atomic[EB/OL].

http：//www.ibm.com/developerworks/java/library/j-jtp11234/.

[2] Brian Goetz .Java theory and practice： Introduction to nonblocking algorithms[EB/OL].http：//www.ibm.com/developerworks/java/library/j-jtp04186/.

[3] 朱贇. 小议同步和原子变量类[J]. 福建电脑， 2010， 26（6）.

[3] 陈国君. Java程序设计基础[M]. 4版.北京： 清华大学出版社， 2013.

[4] Robert Lafore. Java数据结构和算法[M]. 计晓云， 译. 2版. 北京： 中国电力出版社， 2004.