谈谈CAS

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

1、简介

CAS（Compare and Swap），即比较并替换，实现并发算法时常用到的一种技术，Doug lea大神在java同步器中大量使用了CAS技术，鬼斧神工的实现了多线程执行的安全性。

CAS的思想很简单：三个参数，一个当前内存值V、旧的预期值A、即将更新的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做，并返回false。

和CAS相关的一个概念是原子操作，什么是原子呢？原子是不能被进一步分割的最小粒子，而原子操作则是不可被中断的一个或一系列操作。而CAS则是Java中保证原子操作的一种方式。从Java1.5开始，JDK的并发包里就提供了一些类来支持原子操作，都是以Atomic开头。

之前讲volatile的时候说过，volatile不能保证类似i++这样操作的原子性，那么CAS为什么能够保证原子性呢？原理是什么呢？这得从JVM指令说起。

2、原理分析

Atomic包下的类都调用了Unsafe的compareAndSwap*方法来实现CAS操作，它是一个本地方法，实现位于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);
  jint* addr =(jint *)index_oop_from_field_offset_long(p, offset);
return(jint)(Atomic::cmpxchg(x, addr, e))== e;
UNSAFE_END

可以看到它通过 Atomic::cmpxchg 来实现比较和替换操作。其中参数x是即将更新的值，参数e是原内存的值。

如果是Linux的x86，Atomic::cmpxchg方法的实现如下：

inline jint Atomic::cmpxchg(jint exchange_value,volatile jint* dest, jint compare_value){
int mp = os::is_MP();
  __asm__ volatile(LOCK_IF_MP(%4)"cmpxchgl %1,(%3)"
:"=a"(exchange_value)
:"r"(exchange_value),"a"(compare_value),"r"(dest),"r"(mp)
:"cc","memory");
return exchange_value;
}

而windows的x86的实现如下：

inline jint Atomic::cmpxchg(jint exchange_value,volatile jint* dest, jint compare_value){
int mp = os::isMP();//判断是否是多处理器
    _asm {
        mov edx, dest
        mov ecx, exchange_value
        mov eax, compare_value
LOCK_IF_MP(mp)
        cmpxchg dword ptr [edx], ecx
}
}
// Adding a lock prefix to an instruction on MP machine
// VC++ doesn"t like the lock prefix to be on a single line
// so we can"t insert a label after the lock prefix.
// By emitting a lock prefix, we can define a label after it.
#define LOCK_IF_MP(mp) __asm cmp mp,0
                       __asm je L0      
                       __asm _emit 0xF0
                       __asm L0:

如果是多处理器，为cmpxchg指令添加lock前缀。反之，就省略lock前缀（单处理器会不需要lock前缀提供的内存屏障效果）。这里的lock前缀就是使用了处理器的总线锁（最新的处理器都使用缓存锁代替总线锁来提高性能）。

cmpxchg(void* ptr, int old, int new)，如果ptr和old的值一样，则把new写到ptr内存，否则返回ptr的值，整个操作是原子的。在Intel平台下，会用lock cmpxchg来实现，使用lock触发缓存锁，这样另一个线程想访问ptr的内存，就会被block住。

更多lock指令相关的可以参考之前写volatile的一篇文章：【细谈Java并发】内存模型之volatile

3、CAS的三大问题

3.1、ABA问题

因为CAS需要在操作值的时候，检查值有没有发生变化，比如没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时则会发现它的值没有发生变化，但是实际上却变化了。

ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加1，那么A->B->A就会变成1A->2B->3A。

从Java 1.5开始，JDK的Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

3.2、循环时间长开销大

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

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

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁。

还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量i = 2，j = a，合并一下ij = 2a，然后用CAS来操作ij。

从Java 1.5开始，JDK提供了AtomicReference类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行CAS操作。

转载自：谈谈 CAS

以上是 谈谈CAS 的全部内容， 来源链接： utcz.com/z/515482.html

回到顶部