Java并发编程实战.笔记十一(非阻塞同步机制)

关于非阻塞算法CAS。 比较并交换CAS:CAS包含了3个操作数---需要读写的内存位置V,进行比较的值A和拟写入的新值B。当且仅当V的值等于A时,CAS才会通过原子的方式用新值B来更新V的值,否则不会执行任何操作。无论位置V的值是否等于A,都将返回V原有的值。然后线程可以基于新返回的V值来做对应的操作,可以反复尝试。通常,反复重试是一种合理的策略,但在一些竞争很激烈的情况下,更好的方式是在重试之前首先等待一段时间或者回退,从而避免造成活锁问题。CAS的主要缺点就是,它将使调用者处理竞争问题,而在锁中能自动处理竞争问题。虽然java语言的锁定语句比较简洁,但JVM和操作在管理锁时需要完成的工作却并不简单。在实现锁定时需要遍历JVM中一条非常复杂的代码路径,并可能导致操作系统级的锁定、线程挂起以及上下文却换等动作。在最好的情况下,在锁定时至少需要一次CAS,因此虽然在使用锁时没有用到CAS,但实际上也无法节约任何执行开销。另外,在程序内部执行CAS不需要执行JVM代码、系统调用或线程调度操作。在应用级上看起来越长的代码路径,如果加上JVM和操作系统中的代码调用,那么事实上却变得更短。

在非阻塞算法中不存在死锁和其他活跃性问题。

而在基于锁的算法中,如果一个线程在休眠或自旋的同时持有一个锁,那么其他线程都无法执行下去,而非阻塞算法不会受到单个线程失败的影响。

锁的劣势

许多JVM都对非竞争锁获取和释放操作进行了极大的优化,但如果有多个线程同时请求锁,那么JVM就需要借助操作系统地功能。如果出现了这种情况,那么一些线程将被挂起并且在稍后恢复运行。当线程恢复执行时,必须等待其他线程执行完它们的时间片以后,才能被调度执行。在挂起和恢复线程等过程中存在着很大的开销,并且通常存在着较大时间的中断。如果在基于锁的类中包含细粒度的操作(例如同步器类,在其大多数方法中只包含了少量操作),那么当在锁上存在着激烈的竞争时,调度开销与工作开销的比值会非常高。

另外,当一个线程正在等待锁时,它不能做任何其他事情。如果一个线程在持有锁的情况下被延迟执行,那么所有需要这个锁的线程都无法执行下去。如果被阻塞线程的优先级高,而持有锁的线程优先级低,那么将是一个严重的问题。

比较并交换CAS

CAS包含了3个操作数---需要读写的内存位置V,进行比较的值A和拟写入的新值B。当且仅当V的值等于A时,CAS才会通过原子的方式用新值B来更新V的值,否则不会执行任何操作。无论位置V的值是否等于A,都将返回V原有的值。

CAS的含义:我认为V的值应该为A,如果是,那么将V的值更新为B,否则不修改并告诉V的值实际为多少。CAS是一种乐观的态度,它希望能成功地执行更新操作,并且如果有另一个线程在最近一次检查后更新了该变量,那么CAS能检测到这个错误。

/**
 * 当多个线程尝试使用CAS同时更新同一个变量时,只有其中一个线程能更新变量的值,而其他线程都将失败。
 * 然而,失败的线程并不会被挂起,而是被告知在这次竞争中失败,并可以再次尝试。
 * 由于一个线程在竞争CAS时不会阻塞,因此它可以决定是否重新尝试,或者执行一些恢复操作,也或者不执行任何操作。
 */
public class SimulatedCAS {
    private int value;

