Java & Collection/Executor & SynchronousQueue & 总结

前言

 相关系列

• 《Java & Collection & 目录》
• 《Java & Executor & 目录》
• 《Java & Collection/Executor & SynchronousQueue & 源码》
• 《Java & Collection/Executor & SynchronousQueue & 总结》
• 《Java & Collection/Executor & SynchronousQueue & 问题》
   

 涉及内容

• 《Java & Collection & 总结》
• 《Java & Collection & Queue & 总结》
• 《Java & Collection/Executor & BlockingQueue & 总结》
• 《Java & Collection/Executor & LinkedTransferQueue & 总结》
• 《Java & Executor & 总结》
• 《Java & Executor & FutureTask & 总结》
   
   

概述

简介

    SynchronousQueue @ 同步队列类是BlockingQueue @ 阻塞队列接口的实现类之一，基于链表实现。同步队列类有两大特点：一是没有容量概念，即不保存元素而保存操作（但插入操作本身会携带元素）；二是尾部插入方法与头部移除方法必须互补执行，即插入者会等待至存在移除者移除其携带元素后才会执行结束，反之亦然，除非取消或超时，例如“特殊值”形式的实现就是通过零时间超时实现的。

    同步队列类不允许存null，或者说阻塞队列接口的所有实现类都不允许存null。null被作为poll()及peek()方法表示同步队列不存在元素的标记值，因此所有的阻塞队列接口实现类都不允许存null。

    同步队列类是线程安全的，或者说阻塞队列接口的所有实现类都是线程安全的，其接口定义中强制要求实现类必须线程安全。同步队列类采用“无锁”线程安全机制，即使用CAS乐观锁来保证整体的线程安全。由于CAS乐观锁并不是真正意义上的锁，因此被称为“无锁”线程安全机制。

    同步队列类支持公平访问策略，即支持线程按到达顺序对同步队列进行访问，但默认是非公平的。虽然名为队列，但实际上同步队列类拥有迁移堆栈（先入后出）/迁移队列（先入先出）两种实现结构，分别对应非公平访问策略/公平访问策略。两种访问策略的性能大体相似，但迁移队列通常在线程竞争下支持更高的吞吐量，因此其不像迁移堆栈一样将所有竞争都集中在头部。而在普通应用程序中，迁移堆栈可以维护更高的线程局部性（源码中的解释，个人不是太理解什么是线程局部性…可能是指可以更少的与其它线程产生交互）。

    同步队列类的迭代器是没有意义的。由于同步队列类没有容量概念，即没有直接保存元素，故而也就没有元素可以遍历。同步队列类是空迭代器实现，迭代器的hasNext()方法会永远返回false，表示没有元素可遍历。

    同步队列类虽然与阻塞队列接口一样都被纳入Executor @ 执行器框架的范畴，但同时也是Collection @ 集框架的成员。
 

方法的不同形式

    所谓方法的不同形式是指方法在保证自身核心操作不变的情况下实现多种不同的回应形式来应对不同场景下的使用要求。方法的不同形式实际上是Queue @ 队列接口的定义，阻塞队列接口拓展了该定义，而同步队列类实现了该定义。例如对于插入，当容量不足时，有些场景希望在失败时抛出异常；而有些场景则希望能直接返回失败的标记值；而有些场景又希望可以等待至存在可用容量后成功新增为止…正是因为这些不同场景的存在，方法的不同形式才应运而生。方法最多可以拥有四种不同回应形式，这四种回应形式的具体设定如下：

异常 —— 队列接口定义 —— 当不满足操作条件时直接抛出异常；
特殊值 —— 队列接口定义 —— 当不满足操作条件时直接返回失败标记值。例如之所以不允许存null就是因为null被作为了操作失败时的标记值；
阻塞（无限等待） —— 阻塞队列接口定义 —— 当不满足操作条件时无限等待，直至满足操作条件后执行；
超时（有限等待） —— 阻塞队列接口定义 —— 当不满足操作条件时有限等待，如果在指定等待时间之前满足操作条件则执行；否则返回失败标记值。
 

与LinkedTransferQueue @ 链接迁移队列类的对比

