原子操作CAS

CAS

悲观锁

具有强烈的独占和排他特性。在有悲观锁的情况下，对数据进行处理，数据会处于锁定状态。前面讲到的synchronized同一时间只允许一个线程访问某块资源，其他线程处于阻塞状态，就是一个独占锁，是悲观锁中的一种。悲观锁适用于写操作比较多的场景。

乐观锁

对数据有更加宽松的加锁机制，允许多个线程同时访问对某块资源，一般通过版本号机制+CAS来实现。乐观锁适用于读操作比较多的场景。

CAS原理

CAS目的：保证在同一时间，只有一个线程能够更新值。

CAS基本流程：

• 读取内存（地址i）中共享变量的值A，作为旧址
• 业务逻辑处理得到值B
• 读取相同共享变量（地址i）的值C，作为新值
• 比较A和C是否相等
• 相等就修改变量(地址)的值为B
• 不等就自旋从第一步开始即Retry-Loop实现

在这个过程中，CPU会通过总线锁定机制来保证CAS操作的原子性，即在CAS操作期间，其他线程无法访问被操作的内存地址。由CPU底层硬件保证的。

对于Retry-Loop，感觉其实和锁什么什么两样。只是这种“锁”的粒度变小了，主要是“锁”关键资源，而不是整个数据结构。

自旋锁的实现依赖于CAS（Compare and Swap）操作，这是一种硬件级别的原子操作。

实现

CAS（Compare-and-Swap）通常使用类似cmpxchg指令实现的，cmpxchg（Compare-and-Exchange）指令是一种原子操作的CPU指令。例如

unsigned long cmpxchg(void *addr, unsigned long _old, unsigned long _new)
{
  int *a = addr; //或者用volatile int a;
  if(*a == _old){
    *a = _new;
  }
  return _old;
}

cmpxchg是设置一个新值，返回旧值。返回旧值可以做一些其他的业务操作。

CAS也是设置一个新值，但是可以自定义返回一个bool量。

例如：

bool compare_and_swap (int *addr, int oldval, int newval)
{
  if ( *addr != oldval ) {
      return false;
  }
  *addr = newval;
  return true;
}

volatile

内存中value值通过volatile进行修饰，保证了该属性值的线程可见性。在多并发的情况下，一个线程的修改，可以保证到其他线程立马看到修改后的值。

ABA问题

虽然使用CAS可以实现非阻塞式的原子性操作，但是会产生ABA问题，ABA问题出现的基本流程：

• 进程P1在共享变量中读到值为A；
• P1被抢占了，进程P2执行；
• P2把共享变量里的值从A改成了B，再改回到A，此时被P1抢占；
• P1回来看到共享变量里的值没有被改变，于是继续执行；

虽然P1以为变量值没有改变，继续执行了，但是这个会引发一些潜在的问题。ABA问题最容易发生在lock free的算法中的，CAS首当其冲，因为CAS判断的是指针的地址。如果这个地址被重用了呢，问题就很大了（地址被重用是很经常发生的，一个内存分配后释放了，再分配，很有可能还是原来的地址）。

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