原子类：无锁工具类的典范

//累加器
public class Test {
    long count = 0;
    void add10K() {
        int idx = 0;
        whlie(idx++ < 10000) {
            count += 1;
        }
    }
}

add10K()这个方法不是线程安全的，变量count的可见性和count+=1的原子性都是问题。可见性问题可以用volatile来解决，原子性问题采用互斥锁方案。

对于简单的原子性问题，还可以采用无锁方案-Java SDK并发包中的原子类。

public class Test {
    AtomicLong count = new AtomicLong(0);
    void add10K() {
        int idx = 0;
        while(idx++ < 10000) {
            count.getAndIncrement();
        }
    }
}

无锁方案相对互斥锁方案，最大的好处就是性能。互斥锁方案为了保证互斥性，需要执行加锁、解锁操作，而加锁、解锁操作本身就消耗性能；同时拿不到锁的线程还会进入阻塞状态，进而触发线程切换，线程切换对性能的消耗也很大。无锁方案则没有这些问题。

无锁方案的实现原理

原子类性能高是硬件支持的原因。CPU为了解决并发问题，提供了CAS指令(Compare And Swap, 比较并交换)。CAS指令包含了3个参数：共享变量的内存地址A、用于比较的值B和共享变量的新值C：并且只有当内存中地址A处的值等于B时，才能将内存中地址A处的值更新为新值C。作为一条CPU指令，CAS指令本身是能够保证原子性的。

class SimulatedCAS {
    int count;
    synchronized int cas(int expect, int newValue) {
        //读目前count的值
        int curValue = count;
        //比较目前count值是否==期望值
        if(curValue == expect) {
            //如果是，则更新count的值
            count = newValue;
        }
        //返回写入前的值
        return curValue;
    }
}
//只有当目前count的值和期望值expect相等时，才会将count更新为newValue

使用CAS来解决并发问题，一般都会伴随着循环尝试-自旋。

class SimulatedCAS {
    volatile int count;
    //实现count+=1
    addOne() {
        do {
            newValue = count+1;
        } while(count != cas(count, newValue));
    }

    //模拟实现CAS
    //(CAS大部分是CPU提供的指令，这里是模拟实现，实际没有synchronized)
    //多处理器计算机指令TSL(test and set lock)，硬件支持的互斥方案，
    //执行这个指令的CPU将锁住内存总线，以禁止其它CPU在本指令结束之前访问内存
    synchronized int cas(int expect, int newValue) {
        int curValue = count;
        if(cutValue == expect) {
            count = newValue;
        }
        return curValue;
    }
}

CAS方案中，可能会产生ABA问题。
方案中”如果cas(count,newValue)返回的值不等于count，意味着线程在执行完do后，执行while之前，count的值被其他线程更新过”，如果cas(count,newValue)返回的值等于count，并不能认为count的值没被其他线程更新过。假设count原本是A，线程T1在执行完代码do之后，执行代码while之前，有可能count被线程T2更新成了B，之后又被线程T3更新回了A，这样线程T1虽然看到的一直是A，但是其实已经被其他线程更新过了，这就是ABA问题。

大多数情况下ABA不会产生问题，如数值的原子递增。但原子化的更新对象需要关心ABA问题，虽然两个A相等，但是第二个A的属性可能已经发生变化了。

Java实现原子化的递增

原子类AtomicLong的getAndIncrement()方法内部是基于CAS实现的。
在Java1.8版本中，getAndIncrement()方法会转调unsafe.getAndAddLong()方法。(unsafe的命名和多线程无关)

final long getAndIncrement() {
    return unsafe.getAndAddLong(this, valueOffset, 1L);
}
//this和valueOffset两个参数可以唯一确定共享变量的内存地址  

public final long getAndAddLong(Object o, long offset, long delta) {
    long v;
    do {
        //读取内存中的值
        v = getLongVolatile(o, offset);
    } whlie(!compareAndSwapLong(o, offset, v, v+delta));
    return v;
}