• 链接迁移队列类与同步队列类都存在迁移方法（同步队列类的迁移操作是自实现的，而不是实现自迁移队列接口），如果抛开各类方法在底层实现上的纠缠不谈，在链接迁移队列中迁移方法是一类独立于插入及移除方法的操作类型，因此其既直接保存元素也直接保存操作；而在同步队列类中迁移方法是插入方法的底层实现（实际上也是移除方法的），因此插入方法与迁移方法实际上是等价的，故而其只直接保存操作而不直接保存元素；
• 链接迁移队列类中有容量的说法，因为其即直接保存元素也直接保存操作，并且是真正意义上的无界队列；而同步队列类则没有容量的说法，因为其只直接保存操作；
• 链接迁移队列类与同步队列类都采用链表的方式实现，但链接迁移队列类只有队列一种结构的实现，而同步队列类则存在队列（公平）与堆栈（非公平）两种结构的实现；
• 链接迁移队列类与同步队列类都采用节点来保存操作，但链接迁移队列类支持数据与请求两种模式的节点共存（但实际只有一种可用），而同步队列类只能存在其中一种；
• 链接迁移队列类是非同步的，即支持多个互补/实现并发执行，并采用了懈怠机制来缓解线程间的CAS竞争；而同步队列类则是同步的，即同一时间最多只允许存在一个互补/实现。
   
   

使用

创建

• public SynchronousQueue() —— 创建迁移堆栈实现的非公平同步队列。

• public SynchronousQueue(boolean fair) —— 创建指定访问策略的同步队列。当传入true时创建迁移队列实现的公平同步队列；否则创建迁移堆栈实现的非公平同步队列。
   

插入

• public boolean add(E e) —— 新增 —— 从当前同步队列的头部同步移除者。该方法是插入方法尾部位置“异常”形式的实现，当当前同步队列存在移除者时同步并返回true；否则抛出非法状态异常。
      同步队列类并没有自实现add(E e)方法，而是直接使用了父类AbstractQueue（抽象队列）抽象类的实现。在实现中其调用了尾部插入方法“特殊值”形式的offer(E e)方法来达成目的，使得所有抽象队列抽象类的子类只需实现offer(E e)方法后就可以正常调用add(E e)方法。这种代码结构是设计模式的一种，被称为“模板模式”。

/**
 * Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning <tt>true</tt>
 * upon success and throwing an <tt>IllegalStateException</tt> if no space is currently available.
 * 再没有违背容量限制的情况下并指定元素插入至队列，并在成功之后返回true。如果当前没有可用空间则抛出非法状态异常。
 * <p>
 * This implementation returns <tt>true</tt> if <tt>offer</tt> succeeds, else throws an <tt>IllegalStateException</tt>.
 * 该实现如果offer()方法成功则返回true，否则抛出一个非法状态异常（该方法底层是通过调用offer()方法实现的，而offer()方法则交由子类进行
 * 实现，故而子类可以无需实现add()方法，这是一种模板模式的使用）。
 *
 * @param e the element to add 新增的元素
 * @return <tt>true</tt> (as specified by {@link Collection#add})  true（具体看Collection#add方法文档）
 * @throws IllegalStateException    if the element cannot be added at this time due to capacity restrictions
 *                                  非法状态异常：如果元素当前由于容量限制无法新增
 * @throws ClassCastException       if the class of the specified element prevents it from being added to this queue
 *                                  类型转换异常：如果指定元素的类妨碍其新增至队列
 * @throws NullPointerException     if the specified element is null and this queue does not permit null elements
 *                                  空指针异常：如果元素为null并且该队列不允许null元素
 * @throws IllegalArgumentException if some property of this element prevents it from being added to this queue
 *                                  非法参数异常：如果元素的特性妨碍其新增至队列
 */
public boolean add(E e) {
    // 调用offer(E)方法。
    if (offer(e))
        // 如果调用成功，直接返回true。
        return true;
    else
        // 如果调用失败，抛出一个非法状态异常。
        throw new IllegalStateException("Queue full");
}

• public boolean offer(E e) —— 提供 —— 从当前同步队列的头部同步移除者。该方法是插入方法尾部位置“特殊值”形式的实现，当当前同步队列存在移除者时同步并返回true；否则返回false。

• public void put(E e) throws InterruptedException —— 放置 —— 从当前同步队列的头部同步移除者。该方法是插入方法尾部位置“阻塞”形式的实现，当当前同步队列存在移除者时同步；否则加入队尾等待至存在移除者为止。

