深入理解 CAS 算法原理已经在jdk中的运用

1、什么是CAS？

CAS：Compare and Swap，即比较再交换。

jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。JDK 5之前Java语言是靠synchronized关键字保证同步的，这是一种独占锁，也是是悲观锁。

2、CAS算法理解

对CAS的理解，CAS是一种无锁算法，CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。

CAS比较与交换的伪代码可以表示为：

do{
       备份旧数据；
       基于旧数据构造新数据；
}while(!CAS( 内存地址，备份的旧数据，新数据 ))

注：t1，t2线程是同时更新同一变量56的值

因为t1和t2线程都同时去访问同一变量56，所以他们会把主内存的值完全拷贝一份到自己的工作内存空间，所以t1和t2线程的预期值都为56。

假设t1在与t2线程竞争中线程t1能去更新变量的值，而其他线程都失败。（失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次发起尝试）。t1线程去更新变量值改为57，然后写到内存中。此时对于t2来说，内存值变为了57，与预期值56不一致，就操作失败了（想改的值不再是原来的值）。

（上图通俗的解释是：CPU去更新一个值，但如果想改的值不再是原来的值，操作就失败，因为很明显，有其它操作先改变了这个值。）

就是指当两者进行比较时，如果相等，则证明共享数据没有被修改，替换成新值，然后继续往下运行；如果不相等，说明共享数据已经被修改，放弃已经所做的操作，然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设，采用了类似于数据库的commit-retry 的模式。当同步冲突出现的机会很少时，这种假设能带来较大的性能提升。

3、CAS开销

前面说过了，CAS（比较并交换）是CPU指令级的操作，只有一步原子操作，所以非常快。而且CAS避免了请求操作系统来裁定锁的问题，不用麻烦操作系统，直接在CPU内部就搞定了。但CAS就没有开销了吗？不！有cache miss的情况。这个问题比较复杂，首先需要了解CPU的硬件体系结构：

上图可以看到一个8核CPU计算机系统，每个CPU有cache（CPU内部的高速缓存，寄存器），管芯内还带有一个互联模块，使管芯内的两个核可以互相通信。在图中央的系统互联模块可以让四个管芯相互通信，并且将管芯与主存连接起来。数据以“缓存线”为单位在系统中传输，“缓存线”对应于内存中一个 2 的幂大小的字节块，大小通常为 32 到 256 字节之间。当 CPU 从内存中读取一个变量到它的寄存器中时，必须首先将包含了该变量的缓存线读取到 CPU 高速缓存。同样地，CPU 将寄存器中的一个值存储到内存时，不仅必须将包含了该值的缓存线读到 CPU 高速缓存，还必须确保没有其他 CPU 拥有该缓存线的拷贝。

比如，如果 CPU0 在对一个变量执行“比较并交换”（CAS）操作，而该变量所在的缓存线在 CPU7 的高速缓存中，就会发生以下经过简化的事件序列：

  • CPU0 检查本地高速缓存，没有找到缓存线。
  • 请求被转发到 CPU0 和 CPU1 的互联模块，检查 CPU1 的本地高速缓存，没有找到缓存线。
  • 请求被转发到系统互联模块，检查其他三个管芯，得知缓存线被 CPU6和 CPU7 所在的管芯持有。
  • 请求被转发到 CPU6 和 CPU7 的互联模块，检查这两个 CPU 的高速缓存，在 CPU7 的高速缓存中找到缓存线。
  • CPU7 将缓存线发送给所属的互联模块，并且刷新自己高速缓存中的缓存线。
  • CPU6 和 CPU7 的互联模块将缓存线发送给系统互联模块。
  • 系统互联模块将缓存线发送给 CPU0 和 CPU1 的互联模块。
  • CPU0 和 CPU1 的互联模块将缓存线发送给 CPU0 的高速缓存。
  • CPU0 现在可以对高速缓存中的变量执行 CAS 操作了

