glmapper

并发编程-关于 CAS 的几个问题

字数统计: 2.4k阅读时长: 9 min
2019/04/29 Share

CAS 相关基础知识

CAS的全称是Compare And Swap ,即比较交换。CAS 中一般会设计到3个参数:

  • 内存值 V
  • 旧的预期值A
  • 要修改的新值B

当且仅当预期值 A 和内存值 V 相同时,将内存值V修改为 B,否则什么都不做。

这里关于 CPU 指令对于 CAS 的支持不深入研究,有兴趣的可以自行了解。

CAS 几个问题

很多书籍和文章中都有提出它存在的几个问题:

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

下面就这三个问题展开来聊一下。

1、关于“循环时间长开销很大”的疑惑与验证

自旋 CAS 如果长时间不成功,会给 CPU 带来非常大的开销。但是真的是这样吗?到底多大的并发量才造成 CAS 的自旋次数会增加呢?另外,对于当前的机器及JDK,在无锁,无CAS 的情况下,是否对于结果的影响是真的那么明显呢?对于这个问题,下面做了一个简单的测试,但是测试结果也只是针对在我本地环境下,各位看官可以拉一下代码,在自己电脑上 run 一下,把机器信息、JDK版本以及测试结果留言到评论区。

本文案例可以这里获取:glmapper-blog-sample-cas

这里我是用了一个很简单的案例,就是整数自增。使用了两种方式去测试的,一种是无锁,也不用 CAS 操作,另外一种是基于 CAS 的方式。(关于加锁的方式没有验证,有时间再补充吧~)

计数器类

计数器里面有两个方法,一种是CAS 自旋方式,一种是直接自增。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Counter {
public AtomicInteger safeCount = new AtomicInteger(0);
public int unsafe = 0;
// 使用自旋的方式
public void safeCount(){
for (;;){
int i = safeCount.get();
boolean success = safeCount.compareAndSet(i,++i);
if (success){
break;
}
}
}
// 普通方式自增
public void unsafeCount(){
unsafe++;
}
}

模拟并发

这里我们模拟使用 1000 个线程,执行 30 次来看下结果,包括总耗时和结果的正确性。

  • CAS 方式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public static int testSafe() throws InterruptedException {
    // 记录开始时间
    long start = System.currentTimeMillis();
    // 实例化一个 Counter 计数器对象
    Counter counter = new Counter();
    CountDownLatch countDownLatch = new CountDownLatch(testCounts);
    for (int i =0 ;i < testCounts;i++){
    new Thread(()->{
    // 调用 safeCount 方法
    counter. safeCount();
    countDownLatch.countDown();
    }).start();
    }
    countDownLatch.await();
    // 结束时间
    long end = System.currentTimeMillis();
    safeTotalCostTime += (end-start);
    return counter.safeCount.get();
    }
  • 普通方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int testUnSafe() throws InterruptedException {
// 记录开始时间
long start = System.currentTimeMillis();
// 实例化一个 Counter 计数器对象
Counter counter = new Counter();
CountDownLatch countDownLatch = new CountDownLatch(testCounts);
for (int i =0 ;i< testCounts;i++){
new Thread(()->{
// 调用 unsafeCount 方法
counter.unsafeCount();
countDownLatch.countDown();
}).start();
}
countDownLatch.await();
// 结束时间
long end = System.currentTimeMillis();
unsafeTotalCostTime += (end-start);
return counter.unsafe;
}
  • main 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void main(String[] args) throws InterruptedException {
// 执行 300 次
for (int i =0 ;i< 300;i++){
// 普通方式
int unSafeResult = testUnSafe();
// cas 方式
int safeResult = testSafe();
// 结果验证,若果正确就将成功次数增加
if (unSafeResult == testCounts){
totalUnSafeCount++;
}
// 同上
if (safeResult == testCounts){
totalSafeCount++;
}
}
System.out.println("test count = " + testCounts);
System.out.println("非安全计数器正确个数 = " + totalUnSafeCount);
System.out.println("非安全计数器耗时 = " + unsafeTotalCostTime);
System.out.println("安全计数器正确个数 = " + totalSafeCount);
System.out.println("安全计数器耗时 = " + safeTotalCostTime);
}

我的机器信息如下:

  • MacBook Pro (Retina, 15-inch, Mid 2015)
  • 处理器:2.2 GHz Intel Core i7
  • 内存:16 GB 1600 MHz DDR3

下面是一些测试数据。

1000(线程数) * 300(次数)

测试结果如下:

1
2
3
4
5
test count = 1000
非安全计数器正确个数 = 300
非安全计数器耗时 = 27193
安全计数器正确个数 = 300
安全计数器耗时 = 26337

居然发现不使用 CAS 的方式居然比使用自旋 CAS 的耗时要高出将近 1s。另外一个意外的点,我尝试了好几次,不使用 CAS 的情况得到的结果正确率基本也是 4 个 9 以上的比率,极少数会出现计算结果错误的情况。

3000(线程数) * 30(次数)

测试结果如下:

1
2
3
4
5
test count = 3000
非安全计数器正确个数 = 30
非安全计数器耗时 = 7816
安全计数器正确个数 = 30
安全计数器耗时 = 8073

这里看到在耗时上已经很接近了。这里需要考虑另外一个可能影响的点是,因为 testUnSafe 是 testSafe 之前执行的,“JVM 和 机器本身热身” 影响耗时虽然很小,但是也存在一定的影响。

5000(线程数) * 30(次数)

测试结果如下:

1
2
3
4
5
test count = 5000
非安全计数器正确个数 = 30
非安全计数器耗时 = 23213
安全计数器正确个数 = 30
安全计数器耗时 = 14161