• public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException —— 提供 —— 从当前同步队列的头部同步移除者。该方法是插入方法尾部位置“超时”形式的实现，当当前同步队列存在移除者时同步并返回true；否则加入队尾在指定等待时间内等待至存在移除者为止，超出指定等待时间则返回false。
   

移除

• public E remove() —— 移除 —— 从当前同步队列的头部同步插入者并返回携带元素。该方法是移除方法头部位置“异常”形式的实现，当当前同步队列存在插入者时同步并返回头元素；否则抛出无如此元素异常。
      数组阻塞队列并没有自实现remove()方法，而是直接使用了父类AbstractQueue（抽象队列）抽象类的实现（具体源码如下）。在实现中其调用了头部移除方法“特殊值”形式的poll()方法来达成目的，使得所有抽象队列抽象类的子类只需实现poll()方法后就可以正常调用remove()方法。这种代码结构是设计模式的一种，被称为“模板模式”。

/**
 * Retrieves and removes the head of this queue.  This method differs from {@link #poll poll} only in that it throws an exception if this queue is empty.
 * 检索并移除队列的头。该方法不同于poll()方法，如果队列为空时其会抛出一个异常。
 * <p>
 * This implementation returns the result of <tt>poll</tt> unless the queue is empty.
 * 除非队列为空，否则该实现返回poll()的结果。
 *
 * @return the head of this queue 队列的头（元素）
 * @throws NoSuchElementException if this queue is empty
 *                                无元素异常：如果队列为空
 */
public E remove() {
    // 调用poll()方法获取元素。
    E x = poll();
    if (x != null)
        // 如果元素存在，直接返回。
        return x;
    else
        // 如果元素不存在，抛出无元素异常。
        throw new NoSuchElementException();
}

• public E poll() —— 轮询 —— 从当前同步队列的头部同步插入者并返回携带元素。该方法是移除方法头部位置“特殊值”形式的实现，当当前同步队列存在插入者时同步并返回头元素；否则返回null。

• public E take() throws InterruptedException —— 拿取 —— 从当前同步队列的头部同步插入者并返回携带元素。该方法是移除方法头部位置“阻塞”形式的实现，当当前同步队列存在插入者时同步并返回头元素；否则加入队尾等待至存在插入者为止。

• public E poll(long timeout, TimeUnit unit) throws InterruptedException —— 轮询 —— 从当前同步队列的头部同步插入者并返回携带元素。该方法是移除方法头部位置“超时”形式的实现，当当前同步队列存在插入者时同步并返回头元素；否则加入队尾在指定等待时间内等待至存在插入者为止，超出指定等待时间则返回null。

• public boolean remove(Object o) —— 移除 —— 从当前同步队列中按迭代器顺序移除首个指定元素。该方法是移除方法内部位置“超时”形式的实现，成功则返回true；否则返回false。虽说定义如此，但由于同步队列类没有容量概念，其内部保存的是操作而不是元素，因此该方法会固定返回false。

• public void clear() —— 清理 —— 从当前同步队列中移除所有元素。虽说定义如此，但由于同步队列类没有容量概念，其内部保存的是操作而不是元素，因此该方法什么也不会做。
   

检查

• public E element() —— 元素 —— 从当前同步队列的头部获取元素。该方法是检查方法头部位置“异常”形式的实现，当当前同步队列存在元素时返回头元素；否则抛出无如此元素异常。虽说定义如此，但由于同步队列类没有容量概念，其内部保存的是操作而不是元素，因此该方法会固定抛出无元素异常。
      同步队列类并没有自实现element()方法，而是直接使用了父类AbstractQueue（抽象队列）抽象类的实现（具体源码如下）。在实现中其调用了头部检查方法“特殊值”形式的peek()方法来达成目的，使得所有AbstractQueue（抽象队列）抽象类的子类只需实现peek()方法后就可以正常调用element()方法。这种代码结构是设计模式的一种，被称为“模板模式”。

/**
 * Retrieves, but does not remove, the head of this queue. This method differs from {@link #peek peek} only in that it throws an exception if this
 * queue is empty.
 * 检索，但不移除队列的头（元素）。该方法不同于peek()方法，如果队列为空时其会抛出一个异常。
 * <p>
 * This implementation returns the result of <tt>peek</tt> unless the queue is empty.
 * 除非队列为空，否则该实现返回peek()的结果。
 *
 * @return the head of this queue 队列的头（元素）
 * @throws NoSuchElementException if this queue is empty
 *                                无元素异常：如果队列为空
 * @Description: 元素：用于返回队列的头元素（但不移除）。当队列中不存在元素时抛出无元素异常。
 */
