CAS
# CAS
# CAS 是什么
CAS(compare and swap)的缩写,中文翻译成比较并交换,实现并发算法时常用到的一种技术。它包含三个操作数 —— 内存位置、预期原值及更新值。执行 CAS 操作的时候,将内存位置的值与预期原值比较:
- 如果相匹配,那么处理器会自动将该位置值更新为新值,
- 如果不匹配,处理器不做任何操作,多个线程同时执行 CAS 操作只有一个会成功。
CAS 有 3 个操作数,位置内存值 V,旧的预期值 A,要修改的更新值 B。 当且仅当旧的预期值 A 和内存值 V 相同时,将内存值 V 修改为 B,否则什么都不做或重来

CAS 是 JDK 提供的非阻塞原子性操作,它通过硬件保证了比较 - 更新的原子性。它是非阻塞的且自身原子性,也就是说这玩意效率更高且通过硬件保证,说明这玩意更可靠。
作用:比较当前工作内存中的值和主物理内存中的值,如果相同则执行规定操作,否则继续比较直到主内存和工作内存的值一致为止
CAS 特点:
- CAS 体现的是无锁并发、无阻塞并发,线程不会陷入阻塞,线程不需要频繁切换状态(上下文切换,系统调用)
- CAS 是基于乐观锁的思想
CAS 缺点:
- 执行的是循环操作,如果比较不成功一直在循环,最差的情况某个线程一直取到的值和预期值都不一样,就会无限循环导致饥饿,使用 CAS 线程数不要超过 CPU 的核心数,采用分段 CAS 和自动迁移机制
- 只能保证一个共享变量的原子操作
- 对于一个共享变量执行操作时,可以通过循环 CAS 的方式来保证原子操作
- 对于多个共享变量操作时,循环 CAS 就无法保证操作的原子性,这个时候只能用锁来保证原子性
- 引出来 ABA 问题
CAS 是一条 CPU 的原子指令(cmpxchg 指令),不会造成所谓的数据不一致问题,Unsafe 提供的 CAS 方法(如 compareAndSwapXXX)底层实现即为 CPU 指令 cmpxchg。 执行 cmpxchg 指令的时候,会判断当前系统是否为多核系统,如果是就给总线加锁,只有一个线程会对总线加锁成功,加锁成功之后会执行 cas 操作,也就是说 CAS 的原子性实际上是 CPU 实现的, 其实在这一点上还是有排他锁的,只是比起用 synchronized, 这里的排他时间要短的多, 所以在多线程情况下性能会比较好
package com.atguigu.juc.prepare;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @auther zzyy
* @create 2020-04-15 7:51
*/
public class CASDemo
{
public static void main(String[] args) throws InterruptedException
{
AtomicInteger atomicInteger = new AtomicInteger(5);
System.out.println(atomicInteger.compareAndSet(5, 2020)+"\t"+atomicInteger.get());
System.out.println(atomicInteger.compareAndSet(5, 1024)+"\t"+atomicInteger.get());
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
源码分析 compareAndSet(int expect,int update)

上面三个方法都是类似的,主要对 4 个参数做一下说明。
- var1:表示要操作的对象
- var2:表示要操作对象中属性地址的偏移量
- var4:表示需要修改数据的期望的值
- var5/var6:表示需要修改为的新值

那么 UnSafe 类是什么?
# 没有 CAS 之前
多线程环境不使用原子类保证线程安全(基本数据类型)
package com.atguigu.juc.prepare;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @auther zzyy
* @create 2020-04-15 10:41
*/
public class T3
{
volatile int number = 0;
//读取
public int getNumber()
{
return number;
}
//写入加锁保证原子性
public synchronized void setNumber()
{
number++;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
多线程环境,使用原子类保证线程安全(基本数据类型)
package com.atguigu.juc.prepare;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @auther zzyy
* @create 2020-04-15 10:41
*/
public class T3
{
volatile int number = 0;
//读取
public int getNumber()
{
return number;
}
//写入加锁保证原子性
public synchronized void setNumber()
{
number++;
}
//=================================
AtomicInteger atomicInteger = new AtomicInteger();
public int getAtomicInteger()
{
return atomicInteger.get();
}
public void setAtomicInteger()
{
atomicInteger.getAndIncrement();
}
}
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
# CAS 底层原理
# UnSafe

Unsafe 是 CAS 的核心类,由于 Java 方法无法直接访问底层系统,需要通过本地(native)方法来访问,Unsafe 相当于一个后门,基于该类可以直接操作特定内存的数据。Unsafe 类存在于 sun.misc 包中,其内部方法操作可以像 C 的指针一样直接操作内存,因为 Java 中 CAS 操作的执行依赖于 Unsafe 类的方法。 注意 Unsafe 类中的所有方法都是 native 修饰的,也就是说 Unsafe 类中的方法都直接调用操作系统底层资源执行相应任务
变量 valueOffset,表示该变量值在内存中的偏移地址,因为 Unsafe 就是根据内存偏移地址获取数据的。

变量 value 用 volatile 修饰,保证了多线程之间的内存可见性。
# getAndIncrement()
我们知道 i++ 线程不安全的,那 atomicInteger.getAndIncrement ()
CAS 的全称为 Compare-And-Swap,它是一条 CPU 并发原语。 它的功能是判断内存某个位置的值是否为预期值,如果是则更改为新的值,这个过程是原子的。 AtomicInteger 类主要利用 CAS (compare and swap) + volatile 和 native 方法来保证原子操作,从而避免 synchronized 的高开销,执行效率大为提升。

CAS 并发原语体现在 JAVA 语言中就是 sun.misc.Unsafe 类中的各个方法。调用 UnSafe 类中的 CAS 方法,JVM 会帮我们实现出 CAS 汇编指令。这是一种完全依赖于硬件的功能,通过它实现了原子操作。再次强调,由于 CAS 是一种系统原语,原语属于操作系统用语范畴,是由若干条指令组成的,用于完成某个功能的一个过程,并且原语的执行必须是连续的,在执行过程中不允许被中断,也就是说 CAS 是一条 CPU 的原子指令,不会造成所谓的数据不一致问题。
# 源码分析
new AtomicInteger().getAndIncrement();



假设线程 A 和线程 B 两个线程同时执行 getAndAddInt 操作(分别跑在不同 CPU 上):
- AtomicInteger 里面的 value 原始值为 3,即主内存中 AtomicInteger 的 value 为 3,根据 JMM 模型,线程 A 和线程 B 各自持有一份值为 3 的 value 的副本分别到各自的工作内存。
- 线程 A 通过 getIntVolatile (var1, var2) 拿到 value 值 3,这时线程 A 被挂起。
- 线程 B 也通过 getIntVolatile (var1, var2) 方法获取到 value 值 3,此时刚好线程 B 没有被挂起并执行 compareAndSwapInt 方法比较内存值也为 3,成功修改内存值为 4,线程 B 打完收工,一切 OK。
- 这时线程 A 恢复,执行 compareAndSwapInt 方法比较,发现自己手里的值数字 3 和主内存的值数字 4 不一致,说明该值已经被其它线程抢先一步修改过了,那 A 线程本次修改失败,只能重新读取重新来一遍了。
- 线程 A 重新获取 value 值,因为变量 value 被 volatile 修饰,所以其它线程对它的修改,线程 A 总是能够看到,线程 A 继续执行 compareAndSwapInt 进行比较替换,直到成功。
# 底层汇编
native 修饰的方法代表是底层方法
Unsafe 类中的 compareAndSwapInt,是一个本地方法,该方法的实现位于 unsafe.cpp 中
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
UnsafeWrapper("Unsafe_CompareAndSwapInt");
oop p = JNIHandles::resolve(obj);
// 先想办法拿到变量value在内存中的地址,根据偏移量valueOffset,计算 value 的地址
jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
// 调用 Atomic 中的函数 cmpxchg来进行比较交换,其中参数x是即将更新的值,参数e是原内存的值
return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END
2
3
4
5
6
7
8
(Atomic::cmpxchg(x, addr, e)) == e;
// 调用 Atomic 中的函数 cmpxchg来进行比较交换,其中参数x是即将更新的值,参数e是原内存的值
return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
2
cmpxchg()
unsigned Atomic::cmpxchg(unsigned int exchange_value,volatile unsigned int* dest, unsigned int compare_value) {
assert(sizeof(unsigned int) == sizeof(jint), "more work to do");
/*
* 根据操作系统类型调用不同平台下的重载函数,这个在预编译期间编译器会决定调用哪个平台下的重载函数*/
return (unsigned int)Atomic::cmpxchg((jint)exchange_value, (volatile jint*)dest, (jint)compare_value);
}
2
3
4
5
6
在不同的操作系统下会调用不同的 cmpxchg 重载函数
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
//判断是否是多核CPU
int mp = os::is_MP();
__asm {
//三个move指令表示的是将后面的值移动到前面的寄存器上
mov edx, dest
mov ecx, exchange_value
mov eax, compare_value
//CPU原语级别,CPU触发
LOCK_IF_MP(mp)
//比较并交换指令
//cmpxchg: 即“比较并交换”指令
//dword: 全称是 double word 表示两个字,一共四个字节
//ptr: 全称是 pointer,与前面的 dword 连起来使用,表明访问的内存单元是一个双字单元
//将 eax 寄存器中的值(compare_value)与 [edx] 双字内存单元中的值进行对比,
//如果相同,则将 ecx 寄存器中的值(exchange_value)存入 [edx] 内存单元中
cmpxchg dword ptr [edx], ecx
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
CAS 的机制为最终是由操作系统的汇编指令完成的。
CAS 是靠硬件实现的从而在硬件层面提升效率,最底层还是交给硬件来保证原子性和可见性 实现方式是基于硬件平台的汇编指令,在 intel 的 CPU 中 (X86 机器上),使用的是汇编指令 cmpxchg 指令。
核心思想就是:比较要更新变量的值 V 和预期值 E(compare),相等才会将 V 的值设为新值 N(swap)如果不相等自旋再来。
# 原子引用
AtomicInteger 原子整型,可否有其它原子类型?
- AtomicBook
- AtomicOrder
简单使用 AtomicReference
package com.atguigu.Interview.study.thread;
import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.ToString;
import java.util.concurrent.atomic.AtomicReference;
@Getter
@ToString
@AllArgsConstructor
class User
{
String userName;
int age;
}
/**
* @auther zzyy
* @create 2018-12-31 17:22
*/
public class AtomicReferenceDemo
{
public static void main(String[] args)
{
User z3 = new User("z3",24);
User li4 = new User("li4",26);
AtomicReference<User> atomicReferenceUser = new AtomicReference<>();
atomicReferenceUser.set(z3);
System.out.println(atomicReferenceUser.compareAndSet(z3,li4)+"\t"+atomicReferenceUser.get().toString());
System.out.println(atomicReferenceUser.compareAndSet(z3,li4)+"\t"+atomicReferenceUser.get().toString());
}
}
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
# 自旋锁
自旋锁(spinlock)是指尝试获取锁的线程不会立即阻塞,而是采用循环的方式去尝试获取锁,当线程发现锁被占用时,会不断循环判断锁的状态,直到获取。这样的好处是减少线程上下文切换的消耗,缺点是循环会消耗 CPU
自己实现一个自旋锁 SpinLockDemo
package com.atguigu.Interview.study.thread;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicReference;
/**
* @auther zzyy
* @create 2018-12-28 17:57
* 题目:实现一个自旋锁
* 自旋锁好处:循环比较获取没有类似wait的阻塞。
*
* 通过CAS操作完成自旋锁,A线程先进来调用myLock方法自己持有锁5秒钟,B随后进来后发现
* 当前有线程持有锁,不是null,所以只能通过自旋等待,直到A释放锁后B随后抢到。
*/
public class SpinLockDemo
{
AtomicReference<Thread> atomicReference = new AtomicReference<>();
public void myLock()
{
Thread thread = Thread.currentThread();
System.out.println(Thread.currentThread().getName()+"\t come in");
while(!atomicReference.compareAndSet(null,thread))
{
}
}
public void myUnLock()
{
Thread thread = Thread.currentThread();
atomicReference.compareAndSet(thread,null);
System.out.println(Thread.currentThread().getName()+"\t myUnLock over");
}
public static void main(String[] args)
{
SpinLockDemo spinLockDemo = new SpinLockDemo();
new Thread(() -> {
spinLockDemo.myLock();
try { TimeUnit.SECONDS.sleep( 5 ); } catch (InterruptedException e) { e.printStackTrace(); }
spinLockDemo.myUnLock();
},"A").start();
//暂停一会儿线程,保证A线程先于B线程启动并完成
try { TimeUnit.SECONDS.sleep( 1 ); } catch (InterruptedException e) { e.printStackTrace(); }
new Thread(() -> {
spinLockDemo.myLock();
spinLockDemo.myUnLock();
},"B").start();
}
}
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
# CAS 缺点
循环时间长开销很大。
我们可以看到 getAndAddInt 方法执行时,有个 do while

如果 CAS 失败,会一直进行尝试。如果 CAS 长时间一直不成功,可能会给 CPU 带来很大的开销。
CAS 会导致 “ABA 问题”。
CAS 算法实现一个重要前提需要取出内存中某时刻的数据并在当下时刻比较并替换,那么在这个时间差类会导致数据的变化。
比如说一个线程 one 从内存位置 V 中取出 A,这时候另一个线程 two 也从内存中取出 A,并且线程 two 进行了一些操作将值变成了 B, 然后线程 two 又将 V 位置的数据变成 A,这时候线程 one 进行 CAS 操作发现内存中仍然是 A,然后线程 one 操作成功。
尽管线程 one 的 CAS 操作成功,但是不代表这个过程就是没有问题的。
版本号时间戳原子引用, AtomicStampedReference
package com.atguigu.Interview.study.thread;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicStampedReference;
/**
* @auther zzyy
* @create 2018-11-20 17:14
*/
public class ABADemo
{
static AtomicInteger atomicInteger = new AtomicInteger(100);
static AtomicStampedReference atomicStampedReference = new AtomicStampedReference(100,1);
public static void main(String[] args)
{
new Thread(() -> {
atomicInteger.compareAndSet(100,101);
atomicInteger.compareAndSet(101,100);
},"t1").start();
new Thread(() -> {
//暂停一会儿线程
try { Thread.sleep( 500 ); } catch (InterruptedException e) { e.printStackTrace(); }; System.out.println(atomicInteger.compareAndSet(100, 2019)+"\t"+atomicInteger.get());
},"t2").start();
//暂停一会儿线程,main彻底等待上面的ABA出现演示完成。
try { Thread.sleep( 2000 ); } catch (InterruptedException e) { e.printStackTrace(); }
System.out.println("============以下是ABA问题的解决=============================");
new Thread(() -> {
int stamp = atomicStampedReference.getStamp();
System.out.println(Thread.currentThread().getName()+"\t 首次版本号:"+stamp);//1
//暂停一会儿线程,
try { Thread.sleep( 1000 ); } catch (InterruptedException e) { e.printStackTrace(); }
atomicStampedReference.compareAndSet(100,101,atomicStampedReference.getStamp(),atomicStampedReference.getStamp()+1);
System.out.println(Thread.currentThread().getName()+"\t 2次版本号:"+atomicStampedReference.getStamp());
atomicStampedReference.compareAndSet(101,100,atomicStampedReference.getStamp(),atomicStampedReference.getStamp()+1);
System.out.println(Thread.currentThread().getName()+"\t 3次版本号:"+atomicStampedReference.getStamp());
},"t3").start();
new Thread(() -> {
int stamp = atomicStampedReference.getStamp();
System.out.println(Thread.currentThread().getName()+"\t 首次版本号:"+stamp);//1
//暂停一会儿线程,获得初始值100和初始版本号1,故意暂停3秒钟让t3线程完成一次ABA操作产生问题
try { Thread.sleep( 3000 ); } catch (InterruptedException e) { e.printStackTrace(); }
boolean result = atomicStampedReference.compareAndSet(100,2019,stamp,stamp+1);
System.out.println(Thread.currentThread().getName()+"\t"+result+"\t"+atomicStampedReference.getReference());
},"t4").start();
}
}
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
# ABA
ABA 问题:当进行获取主内存值时,该内存值在写入主内存时已经被修改了 N 次,但是最终又改成原来的值
其他线程先把 A 改成 B 又改回 A,主线程仅能判断出共享变量的值与最初值 A 是否相同,不能感知到这种从 A 改为 B 又 改回 A 的情况,这时 CAS 虽然成功,但是过程存在问题
static AtomicReference<String> ref = new AtomicReference<>("A");
public static void main(String[] args) throws InterruptedException {
log.debug("main start...");
// 获取值 A
// 这个共享变量被它线程修改过?
String prev = ref.get();
other();
sleep(1);
// 尝试改为 C
log.debug("change A->C {}", ref.compareAndSet(prev, "C"));
}
private static void other() {
new Thread(() -> {
log.debug("change A->B {}", ref.compareAndSet(ref.get(), "B"));
}, "t1").start();
sleep(0.5);
new Thread(() -> {
log.debug("change B->A {}", ref.compareAndSet(ref.get(), "A"));
}, "t2").start();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
输出
11:29:52.325 c.Test36 [main] - main start...
11:29:52.379 c.Test36 [t1] - change A->B true
11:29:52.879 c.Test36 [t2] - change B->A true
11:29:53.880 c.Test36 [main] - change A->C true
2
3
4
主线程仅能判断出共享变量的值与最初值 A 是否相同,不能感知到这种从 A 改为 B 又 改回 A 的情况,如果主线程 希望:
只要有其它线程【动过了】共享变量,那么自己的 cas 就算失败,这时,仅比较值是不够的,需要再加一个版本号
# ABA 问题解决方案
# AtomicStampedReference
我们可以使用 AtomicStampedReference 这个原子引用类进行解决 ABA 问题
- 构造方法:
AtomicStampedReference(V initialRef, int initialStamp):初始值和初始版本号 boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp):期望引用和期望版本号都一致才进行 CAS 修改数据set(V newReference, int newStamp):设置值和版本号V getReference():返回引用的值int getStamp():返回当前版本号
static AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);
public static void main(String[] args) throws InterruptedException {
log.debug("main start...");
// 获取值 A
String prev = ref.getReference();
// 获取版本号
int stamp = ref.getStamp();
log.debug("版本 {}", stamp);
// 如果中间有其它线程干扰,发生了 ABA 现象
other();
sleep(1);
// 尝试改为 C
log.debug("change A->C {}", ref.compareAndSet(prev, "C", stamp, stamp + 1));
}
private static void other() {
new Thread(() -> {
log.debug("change A->B {}", ref.compareAndSet(ref.getReference(), "B",
ref.getStamp(), ref.getStamp() + 1));
log.debug("更新版本为 {}", ref.getStamp());
}, "t1").start();
sleep(0.5);
new Thread(() -> {
log.debug("change B->A {}", ref.compareAndSet(ref.getReference(), "A",
ref.getStamp(), ref.getStamp() + 1));
log.debug("更新版本为 {}", ref.getStamp());
}, "t2").start();
}
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
输出为
15:41:34.891 c.Test36 [main] - main start...
15:41:34.894 c.Test36 [main] - 版本 0
15:41:34.956 c.Test36 [t1] - change A->B true
15:41:34.956 c.Test36 [t1] - 更新版本为 1
15:41:35.457 c.Test36 [t2] - change B->A true
15:41:35.457 c.Test36 [t2] - 更新版本为 2
15:41:36.457 c.Test36 [main] - change A->C false
2
3
4
5
6
7
AtomicStampedReference 可以给原子引用加上版本号,追踪原子引用整个的变化过程,如: A -> B -> A -> C ,通过 AtomicStampedReference,我们可以知道,引用变量中途被更改了几次。
但是有时候,并不关心引用变量更改了几次,只是单纯的关心是否更改过,所以就有了 AtomicMarkableReference
graph TD
s(保洁阿姨)
m(主人)
g1(垃圾袋)
g2(新垃圾袋)
s -. 倒空 .-> g1
m -- 检查 --> g1
g1 -- 已满 --> g2
g1 -- 还空 --> g1
2
3
4
5
6
7
8
9
10
# AtomicMarkableReference
class GarbageBag {
String desc;
public GarbageBag(String desc) {
this.desc = desc;
}
public void setDesc(String desc) {
this.desc = desc;
}
@Override
public String toString() {
return super.toString() + " " + desc;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
@Slf4j
public class TestABAAtomicMarkableReference {
public static void main(String[] args) throws InterruptedException {
GarbageBag bag = new GarbageBag("装满了垃圾");
// 参数2 mark 可以看作一个标记,表示垃圾袋满了
AtomicMarkableReference<GarbageBag> ref = new AtomicMarkableReference<>(bag, true);
log.debug("主线程 start...");
GarbageBag prev = ref.getReference();
log.debug(prev.toString());
new Thread(() -> {
log.debug("打扫卫生的线程 start...");
bag.setDesc("空垃圾袋");
while (!ref.compareAndSet(bag, bag, true, false)) {}
log.debug(bag.toString());
}).start();
Thread.sleep(1000);
log.debug("主线程想换一只新垃圾袋?");
boolean success = ref.compareAndSet(prev, new GarbageBag("空垃圾袋"), true, false);
log.debug("换了么?" + success);
log.debug(ref.getReference().toString());
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
输出
2019-10-13 15:30:09.264 [main] 主线程 start...
2019-10-13 15:30:09.270 [main] cn.itcast.GarbageBag@5f0fd5a0 装满了垃圾
2019-10-13 15:30:09.293 [Thread-1] 打扫卫生的线程 start...
2019-10-13 15:30:09.294 [Thread-1] cn.itcast.GarbageBag@5f0fd5a0 空垃圾袋
2019-10-13 15:30:10.294 [main] 主线程想换一只新垃圾袋?
2019-10-13 15:30:10.294 [main] 换了么?false
2019-10-13 15:30:10.294 [main] cn.itcast.GarbageBag@5f0fd5a0 空垃圾袋
2
3
4
5
6
7
可以注释掉打扫卫生线程代码,再观察输出