基于锁的并发算法 vs 无锁的并发算法

文本通过实例比较了各种基于锁的并发算法和无锁并发算法的性能：系 http://mechanical-sympathy.blogspot.com/2013/08/lock-based-vs-lock-free-concurrent.html  文翻译

 

      上周在由Heinz Kabutz通过JCrete 组织的开放空间会议(unconference)上，我参加一个新的java规范 JSR166 StampedLock的审查会议。StampedLock 是为了解决多个readers 并发访问共享状态时，系统出现的地址竞争问题。在设计上通过使用乐观的读操作，StampedLock 比ReentrantReadWriteLock 更加高效；

 

      在会议期间，我突然意思到两点：第一、我想是时候该去回顾java中锁的实现的现状；第二、虽然StampedLock 看上去是JDK很好的补充，但是它视乎忽略了一个事实，即在多个reader的场景里，无锁的算法通常是更好的解决方案。

 测试：

      为了比较不同的实现方式，我需要采用一种不偏向任意一方的API测试用例。 比如：API必须不产生垃圾、并且允许方法是原子性的。一个简单的测试用例是设计一个可在两维空间中移动其位置的太空船，它位置的坐标可以原子性的读取；每一次事物里至少需要读写2个域，这使得并发变得非常有趣；

  

/**
 * 并发接口，表示太空船可以在2维的空间中移动位置;并且同时更新读取位置
 */
public interface Spaceship
{
    /**
     *  读取太空船的位置到参数数组 coordinates 中
     *
     * @param coordinates 保存读取到的XY坐标.
     * @return 当前的状态
     */
    int readPosition(final int[] coordinates);
 
    /**
     *  通过增加XY的值表示移动太空船的位置。
     *
     * @param xDelta x坐标轴上移动的增量.
     * @param yDelta y坐标轴上移动的增量.
     * @return the number of attempts made to write the new coordinates.
     */
    int move(final int xDelta, final int yDelta);
}

 

      上面的API通过分解一个不变的位置对象，本身是干净的 。但是我想保证它不产生垃圾，并且需要能最直接的更新多个内容域。这个API可以很容易地扩展到三维空间，并实现原子性要求。

 

      为每一个飞船都设置多个实现，并且作为一个测试套件。本文中所有的代码和结果都可以在这里找到。

 

      该测试套件会依次运行每一种实现.并且使用 megamorphic dispatch模式，防止并发访问中的方法内联(inlining)，锁粗化(lock-coarsening)，循环展开( loop unrolling)的问题;

 

       每种实现都执行下面4个不同的线程的情况，结果也是不同的;

      1 reader - 1 writer

      2 readers - 1 writer

      3 readers - 1 writer

      2 readers - 2 writers

 

      所有的测试运行在64位机器、Java版本：1.7.0_25、 Linux版本：3.6.30、4核 2.2GHz Ivy Bridge （第三代Core i系列处理器）i7-3632QM的环境上。

 

      测试吞吐量的时候，是通过每一种实现都重复测试超过5次，每一次都运行5秒以上，以保证系统足够预热，下面的结果都是第5次之后平均每秒吞吐量。为了更像一个典型的java应用;没有采用会导致明显减少差异的线程依附性（thread affinity）和多核隔离（core isolation ）技术;

结果：

 

 

 

 

      上述图表的原始数据可以在这里找到

分析：

      结果里面真正令我吃惊的是ReentrantReadWriteLock的性能，我没有想到的是，在这样的场景下它在读和少量写之间取得的巨大的平衡性，

 

      我主要的收获：

      1、StampedLock 对现存的锁实现有巨大的改进，特别是在读线程越来越多的场景下：

      2、StampedLock有一个复杂的API，对于加锁操作，很容易误用其他方法;

      3、当只有2个竞争者的时候，Synchronised是一个很好的通用的锁实现;

      4、当线程增长能够预估，ReentrantLock是一个很好的通用的锁实现;

      5、选择使用ReentrantReadWriteLock时，必须经过小心的适度的测试 ;所有重大的决定，必须在基于测试数据的基础上做决定;

      6、无锁的实现比基于锁的算法有更好短吞吐量;

 

结论：

      非常开心能看到无锁技术对基于锁的算法的影响; 乐观锁的策略，实际上就是一个无锁算法技术。

      以我的经验看，教学和开发中的无锁算法，不仅能显著改善吞吐量;同时他们也提供更低的延迟。