非阻塞同步机制与CAS操作

锁的劣势

Java在JDK1.5之前都是靠synchronized关键字保证同步的，这种通过使用一致的锁定协议来协调对共享状态的访问，可以确保无论哪个线程 持有守护变量的锁，都采用独占的方式来访问这些变量，如果出现多个线程同时访问锁，那第一些线线程将被挂起，当线程恢复执行时，必须等待其它线程执行完他 们的时间片以后才能被调度执行，在挂起和恢复执行过程中存在着很大的开销。锁还存在着其它一些缺点，当一个线程正在等待锁时，它不能做任何事。如果一个线 程在持有锁的情况下被延迟执行，那么所有需要这个锁的线程都无法执行下去。如果被阻塞的线程优先级高，而持有锁的线程优先级低，将会导致优先级反转 (Priority Inversion)。

volatile的优势

与锁相比，volatile变量是一和更轻量级的同步机制，因为在使用这些变量时不会发生上下文切换和线程调度等操作，但是volatile变量也存在一些局限：不能用于构建原子的复合操作，因此当一个变量依赖旧值时就不能使用volatile变量

悲观锁和乐观锁

独占锁是一种悲观锁，synchronized就是一种独占锁，它假设最坏的情况，并且只有在确保其它线程不会造成干扰的情况下执行，会导致其它所 有需要锁的线程挂起，等待持有锁的线程释放锁。而另一个更加有效的锁就是乐观锁。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为 冲突失败就重试，直到成功为止。

CAS操作

Compare and Swap，比较并操作，CPU指令，在大多数处理器架构，包括IA32、Space中采用的都是CAS指令，CAS的语义是“我认为V的值应该为A，如果 是，那么将V的值更新为B，否则不修改并告诉V的值实际为多少”，CAS是项乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线 程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。CAS有3个操作数，内存值V，旧的预期值 A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。

JVM对CAS的支持

在JDK1.5之前，如果不编写明确的代码就无法执行CAS操作，在JDK1.5中引入了底层的支持，在int、long和对象的引用等类型上都公开了 CAS的操作，并且JVM把它们编译为底层硬件提供的最有效的方法，在运行CAS的平台上，运行时把它们编译为相应的机器指令，如果处理器不支持CAS指 令，那么JVM将使用自旋锁。在原子类变量中，如java.util.concurrent.atomic中的AtomicXXX，都使用了这些底层的 JVM支持为数字类型的引用类型提供一种高效的CAS操作，而在java.util.concurrent中的大多数类在实现时都直接或间接的使用了这些 原子变量类。

下面代码说明了CAS的语义（并不是真正的实现，CAS的实现是调用native方法）：

/**
 * Huisou.com Inc.
 * Copyright (c) 2011-2012 All Rights Reserved.
 */

package thread;

import org.apache.http.annotation.GuardedBy;
import org.apache.http.annotation.ThreadSafe;

/**
 * @description
 *
 * @author chenzehe
 * @email [e-mail]
 * @create 2013-1-6 上午09:02:47
 */
@ThreadSafe
public class SimulatedCAS {
    @GuardedBy("this")
    private int    value;

    public synchronized int get() {
        return value;
    }

    public synchronized int comparedAndSwap(int expectedValue, int newValue) {
        int oldValue = value;
        if (oldValue == expectedValue) {
            value = newValue;
        }
        return oldValue;
    }

    public synchronized boolean compareAndSet(int expectedValue, int newValue) {
        return (expectedValue == comparedAndSwap(expectedValue, newValue));
    }
}

下面代码演示了非阻塞计数器：

/**
 * Huisou.com Inc.
 * Copyright (c) 2011-2012 All Rights Reserved.
 */

package thread;

/**
 * @description
 *
 * @author chenzehe
 * @email [e-mail]
 * @create 2013-1-6 上午09:48:52
 */

public class CasCounnter {
    private SimulatedCAS    value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        } while (v != value.comparedAndSwap(v, v + 1));
        return v + 1;
    }
}

AtomicInteger中实现自增的代码为：

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);
}