public E element() {
    E x = peek();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}

• public E peek() —— 窥视 —— 从当前同步队列的头部获取元素。该方法是检查方法头部位置“特殊值”形式的实现，当当前同步队列存在元素时返回头元素；否则返回null。虽说定义如此，但由于同步队列类没有容量概念，其内部保存的是操作而不是元素，因此该方法会固定返回false。
   

流失

    比较令人奇怪的是，基于同步队列类没有容量概念的原因，该方法理论上应该没有元素可流失。但实际是如果同步队列中存在插入者，则会将插入者的携带元素流失至指定集中，个人认为这是同步队列类为了嵌合其在执行器框架中的使用场景而做出的调整/妥协。*

• public int drainTo(Collection<? super E> c) —— 流失 —— 将当前同步队列中的所有元素流失到指定集中，并返回流失的元素总数，被流失的元素将不再存在于当前同步队列中。

• public int drainTo(Collection<? super E> c, int maxElements) —— 流失 —— 将当前同步队列中最多指定数量的元素流失到指定集中，并返回流失的元素总数，被流失的元素将不再存在于当前同步队列中。
   

查询

• public int size() —— 大小 —— 获取当前同步队列的元素总数，如果超过Integer.MAX_VALUE则返回Integer.MAX_VALUE。虽说定义如此，但由于同步队列类没有容量概念，因此该方法会固定返回0。

• public boolean isEmpty() —— 是否为空 —— 判断当前同步队列是否为空。由于同步队列类没有容量概念，因此该方法会固定返回true。

• public int remainingCapacity() —— 剩余容量 —— 获取当前同步队列的剩余容量。由于同步队列类没有容量概念，因此该方法会固定返回0。

• public Object[] toArray() —— 转化数组 —— 获取按迭代器顺序包含当前同步队列中所有元素的新数组。虽说定义如此，但由于同步队列类没有容量概念，因此该方法会固定返回空数组。

• public T[] toArray(T[] a) —— 转化数组 —— 获取按迭代器顺序包含当前同步队列中所有元素的泛型数组。如果参数泛型数组长度足以容纳所有元素，则令之承载所有元素后返回。并且如果参数泛型数组的长度大于当前同步队列的元素总数，则将已承载所有元素的参数泛型数组的size索引位置设置为null，表示从当前同步队列中承载的元素到此为止。当然，该方案只对不允许保存null元素的集有效。如果参数泛型数组的长度不足以承载所有元素，则重分配一个相同泛型且长度与当前同步队列元素总数相同的新泛型数组以承载所有元素后返回。虽说定义如此，但由于同步队列类没有容量概念，因此该方法会固定返回空数组。

    事实上，上文中只列举了大部分常用方法。由于同步队列类是集接口的实现类，因此其也实现了其定义的所有方法，例如contains(Object o)、removeAll(Collection<?> c)及containsAll(Collection<?> c)等。由于同步队列类没有容量概念，因此这些方法大多会固定返回0或false，又或者什么也不做。有兴趣的童鞋可以去查看源码实现。
 
 

迁移堆栈

    迁移堆栈是同步队列类的非公平实现结构，当使用SynchronousQueue()构造方法或在SynchronousQueue(boolean fair)构造方法中传入false，则会得到迁移堆栈实现的非公平同步队列。

    在讲解迁移堆栈及后续迁移队列之前，我们需要先了解一些专属名词，具体如下：

等待节点：保存于迁移堆栈/队列中的节点被称为等待节点，等待实现节点/者来进行互补/实现。等待节点与模式（操作类型）无关，当操作到达时，如果迁移堆栈/队列为空或已存在与当前操作相同模式的等待节点时，当前操作会被封装为等待节点加入迁移堆栈/队列，并令其线程进入等待状态，直至因为与实现节点互补/实现或取消而唤醒并出栈/队。由于迁移堆栈/队列可能会因为出栈/队而为空，并且迁移堆栈/队列为空时首个操作也是不确定的，因此虽然迁移堆栈/队列中所有等待节点都是相同模式，但是在迁移堆栈/队列为空后可能会整体变为另一种模式的等待节点；

