CAS

什么是CAS

CompareAndSwap，是一种思想和算法，由CPU指令保证原子性。

我认为V的值应该是A，如果是的话那我就把它改成B，如果不是A(说明被别人修改过了)，那我就不修改了，避免多人同时修改导致出错。

CAS有三个操作数︰内存值V、预期值A、要修改的值B，当且仅当预期值A和内存值V相同时，才将内存值修改为B，否则什么都不做。最后返回bool值。

算法本质

其实是比较简单的

private volatile int value;public synchronized boolean compareAndSwap(int expect,int newValue){int oldValue = value;    if (oldValue == expect){value = newValue;        return true;    }    return false;}

应用场景

乐观锁

数据库在修改的时候可以使用版本号的方式去修改

并发容器

比如ConcurrentHashMap中的put方法就使用到了casTabAt，可以看到名字中就有cas，而它调用了unsafe的native方法compareAndSwapObject。

源码：分析Java如何利用CAS实现原子操作

以AtomicInteger为例：

AtomicInteger加载Unsafe工具，用来直接操作内存数据
用Unsafe来实现底层操作
用volatile修饰value字段，保证可见性
getAndAddInt方法分析

static {try {valueOffset = unsafe.objectFieldOffset            (AtomicInteger.class.getDeclaredField("value"));    } catch (Exception ex) { throw new Error(ex); }}

public final int getAndAddInt(Object var1, long var2, int var4) {int var5;    do {var5 = this.getIntVolatile(var1, var2);    } while(!this.compareAndSwapInt(var1, var2, var5, var5   var4));    return var5;}

Unsafe

Unsafe是CAS的核心类。Java无法直接访问底层操作系统，而是通过本地( native )方法来访问。不过尽管如此，JVM还是开了一个后门，JDK中有一个类Unsafe，它提供了硬件级别的原子操作。

valueOffset表示的是变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的原值的，这样我们就能通过unsafe来实现CAS了。

UNSAFE_ENTRY(jboolean,Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe,jobject obj, jlong offset, jint e, jint x))UnsafeWrapper("Unsafe_CompareAndSwapInt");oop p = JNIHandlesresolve(obj);//通过偏移量得到内存地址jint* addr = (jint *) index_oop_from_field_offset_long(p,offset);//通过内存地址就可以执行CAS了，x为更新的值，e为原值return (jint)(Atomic::cmpxchg(x, addr, e))== e;UNSAFE_END

缺点

ABA问题

自旋时间太长，比如unsafe中使用了do-while循环。这会导致消耗cpu资源。

CAS的深度拓展

CAS的ABA问题

如果在CAS执行间有线程已经实施了一定的操作，但是经过几次修改之后的数据和原来的一样，那么CAS就可能无法判断是否改变过，如果这样的情况不允许发生那么可以使用版本号，或者bool值来解决。

CAS的底层原理

CAS的本质和synchronized相同（LOCK CMPXCHG），汇编中都是采用了指令集的LOCK前缀，即在所对应的指令操作期间使此指令的目标操作数指定的存储区域的北桥信号（每个核心都经过都需要看）锁定，以得到保护。

CMPXCHG：比较交换指令，第一操作数先和AL/AX/EAX比较，如果相等ZF置1，第二操作数赋给第一操作数，否则ZF清0，第一操作数赋给AL/AX/EAX。多处理器安全，在80486及以上CPU中支持。

关于volatile

volatile使用的是LOCK; ADDL $0,0(%%rsp)往某个寄存器中加0，其实就是空指令，主要是使用LOCK来达到内存可见性。

lock前缀的作用

将当前处理器缓存行的数据会写回到系统内存。
这个写回内存的操作会引起在其他 CPU 里缓存了该内存地址的数据无效。

volatile伪共享

解决方便是将高速缓存剩余的字节填充填满(pad)，确保不发生多个字段被挤入一个高速缓存区。

无限扩展等等

来源：https://www.icode9.com/content-1-863101.html

Java并发_6 CAS

CAS