文本通过实例比较了各种基于锁的并发算法和无锁并发算法的性能:系 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、无锁的实现比基于锁的算法有更好短吞吐量;
结论:
非常开心能看到无锁技术对基于锁的算法的影响; 乐观锁的策略,实际上就是一个无锁算法技术。
以我的经验看,教学和开发中的无锁算法,不仅能显著改善吞吐量;同时他们也提供更低的延迟。
相关推荐
多线程并发访问无锁队列的算法研究.pdf 多线程并发访问无锁队列的算法研究.pdf 多线程并发访问无锁队列的算法研究.pdf 多线程并发访问无锁队列的算法研究.pdf 多线程并发访问无锁队列的算法研究.pdf
基于机器学习算法的原发性高血压并发冠心病的患病风险研究.pdf
包括并发的基础理论知识、不同并发模型的选择与适用环境、编写并发程序的基本步骤,并发算法的正确性证明与性能评价,以及在编写并发程序时遵循的一些指导原则等
仿真设计进程 PCB、PCB表的数据结构 :1.1仿真进程并发的调度环境,设计...换、进程并发、进程阻塞和进程调度的算法 1.2 掌握进程调度的优先权法、时间片轮转法和多级反馈队列算法的实现 1.3 强化算法设计和数据结构。
本实验是基于Dijkstra的银行家算法的实现,该算法可用于在操作系统中避免死锁。 该算法的基本思想是:让用户输入进程数与资源类数,并输入每个进程对每类资源的最大需求量,已占用数,以及系统中当前每类资源的可用...
单个MapReduce作业中基于Hadoop并发算法:MRPack是MapReduce实现的一种变体,其中多个相关算法可以在单个MapReduce作业中同时执行。 在MRPack中,所有算法都在Map and Reduce编程模型中实现,然后所有这些算法都在...
介绍基于锁的、乐观的和可推测并发控制协议,并对基于PCC协议代表的2PLPA,基于OCC协议代表的OCCBC和WAIT50及基于SCC协议代表的SCC2S和SCCkS的性能进行了评估。在设定实时数据库模式、工作负荷模式以及...
(5) 按银行家算法为进程分配资源,本次分配是否成功要显示出来(要能处理各种情况:可以满足这次请求、由于资源不够不能满足这次请求、由于可能产生不安全不能满足这次请求、请求不合理拒绝请求等) (6) 作业撤销时要...
基于锁(Lock-Base)的算法实现扩充是相当容易的,但基于锁无关(Lock-Free)实现起来难度较大,下面将使用伪代码介绍基于Lock-Free实现可自适应扩充的环形并发队列算法,并提出了优化方案以使特定环境下能再提高...
2父进程的创建的游标实例无法传递给子进程建议用线程(注意一下用锁防止对游标的争夺,导致数据库数据混乱) 3如果用进程处理并发那么一定不要想着父进程创建IO实例对象传递给子进程!无法传递!!!一定要在每个子进程...
30 python算法代码示例(并发和并行算法 YOLO算法).docx
《基于docker容器的高并发web系统架构设计与实现》随着互联网迅速发展,社交、媒体以及电商等web网站用户数量 越来越大,并发流量也越来越高,这对于传统web系统架构设计提出 新的挑战。本文基于...
大数据-算法-实时事务并发控制算法优化.pdf
基于 K-means 算法的校园微博热点话题发现系统 一、研究目的 微博由其 “短平快 ” 的信息能力和快速传播能力 ,已广泛流行于高校学生的常生活中。但微博上的负面舆情信息给社会 、学校和个人带来巨大的危害 。由于...
操作系统对于并发性和多线程处理在real time各种算法下的代码实现 使用一个pcb 作为dispathcer 来控制全过程 能正确输出各种算法的处理步骤,CPU 使用情况以及最后运算时间
基于GPU多流并发并行模型的NDVI提取算法.pdf
操作系统-多进程并发环境模拟以及低级调度算法的仿真实现程序+实验报告.zip 操作系统-多进程并发环境模拟以及低级调度算法的仿真实现程序+实验报告.zip 操作系统-多进程并发环境模拟以及低级调度算法的仿真实现程序+...
基于多线程并发的多目标个性化推荐算法研究,史晓艳,方伟,为了提高推荐系统挖掘用户喜好和冷门产品的能力,提出一种基于三目标的个性化推荐模型,并设计了MOEA-PGMA算法求解。针对MOEA-PGMA算法
2)掌握银行家算法,了解资源在进程并发执行中的资源分配情况。 3)掌握预防死锁的方法,系统安全状态的基本概念。 设计一个n个并发进程共享m个系统资源的程序以实现银行家算法。要求: 1) 简单的选择界面; 2) 能...
根据银行家算法的思想,编写程序,解决并发进程的死锁问题。 本实验要求设计并实现银行家算法。银行家算法是死锁避免的经典算法,其核心思想是:进程动态地申请资源,每次申请资源时系统都执行安全状态检查算法判断...