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

程序员文章站 2022-05-09 12:14:07

...

文本通过实例比较了各种基于锁的并发算法和无锁并发算法的性能：系 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 ）技术;