原子操作的实现原理

原子(atomic)指的是“不能被进一步分割的最小粒子”，原子操作指的是“不可被中断的一个或一系列操作”。在多处理器上实现原子操作就会变得很复杂。

处理器如何实现原子操作

32位IA32处理器使用的是基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作。首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存中读取或者写入一个字节是原子的，意思是当一个处理器读取一个原子时，其他处理器不能访问这个字节的内存地址。现代的处理器能自动保证其原子性，比如跨总线宽度，跨多个缓存行和跨页表的访问。但是，处理器提供总线锁定和缓存锁定两个机制来保证内存操作的原子性。

使用总线保证原子性

如果多个处理器同时对共享变量进行读改写操作（比如i++），那么共享变量就会被多个处理器同时进行操作，这样读改写操作就不是原子的，操作完之后共享变量的值会和期望的不一致。

比如i=1，进行两次i++操作，期望的结果是3，但是有可能结果是2

原因可能是多个处理器同时从各自的缓存中读取变量i，分别进行加1操作，然后分别写入系统内存中。那么，想要保证读改写共享变量的操作是原子的，就必须保证CPU1读改写共享变量的时候，CPU2不能操作缓存了该共享变量内存地址的缓存。

所以处理器使用总线锁来解决这个问题。

总线锁就是使用处理器提供的一个LOCK#信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器就可以独享共享内存。

使用缓存锁保证原子性

使用总线锁的时候把CPU和内存之间的通信锁住了，这使得锁定期间，其他处理器不能操作其他内存地址的数据，所以总线锁定的开销比较大，目前处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。

频繁使用的内存会缓存在处理器的L1，L2，L3告诉缓存里，那么原子操作就可以直接在处理器内部缓存中进行，并不需要声明总线锁，现代处理器中就可以使用“缓存锁定”方式来实现复杂的原子性，那么当他执行锁操作回写到内存时，处理器不在总线上声明LOCK#信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会同时修改由两个以上处理器缓存的内存区域数据，当其他处理器回写已被锁定的缓存行的数据时，会使缓存行无效。

但是两种情况下处理器不会使用缓存锁定

操作的数据不能被缓存在处理器内部，或操作的山上跨多个缓存行时，则处理器会调用总线锁定。
有些处理器不支持缓存锁定。

Java如何实现原子操作

java中可以通过锁和循环CAS的方式来实现原子操作。

使用循环CAS实现原子操作

JVM中的CAS操作就是利用了处理器提供的CMPXCHG指令实现的。自旋CAS实现的基本思路就是循环进行CAS操作知道成功为止。

下面是一个基于CAS线程安全的计数器方法safeCount和一个非线程安全的计数器count。

public class Counter {
    private AtomicInteger atomicI = new AtomicInteger(0);
    public static void main(String... args) {
        final Counter cas = new Counter();
        List<Thread> ts = new ArrayList<>(600);
        long start = System.currentTimeMillis();
        for (int j = 0; j < 100; j++) {
            Thread t = new Thread(() -> {
                for(int i = 0; i < 10000; i++) {
					cas.count();
                    cas.safeCount();
                }
            });
            ts.add(t);
        }
        for(Thread t: ts) {
            t.start();
        }
        for(Thread t: ts) {
            try {
                t.join();
            } cache (InterruptedException e) {
                e.printStackTrace();
            }
        }
        System.out.println(cas.i);
        System.out.println(cas.atomicI.get());
        System.out.println(System.currentTimeMillis() - start);
    }
    private void safeCount() {
        for(;;) {
            int i = atomicI.get();
            boolean suc = atomicI.compareAndSet(i, ++i);
            if (suc) break;
        }
    }
    // 非线程安全计数器
    private void count() {
        i++;
    }
}

从Java5开始，jdk的并发包里提供了原子类，包括以原子的方式将当前值自增1和自减1

CAS实现原子操作的问题

ABA问题

因为CAS需要在操作值的时候，检查值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。

ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候将版本号加1，那么A->B->A就会变成1A->2B->3A。从Java5开始，JDK的Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的新值。