Java集合-SynchronousQueue

Java集合-SynchronousQueue

描述

无缓冲阻塞队列，用来在两个线程之间移交元素
模式相同则入栈（队），不同则出栈（队），所以并非真正的无缓冲
队列为空也入栈（队）
并不是真正的队列，不维护存储空间，维护的是一组线程，这些线程在等待着放入或者移出元素

这种阻塞队列确实是非常复杂的，但是却非常有用。SynchronousQueue是一种极为特殊的阻塞队列，它没有实际的容量，任意线程（生产者线程或者消费者线程，生产类型的操作比如put，offer，消费类型的操作比如poll，take）都会等待直到获得数据或者交付完成数据才会返回，一个生产者线程的使命是将线程附着的数据交付给一个消费者线程，而一个消费者线程则是等待一个生产者线程的数据。它们在匹配到互斥线程的时候就会做数据交易，比如生产者线程遇到消费者线程时，或者消费者线程遇到生产者线程时，一个生产者线程就会将数据交付给消费者线程，然后共同退出。在java线程池newCachedThreadPool中就使用了这种阻塞队列。

优点

将更多关于任务状态的信息反馈给生产者。当交付被接受时，它就知道消费者已经得到了任务，而不是简单地把任务放入一个队列——这种区别就好比将文件直接交给同事，还是将文件放到她的邮箱中并希望她能尽快拿到文件。

特性

// CPU的数量
static final int NCPUS = Runtime.getRuntime().availableProcessors();
// 有超时的情况自旋多少次，当CPU数量小于2的时候不自旋
static final int maxTimedSpins = (NCPUS < 2) ? 0 : 32;
// 没有超时的情况自旋多少次
static final int maxUntimedSpins = maxTimedSpins * 16;
// 针对有超时的情况，自旋了多少次后，如果剩余时间大于1000纳秒就使用带时间的LockSupport.parkNanos()这个方法
static final long spinForTimeoutThreshold = 1000L;
// 传输器，即两个线程交换元素使用的东西
private transient volatile Transferer<E> transferer;
//主要定义了一个transfer方法用来传输元素
abstract static class Transferer<E> {
    abstract E transfer(E e, boolean timed, long nanos);
}
// 以栈方式实现的Transferer
static final class TransferStack<E> extends Transferer<E> {
    // 栈中节点的几种类型： 
    static final int REQUEST    = 0;// 1. 消费者（请求数据的）
    static final int DATA       = 1;// 2. 生产者（提供数据的）
    static final int FULFILLING = 2;// 3. 二者正在匹配中
    // 栈中的节点
    static final class SNode {
        volatile SNode next;        // 下一个节点
        volatile SNode match;      // 匹配者     
        volatile Thread waiter;     // 等待着的线程      
        Object item;                // 元素  
        int mode;//也就是节点的类型，是消费者，是生产者，还是正在匹配中
    }
    volatile SNode head;// 栈的头节点
}
// 以队列方式实现的Transferer
static final class TransferQueue<E> extends Transferer<E> {
    // 队列中的节点
    static final class QNode {
        volatile QNode next;          // 下一个节点
        volatile Object item;         // 存储的元素   
        volatile Thread waiter;       // 等待着的线程
        final boolean isData;// 是否是数据节点
    }
    transient volatile QNode head;// 队列的头节点
    transient volatile QNode tail;// 队列的尾节点
}

构造器

public SynchronousQueue() {
	// 默认非公平模式
    this(false);
}
public SynchronousQueue(boolean fair) {
	// 公平模式使用队列，非公平模式使用栈
    transferer = fair ? new TransferQueue<E>() : new TransferStack<E>();
}

入队

public void put(E e) throws InterruptedException {  
	// 元素不可为null
    if (e == null) throw new NullPointerException();
    // 三个参数分别是：传输的元素，是否需要超时，超时的时间
    if (transferer.transfer(e, false, 0) == null) {
        // 如果传输失败，直接让线程中断并抛出中断异常
        Thread.interrupted();
        throw new InterruptedException();
    }
}

出队

public E take() throws InterruptedException {
    // 第一个参数为null表示是消费者，要取元素
    E e = transferer.transfer(null, false, 0);
    if (e != null)// 如果取到了元素就返回
        return e;
    // 否则让线程中断并抛出中断异常
    Thread.interrupted();
    throw new InterruptedException();
}

栈的transfer