//原子性的将变量更新为x
//条件是内存中的值等于expected
//更新成功则返回true
native boolean compareAndSwapLong(Object o, long offset, long expected, long x);
//该native方法的语义和CAS指令的语义的差别仅仅是返回值不同而已

getAndAddLong()方法的实现，是CAS使用的经典范例。在很多无锁程序中经常出现。
Java提供的原子类里面CAS一般被实现为compareAndSet()。与CAS指令的语义差别也仅仅是返回值不同而已。

do {
    //获取当前值
    oldV = xxx;
    //根据当前值计算新值
    newV = ...oldV...;
} while(!compareAndSet(oldV,newV));

原子类概览

Java SDK并发包里的原子类可以分为五个类别：

原子化的基本数据类型
原子化的对象引用类型
原子化数组
原子化对象属性更新器
原子化的累加器

原子化的基本数据类型

相关实现有AtomicBoolean、AtomicInteger、AtomicLong。

getAndIncrement() //原子化的i++  
getAndDecrement() //原子化的i--  
incrementAndGet() //原子化的++i  
decrementAndGet() //原子化的--i  
//当前值+=delta，返回+=前的值
getAndAdd(delta)
//当前值+=delta，返回+=后的值
addAndGet(delta)
//CAS操作，返回是否成功
compareAndSet(expect, update)
//以下四个方法，新值可以通过传入func函数来计算
getAndUpdate(func)
updateAndGet(func)
getAndAccumulate(x, func)
accumulateAndGet(x, func)

原子化的对象引用类型

相关实现有AtomicReference、AtomicStampedReference、AtomicMarkableReference。
利用它们可以实现对象引用的原子化更新。

AtomicReference提供的方法和原子化的基本数据类型类似。
对象引用的更新需要重点关注ABA问题，AtomicStampedeReference和AtomicMarkableReference这两个原子类可以解决ABA问题。

解决ABA问题增加一个版本号维度就可以了。和StampedLock介绍的乐观锁机制很类似，每次执行CAS操作，附加再更新一个版本号，只要保证版本号是递增的，那么即便是A变成B之后再变回A，版本号也不会变回来(版本号递增的)。

AtomicStampedeReference实现的CAS方法增加了版本号参数

1	boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp)

AtomicMarkableReference将版本号简化成了一个Boolean值

1	boolean compareAndSet(V expectedReference, V newReference, boolean expectedMark, boolean newMark)

原子化数组

相关实现有AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray。
利用这些原子类，可以原子化的更新数组里面的每一个元素。

这些类提供的方法和原子化的基本数据类型的区别是：每个方法多了一个数组的索引参数。

原子化对象属性更新器

相关实现有AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater。
利用它们可以原子化的更新对象的属性。

这三个方法都是利用反射机制实现的

1	public static <U> AtomicXXXFieldUpdater<U> newUpdater(Class<U> clazz, String fieldName)

对象属性必须是volatile类型的，只有这样才能保证可见性；如果对象属性不是volatile类型的，newUpdater()方法会抛出IllegalArgumentException运行时异常。

newUpdater()的方法参数只有类的信息，没有对象的引用，而更新对象的属性，一定需要对象的引用，这个参数是在原子操作的方法参数中传入的。
compareAndSet()这个原子操作，相比原子化的基本数据类型多了一个对象引用obj。原子化对象属性更新器相关的方法，相比原子化的基本数据类型仅仅是多了对象引用参数。

1	boolean compareAndSet(T obj, int expect, int update)

原子化的累加器

DoubleAccumulator、DoubleAdder、LongAccumulator、LongAdder。
这四个类仅用来执行累加操作，相比原子化的基本数据类型，速度快，但是不支持compareAndSet()方法。

总结

无锁方法相对于互斥锁方案，性能好，基本不会出现死锁问题(但是可能出现饥饿和活锁问题，自旋会反复重试)。

Java提供的原子类大部分都实现了CompareAndSet()方法，基于这个方法，可以构建自己的无锁数据结构。

Java提供的原子类能够解决一些简单的原子性问题，但是所有原子类的方法都是针对一个共享变量的，如果需要解决多个变量的原子性问题，需要使用互斥锁方案。