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

原文链接 作者:Martin Thompson  译者:曹姚君 校对: 方腾飞

上周在由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);
 }
<pre>

上面的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、无锁的实现比基于锁的算法有更好短吞吐量;

结论:

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

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

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 基于锁的并发算法 vs 无锁的并发算法


曹 姚君

花名无叶,阿里巴巴国际事业部资深开发工程师。

Latest posts by 曹 姚君 (see all)

FavoriteLoading添加本文到我的收藏
  • Trackback 关闭
  • 评论 (10)
    • 伽达默尔
    • 2013/10/19 2:38下午

    在现实中,reader就3个的场景,还需要考虑5m跟20m的吞吐量差异?

  1. 很高兴能看到介绍无锁并发算法的文章,忍不住起说两句,我有时跟人提起无锁算法的一些优点时,好多人都不以为然,让人不解的是,有一次在阿里的电话面试中,那人还跟我扯无锁算法的死锁问题,这完全是在用有锁并发的思维来思考问题

      • 伽达默尔
      • 2013/10/23 5:53下午

      无锁算法的死锁问题。。。。。。

      • 是啊,很匪夷所思吧,可他是面试官,我是面试者,我表明观点后,他还坚持己见,我也不好多说什么了,他的逻辑是:有AB两处需要修改,先无锁地修改完A后,再尝试修改B,但同时另一个线程先修改了B,去尝试修改A,然后两个线程就死锁了。这不仍旧是用锁的方式去解决问题么

          • 匿名
          • 2013/12/06 3:51上午

          无锁会有race 情况吧?数据得不到保护不是?

          • 是的

          • lock-free的实现还是会有死锁问题的,这个和你底层用什么没有关系,和具体方法有关。

            只能说正确的lock-free实现不会有死锁

  2. > 但是它视乎忽略了一个事实

    s/视/似/

    • dragon
    • 2014/05/06 5:16下午

    在会议期间,我突然意思到两点:

    改为

    在会议期间,我突然意识到两点:

    • roger.huang
    • 2015/10/10 2:59下午

    周 可人 :
    lock-free的实现还是会有死锁问题的,这个和你底层用什么没有关系,和具体方法有关。
    只能说正确的lock-free实现不会有死锁

    请问你能举个例子来说明无锁实现产生死锁的例子么?

您必须 登陆 后才能发表评论

return top