无锁编程和比较并交换Compare-And-Swap

转自：无锁编程和比较并交换Compare-And-Swap（CAS）


对操作都用synchronized关键字进行修饰，保证对属性a的同步访问，虽然可以保证在并发环境下a的一致性，但是由于使用了锁，锁的开销，线程的调度等等会使得程序的伸缩性受到了限制，于是就有了很多无锁的实现方式。
无锁编程 / lock-free / 非阻塞同步
无锁编程，即不使用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。
实现非阻塞同步的方案称为"无锁编程算法"（Non-blocking algorithm）。lock-free是目前最常见的无锁编程的实现级别。
为什么要 Non-blocking sync
使用lock实现线程同步有很多缺点：
* 产生竞争时，线程被阻塞等待，无法做到线程实时响应。
* dead lock。
* live lock。
* 优先级翻转。
* 使用不当，造成性能下降。
如果在不使用 lock 的情况下，实现变量同步，那就会避免很多问题。虽然目前来看，无锁编程并不能替代 lock。
实现级别
1
2
AtomicInteger atom = new AtomicInteger(1);
boolean r = atom.compareAndSet(1, 2);
1. incrementAndGet的实现
1
2
3
4
5
6
7
8
    public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
    }
首先可以看到他是通过一个无限循环（spin）直到increment成功为止。
循环的内容是：
1. 取得当前值；2. 计算+1后的值；3. 如果当前值还有效（没有被）的话设置那个+1后的值；4. 如果设置没成功（当前值已经无效了即被别的线程改过了），再从1开始。
2. compareAndSet的实现
1
2
3
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
直接调用的是UnSafe这个类的compareAndSwapInt方法。
全称是sun.misc.Unsafe，这个类是Oracle(Sun)提供的实现，可以在别的公司的JDK里就不是这个类了。
3. compareAndSwapInt的实现
1
2
3
4
5
6
7
8
    /**
     * Atomically update Java variable to x if it is currently
     * holding expected.
     * @return true if successful
     */
    public final native boolean compareAndSwapInt(Object o, long offset,
                                                  int expected,
                                                  int x);
可以看到，不是用Java实现的，而是通过JNI调用操作系统的原生程序，可以猜到是JVM调用了处理器本身的CAS指令来实现原子的操作。
基本上AtomicInteger类型的重要方法都是采用无锁的方式实现的。因此在并发环境下，用这种类型能有更好的性能。


转载请并标注: “本文转载自 linkedkeeper.com (文／张松然)”


时间：