1. 原子操作
原子操作（atomic operation）意为”不可被中断的一个或一系列操作” 。在多处理器上实现原子操作就变得有点复杂。本文让我们一起来聊一聊在Inter处理器和Java里是如何实现原子操作的。
1.1 相关术语
| 术语 | 术语描述 |
|---|---|
| 内存屏障 | 用一组处理器指令，用于实现对内存操作的顺序限制 |
| 缓冲行 | 缓存中可以分配的最小存储单位。处理器填写缓存线时会加载整个缓存线，需要使用多个主内存读周期 |
| 原子操作 | 不可中断的一个或一系列操作 |
| 缓存行填充 | 当处理器识别到从内存中读取操作数是可缓存的，处理器读取整个缓存行到适当的缓存(L1、L2、L3的或所有) |
| 缓存命中 | 如果进行高速缓存行填充操作的内存位置仍然是下次处理器访问的地址时，处理器从缓存中读取操作数，而不是从内存读取 |
| 写命中 | 当处理器将操作数写回到一个内存缓存的区域时，它首先会检查这个缓存的内存地址是否在缓存行中，如果存在一个有效的缓存行，则处理器将这个操作数写回到缓存，而不是写回到内存，这个操作被称为写命中。 |
| 写缺失 | 一个有效的缓存行被写入到不存在的内存区域。 |
1.2 处理器如何实现原子性
1.2.1 总线加锁
使用处理器提供的一个LOCK＃信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存。
1.2.2 缓存加锁
只对单个缓存行的数据加锁。一个处理器的缓存值通过总线回写到内存会导致其他处理器相应的缓存失效：若干个CPU核心通过ringbus连到一起。每个核心都维护自己的Cache的状态。如果对于同一份内存数据在多个核里都有cache，则状态都为S（shared）。一旦有一核心改了这个数据（状态变成了M），其他核心就能瞬间通过ringbus感知到这个修改，从而把自己的cache状态变成I（Invalid），并且从标记为M的cache中读过来。同时，这个数据会被原子的写回到主存。最终，cache的状态又会变为S。
2. Java实现原子性
2.1 CAS
2.1.1 算法
Compare and Swap，即比较再交换。CAS是一种无锁算法，CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。执行CAS操作，但如果期望值与当前线程不符，则说明该值已被其他线程修改，此时不执行更新操作，但可以选择重新读取该变量再尝试再次修改该变量，也可以放弃操作。
2.1.2 底层实现
用处理器提供的CMAPXCHG指令实现
2.1.3 缺陷
在Java并发包中有一些并发框架也使用了自旋CAS的方式来实现原子操作，比如LinkedTransferQueue类的Xfer方法。CAS虽然很高效地解决了原子操作，但是CAS仍然存在三大问题。ABA问题，循环时间长开销大，以及只能保证一个共享变量的原子操作。
2.1.3.1 ABA
问题描述：线程t1将它的值从A变为B，再从B变为A。同时有线程t2要将值从A变为C。但CAS检查的时候会发现没有改变，但是实质上它已经发生了改变 。可能会造成数据的缺失。
解决：CAS还是类似于乐观锁，同数据乐观锁的方式给它加一个版本号或者时间戳，如AtomicStampedReference
2.1.3.2 自旋消耗资源
问题描述：多个线程争夺同一个资源时，如果自旋一直不成功，将会一直占用CPU。
解决：破坏掉for死循环，当超过一定时间或者一定次数时，return退出。JDK8新增的LongAddr,和ConcurrentHashMap类似的方法。当多个线程竞争时，将粒度变小，将一个变量拆分为多个变量，达到多个线程访问多个资源的效果，最后再调用sum把它合起来。
2.1.3.3 多变量共享一致性问题
问题描述：当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性
解决：
- 可以加锁来解决。
- 封装成对象类解决。从Java 1.5开始，JDK提供了
AtomicReference类来保证引用对之间的原子性，就可以把多个变量放在一个对象里来进行CAS操作。
3. Java原子类
从JDK 1.5开始提供了java.util.concurrent.atomic包（以下简称Atomic包），这个包中 的原子操作类提供了一种用法简单、性能高效、线程安全地更新一个变量的方式。
3.1 原子更新基本类型类
主要包含以下三个类
- AtomicBoolean:原子更新布尔类型
- AtomicInteger:原子更新整型
- AtomicLong:原子更新长整型
3.1.1 AtomicInteger主要方法
- int addAndGet（int delta）：以原子方式将输入的数值与实例中的值（AtomicInteger里的 value）相加，并返回结果。
- boolean compareAndSet（int expect，int update）：如果输入的数值等于预期值，则以原子方 式将该值设置为输入的值。
- int getAndIncrement()：以原子方式将当前值加1，注意，这里返回的是自增前的值。
- void lazySet（int newValue）：最终会设置成newValue，使用lazySet设置值后，可能导致其他 线程在之后的一小段时间内还是可以读到旧的值。
- int getAndSet（int newValue）：以原子方式设置为newValue的值，并返回旧值。
3.1.2 getAndIncrement如何工作
public final int getAndIncrement() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return current;
}
}
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
源码中for循环体的第一步先取得AtomicInteger里存储的数值，第二步对AtomicInteger的当前数值进行加1操作，关键的第三步调用compareAndSet方法来进行原子更新操作，该方法先检查当前数值是否等于current，等于意味着AtomicInteger的值没有被其他线程修改过，则将AtomicInteger的当前数值更新成next的值，如果不等compareAndSet方法会返回false，程序会进入for循环重新进行compareAndSet操作。
3.1.3 如何原子的更新其他的基本类型
Unsafe只提供了3种CAS方法：compareAndSwapObject、compare-AndSwapInt和compareAndSwapLong，再看AtomicBoolean源码，发现它是先把Boolean转换成整 型，再使用compareAndSwapInt进行CAS，所以原子更新char、float和double变量也可以用类似的思路来实现。
3.2 原子更新数组
通过原子的方式更新数组里的某个元素，Atomic包提供了以下4个类。
- AtomicIntegerArray:原子更新整型数组里的元素
- AtomicLongArray:原子更新长整型数组里的元素
- AtomicReferenceArray:原子更新引用类型数组里的元素
- AtomicIntegerArray:主要是提供原子的方式更新数组里的整型
3.2.1 AtomicIntegerArray常用方法
- int addAndGet（int i，int delta）：以原子方式将输入值与数组中索引i的元素相加
- boolean compareAndSet（int i，int expect，int update）：如果当前值等于预期值，则以原子 方式将数组位置i的元素设置成update值
数组value通过构造方法传递进去，然后AtomicIntegerArray会将当前数组复制一份，所以当AtomicIntegerArray对内部的数组元素进行修改时，不会影响传入的数组。
3.3 原子更新引用类型
原子更新基本类型的AtomicInteger，只能更新一个变量，如果要原子更新多个变量，就需要使用这个原子更新引用类型提供的类。Atomic包提供了以下3个类。
- AtomicReference：原子更新引用类型
- AtomicReferenceFieldUpdater：原子更新引用类型里的字段
- AtomicMarkableReference：原子更新带有标记位的引用类型
3.4 原子更新字段类
如果需原子地更新某个类里的某个字段时，就需要使用原子更新字段类，Atomic包提供了以下3个类进行原子字段更新。
- AtomicIntegerFieldUpdater：原子更新整型的字段的更新器
- AtomicLongFieldUpdater：原子更新长整型字段的更新器
- AtomicStampedReference：原子更新带有版本号的引用类型。该类将整数值与引用关联起来，可用于原子的更新数据和数据的版本号，可以解决使用CAS进行原子更新时可能出现的ABA问题
参考资料
- 《Java并发编程的艺术》