实现节点：实现节点是与等待节点相对的概念。当操作到达时，如果发现迁移堆栈中已存在等待节点，并且模式与当前操作相反，则当前操作会被封装为实现节点。实现节点的作用是入栈与头等待节点进行互补/实现，从而使双方的操作皆得以顺利完成，并双双从迁移堆栈中出栈；

实现者：执行与迁移堆栈/队列中等待节点模式相反操作的线程，可与迁移队列中的头等待节点进行互补/实现，从而使双方的操作皆得以顺利完成，并使等待节点从迁移队列中出队；

取消节点：取消节点本质是已取消的等待节点。等待节点并非都是永久有效的，当其等待时间超时或其所属线程被中断时会被取消而成为取消节点。取消节点是没有意义的，无法被实现节点/者互补/实现，因此会触发清理，将迁移堆栈/队列中的取消节点移除。
 

入栈/自旋/等待

    当迁移堆栈为空或已存在与当前操作相同模式的等待节点时，当前操作会被封装为等待节点加入迁移堆栈以等待实现节点进行互补/实现。关于迁移堆栈的入栈并没有值得注意的地方，但对于定时操作而言，如果时间参数不合法是不允许入栈的。例如设置等待节点需要定时等待，但具体的等待时间却为0，显然该操作必然是超时的，完全没有加入迁移堆栈的意义（下文的迁移队列也是如此），只是徒增清理的消耗而已。该机制通常是为了防止开发者在使用时传入错误的时间参数而导致奇怪的运行异常，而API本身并不会传入错误的时间参数，但在同步队列类中却是存在的。为了实现offer(E e)及poll()等“特殊值”形式的方法，同步队列会故意传入错误的时间参数来避免相关的节点入队，从而使方法可以在不经历互补/实现及取消的情况下实时返回（会触发一次栈顶的取消节点清理）。

    为了等待实现节点，等待节点会令自身所属线程进入等待状态。而在所属线程正式进入等待状态前，其会先进行指定次数（阻塞：32 * 16/超时：32）的自旋操作（只在多核处理器中执行），以避免因为实现节点快速到来而导致的无意义线程状态转换开销。Java多线程采用1:1线程模型实现，线程的状态转换需要依赖底层操作系统，是非常耗时耗力的行为。在实现节点快速到来的情况下，两次线程转换的开销会远远大于线程运行的开销，因此进行短期自旋是非常有必要的。
 

互补/实现

    所谓互补/实现，是指等待节点与实现节点/者进行元素交换的过程，是所谓同步的底层实现。当操作到达时，如果发现迁移堆栈中已存在等待节点，且模式与当前操作相反，则当前操作会被封装为实现节点。实现节点会入栈与头等待节点进行互补/实现（由于后入栈的操作反而会被先互补/实现，因此迁移堆栈是非公平的），关于实现节点入栈是一个值得讨论的点，并不是因为其入栈复杂/精妙，而是其为什么要入栈。在后续的迁移队列中，实现节点是无需入队的，甚至于操作都不会被封装为实现节点，而是以实现者的身份完成互补/实现，这是两种实现结构的一个明显差异。

    实现节点入栈的核心原因是为了避免在互补/实现过程中其它线程活动的并发干扰。会对互补/实现过程进行并发干扰的线程活动有两种：一是其它等待节点入栈；二是其它实现节点同样要对当前头等待节点进行互补/实现。为了同时避免两种线程活动干扰，相关预防手段必须在一个原子操作中同步达成，因此直接通过CAS操作入栈一个实现中状态（在迁移堆栈中，节点模式与状态使用同一个int类型字段记录，其将二进制首位用于记录模式，第二位用于记录状态）的实现节点是最好的做法，否则将难以保证同时预防的效果。例如：如果我们不将实现节点入栈，只将头等待节点设置为等待中状态，则确实可以避免其它实现节点的重复互补/实现，但却无法阻止其它等待节点入栈。因为CAS修改头等待节点的前提条件是头等待节点实例不变，状态的变化并不会对该CAS操作产生任何影响。

    实现节点成功入栈后，会与栈顶的等待节点进行互补/实现。互补/实现并不复杂，其核心是交换等待节点与实现节点各自持有的元素，如此尾部插入会失去元素，而头部移除会获得元素，从而两项操作都实现了自身作用。

    如果在此元素交换期间头等待节点被取消而成为取消节点，则实现节点会与清理后的新头等待节点继续进行互补/实现。而如果所有的等待节点都已取消（有点难以想象那种场景…），则清理完成后整个迁移堆栈就只剩下了栈顶的实现节点。此时其实可以直接将实现节点切换为非实现状态，这样其就成为了新的等待节点。但迁移堆栈的做法是直接将实现节点出栈，重新参与竞争。

    元素交换完成后，实现节点会唤醒等待节点的所属线程。两个线程都会通过CAS操作尝试将两个节点出栈，但最终只会有一个线程能够成功。这么做的目的是为了基于性能上的考虑，加速整体流程结束。除此以外，在互补/实现期间，被阻拦在外的各类操作线程也会提供辅助操作。所谓辅助，即帮助/加速进行互补/实现。根据这些线程参与时间的不同，辅助的具体操作也不同。例如参与早的线程可以帮助进行元素交换，而参与较晚的线程则可以帮助进行等待/实现节点的出队，再晚的…划水吧…
 

