CAS (Compare-and-Swap) 是一种硬件上, 实现非锁同步的一种方法. 这种方法比传统的blocked方法在硬件上实现, 效率高而且内存命中率高.

CAS实现的是一种先验的赋值方法, 即: 给出一个当前值v, 当想改变这个当前值的时候, 一个线程需要进行先验操作, 以当前线程为观察者, 查看改变对象是否是当前线程中期待的对象的值. 如果是才去改变它.  整个行为并非通过锁住线程实现的, 而在硬件上, 访问一个内存片段上的速度远远快于在更高层锁住当前线程的速度. 所以CAS被认为是比所要快速的实现原子化操作的方法之一.CAS 和 CAS2 被用在了Java自带的AtomicInteger, AtomicBoolean, AtomicReference上. 这些变量都是可以常常用作判断线程进行状态的flag. 传统的关键字volatile只保证了变量的visibility, 却缺乏了accessibility. 而使用Java自带的原子变量, 可以更有效的, 快速的解决并发的实际问题.

一个CAS的赋值操作, 由一个pair组成: (expectedCurrentValue, newValue). 当赋值实现了CAS的变量一个新值的时候, 先验当前值是否等于expectedCurrentValue, 如果等于, 则赋newValue, 否则返回CAS变量的值, 这样, 通过比较返回的值, 就可以知道是否赋值成功.

通过以上的CAS, 延伸出了ConcurrentStack (Treiber, 1986), Non-blocking Queue (Michael and Scoot, 1996) 等non-blocking的数据结构. 这些数据结构因为更贴近硬件操作并且是线程安全的, 所以在新的JVM中, 很多Concurrent的数据结构都使用了这种CAS的思想.

但是设计一个CAS的数据结构, 需要充分理解数据结构在并发下的state机制, 设置一个或者两个CAS的flag解决对个state之间转换, 来增加运行速度, 当CAS的变量过多, 并发下, 其实与blocked的数据结构比并没有太大优势.