以上是刷新不同CPU缓存的开销。最好情况下的 CAS 操作消耗大概 40 纳秒，超过 60 个时钟周期。这里的“最好情况”是指对某一个变量执行 CAS 操作的 CPU 正好是最后一个操作该变量的CPU，所以对应的缓存线已经在 CPU 的高速缓存中了，类似地，最好情况下的锁操作（一个“round trip 对”包括获取锁和随后的释放锁）消耗超过 60 纳秒，超过 100 个时钟周期。这里的“最好情况”意味着用于表示锁的数据结构已经在获取和释放锁的 CPU 所属的高速缓存中了。锁操作比 CAS 操作更加耗时，是因深入理解并行编程
为锁操作的数据结构中需要两个原子操作。缓存未命中消耗大概 140 纳秒，超过 200 个时钟周期。需要在存储新值时查询变量的旧值的 CAS 操作，消耗大概 300 纳秒，超过 500 个时钟周期。想想这个，在执行一次 CAS 操作的时间里，CPU 可以执行 500 条普通指令。这表明了细粒度锁的局限性。

以下是cache miss cas 和lock的性能对比：

4、CAS算法在JDK中的应用

在原子类变量中，如java.util.concurrent.atomic中的AtomicXXX，都使用了这些底层的JVM支持为数字类型的引用类型提供一种高效的CAS操作，而在java.util.concurrent中的大多数类在实现时都直接或间接的使用了这些原子变量类。

Java 1.7中AtomicInteger.incrementAndGet()的实现源码为：

由此可见，AtomicInteger.incrementAndGet的实现用了乐观锁技术，调用了类sun.misc.Unsafe库里面的 CAS算法，用CPU指令来实现无锁自增。所以，AtomicInteger.incrementAndGet的自增比用synchronized的锁效率倍增。

