Java Concurrency In Practice之Java非阻塞算法解析

基于锁得算法会带来一些活跃度失败的风险。如果线程在持有锁得时候因为阻塞I/O，页面错误，或其它原因发生延迟，很可能所有线程都不能前进了。一个线程的失败或者挂起 不应该影响其他线程的失败或挂起，这样的算法称为非阻塞(nonblocking)算法；如果算法的每一步骤中都有一些线程能够继续执行，那么这样的算法称为锁自由(lock-free)算法。在线程间使用CAS进行协调，这样的算法如果能够正确的构建的话，那么它就既是非阻塞的，有事锁自由的。在实现同等功能的前提下，非阻塞算法比基于锁得算法更加复杂。创建非阻塞算法的前提是为了维护数据的一致性，解决如何把原子化范围缩小到一个唯一的变量。下面通过两个例子来说明如果设计基于非阻塞算法的数据结构。一个例子是仅需维护一个变量的栈，零一个例子就是JDK Concurrent 包里的ConcurrentLinkedQueue，这个例子展示如何通过通过非阻塞算法来维护两个变量的一致性。

 

public class ConcurrentStack<E> {

	AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();
	
	public void push(E item)
	{
		Node<E> newHead = new Node<E>(item);
		Node<E> oldHead;
		
		do
		{
			oldHead = top.get();
			newHead.next = oldHead;
		}while(!top.compareAndSet(oldHead, newHead));
	}
	
	public E pop()
	{
		Node<E> newHead;
		Node<E> oldHead;
		
		do
		{
			oldHead = top.get();
			if(oldHead == null)
			{
				return null;
			}
			
			newHead = oldHead.next;
		}while(!top.compareAndSet(oldHead, newHead));
		
		return oldHead.item;
	}
	
	private static class Node<E>
	{
		public final E item;
		public Node<E> next;
		
		public Node(E item)
		{
			this.item = item;
		}
	}
}

  在上面的代码中，栈顶top变量是一个原子引用变量，其包含一个值和一个指向下一个元素的链接next。在Push的时候，通过创建一个新的Node，然后把这个新创建的Node的next指向当前的top节点，然后用CAS去把这个新创建的节点加入到栈中，即把新创建的节点作为栈新的top节点。Pop操作采用的是类似的思路。此处我的理解是：通过不停的轮询和CAS更新，来保证多线程环境下的数据一致性，虽然这样的轮询也需要时间，但相对获取锁及等待锁得阻塞算法，这个时间要小，而且还不存在死锁等风险。

一个链接队列比栈更加复杂，因为栈只需维护一个栈顶节点，因此通过CAS来保持一致性比较容易，但队列需要支持首尾的快速访问，因此队列需要维护首节点和队尾节点。因此为链表队列构建非阻塞算法需要考虑如何原子地更新两个节点。下面我们看ConcurrentLinkedQueue的代码是如何实现这一点的。

  要理解ConcurrentLinkedQueue的代码，首先要明白一下两个概念：

队列的稳定状态：指的是当前没有线程在操作队列，即队列的tail（队尾节点）的next为null；

队列的中间状态：指的是当前有线程在往队列里添加元素，因为添加元素需要涉及更新tail节点，所以当队列处于中间状态时，tail节点的next不为null，这是因为我们往队列里添加一个元素，进行的操作一般为：

Node oldTail = tail;
oldTail.next = newNode;
tail = newNode;
tail.next = null;

 在这个添加过程中，tail的next不为null，一旦添加完成，队列又变为稳定状态，tail的next重新被置为null。

下面通过分析ConcurrentLinkedQueue的Offer方法来说明其是如何实现非阻塞的。

/**
     * Inserts the specified element at the tail of this queue.
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws NullPointerException if the specified element is null
     */
    public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        Node<E> n = new Node<E>(e);
        retry:
        for (;;) {
            Node<E> t = tail;
            Node<E> p = t;
            for (int hops = 0; ; hops++) {
                Node<E> next = succ(p);
                if (next != null) {             /A
                    if (hops > HOPS && t != tail)        //B
                        continue retry;         
                    p = next;
                } else if (p.casNext(null, n)) {      //C
                    if (hops >= HOPS)
                        casTail(t, n); // Failure is OK.       //D
                    return true;   
                } else {
                    p = succ(p);                                   //E
                }
            }
        }
    }

  A：首先判断tail节点的next是否为null，如果为null，则队列当前处于中间状态，即有其它的线程正在对其进行插入操作，转而执行B处代码；如果不为null，则队列处于稳定状态，转而执行C，D处得插入代码；

  B：通过轮询来等待另外的线程完成插入状态，直到队列重新进入稳定状态时，再进行插入。此处的HOPS=1，当这个内嵌的for循环执行2次后，跳回retry处，重新获取台tail节点，因为指向tail节点的变量是volatile的，所以这样做，在高并发，多线程插入队列的时候，能够更快地知道队列重新处于稳定状态这一消息。

  C：队列处于静止状态，插入新节点。

  D：如果C处得代码插入成功，则尝试推进尾节点。此处如果推进失败了，也没关系，正常返回，因为推进失败则意味着有其它线程也在进行插入操作，这个推进工作留给其它线程去完成。

  E：如果C处的插入不成功，则说明有其他线程先一步完成了插入操作，则执行E处代码，继续获取当前节点的下一个节点，判断队列是否处于稳定状态。

试想，如果有t1和t2两个线程同时对队列Q进行插入操作，t1,t2同时执行A出代码，如果t1进行C处代码进行插入操作，则t2线程通过A出代码得知目前队列处于中间状态，则执行B出代码进行轮询，以便当t2插入完成，队列重新进入稳定状态时，进行插入操作；当t1线程完成C处代码，成功插入新节点后，如果此时t2线正好通过轮询得知队列正处于稳定状态（因为next=null），所以执行插入操作，则t2线程D处得推进操作不能成功，但这t2线程照样可以正常返回，因为t1线程会完成此处得推进操作。

在ConcurrentLinkedQueue的Offer方法里，没有通过加锁来保护节点更新过程中的一致性保护，多个线程之间通过CAS操作判断和同步队列的状态，以此达到了Non-Blocking的更新操作。虽然实现起来比加锁操作复杂，但这种实现不像加锁操作那也牺牲了一定的性能，更适合高并发情况的写操作。

  

       总之,因为Non-Blocking的算法在多线程环境下不需要通过加锁来保护共享的状态数据或者变量，因此其必须确保在多线程环境下做到使各个线程能够实时地获取到共享数据或变量的最新值，Java Concurrenct包的实现就是通过Volatile和CAS操作来保证的。虽然循环CAS操作也需要耗费一定的时间，但是这个时间和锁操作的时间相比，还是有很大的优势的。在另一篇文章里，我讲测试在多线程环境下，基于非阻塞算法的concurrentStack和基于锁得阻塞stack的性能差异。见：http://olylakers.iteye.com/blog/1046919