表面上看起来，基于CAS的计数器似乎比基于锁的计数器在性能上更差一些，因为它还要执行更多的操作和更复杂的控制流，并且还依赖看似复杂的CAS 操作，实际上，当竞争程度不高时，基于CAS的计数器在性能上远远超过了基于锁的计数器，而在没有竞争时甚至更高，如果要快速获取无竞争的锁，那么至少需 要一次CAS操作加上与其它锁相关的操作，因此基于锁的计数即使在最好的情况下也会比基于CAS的计数器在一般情况下执行更多的操作。由于CAS在大多数 情况下都能执行成功，因此硬件能够正确的预测while循环中的分支，从而把控制逻辑的开锁降到最低。

锁与原子变量的性能比较

在高度竞争的情况下，锁的性能将超过原子变量的性能，但在更真实的竞争情况下，原子变量的性能将超过锁的性能，这是因为锁在发竞争时会挂起线程，从而降低 了CPU的使用率和共享内存总线上的同步通信量，另一方面，如果使用原子变量，那么发出调用的类负责对竞争进行管理，在遇到竞争时立即重试，这通常是种正 确的做法，但是在竞争激烈环境下会导致更多的竞争。在实际的情况中，任何一个程序都不会除了竞争锁或原子变量而什么事都不做，不会达到很高的竞争，所以在 更常见的情况下，原子变量的效率会更高，在可伸缩性上要高于锁。

非阻塞算法

如果在某个算法中，一个线程的失败或挂起不会引起其它线程也失败或挂起，那么这个算法就被称为非阻塞算法；如果在算法的每个步骤中都存在每个线程能够执行 下去，那么这种算法称为无锁算法(Lock-Free)。如果在算法中仅将CAS用于协调线程之间的操作，并且能正确的实现，那么它即是一种非阻塞算法， 也是一种无锁算法。在非阻塞算法中通常不会出现死锁和优先级反转问题，但可能出现饥饿和活锁问题，因为在算法中会反复的重试。

下面代码为非阻塞的栈（使用Treiber算法）：

package thread;
import java.util.concurrent.atomic.AtomicReference;
public class ConcurrentStack<T> {
    private AtomicReference<Node<T>>    stacks    = new AtomicReference<Node<T>>();
    public T push(T e) {
        Node<T> oldNode, newNode;
        for (;;) { // 这里的处理非常的特别，也是必须如此的。
            oldNode = stacks.get();
            newNode = new Node<T>(e, oldNode);
            if (stacks.compareAndSet(oldNode, newNode)) {
                return e;
            }
        }
    }
    public T pop() {
        Node<T> oldNode, newNode;
        do{
                        oldNode = stacks.get();
                        if(oldNode==null){
                              return null;
                        }
            newNode = oldNode.next;
                }while(!stacks.compareAndSet(oldNode, newNode));
                 return oldNode.object;
    }
    private static final class Node<T> {
        private T        object;
        private Node<T>    next;
        private Node(T object, Node<T> next) {
            this.object = object;
            this.next = next;
        }
    }
}

如果在算法中的节点可以被循环使用，那么在使用CAS指令时就会出现这种问题，主要指在没有垃圾回收机制的环境中，在CAS操作中，在更新之前先判断V的 值是否仍然A，如果是的话就继续执行更新操作，但是有的时候还需要知道“自从上次看到V的值为A以后，这个值是否发生了变化？”，在某些算法中，如果V的 值先由A变成B，再由B变成A，那么仍然认为是发生了变化，并需要重新执行算法中的步骤。在这种情况下，即使链表的头节点仍然指向之前观察到的节点，但也 不足以说明链表的内容没有变化。如果通过垃圾回收机制仍然无法避免ABA问题，那么还有下面简单方案：不是更新某个引用的值，而是更新两个值，包括一个引 用和一个版本号，即使这个值由A变为B，然后为变为A，版本号也是不同的。AtomicStampedReference和 AtomicMarkableReference支持在两个变量上执行原子的条件更新。AtomicStampedReference更新一个“对象-引 用”二元组，通过在引用上加上“版本号”，从而避免ABA问题，AtomicMarkableReference将更新一个“对象引用-布尔值”的二元 组。

转载自：http://chenzehe.iteye.com/blog/1762893