    public synchronized int get(){
        return value;
    }

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

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

CAS的典型使用模式是:首先从V中读取值A,并根据A计算新值B,然后再通过CAS以原子方式将V中的值由A变成B。由于CAS能检测到来自其他线程的干扰,因此即使不使用锁也能够实现原子的读--改--写操作。

非阻塞的计算器

/**
 * 通常,反复重试是一种合理的策略,但在一些竞争很激烈的情况下,更好的方式是在重试之前首先等待一段时间或者回退,从而避免造成活锁问题。
 *
 * 虽然java语言的锁定语句比较简洁,但JVM和操作在管理锁时需要完成的工作却并不简单。
 * 在实现锁定时需要遍历JVM中一条非常复杂的代码路径,并可能导致操作系统级的锁定、线程挂起以及上下文却换等动作。
 * 在最好的情况下,在锁定时至少需要一次CAS,因此虽然在使用锁时没有用到CAS,但实际上也无法节约任何执行开销。
 * 另外,在程序内部执行CAS不需要执行JVM代码、系统调用或线程调度操作。
 * 在应用级上看起来越长的代码路径,如果加上JVM和操作系统中的代码调用,那么事实上却变得更短。
 * CAS的主要缺点是,它要求调用者处理竞争问题,而在锁中能自动处理竞争问题
 */
public class CasCounter {
    private SimulatedCAS value;

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

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

JVM对CAS的支持

Java5.0中引入了底层的支持,在int,long和对象引用等类型上都公开了CAS操作,并且JVM把它们编译为底层硬件提供的最有效方法。在原子变量类中,使用了这些底层的JVM支持为数字类型和引用类型提供一种高效的CAS操作,而在java.util.concurrent中的大多数类在实现时都直接或间接地使用了这些原子变量类。

  • 示例:非阻塞的栈
/**
 * 栈是由Node元素构成的一个链表,根节点为栈顶yop,每个元素中都包含了一个值以及指向下一个元素的链接。
 * push方法创建一个新的节点,该节点的next域指向当前的栈顶,然后使用CAS把这个新节点放入栈顶。
 *
 * @param <E>
 */
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;
        }
    }
}
  • 示例:非阻塞链表

链表队列比栈复杂,它必须支持对头节点和尾节点的快速访问。它需要单独维护头指针和尾指针。

对于尾部的插入,有两个点需要更新:将当前尾节点的next指向要插入的节点,和将尾节点更新为新插入的节点。这两个更新操作需要不同的CAS操作,不好通过原子变量来实现。

需要使用一些策略:

策略一是,即使在一个包含多个步骤的更新操作中,也要确保数据结构总是处于抑制的状态。这样,线程B到达时,如果发现A正在执行更新,那么线程B就可以知道有一个操作已部分完成,并且不能立即执行自己的更新操作。然后B可以等待并直到A完成更新。虽然能使不同的线程轮流访问数据结构,并且不会造成破坏,但如果有一个线程在更新操作中失败了,那么其他的线程都无法再方位队列。

策略二是,如果B到达时发现A正在修改数据结构,那么在数据结构中应该有足够多的信息,使得B能完成A的更新操作。如果B帮助A完成了更新操作,那么B可以执行自己的操作,而不用等待A的操作完成。当A恢复后再试图完成其操作时,会发现B已经替它完成了。

/**
 * 实现的关键点在于:
 * 当队列处于稳定状态时,未节点的next域将为空,如果队列处于中间状态,那么tail.next将为非空。
 * 因此,任何线程都能够通过检查tail.next来获取队列当前的状态。而且,当队列处于中间状态时,可以通过将尾节点向前移动一个节点,
 * 从而结束其他线程正在执行的插入元素操作,并使得队列恢复为稳定状态。
 *
 * @param <E>
 */
public class LinkedQueue<E> {

    private static class Node<E>{
        final E item;
        final AtomicReference<Node<E>> next;

        public Node(E item,Node<E> next){
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }

        private final Node<E> dummy = new Node<E>(null,null);
        private final AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(dummy);
        private final AtomicReference<Node<E>> tail = new AtomicReference<Node<E>>(dummy);

        private boolean put(E item){
            Node<E> newNode = new Node<E>(item,null);
            while(true){
                Node<E> curTail = tail.get();
                Node<E> tailNext = curTail.next.get();
                if(curTail == tail.get()){
                    if(tailNext != null){
                        //队列处于中间状态,推进尾节点
                        tail.compareAndSet(curTail, tailNext);
                    }else{
                        //处于稳定状态。尝试插入新节点
                        if(curTail.next.compareAndSet(null, newNode)){
                            //插入成功,尝试推进尾节点,这一步如果未来得及完成,可由别的线程帮忙
                            tail.compareAndSet(curTail, newNode);
                            return true;
                        }
                    }
                }
            }
        }
    }
}

ABA问题

在某些算法中,如果V的值首先由A变成B,再由B变成A。

解决办法是:不是更新某个引用的值,而是更新两个值,包括一个引用和一个版本号。AtomicStampedReference以及AtomicMarkableReference支持在两个变量上执行原子的条件更新。

#笔记内容参考 《 java并发编程实战》

上一篇:git 查看当前与上一次version的差异


下一篇:热部署环境下,dubbo序列化的bug和优化