E transfer(E e, boolean timed, long nanos) {
    SNode s = null; 
    int mode = (e == null) ? REQUEST : DATA;// 根据e是否为null决定是生产者还是消费者
    for (;;) {// 自旋
        SNode h = head;// 栈顶元素 
        if (h == null || h.mode == mode) {// 入栈
            if (timed && nanos <= 0) {     // 如果有超时设置而且已到期，不能再入栈,协助清理cancel状态的元素
                if (h != null && h.isCancelled())// 如果头节点不为空且是取消状态
                    casHead(h, h.next);//头节点弹出，将h.next设置为新的head，并进入下一次循环
                else  
                    return null;// 否则，直接返回null（超时返回null）
            } else if (casHead(h, s = snode(s, e, h, mode))) {// 入栈成功      
                // 调用awaitFulfill()方法自旋+阻塞当前入栈的线程并等待被匹配到
                SNode m = awaitFulfill(s, timed, nanos);
                // 如果m等于s，说明取消了，那么就把它清除掉，并返回null
                if (m == s) {               
                    clean(s);
                    return null;// 被取消了返回null
                }
                
                // 到这里说明匹配到元素了,因为从awaitFulfill()里面出来要不被取消了要不就匹配到了,如果头节点不为空，并且头节点的下一个节点是s,就把头节点换成s的下一个节点,也就是把h和s都弹出了,也就是把栈顶两个元素都弹出了
                if ((h = head) != null && h.next == s)
                    casHead(h, s.next);     
                // 根据当前节点的模式判断返回m还是s中的值
                return (E) ((mode == REQUEST) ? m.item : s.item);
            }
        } else if (!isFulfilling(h.mode)) {     
            if (h.isCancelled())// 节点和当前节点模式不一样,如果头节点不是正在匹配中并且已经取消了，就把它弹出栈         
                casHead(h, h.next);         
            else if (casHead(h, s=snode(s, e, h, FULFILLING|mode))) {
                // 头节点没有在匹配中，就让当前节点先入队，再让他们尝试匹配
                // 且s成为了新的头节点，它的状态是正在匹配中
                for (;;) { 
                    SNode m = s.next;       
                    // 如果m为null，说明除了s节点外的节点都被其它线程先一步匹配掉了
                    // 就清空栈并跳出内部循环，到外部循环再重新入栈判断
                    if (m == null) {        
                        casHead(s, null);   
                        s = null;           
                        break;            
                    }
                    SNode mn = m.next;
                    // 如果m和s尝试匹配成功，就弹出栈顶的两个元素m和s
                    if (m.tryMatch(s)) {
                        casHead(s, mn);     
                        // 返回匹配结果
                        return (E) ((mode == REQUEST) ? m.item : s.item);
                    } else                 
                        // 尝试匹配失败，说明m已经先一步被其它线程匹配了,就协助清除它
                        s.casNext(m, mn);   
                }
            }
        } else {                            
            //当前节点和头节点模式不一样,且头节点是正在匹配中
            SNode m = h.next;              
            if (m == null)                 
                // 如果m为null，说明m已经被其它线程先一步匹配了
                casHead(h, null);           
            else {
                SNode mn = m.next;
                // 协助匹配，如果m和s尝试匹配成功，就弹出栈顶的两个元素m和s
                if (m.tryMatch(h))          
                    // 将栈顶的两个元素弹出后，再让s重新入栈
                    casHead(h, mn);         
                else                        
                    // 尝试匹配失败，说明m已经先一步被其它线程匹配了
                    // 就协助清除它
                    h.casNext(m, mn);       
            }
        }
    }
}
// 三个参数：需要等待的节点，是否需要超时，超时时间
//等待其他的线程来匹配，这个线程一直阻塞直到被匹配，在阻塞之前首先会自旋，这个自旋会在阻塞之前进行，它会调用shouldSpin方法来进行判断是否需要自选
SNode awaitFulfill(SNode s, boolean timed, long nanos) {
    final long deadline = timed ? System.nanoTime() + nanos : 0L;// 到期时间
    Thread w = Thread.currentThread();// 当前线程
    int spins = (shouldSpin(s) ? (timed ? maxTimedSpins : maxUntimedSpins) : 0);    // 自旋次数
    for (;;) {
        if (w.isInterrupted())// 当前线程中断了，尝试清除s
            s.tryCancel();
        
        // 检查s是否匹配到了元素m（有可能是其它线程的m匹配到当前线程的s）
        SNode m = s.match;
        if (m != null)// 如果匹配到了，直接返回m
            return m;
        
        // 如果需要超时
        if (timed) {
            // 检查超时时间如果小于0了，尝试清除s
            nanos = deadline - System.nanoTime();
            if (nanos <= 0L) {
                s.tryCancel();
                continue;
            }
        }
        if (spins > 0)
            // 如果还有自旋次数，自旋次数减一，并进入下一次自旋
            spins = shouldSpin(s) ? (spins-1) : 0;
        
        // 后面的elseif都是自旋次数没有了
        else if (s.waiter == null)
            // 如果s的waiter为null，把当前线程注入进去，并进入下一次自旋
            s.waiter = w; // establish waiter so can park next iter
        else if (!timed)
            // 如果不允许超时，直接阻塞，并等待被其它线程唤醒，唤醒后继续自旋并查看是否匹配到了元素
            LockSupport.park(this);
        else if (nanos > spinForTimeoutThreshold)
            // 如果允许超时且还有剩余时间，就阻塞相应时间
            LockSupport.parkNanos(this, nanos);
    }
}
// SNode里面的方向，调用者m是s的下一个节点
// 这时候m节点的线程应该是阻塞状态的
boolean tryMatch(SNode s) {
    // 如果m还没有匹配者，就把s作为它的匹配者
    if (match == null &&
        UNSAFE.compareAndSwapObject(this, matchOffset, null, s)) {
        Thread w = waiter;
        if (w != null) {    
            waiter = null;
            // 唤醒m中的线程，两者匹配完毕
            LockSupport.unpark(w);
        }
        // 匹配到了返回true
        return true;
    }
    // 可能其它线程先一步匹配了m，返回其是否是s
    return match == s;
}

