CAS 自旋锁/无锁机制算法

发布时间:2022-03-01 12:09:55 作者:yexindonglai@163.com 阅读(74)

       CAS全称叫做 Compare and swap (比较和交换),CAS无锁机制是乐观锁的一种,也叫自旋锁,CAS假设认为数据一般情况下不会造成冲突,所以在数据进行提交更新的时候,才会正式对数据的冲突与否进行检测,如果发现冲突了,则重新再来一次,无限循环地进行对比,直到没有冲突为止;

 

Atomic 类就是使用CAS无锁机制实现的类;

CAS操作依赖底层硬件的CAS指令,CAS指令有两个步骤:冲突检测和更新操作,但是这两个步骤合起来成为一个原子性操作。

CAS指令需要3个操作数:

  • 需要更新的变量(V)(主内存)
  • 旧的预期值(E)(本地内存)
  • 新值(B)

CAS指令执行时,首先比较内存位置V(主内存)处的值和E(本地内存)的值是否相等(冲突检测),如果相等,就用新值B(新值)覆盖V(更新操作),否则,就什么也不做。所以,一般循环执行CAS操作,直到成功为止。执行流程如下图

 

JDK 1.5 之后引进了一个叫做原子类的东西,它们都是以 Atomic 开头的,就拿 AtomicInteger 类来说,底层执行原理如下图:

 

原子类的常用方法如下

  1. // 以原子方式将给定值与当前值相加,可用于线程中的计数使用,(返回更新的值)。
  2. int addAndGet(int delta)
  3. // 以原子方式将给定值与当前值相加,可用于线程中的计数使用,(返回以前的值)
  4. int getAndAdd(int delta)
  5. // 以原子方式将当前值加 1(返回更新的值)
  6. int incrementAndGet()
  7. // 以原子方式将当前值加 1(返回以前的值)
  8. int getAndIncrement()
  9. // 以原子方式设置为给定值(返回旧值)
  10. int getAndSet(int newValue)
  11. // 以原子方式将当前值减 1(返回更新的值)
  12. int decrementAndGet()
  13. // 以原子方式将当前值减 1(返回以前的值)
  14. int getAndDecrement()
  15. // 获取当前值
  16. get()

还是写个代码例子出来吧

  1. package com.test;
  2. import java.util.concurrent.ExecutorService;
  3. import java.util.concurrent.Executors;
  4. import java.util.concurrent.atomic.AtomicInteger;
  5. /*
  6. 原子类测试
  7. */
  8. public class AtomicThreadTest {
  9. //普通int类型
  10. static int intNum = 0;
  11. // 原子类
  12. static AtomicInteger num = new AtomicInteger(0);
  13. public static void main(String[] args) {
  14. // 线程数量
  15. int threadNum = 10;
  16. ExecutorService executorService = Executors.newCachedThreadPool();
  17. // 创建多个线程进行++运算
  18. for (int j = 0; j < threadNum; j++) {
  19. executorService.execute(new Runnable() {
  20. @Override
  21. public void run() {
  22. for (int i = 0; i < 1000; i++) {
  23. // 每次将数字 + 1,相当于 i++
  24. num.incrementAndGet();
  25. intNum++;
  26. }
  27. }
  28. });
  29. }
  30. // 关闭线程池指令,不在接受新任务,待原有任务执行完成后关闭线程池
  31. executorService.shutdown();
  32. System.out.println("原子类结果:" + num);
  33. System.out.println("普通int类型结果:" + intNum);
  34. }
  35. }

 

看上面的图和例子还是有些抽象,那我们在看看下面这张图,3个线程的执行顺序和内部活动具体执行情况都清楚地描述出来了;

CAS 存在的问题

cas 虽然可以很高效地解决原子操作,但是仍然会有三个问题

  1. ABA问题
  2. 循环时间长开销大
  3. 只能保证一个共享变量的原子操作

1、ABA问题

因为cas会在更新的时候检查值是否发生变化,没有变化才会更新,但是如果一个值原来是A,变成了B,又变成了A,那么CAS在检查的时候就会认为它的值没有发生变化,但实际上是有变化的。

ABA问题如何解决?

ABA的问题的解决思路是使用版本号 version,每次变量更新的时候把版本号 加一,那么 A-B-A 就会变成 A1-B2-A3;可以使用AtomicStampedReference 来解决ABA问题,AtomicStampedReference 可以存放对象,在对象内增加一个version的属性即可;数据库的乐观锁也是用version版本号解决的,在表内增加一个version的字段,每次更新数据时 version + 1, 更新前先比较原版本号是否一致;sql语句如下:

update table set data = '更新的数据' , version = version + 1 where version = 1

 

2、循环时间长开销大

自旋CAS如果长时间不成功,会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升,pause指令有两个作用,第一它可以延迟流水线执行指令(de-pipeline),使CPU不会消耗过多的执行资源,延迟的时间取决于具体实现的版本,在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突(memory order violation)而引起CPU流水线被清空(CPU pipeline flush),从而提高CPU的执行效率。

 

3、只能保证一个共享变量的原子操作

当对一个共享变量执行操作时,我们可以使用循环CAS的方式来保证原子操作,但是对多个共享变量操作时,循环CAS就无法保证操作的原子性,这个时候就可以用锁,或者有一个取巧的办法,就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i=2,j=a,合并一下ij=2a,然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性,你可以把多个变量放在一个对象里来进行CAS操作。

 

cas本身具备原子性吗?

答:cas本身是具备原子性,cas本身锁的操作是在hotSpot源码中实现的,也就是c++层面的,在hotSpot中的cas逻辑中有这么一行代码:

#define LOCK_IF_MP(mp)

这句代码是什么意思呢? 意思是如果你有好多个cpu,就执行如下代码:

lock cmpxchg

这个代码意思是lock compare exchange ,锁住这个cpu的北桥信号,属于硬件级别的锁;

但如果只有一个CPU,就只执行以下代码:

cmpxchg

cas底层上锁流程图如下

 

 

 

 

关键字Java