CAS?
比较并交换(compare and swap, CAS)，是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。 该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。
CAS应用
在应用中CAS可以用于实现无锁数据结构，常见的有无锁队列(先入先出) 以及无锁堆(先入后出)。对于可在任意位置插入数据的链表以及双向链表，实现无锁操作的难度较大。
CAS实现
CAS操作基于CPU提供的原子操作指令实现。对于Intel X86处理器，可通过在汇编指令前增加LOCK前缀来锁定系统总线，使系统总线在汇编指令执行时无法访问相应的内存地址。而各个编译器根据这个特点实现了各自的原子操作函数。
- C语言，C11的头文件<stdatomic.h>。由GNU提供了对应的__sync系列函数完成原子操作。
- C++11，STL提供了atomic系列函数。
- JAVA，sun.misc.Unsafe提供了compareAndSwap系列函数。
- C#，通过Interlocked方法实现。
- Go， 通过import "sync/atomic"包实现。
- Windows，通过Windows API实现了InterlockedCompareExchangeXYZ系列函数。
什么是原子操作？
所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch （切换到另一个线程）
image.png
假定有两个操作A和B(A和B可能都很复杂)，如果从执行A的线程来看，当另一个线程执行B时，要么将B全部执行完，要么完全不执行B，那么A和B对彼此来说是原子的
- 实现原子操作可以使用锁，锁机制，满足基本的需求是没有问题的了，但是有的时候我们的需求并非这么简单，我们需要更有效，更加灵活的机制，
synchronized关键字是基于阻塞的锁机制，也就是说当一个线程拥有锁的时候，访问同一资源的其它线程需要等待，直到该线程释放锁，
**这里会有些问题：
1、首先，如果被阻塞的线程优先级很高很重要怎么办？
2、其次，如果获得锁的线程一直不释放锁怎么办？（这种情况是非常糟糕的）
3、还有一种情况，如果有大量的线程来竞争资源，那CPU将会花费大量的时间和资源来处理这些竞争，同时，还有可能出现一些例如死锁之类的情况
4、其实锁机制是一种比较粗糙，粒度比较大的机制，相对于像计数器（一个计算器，我要实现简单的加减，但是这个计算器是可以多线程条件下使用的）这样的需求有点儿过于笨重。
** - 一个CAS操作的过程可以用以下c代码表示:
int cas(long *addr, long old, long new)
{
/* Executes atomically. */
if(*addr != old)
return 0;
*addr = new;
return 1;
}
如何实现原子操作？
image.png
实现原子操作还可以使用当前的处理器基本都支持CAS()的指令，只不过每个厂家所实现的算法并不一样，每一个CAS操作过程都包含三个运算符：一个内存地址V，一个期望的值A和一个新值B，操作的时候如果这个地址上存放的值等于这个期望的值A，则将地址上的值赋为新值B，否则不做任何操作。
CAS的基本思路就是，如果这个地址上的值和期望的值相等，则给其赋予新值，否则不做任何事儿，但是要返回原值是多少。循环CAS就是在一个循环里不断的做cas操作，直到成功为止
CAS实现原子操作的三大问题?
ABA问题
-
ABA问题是无锁结构实现中常见的一种问题，可基本表述为：
进程P1读取了一个数值A
P1被挂起(时间片耗尽、中断等)，进程P2开始执行
P2修改数值A为数值B，然后又修改回A
P1被唤醒，比较后发现数值A没有变化，程序继续执行。
对于P1来说，数值A未发生过改变，但实际上A已经被变化过了，继续使用可能会出现问题。在CAS操作中，由于比较的多是指针，这个问题将会变得更加严重 -
ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加1，那么A→B→A就会变成1A→2B→3A。
循环时间长开销大。
自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。
只能保证一个共享变量的原子操作
当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁。
还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量i＝2，j=a，合并一下ij=2a，然后用CAS来操作ij。从Java 1.5开始，JDK提供了AtomicReference类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行CAS操作。
Jdk中相关原子操作类的使用
image.png
AtomicInteger
image.png
•int addAndGet（int delta）：以原子方式将输入的数值与实例中的值（AtomicInteger里的value）相加，并返回结果。
•boolean compareAndSet（int expect，int update）：如果输入的数值等于预期值，则以原子方式将该值设置为输入的值。
•int getAndIncrement()：以原子方式将当前值加1，注意，这里返回的是自增前的值。
•int getAndSet（int newValue）：以原子方式设置为newValue的值，并返回旧值。
AtomicIntegerArray
主要是提供原子的方式更新数组里的整型，其常用方法如下。
•int addAndGet（int i，int delta）：以原子方式将输入值与数组中索引i的元素相加。
•boolean compareAndSet（int i，int expect，int update）：如果当前值等于预期值，则以原子方式将数组位置i的元素设置成update值。
需要注意的是，数组value通过构造方法传递进去，然后AtomicIntegerArray会将当前数组复制一份，所以当AtomicIntegerArray对内部的数组元素进行修改时，不会影响传入的数组。
更新引用类型
原子更新基本类型的AtomicInteger，只能更新一个变量，如果要原子更新多个变量，就需要使用这个原子更新引用类型提供的类。
Atomic包提供了以下3个类。
AtomicReference
原子更新引用类型。
AtomicStampedReference
利用版本戳的形式记录了每次改变以后的版本号，这样的话就不会存在ABA问题了。这就是 AtomicStampedReference的解决方案,AtomicMarkableReference跟 AtomicStampedReference差不多， AtomicStampedReference是使用pair的int stamp作为计数器使用，AtomicMarkableReference的pair使用的是boolean mark。
AtomicStampedReference可能关心的是动过几次，AtomicMarkableReference关心的是有没有被人动过，方法都比较简单。
AtomicMarkableReference：
原子更新带有标记位的引用类型。可以原子更新一个布尔类型的标记位和引用类型。构造方法是AtomicMarkableReference（V initialRef，booleaninitialMark
总结
更新基本类型类：AtomicBoolean，AtomicInteger，AtomicLong
更新数组类：AtomicIntegerArray，AtomicLongArray，AtomicReferenceArray
更新引用类型：AtomicReference，AtomicMarkableReference，AtomicStampedReference
网友评论