以上就是深入理解 CAS 算法原理已经在jdk中的运用的详细内容，更多关于CAS 算法原理的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Java多线程之CAS算法实现线程安全

    前言 对于线程安全,我们有说不尽的话题.大多数保证线程安全的方法是添加各种类型锁,使用各种同步机制,用限制对共享的.可变的类变量并发访问的方式来保证线程安全.文本从另一个角度,使用"比较交换算法"(CompareAndSwap)实现同样的需求.我们实现一个简单的"栈",并逐步重构代码来进行讲解. 本文通俗易懂,不会涉及到过多的底层知识,适合初学者阅读(言外之意是各位大神可以绕道了). 旅程开始 1.先定个小目标,实现一个"栈" "栈&q

  • Java CAS底层实现原理实例详解

    Java CAS底层实现原理实例详解

    这篇文章主要介绍了Java CAS底层实现原理实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一.CAS(compareAndSwap)的概念 CAS,全称Compare And Swap(比较与交换),解决多线程并行情况下使用锁造成性能损耗的一种机制. CAS(V, A, B),V为内存地址.A为预期原值,B为新值.如果内存地址的值与预期原值相匹配,那么将该位置值更新为新值.否则,说明已经被其他线程更新,处理器不做任何操作:无论哪种情

  • java使用MulticastSocket实现组播

    组播是一种允许源进程将数据包发送到多个目标进程的网络技术.组播源将数据包发送到特定组播组,只有属于该组播组的进程才能接收到数据包.这些进程可以是在同一个物理网络,也可以来自不同的物理网络(只要有组播路由器支持). 组播分为无连接和面向连接组播,但是基本的组播机制是无连接的,我们这里所讲的也是无连接组播. 我们说过使用MulticastSocket类,这个类叫组播数据报套接字类,主要用来发送和接收IP组播报文.MulticastSocket是DatagramSocket的子类,它增加了加入和离开组

  • Java switch case数据类型原理解析

    这篇文章主要介绍了Java switch case数据类型原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java 中 switch case 语句用来判断一个变量与一系列值中某个值是否相等,每个值称为一个分支. 语法格式如下: switch(expression){ case value : //语句 break; //可选 case value : //语句 break; //可选 //你可以有任意数量的case语句 default

  • java使用MulticastSocket实现基于广播的多人聊天室

    java使用MulticastSocket实现基于广播的多人聊天室

    使用MulticastSocket实现多点广播: (1)DatagramSocket只允许数据报发给指定的目标地址,而MulticastSocket可以将数据报以广播的方式发送到多个客户端. (2)IP协议为多点广播提供了这批特殊的IP地址,这些IP地址的范围是:224.0.0.0至239.255.255.255.. (3)MulticastSocket类时实现多点广播的关键,当MulticastSocket把一个DaragramPocket发送到多点广播的IP地址时,该数据报将会自动广播到加入

  • Java通用BouncyCastle实现的DES3加密的方法

    Java通用BouncyCastle实现的DES3加密的方法

    对于BouncyCastle类库(包)来说,他提供了很多加密算法,在与.net和java进行相互加解密过程中,得到了不错的应用,本文以DES3为例,来说一下DES3加解密的过程. 加密过程 明文字符转为byte数组 对密钥进行处理,处理后一般为16或者24字节 对明文进行DES3加密,生成密文的byte数组 对密文byte数组进行base64的编码 解密过程 对密文byte数组进行base64的解码 对密钥进行处理,处理后一般为16或者24字节 对解码后的byte数组进行DES3解密 对解密之后

  • Java异常ClassCastException的解决

    在说ClassCastException之前,先介绍下引用类型转换: 引用类型转换分为向上转型和向下转型两种: 向上转型:多态本身是子类类型向父类类型向上转换的过程,这个过程是默认的:当父类引用指向一个子类对象时,便是向上转换: 使用格式: 父类类型 变量名 = new 子类类型(); 向下转型:父类类型向子类类型向下转换的过程,这个过程时强制:一个已经向上转型的子类对象,将父类引用转为子类引用,可以使用强制转换的格式,便是向下转换: 使用格式: 子类类型 变量名 = (子类类型) 父类变量名;

  • 解决java.lang.ClassCastException的java类型转换异常的问题

    在项目中,需要使用XStream将xml string转成相应的对象,却报出了java.lang.ClassCastException: com.model.test cannot be cast to com.model.test的错误. 原因: 项目中应该是采用了热部署,devtools,因为累加载器的不同所以会导致类型转换失败 措施: 在pom.xml中将以下代码注释掉: <dependency> <groupId>org.springframework.boot</g

  • java中的switch case语句使用详解

    java中的switch case语句 switch-case语句格式如下: switch(变量){ case 变量值1: //; break; case 变量值2: //...; break; ... case default: //...; break; } swtich()变量类型只能是int.short.char.byte和enum类型(JDK 1.7 之后,类型也可以是String了).当进行case判断时,JVM会自动从上到小扫描,寻找匹配的case,可能存在以下情况: 情况一:若未

  • 深入理解 CAS 算法原理已经在jdk中的运用

    深入理解 CAS 算法原理已经在jdk中的运用

    1.什么是CAS? CAS:Compare and Swap,即比较再交换. jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁.JDK 5之前Java语言是靠synchronized关键字保证同步的,这是一种独占锁,也是是悲观锁. 2.CAS算法理解 对CAS的理解,CAS是一种无锁算法,CAS有3个操作数,内存值V,旧的预期值A,要修改的新值B.当且仅当预期值A和内存值V相同时,将内存值V修改为B,

  • 贪心算法原理及在Java中的使用

    贪心算法原理及在Java中的使用

    贪心算法 由于贪心算法本身的特殊性,我们在使用贪心算法之前必须要进行证明,保证算法满足贪心选择性质.具体的证明方法无外乎就是通过数学归纳法来进行证明.但大部分人可能并不喜欢枯燥的公式,因而我这里提供一个使用贪心算法的小技巧.由于贪心算法某种程度上算是动态规划算法的特例,使用条件比较苛刻,因而能够用动态规划解决的问题尽量都是用动态规划来进行先解决,如果在用完动态规划之后,提交时发现问题超时,并且进行状态压缩之后仍然超时,此时我们就可以**考虑使用贪心算法来进行解决.**最后强调一下,我们在使用贪心

  • 深入理解js A*寻路算法原理与具体实现过程

    深入理解js A*寻路算法原理与具体实现过程

    本文实例讲述了js A*寻路算法原理与具体实现过程.分享给大家供大家参考,具体如下: 这两天研究了下 A* 寻路算法, 主要学习了这篇文章, 但这篇翻译得不是很好, 我花了很久才看明白文章中的各种指代. 特写此篇博客用来总结, 并写了寻路算法的代码, 觉得有用的同学可以看看. 另外因为图片制作起来比较麻烦, 所以我用的是原文里的图片. 当然寻路算法不止 A* 这一种, 还有递归, 非递归, 广度优先, 深度优先, 使用堆栈等等, 有兴趣的可以研究研究~~ 简易地图 如图所示简易地图, 其中绿色方

  • 关于SHA算法原理与常用实现方式

    关于SHA算法原理与常用实现方式

    目录 定义 MD5和SHA-1的碰撞问题 常见应用场景 1.类似MD5的应用场景 2.比特币 3.https签名算法会用到 SHA-256算法原理 1.填补信息 2.拿到初始值 3.真正的计算 java实现和使用 看本文前,最好先看看之前的这一篇关于MD5算法的介绍. MD5算法原理与常用实现 定义 SHA算法(Secure Hash Algorithm),又叫安全散列算法. SHA算法是基于MD4算法的基础上,演变而来. 但SHA算法出生好,是美国国家安全局设计的. SHA算法,是一个系列家族

  • Java贪心算法之Prime算法原理与实现方法详解

    Java贪心算法之Prime算法原理与实现方法详解

    本文实例讲述了Java贪心算法之Prime算法原理与实现方法.分享给大家供大家参考,具体如下: Prime算法:是一种穷举查找算法来从一个连通图中构造一棵最小生成树.利用始终找到与当前树中节点权重最小的边,找到节点,加到最小生成树的节点集合中,直至所有节点都包括其中,这样就构成了一棵最小生成树.prime在算法中属于贪心算法的一种,贪心算法还有:Kruskal.Dijkstra以及哈夫曼树及编码算法. 下面具体讲一下prime算法: 1.首先需要构造一颗最小生成树,以及两个节点之间的权重数组,在

  • Kmeans均值聚类算法原理以及Python如何实现

    第一步.随机生成质心 由于这是一个无监督学习的算法,因此我们首先在一个二维的坐标轴下随机给定一堆点,并随即给定两个质心,我们这个算法的目的就是将这一堆点根据它们自身的坐标特征分为两类,因此选取了两个质心,什么时候这一堆点能够根据这两个质心分为两堆就对了.如下图所示: 第二步.根据距离进行分类 红色和蓝色的点代表了我们随机选取的质心.既然我们要让这一堆点的分为两堆,且让分好的每一堆点离其质心最近的话,我们首先先求出每一个点离质心的距离.假如说有一个点离红色的质心比例蓝色的质心更近,那么我们则将这个

  • vue.js diff算法原理详细解析

    目录 diff算法的概念 虚拟Dom h函数 diff对比规则 patch patchVnode updateChildren 总结 diff算法的概念 diff算法可以看作是一种对比算法,对比的对象是新旧虚拟Dom.顾名思义,diff算法可以找到新旧虚拟Dom之间的差异,但diff算法中其实并不是只有对比虚拟Dom,还有根据对比后的结果更新真实Dom. 虚拟Dom 上面的概念我们提到了虚拟Dom,相信大家对这个名词并不陌生,下面为大家解释一下虚拟Dom的概念,以及diff算法中为什么要对比虚拟

  • 图文详解感知机算法原理及Python实现

    图文详解感知机算法原理及Python实现

    目录 写在前面 1.什么是线性模型 2.感知机概述 3.手推感知机原理 4.Python实现 4.1 创建感知机类 4.2 更新权重与偏置 4.3 判断误分类点 4.4 训练感知机 4.5 动图可视化 5.总结 写在前面 机器学习强基计划聚焦深度和广度,加深对机器学习模型的理解与应用.“深”在详细推导算法模型背后的数学原理:“广”在分析多个机器学习模型:决策树.支持向量机.贝叶斯与马尔科夫决策.强化学习等. 本期目标:实现这样一个效果 1.什么是线性模型 线性模型的假设形式是属性权重.偏置与属性

  • Python实现的插入排序算法原理与用法实例分析

    Python实现的插入排序算法原理与用法实例分析

    本文实例讲述了Python实现的插入排序算法原理与用法.分享给大家供大家参考,具体如下: 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法 插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 插

  • Java笛卡尔积算法原理与实现方法详解

    Java笛卡尔积算法原理与实现方法详解

    本文实例讲述了Java笛卡尔积算法原理与实现方法.分享给大家供大家参考,具体如下: 笛卡尔积算法的Java实现: (1)循环内,每次只有一列向下移一个单元格,就是CounterIndex指向的那列. (2)如果该列到尾部了,则这列index重置为0,而CounterIndex则指向前一列,相当于进位,把前列的index加一. (3)最后,由生成的行数来控制退出循环. public class Test { private static String[] aa = { "aa1", &q

随机推荐