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

tomorrowwu 发布于2019-08-14 11:40 / 2469人阅读

摘要：测试吞吐量的时候，是通过每一种实现都重复测试超过次，每一次都运行秒以上，以保证系统足够预热，下面的结果都是第次之后平均每秒吞吐量。以我的经验看，教学和开发中的无锁算法，不仅能显著改善吞吐量同时他们也提供更低的延迟。

上周在由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的性能，我没有想到的是，在这样的场景下它在读和少量写之间取得的巨大的平衡性，

我主要的收获：

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

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

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

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

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

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

结论：

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

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

原文 Lock based vs lock free concurrent
翻译曹姚君校对方腾飞
via ifeve

GPU云服务器云服务器服务器并发测试算法高并发无锁锁的优化被锁的表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64054.html

【实战Java高并发程序设计6】挑战无锁算法

摘要：在本例中，讲述的无锁来自于并发包我们将这个无锁的称为。在这里，我们使用二维数组来表示的内部存储，如下变量存放所有的内部元素。为什么使用二维数组去实现一个一维的呢这是为了将来进行动态扩展时可以更加方便。我们已经比较完整得介绍了有关无锁的概念和使用方法。相对于有锁的方法，使用无锁的方式编程更加考验一个程序员的耐心和智力。但是，无锁带来的好处也是显而易见的，第一，在高并发的情况下，它比有锁...

zengdongbao 2019-08-14 15:26 评论0 收藏0
Java多线程学习（七）并发编程中一些问题

摘要：因为多线程竞争锁时会引起上下文切换。减少线程的使用。举个例子如果说服务器的带宽只有，某个资源的下载速度是，系统启动个线程下载该资源并不会导致下载速度编程，所以在并发编程时，需要考虑这些资源的限制。最近私下做一项目，一bug几日未解决，总惶恐。一日顿悟，bug不可怕，怕的是项目不存在bug,与其惧怕，何不与其刚正面。系列文章传送门: Java多线程学习（一）Java多线程入门 Jav...

yimo 2019-08-15 15:20 评论0 收藏0
Java多线程学习（七）并发编程中一些问题

摘要：相比与其他操作系统包括其他类系统有很多的优点，其中有一项就是，其上下文切换和模式切换的时间消耗非常少。因为多线程竞争锁时会引起上下文切换。减少线程的使用。很多编程语言中都有协程。所以如何避免死锁的产生，在我们使用并发编程时至关重要。系列文章传送门: Java多线程学习（一）Java多线程入门 Java多线程学习（二）synchronized关键字（1） java多线程学习（二）syn...

dingding199389 2019-08-15 15:30 评论0 收藏0
不可不说的Java“锁”事

摘要：本文旨在对锁相关源码本文中的源码来自使用场景进行举例，为读者介绍主流锁的知识点，以及不同的锁的适用场景。中，关键字和的实现类都是悲观锁。自适应意味着自旋的时间次数不再固定，而是由前一次在同一个锁上的自旋时间及锁的拥有者的状态来决定。前言 Java提供了种类丰富的锁，每种锁因其特性的不同，在适当的场景下能够展现出非常高的效率。本文旨在对锁相关源码（本文中的源码来自JDK 8）、使用场景...

galaxy_robot 2019-08-16 13:43 评论0 收藏0