JAVA并发——CAS算法原理

什么是CAS(Compare And Swap)？

CAS(Compare And Swap)是一种无锁的原子算法，是一条CPU的原子指令，其作用是让CPU先进行比较两个值是否相等，然后原子地更新某个位置的值，其实现方式是基于硬件平台的汇编指令，在CPU中，使用的是cmpxchg指令，就是说CAS是靠硬件实现的，从而在硬件层面提升效率。CAS应用的场景：简单的数据计算   适合线程冲突少的场景

       悲观锁 ：写的多一些（增删改）读的（查）少，会引起数据不一致性
       乐观锁 ：读多，写少   一般会版本的控制，对修改的对象给一个版本号（cas属于乐观锁）

多线程开发中最严重的问题就是数据不一致性，通常使用synchronized（jdk的内置锁）保证数据的原子性、有序性、可见性  ，但是其封装力度太大，影响性能。 volatile可保证可见性  有序性，但不能保证原子性。所以jdk1.5后引入了CAS工具类(位于java.util.concurrent.atomic包下)

基于CAS的原子操作类有

cas算法的基本思想：
        如果需要修改一个值，会给一个期望值，和现有的值比较，如果相等就是需要修改的，如果不相等，表示不能修改，什么事情都不做，这就会导致经典的问题  ABA 问题

什么是ABA问题？

       CAS需要检查操作值有没有发生改变，如果没有发生改变则更新。但是存在这样一种情况：如果一个值原来是A，变成了B，然后又变成了A，那么在CAS检查的时候会发现没有改变，但是实质上它已经发生了改变，这就是所谓的ABA问题。对于ABA问题其解决方案是加上版本号，即在每个变量都加上一个版本号，每次改变时加1，即A —> B —> A，变成1A —> 2B —> 3A。

cas算法的优点：
        相对synchronized是比较“乐观的”，由于CAS是非阻塞的，不会存在死锁问题，并且线程间的相互影响也非常小，不存在阻塞，提高效率，cpu的吞吐量就高了

cas算法的缺点：

• 循环时间太长

       如果CAS一直不成功呢？这种情况绝对有可能发生，如果自旋CAS长时间地不成功，则会给CPU带来非常大的开销。在JUC （java.util.concurrent）中有些地方就限制了CAS自旋的次数，例如BlockingQueue的SynchronousQueue。

• 只能保证一个共享变量原子操作

       看了CAS的实现就知道这只能针对一个共享变量，如果是多个共享变量就只能使用锁了，当然如果你有办法把多个变量整成一个变量，利用CAS也不错。例如读写锁中state的高地位

• ABA问题

       上面已经解释过了

底层原理

首先了解下CPU 实现原子指令的2种方式：

1. 通过总线锁定来保证原子性。

总线锁定其实就是处理器使用了总线锁，所谓总线锁就是使用处理器提供的一个 LOCK# 信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存。但是该方法成本太大。因此有了下面的方式。

2、通过缓存锁定来保证原子性。

所谓 缓存锁定 是指内存区域如果被缓存在处理器的缓存行中，并且在Lock 操作期间被锁定，那么当他执行锁操作写回到内存时，处理器不在总线上声言 LOCK# 信号，而时修改内部的内存地址，并允许他的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改两个以上处理器缓存的内存区域数据（这里和 volatile 的可见性原理相同），当其他处理器回写已被锁定的缓存行的数据时，会使缓存行无效。

注意：有两种情况下处理器不会使用缓存锁定。

1. 当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行时，则处理器会调用总线锁定。

2. 有些处理器不支持缓存锁定，对于 Intel 486 和 Pentium 处理器，就是锁定的内存区域在处理器的缓存行也会调用总线锁定。

CAS原理分析

以实现CAS的AtomicInteger类

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

AtomicInteger代码片段：

  

   

    

     

    
    

     

      public 
      class AtomicInteger extends Number implements java.io.Serializable {
     
    
   

    

     

    
    

     
    
      private 
      static 
      final 
      long serialVersionUID = 
      6214790243416807050L;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    
      // setup to use Unsafe.compareAndSwapInt for updates
     
    
   

    

     

    
    

     
    
      private 
      static 
      final Unsafe unsafe = Unsafe.getUnsafe();
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    
      //内存中的偏移地址，unsafe通过偏移地址来得到数据的原值
     
    
   

    

     

    
    

     
    
      private 
      static 
      final 
      long valueOffset;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    
      static {
     
    
   

    

     

    
    

     
        
      try {
     
    
   

    

     

    
    

     

                  valueOffset = unsafe.objectFieldOffset
     
    
   

    

     

    
    

     

                      (AtomicInteger.class.getDeclaredField(
      "value"));
     
    
   

    

     

    
    

     

              } 
      catch (Exception ex) { 
      throw 
      new Error(ex); }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      //当前值，保证了多线程环境下的可见性
     
    
   

    

     

    
    

     
    
      private 
      volatile 
      int value;
     
    
   

    

     

    
    

     

      }
     
    
  

 内部调用unsafe的getAndAddInt方法，在getAndAddInt方法中主要是看compareAndSwapInt方法：

CAS可以保证一次的读-改-写操作是原子操作，在单处理器上该操作容易实现，但是在多处理器上会使用缓存加锁：其实针对于上面那种情况我们只需要保证在同一时刻对某个内存地址的操作是原子性的即可。缓存加锁就是缓存在内存区域的数据如果在加锁期间，当它执行锁操作写回内存时，处理器不在输出LOCK#信号，而是修改内部的内存地址，利用缓存一致性协议来保证原子性。缓存一致性机制可以保证同一个内存区域的数据仅能被一个处理器修改，也就是说当CPU1修改缓存行中的i时使用缓存锁定，那么CPU2就不能同时缓存了i的缓存行