清理

    当等待节点由于超时/中断而被取消时，会触发迁移堆栈清理。迁移堆栈清理的核心逻辑是从栈顶一路遍历到指定取消节点，以移除沿途发现的所有取消节点，该逻辑初看简单，但实际上却有深层次的考量。通常，清理只会针对性移除指定取消节点，其遍历是为了找到指定取消节点的前驱节点以实现移除，而不会像迁移堆栈一样移除沿途遇到的所有取消节点。这是因为每个取消节点的移除都由其所属线程负责，无需依赖其它外部线程实现，反而会增加额外的实现复杂度。那为什么迁移堆栈要抛弃常规做法，选择实现相对更加复杂的辅助清理呢？原因是为了移除因为并发而产生的“遗留”取消节点。

    在并发环境下，从链表中无锁地移除节点存在“节点遗留”的线程安全问题，即虽然已执行移除操作，但取消节点依然存在于链表中，其具体发生场景如下图所示。

    “节点遗留”是并发无锁链表的常见问题，因此基于并发无锁链表实现的API中通常都存在相关的处理机制。同步队列类也不例外，其兼具辅助性质的清理会将沿途包括“遗留”取消节点在内的所有取消节点移除。基于相同原因，其虽然无法保证完全移除，甚至于在过程中还可能产生新“遗留”取消节点，但却可以很好的将“遗留”取消节点控制在相对较低的数量级。此外由于未产生额外遍历，因此对性能的影响也微乎其微，是非常优秀的清理机制。而其它诸如FutureTask @ 未来任务类、链接迁移队列类等API则使用了重复、投票等机制来处理“节点遗留”问题。这些处理机制虽然细节上有所差异，但本质都是遍历移除。

    辅助清理虽然用很小的代价解决了“节点遗留”问题，但却导致了新问题的产生：即作为清理终点的指定取消节点可能会被其它线程并发清理，从而导致当前线程由于无法找到终点而一路清理到栈底，造成可能的资源浪费。因为如果指定取消节点后续已经没有取消节点的话，那遍历到栈底是无意义的行为。为了尽可能的避免这一点，我们将指定取消节点的后继节点作为终点。如果后继节点依然是取消节点的话，那选择后后继节点，并将之作为最终选择。

    我们并无法保证指定取消节点后续一定存在未取消等待节点，因此不断的向后遍历容易造成二次遍历导致性能损失。另一方面，即使真的存在未取消指定节点，也可能在清理过程中被取消，因此将后继/后后继节点作为完成清理终点是不可靠的。如果后继/后后继节点在过程中因为取消而被移除且未被当前线程发现，则当前线程还是会对整个迁移堆栈进行清理…但一般来说不至于这么巧…因此整体的可靠性还是可以保证的。
 
 

迁移队列

    迁移队列是同步队列类的公平底层实现结构，在SynchronousQueue(boolean fair)构造方法中传入true，则会得到迁移队列实现的公平同步队列。
 