如果当前的交易栈是空的，或者包含与请求交易节点模式相同的节点，那么就将这个请求交易的节点作为新的栈顶节点，等待被下一个请求交易的节点匹配，最后会返回匹配节点的数据或者null，如果被取消则会返回null。

如果当前交易栈不为空，并且请求交易的节点和当前栈顶节点模式互补，那么将这个请求交易的节点的模式变为FULFILLING，然后将其压入栈中，和互补的节点进行匹配，完成交易之后将两个节点一起弹出，并且返回交易的数据。

如果栈顶已经存在一个模式为FULFILLING的节点，说明栈顶的节点正在进行匹配，那么就帮助这个栈顶节点快速完成交易，然后继续交易。

队列的transfer

E transfer(E e, boolean timed, long nanos) {  
    
 //在每一种情况，执行的过程中，检查和尝试帮助其他stalled/slow线程移动队列头和尾节点 循环开始，首先进行null检查，防止未初始队列头和尾节点。当然这种情况，在当前同步队列中，不可能发生，如果调用持有transferer的non-volatile/final引用， 可能出现这种情况。一般在循环的开始，都要进行null检查，检查过程非常快，不用过多担心性能问题。 
         
    QNode s = null; 
    //如果元素e不为null，则为DATA模式，否则为REQUEST模式  
    boolean isData = (e != null);  
    for (;;) {  
        QNode t = tail;  
        QNode h = head;  
        //如果队列头或尾节点没有初始化，则自旋  
        if (t == null || h == null)           
            continue;                       
        if (h == t || t.isData == isData) { //如果队列为空，或当前节点与队尾模式相同 ,入队 
            QNode tn = t.next;  
            if (t != tail)                  //如果t不是队尾，非一致性读取，自旋 
                continue;  
            if (tn != null) {               //tn不为null，说明有其他线程添加了tn结点  （设置了tail.next）           
                advanceTail(t, tn);  //如果t.next不为null，设置新的队尾，自旋  
                continue;  
            }  
            if (timed && nanos <= 0) //如果超时，且超时时间小于0，则返回null  
                return null;  
            if (s == null)  
                s = new QNode(e, isData);  //根据元素和模式构造节点
            if (!t.casNext(null, s))        // 新节点入队列失败(t.next被赋值了)，自旋
                continue;
            //设置队尾为当前节点  
            advanceTail(t, s);              // swing tail and wait  
            //自旋或阻塞直到节点被fulfilled  
            Object x = awaitFulfill(s, e, timed, nanos);  
            if (x == s) {                   // wait was cancelled  
                //如果s指向自己，s出队列，并清除队列中取消等待的线程节点  
                clean(t, s);  
                return null;  
            }  
            if (!s.isOffList()) {           // s仍然在队列中 
                advanceHead(t, s);          
                if (x != null)              
                    s.item = s;  
                s.waiter = null;  
            }  
            //如果自旋等待匹配的节点元素不为null，则返回x，否则返回e  
            return (x != null) ? x : e;  
        } else {                              
            //如果队列不为空，且与队头的模式不同，及匹配成功 （与队尾匹配成功，则一定与队头匹配成功！） 
            QNode m = h.next;                
            if (t != tail || m == null || h != head)  
                //如果h不为当前队头，则返回，即读取不一致  
                continue;                   
            Object x = m.item;  
            if (
                isData == (x != null) ||   
                x == m ||                    
                !m.casItem(x, e)   
            ){        
                
                advanceHead(h, m);          //如果队头后继，取消等待，则出队列  
                continue;  
            }  
            //否则匹配成功  
            advanceHead(h, m);                
            //unpark等待线程  
            LockSupport.unpark(m.waiter);  
            //如果匹配节点元素不为null，则返回x，否则返回e，即take操作，返回等待put线程节点元素，  
            //put操作，返回put元素  
            return (x != null) ? x : e;  
        }  
    }  
}

如果队列为空，或者请求交易的节点和队列中的节点具有相同的交易类型，那么就将该请求交易的节点添加到队列尾部等待交易，直到被匹配或者被取消。

如果队列中包含了等待的节点，并且请求的节点和等待的节点是互补的，那么进行匹配并且进行交易
SynchronousQueue一般用于生产、消费的速度大致相当的情况，这样才不会导致系统中过多的线程处于阻塞状态。