首页 > 编程语言 >CAS算法

CAS算法

时间:2023-03-16 17:15:35浏览次数:36  
标签:变量 CAS 原子 算法 保证 操作

CAS算法

今天在看了《Java并发编程的艺术》,学习如何减少上下问切换的时候,里面说到了通过CAS算法来更新数据,而它不需要加锁。不太理解什么是CAS算法,所以在网上搜罗半天资料,看了很久才理解了,给大家整理了一下CAS算法。

1、概述

CAS的全程是:Compare And Swap(比较并交换),CAS是实现并发计算时常用到的技术,Java并发包中的很多类都使用了CAS技术,如ConcurrentHashMap,AtomicInteger原子操作等

CAS操作涉及到3个操作符:当前内存中的值、预估值、即将修改的新增,当且仅当预估值等于内存中的值的时候,才将新的值保存到内存中,否则什么都不做

2、作用

CAS可以将比较和交换转换为原子操作,这个原子操作直接由CPU保证,CAS可以保证共享变量赋值时的原子操作

3、特点

CAS是一种非阻塞算法的实现,它能在不使用锁的情况下实现多线程安全,所以CAS也是一种无锁算法

一个线程失败或挂起并不会导致其他线程也失败或挂起

4、案例

AtomicInteger的incrementAndGet()源码

  • AtomicInteger底层使用到了Unsafe类,它提供了原子操作,Unsafe类可以直接操作内存空间的值

  • Unsafe的CompareAndSwapInt()方法其实就是CAS方法,它会自旋判断当前内存中的值与预期的值是否相等,如果相等就会把内存中的值用更新值替换,如果不相等则不操作,以此来保证原子性

  • 基于硬件平台的汇编指令,在intel的CPU中,使用的是cmpxchg指令,也就是说CAS靠硬件实现,从而在硬件层面提升效率

5、优点

  1. 由于CAS是非阻塞的,可以避免优先级倒置和死锁等问题
  2. 性能好,使用无锁的方式,没有锁竞争带来的系统开销,也没有线程间频繁调度带来的开销

6、缺点

  1. 循环时间长开销大(自旋)
  • 如果CAS失败,会一直进行尝试,如果CAS长时间一直不成功,可能给CPU带来很大的开销
  • 解决方法:破坏调死循环,当超过一定时间或者一定次数时,return退出
  1. 只能保证一个共享变量的原子操作
  • 当对一个共享变量操作时,可以使用循环CAS的方式来保证原子操作,但是对多个共享变量操作时,循环CAS就无法保证操作的原子性
  • 解决方法:
    1. 用锁来保证原子性
    2. 把多个共享变量合成一个共享变量来操作
    3. 封装成对象 ;Java1.5开始,JDK提供了AtomicReference类来保证引用对象之前的原子性,可以把多个变量放到一个对象里来进行CAS操作
  1. ABA问题
  • 如果内存地址V初次读取的值是A,并且在准备赋值的时候检查到它的值仍然为A,那我们就能说明它的值没有被其他线程改变过吗?

    如果在这段期间它的值曾经被改称了B,然后又改为A,那CAS就会误认为它从来没有被修改过,这就是ABA问题

  • 解决方法

    1. Java并发包提供了一个带有标记的原子引用类AtomicStampedReference,它可以通过控制变量值的版本来保证CAS的正确性;即在变量前面添加版本号,每次变量更新的时候都把版本号+1,这样变化过程就变成A-B-A变成1A-2B-3A
    2. 增加时间戳

标签:变量,CAS,原子,算法,保证,操作
From: https://www.cnblogs.com/jundong2177/p/17223325.html

相关文章

  • python 雪花算法demo
    importtimeimportloggingclassInvalidSystemClock(Exception):"""时钟回拨异常"""pass#64位ID的划分WORKER_ID_BITS=5DATACENTER_ID_B......
  • mongodb switch case
    //构造测试数据db.hello100.insertMany([ {"name":"doc01","age":10}, {"name":"doc02","age":11}, {"name":"doc03","age":12}, {"name":"doc03",&qu......
  • 算法 -- 反转链表
    反转链表简单3K相关企业给你单链表的头节点head,请你反转链表,并返回反转后的链表。示例1:输入:head=[1,2,3,4,5]输出:[5,4,3,2,1]示例2:输入:head=[1,2]输出......
  • nodejs的一个十六进制 加密 和 逆算法
    constkaitou="$@$@";Buffer.from(kaitou,"utf8").toString("hex");给以以上nodejs的逆算法consthexString="24402440";//十六进制字符串constbuffer=Bu......
  • m基于kmeans和Cmeans算法的数据聚类仿真分析
    1.算法描述       K-means聚类算法是硬聚类算法,是典型的基于原型的目标函数聚类分析算法点到原型——簇中心的某种距离和作为优化的目标函数,采用函数求极值的方法......
  • 传统CV算法总结-边缘检测系列
    第一章概述1.边缘检测概述1.1认识边缘边缘的定义边缘是不同区域的分界线,是周围(局部)灰度值有显著变化的像素点的集合,有幅值与方向两个属性。这个不是绝对的定义,边缘是局......
  • 基于Pierre Dellacherie的俄罗斯方块-05Pierre Dellacherie算法
    基于PierreDellacherie的俄罗斯方块-05PierreDellacherie算法PierreDellacherie算法感觉上像是一个遍历算法,给与各个参数不同的权重,使得更加合理的摆放方块评估主......
  • 并归排序算法
    【说明】采用归并排序对n个元素进行递增排序时,首先将n个元素的数组分成各含/2个元素的两个子数组,然后用归并排序对两个子数组进行递归排序,最后合并两个已经排好序的......
  • 基于形态学处理算法的迷宫路线搜索matlab仿真
    1.算法描述形态学是图像处理中应用最为广泛的技术之一,主要用于从图像中提取对表达和描绘区域形状有意义的图像分量,使后续的识别工作能够抓住目标对象最为本质的形状特征,如......
  • 基于形态学处理算法的迷宫路线搜索matlab仿真
    1.算法描述       形态学是图像处理中应用最为广泛的技术之一,主要用于从图像中提取对表达和描绘区域形状有意义的图像分量,使后续的识别工作能够抓住目标对象最为本......