入队/自旋/等待

    当迁移队列为空或存在与当前操作相同模式的等待节点时，当前操作会被封装为等待节点加入迁移队列以等待实现者（即执行模式相反操作的线程）进行互补/实现。与迁移堆栈一致，迁移队列的等待节点同样会令自身所属线程进入等待状态，但却未必会进行自旋，这与迁移队列的尾部入队机制有关。

    对于迁移堆栈而言，由于FILO机制的原因，每个新入栈的等待节点都必然会是头等待节点，是与实现节点进行互补/实现的第一顺位，因此每个等待节点入队后都要自旋操作以避免无意义的线程状态转换开销。但对迁移队列而言，互补/实现与新等待节点入队分别在头/尾两端执行，即从尾部入队的新等待节点未必是头等待节点，因此其被快速互补/实现的概率很低。此状况下如果还令每个新等待节点进行自旋无疑是极低收益的行为，反而会大幅的增大开销。毕竟自旋本身也有消耗，我们要做的是用较小的开销来代替更大的开销，而不是徒增消耗。因此，只有在确认新等待节点是迁移队列的头等待节点时才会令之所属线程自旋。

    迁移队列的入队除了与迁移堆栈一样都不会将时间参数不合法的等待节点入队外，其还会先判断迁移队列的头/尾节点是否不为空。这是因为迁移队列采用空节点（即不保存操作的节点）作为初始的头/尾节点以确保所有的等待节点都存在前驱节点（除此之外还存在其它作用，该知识点下文会详述）。这个空节点会在迁移队列创建时生成并设置，但由于迁移队列采用的是CAS乐观锁，该过程并不受真正意义上锁的保护，因此实际有等待节点尝试入队时迁移队列可能还未完成对头/尾节点的设置。因此在入队前会确定这一点，否则就会一直自旋判断。
 

互补/实现

    迁移队列互补/实现的本质与迁移堆栈是一致的。而与迁移堆栈不同的是，迁移队列不会将操作封装为实现节点并加入迁移队列，而是直接以实现者的身份完成元素交换。究其如此的核心原因，是因为等待节点的入队发生在迁移队列的尾部，而互补/实现则在迁移队列的头部发生。等待节点的入队通常不会对实现节点的互补/实现造成影响，因此只需要修改头等待节点为实现中状态（迁移队列中头等待节点的实现中状态是通过交换两者的元素来表示的，即如果头等待节点的元素已通过CAS操作交换为实现者的元素，就说明头等待者为实现中状态。这与迁移堆栈使用字段来记录实现节点实现中状态的做法不同，根本原因还是因为迁移堆栈需要同时预防两种线程活动并发干扰的缘故）来阻止其它实现者对其重复互补/实现即可。而对于当迁移队列只存在单个等待节点时其可能同时受到互补/实现与新等待节点入队两类操作并发影响的问题，则通过使用虚拟节点的方式解决。所谓的虚拟节点即是前文提及的迁移队列头部的空节点，其的存在成功避免了因为并发而导致头等待节点（同时也是尾等待节点）在追加新等待节点时出队使得元素丢失的问题。因为当元素交换结束，出队的并不是头等待节点而是空/虚拟节点，而头等待节点则会成为新的空节点。

    与迁移堆栈相同，当元素交换完成后，实现者会唤醒等待节点的所属线程。两个线程都会通过CAS操作尝试将空/虚拟节点出队，并将头等待节点设置为新的空/虚拟节点，但最终只会有一个线程能够成功。此期间被排斥在外的其它操作线程也会提供辅助操作，但由于等待节点的入队在队尾发生，因此只有其它实现者会来进行辅助。
 

