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

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

?

/**     * 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

?

?

?

?