随着并发量的增加,这里奇怪的是,普通自增方式所消耗的时间要高于CAS方式消耗的时间将近 8-9s 。

当尝试 10000 次时,是的你没猜错,抛出了 OOM 。但是从执行的结果来看,并没有说随着并发量的增大,普通方式错误的概率会增加,也没有出现预想的 CAS 方式的耗时要比 普通模式耗时多。

由于测试样本数据比较单一,对于测试结果没法做结论,欢迎大家将各自机器的结果提供出来,以供参考。另外就是,最近看到很多面试的同学,如果有被问道这个问题,还是需要谨慎考虑下。关于是否“打脸”还是“被打脸”还需要更多的测试结果。

CAS 到底是怎么操作的

  • CPU 指令
  • Unsafe 类

2、ABA 问题的简单复现

网上关于 CAS 讨论另外一个点就是 CAS 中的 ABA 问题,相信大多数同学在面试时如果被问到 CAS ,那么 ABA 问题也会被问到,然后接着就是怎么避免这个问题,是的套路就是这么一环扣一环的。

我相信 90% 以上的开发人员在实际的工程中是没有遇到过这个问题的,即使遇到过,在特定的情况下也是不会影响到计算结果。但是既然这个问题会被反复提到,那就一定有它导致 bug 的场景,找了一个案例供大家参考:CAS下ABA问题及优化方案

这里先不去考虑怎么去规避这个问题,我们想怎么去通过简单的模拟先来复现这个 ABA 问题。其实这个也很简单,如果你对线程交叉、顺序执行了解的话。

如何实现多线程的交叉执行

这个点实际上也是一个在面试过程中很常见的一个基础问题,我在提供的代码中给了三种实现方式,有兴趣的同学可以拉代码看下。

下面以 lock 的方式来模拟下这个场景,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class ConditionAlternateTest{
private static int count = 0;
// 计数器
public AtomicInteger safeCount = new AtomicInteger(0);
// lock
private Lock lock = new ReentrantLock();
// condition 1/2/3 用于三个线程触发执行的条件
Condition c1 = lock.newCondition();
Condition c2 = lock.newCondition();
Condition c3 = lock.newCondition();
// 模拟并发执行
CountDownLatch countDownLatch = new CountDownLatch(1);
// 线程1 ,A
Thread t1 = new Thread(()-> {
try {
lock.lock();
while (count % 3 != 0){
c1.await();
}
safeCount.compareAndSet(0, 1);
System.out.println("thread1:"+safeCount.get());
count++;
// 唤醒条件2
c2.signal();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
});
// 线程2 ,B
Thread t2 = new Thread(()-> {
try {
lock.lock();
while (count % 3 != 1){
c2.await();
}
safeCount.compareAndSet(1, 0);
System.out.println("thread2:"+safeCount.get());
count++;
// 唤醒条件3
c3.signal();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
});
// 线程2 ,A
Thread t3 = new Thread(()-> {
try {
lock.lock();
while (count % 3 != 2){
c3.await();
}
safeCount.compareAndSet(0, 1);
System.out.println("thread3:"+safeCount.get());
count++;
// 唤醒条件1
c1.signal();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
});
// 启动启动线程
public void threadStart() {
t3.start();
t1.start();
t2.start();
countDownLatch.countDown();
}

public static void main(String[] args) throws InterruptedException {
ConditionAlternateTest test = new ConditionAlternateTest();
test.threadStart();
test.countDownLatch.await();
}
}

执行结果:

1
2
3
thread1:1
thread2:0
thread3:1

上面线程交叉的案例实际上并不是严格意义上的 ABA 问题的复现,这里仅是模拟下产生的一个最简单的过程。如果大家有好的案例,也可以分享一下。

ABA 问题解决

常见实践:“版本号”的比对,一个数据一个版本,版本变化,即使值相同,也不应该修改成功。

java 中提供了 AtomicStampedReference 这个类来解决这个 ABA 问题。
AtomicStampedReference 原子类是一个带有时间戳的对象引用,在每次修改后,AtomicStampedReference 不仅会设置新值而且还会记录更改的时间。当 AtomicStampedReference 设置对象值时,对象值以及时间戳都必须满足期望值才能写入成功,这也就解决了反复读写时,无法预知值是否已被修改的窘境。

实现代码这里就不贴了,基于前面的代码改造,下面贴一下运行结果:

1
2
3
thread1,第一次修改;值为=1
thread2,已经改回为原始值;值为=0
thread3,第二次修改;值为=1

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

当对一个共享变量执行操作时,我们可以使用 CAS 的方式来保证原子操作,但是对于对多个变量操作时,循环 CAS 就无法保证操作的原子性了,那么这种场景下,我们就需要使用加锁的方式来解决。

原文作者:GuoLei Song

原文链接:http://www.glmapper.com/2019/04/29/cas-several-qa/

发表日期:April 29th 2019, 10:25:57 am

更新日期:April 29th 2019, 10:28:01 am

版权声明:转载请注明出处

CATALOG
  1. 1. CAS 相关基础知识
  2. 2. CAS 几个问题
    1. 2.1. 1、关于“循环时间长开销很大”的疑惑与验证
      1. 2.1.1. 计数器类
      2. 2.1.2. 模拟并发
      3. 2.1.3. 1000(线程数) * 300(次数)
      4. 2.1.4. 3000(线程数) * 30(次数)
      5. 2.1.5. 5000(线程数) * 30(次数)
    2. 2.2. CAS 到底是怎么操作的
    3. 2.3. 2、ABA 问题的简单复现
    4. 2.4. 如何实现多线程的交叉执行
    5. 2.5. ABA 问题解决
    6. 2.6. 3、只能保证一个共享变量的原子操作