清理

    当等待节点被取消时，会触发迁移队列清理，相比于迁移堆栈的一路式清理，迁移队列的清理则显得复杂的多，可分为头部移除、内部移除及尾部移除三个部分。

    清理最开始会进行头部移除，即清理并不会直接移除指定取消节点，而是会先移除迁移队列的头部取消节点（如果存在的话）。这是因为头部移除受CAS乐观锁及空/虚拟节点的保护，可以安全的将头部取消节点逐个移除而不受并发影响，是最理想/安全的移除方式。此外，头部移除还兼容移除“遗留”取消节点。迁移队列作为无锁并发链表同样存在“节点遗留”问题，基于队列FIFO的特性，这些“遗留”取消节点最终会前移至头部，并最终被头部移除（包括取消触发和互补/实现触发）所移除。有个值得讨论的问题是：既然迁移队列会暂存“遗留”取消节点至被头部移除，那迁移堆栈为何不也暂存“遗留”取消节点，而是采用辅助清理的方式呢？这是因为迁移堆栈是FILO特性，因此“遗留”取消节点可能难以达到头部，故而就有其长时间存在于迁移堆栈中的危险。

    当头部移除将所有头部取消节点移除（或压根不存在）后，会判断是否清理到了迁移队列的尾部，即判断迁移队列是否只剩下空/虚拟节点。是则说明清理已经完成（包括对指定取消节点的移除），直接结束；否则会进行尾节点更新，即判断当前尾节点是否存在后继节点，是则将之设置为新尾节点。在迁移队列中，尾节点与最后节点不是相同概念。由于无锁并发的原因，新加入迁移堆栈的等待节点可能尚未被设置为尾节点，因此线程获取到的尾节点未必是实际的最后节点。尾节点更新不属于头/内/尾部移除的任意一个，清理线程执行该操作的原因一方面是为了辅助尾节点更新，但更多的是为了避免由于指定取消节点为尾节点而无法被移除的情况，该知识点会在下文详述。

    当尾节点更新完成，清理会判断指定取消节点是否是尾节点，不是则会进行内部移除。所谓内部移除即直接将指定取消节点从迁移堆栈中移除，令其前驱节点与后继节点进行重链接。取消节点的移除无需遍历迁移队列，因为前驱节点会在其加入迁移堆栈时确定并保存为线程的局部变量，因此可以直接移除；而如果发现指定取消节点是尾节点，又或者内部移除失败（即移除指定取消节点失败，例如其前驱节点正好被其它线程头部移除），则就会进行尾部移除。

    当发现指定取消节点为尾节点时，由于尾节点被用于追加新等待节点的原因，其是不允许被内部移除的（但是可被头部移除，因为受CAS乐观锁及空/虚拟节点的保护），因为这可能会导致丢失新等待节点的情况发生。因此尾部移除的核心其实是将身为尾节点的指定取消节点的前驱节点记录为清理节点，以备下次触发尾部移除时移除。因为当下次尾部移除触发时，指定取消节点便不再是尾节点了，可被正常的移除。而之所以保存指定移除节点的前驱节点则是为了避免真正移除时需要遍历以寻找前驱节点的情况。由于节点移除时会自引用/保留原后继引用，因此我们无需担心前驱节点被移除的情况，这并不会对指定取消节点的尾部移除造成影响。

    当记录清理节点时，如果发现清理节点已存在，则说明此前已触发过尾部移除，此次尾部移除在记录新清理节点之前，需要先将旧清理节点移除。尾部移除会采用内部移除的方式移除旧清理节点，但实际情况是其可能无需移除指定取消节点，因为指定清理节点可能已/会被头部移除所移除，这种情况下只需重新记录新清洁节点即可。
 
 

GC

    在整个同步队列类的运行机制中，GC会处理大部分节点回收问题，因此没有过多的辅助机制使非阻塞算法复杂化，但是同步队列类会时刻注意“忘记”对元素、后继节点和线程（当线程阻塞前会保存在相应的等待节点中，用于给实现节点唤醒使用）的引用，即断开链接。这些元素、后继节点和线程可能被阻塞的线程长期占有，数据/对象被阻塞的线程长期持有的话，会很容易因为撑过15次的新生代GC而进入老年代。老年代的对象因为存活时间长，因此GC慢而频率低，难以被及时回收。因此线程被唤醒并完成相应任务后要及时的断开这些数据/对象的引用，尽可能的促使及时回收。另一方面，断开后继节点的链接还能在一定程度上防止跨带引用问题，以简化GC的难度。

    对于迁移堆栈来说，断开链接要求并不会十分严格，因为迁移堆栈本身就是FILO形式的实现，栈顶的元素往往都是最新的，而且因为自旋和互补/实现的原因较少阻塞或阻塞时间较短，并会最快出栈，因此数据/对象一般并不会这么容易进入老年代。但对于迁移队列来说则不同，头部的数据是入队最久，也是阻塞最久的，因此引用的数据/对象大概率已经进入了老年代，因此需要及时的断开链接。

    其中对于后继节点，断开链接往往意味着当前节点从迁移堆栈/队列中出栈/队。由于将后继引用设置为null会与主逻辑冲突（后继引用为null是尾节点的标记），因此会将节点的后继引用设置为自身。但事实上只有正常出队/出栈的等待节点会如此，如果等待节点因为取消而被内部移除，是不会将之自引用的，即其将依然持有原本的后继引用，以防止并发线程的遍历操作中断。