Java Collection/Executor DelayedWorkQueue 总结

前言

 相关系列

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

 涉及内容

• 《Java & Collection & 总结》
• 《Java & Collection & Queue & 总结》
• 《Java & Collection & AbstractQueue & 总结》
• 《Java & Collection & PriorityQueue & 总结》
• 《Java & Collection/Executor & BlockingQueue & 总结》
• 《Java & Collection/Executor & DelayQueue & 总结》
• 《Java & Executor & 总结》
• 《Java & Executor & RunnableScheduledFuture & 总结》
• 《Java & Executor & ThreadPoolExecutor & 总结》
• 《Java & Executor & ScheduledThreadPoolExecutor & 总结》
• 《Java & Lock/AQS & ReentrantLock & 总结》
• 《Java & Other & Delayed & 总结》
• 《Java & Other & Comparable & 总结》
   

 注意

    DelayedWorkQueue @ 延迟工作队列类是Executor @ 执行器框架在DelayedQueue @ 延迟队列类的基础上为实现/优化ScheduledThreadPoolExecutor @ 调度线程池执行器类而设计的专项优化类，其功能/实现与延迟队列类高度一致，因此本文不会再对“延迟”功能进行重复阐述，而是着重讲解优化项的相关内容，故而读者在阅读本文前必须先对延迟队列类的功能/实现有所了解，相关资料可通过上方链接获得。
 
 

概述

 简介

    延迟工作队列类是BlockingQueue @ 阻塞队列接口的实现类之一，基于数组实现。与常规阻塞队列接口实现类不同，延迟工作队列类并非独立的类实现，而是以静态内部类的形式存在于调度线程池执行器类中。与此同时其还并非是公共权限的开放类，默认权限意味着其专为调度线程池执行器类及其兄弟/子类而设计，禁止在其之外的类中被使用，因此开发者通常是无法在日常开发中使用延迟工作队列类的，除非使用反射等非常规机制。

    延迟工作队列类提供与延迟队列类一致的“延迟”功能，即元素只有在指定延迟时间到期后才允许被头部移除。实际上，延迟工作队列类与延迟队列类在代码实现上拥有接近完全一致的相似度，基本可以直接认为是延迟工作队列类拷贝了延迟队列类的代码。这不经令人产生疑惑…既然二者如此相似，那延迟工作队列类存在的意义又是什么呢？实际上延迟工作队列类是在延迟队列类的基础上针对调度线程池执行器类的内部运行机制而被设计出来专项优化类，其相比延迟队列类而言其在元素类型/排序方面对元素定位进行了订制，使得元素内部移除操作的时间复杂度由原本的O(n)降低为了O(log n)，并在GC方面也有一定的额外收益，该知识点的内容会在下文讲解优化时详述。

    延迟工作队列类不支持保存任意类型的元素，固定的Runnable @ 可运行接口泛型意味着其只能保存可运行。延迟工作队列类的泛型被指定为可运行接口是因为其只会被作为调度线程池执行器类及其兄弟/子类的任务存储容器使用，但也是因为相同原因，延迟工作队列真正保存的元素实际是可运行接口子接口RunnableScheduledFuture @ 可运行调度未来的对象，因为调度线程池执行器中的任务必然会以可运行调度未来的形式存在，而这不禁会令人产生“为何延迟工作队列类不直接将泛型设置为可运行调度未来接口”的疑惑，该知识点会在下文讲解优化时详述。

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

    延迟工作队列类是无界队列，其最大容量理论上只受限于堆内存的大小。延迟工作队列类的默认初始容量为16，并且只能在创建时隐式/自动设置而无法显式指定。虽然基于长度固定的数组实现，但延迟工作队列类内部存在扩容机制，因此也被纳入无界队列的范畴中。由于在具体实现上受到数组及int类型的物理限制，因此虽说是无界队列，但实际其最大容量仅可扩容至Integer.MAX_VALUE。扩容的本质是创建长度更大的新元素数组来代替旧元素数组，并将旧元素数组中的元素迁移至新元素数组。容量的具体增长规则如下：

新容量 = 旧容量 + 旧容量 >> 1（约1.5倍）

    延迟工作队列类是线程安全的，或者说阻塞队列接口的所有实现类都是线程安全的，其接口定义中强制要求实现类必须线程安全。延迟工作队列类采用“单锁”线程安全机制，即使用一个ReentrantLock @ 可重入锁来保证整体的线程安全。

    延迟工作队列类的迭代器是弱一致性的，即可能迭代到已移除的元素及无法迭代到新插入的元素。延迟工作队列的迭代器实现非常直接（或者说过于直接了），其会直接将数据拷贝一份快照存入生成的迭代器中以进行迭代。这么做的好处是迭代器的实现非常的简单，但缺点也明显，当延迟工作队列元素总数较大或生成的迭代器数量较多时对内存的消耗会非常严重。

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

 方法的不同形式

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

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

 与延迟队列类的区别

• 延迟队列类底层采用优先级队列类实现，而延迟工作队列类底层没有采用优先级队列类实现，其在内部大范围复写了相似代码并进行了专项优化；
• 延迟队列类/优先级队列类的默认初始容量为11，而延迟工作队列类的默认初始容量为16；
• 延迟队列类根据“旧容量 < 64”与否进行“2倍加2”与“1.5倍”的双规则进行扩容，而延迟工作队列类只按“1.5倍”的单规则进行扩容；
• 延迟队列类的泛型被指定为Delayed @ 延迟接口，而延迟工作队列类的泛型被直接指定为可运行接口，虽然其实际保存的可运行调度未来同样也是延迟接口的对象；
• 延迟队列类元素被内部移除的时间复杂度为O(n)，因为在内部移除前需要先遍历数组找到指定元素的首个实例；而延迟工作队列类在元素类型/排序方面对元素定位进行了订制，使得内部移除的元素可以被直接定位而无需进行遍历查找，从而令其时间复杂度和只需计算排序消耗的头部移除一样为O(log n)。
   
   

使用

 创建

• public DelayedWorkQueue() —— 创建延迟工作队列。

 插入

    注意！本文的“元素”与“延迟到期元素”是不同的概念。元素指队列所有元素，而延迟到期元素则是指队列中剩余延迟时间小于等于0的元素。

• public boolean add(E e) —— 新增 —— 向当前延迟工作队列的尾部插入指定元素，并根据指定元素的剩余延迟时间按小顶堆规则将之排序到合适位置。该方法是尾部插入方法“异常”形式的实现，当当前延迟工作队列存在剩余容量时插入并返回true；否则抛出非法状态异常。虽说定义如此，但实际由于延迟工作队列类是真正的无界队列，最大容量只受限于堆内存的大小，故而永远不会抛出非法状态异常，而只会在堆内存不足时抛出内存溢出错误。

• public boolean offer(E e) —— 提供 —— 向当前延迟工作队列的尾部插入指定元素，并根据指定元素的剩余延迟时间按小顶堆规则将之排序到合适位置。该方法是尾部插入方法“特殊值”形式的实现，当当前延迟工作队列存在剩余容量时插入并返回true；否则返回false。虽说定义如此，但实际由于延迟工作队列类是真正的无界队列，最大容量只受限于堆内存的大小，故而永远不会返回false，而只会在堆内存不足时抛出内存溢出错误。

• public void put(E e) —— 放置 —— 向当前延迟工作队列的尾部插入指定元素，并根据指定元素的剩余延迟时间按小顶堆规则将之排序到合适位置。该方法是尾部插入方法“阻塞”形式的实现，当当前延迟工作队列存在剩余容量时插入；否则无限等待至存在剩余容量为止。虽说定义如此，但实际由于延迟工作队列类是真正的无界队列，最大容量只受限于堆内存的大小，故而永远不会等待，而只会在堆内存不足时抛出内存溢出错误。

• public boolean offer(E e, long timeout, TimeUnit unit) —— 提供 —— 向当前延迟工作队列的尾部插入指定元素，并根据指定元素的剩余延迟时间按小顶堆规则将之排序到合适位置。该方法是尾部插入方法“超时”形式的实现，当当前延迟工作队列存在剩余容量时插入并返回true；否则在指定等待时间内有限等待至存在剩余容量为止，超出指定等待时间则返回false。虽说定义如此，但实际由于延迟工作队列类是真正的无界队列，最大容量只受限于堆内存的大小，故而永远不会等待/返回false，而只会在堆内存不足时抛出内存溢出错误。
   

 移除

• public E remove() —— 移除 —— 从当前延迟工作队列的头部移除并获取剩余延迟时间最小的延迟到期元素，并触发后续元素的重排序。该方法是头部移除方法“异常”形式的实现，当当前延迟工作队列存在延迟到期元素时移除并返回头延迟到期元素；否则抛出无元素异常。

• 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。注意是元素，而非延迟到期元素。
      由于指定元素可能处于任意位置（不一定是头/尾），因此被称为内部移除。内部移除并不是常用的方法：一是其不符合FIFO的数据操作方式；二是各类实现为了提高性能可能会使用各种优化策略，而remove(Object o)方法往往无法适配这些策略，导致性能较/极差。

• public void clear() —— 清理 —— 从当前延迟工作队列中移除所有元素。注意是元素，而非延迟到期元素。
   

 检查

• public E element() —— 元素 —— 从当前延迟工作队列的头部获取剩余延迟时间最小的元素。该方法是检查方法头部位置“异常”形式的实现，当当前延迟工作队列存在元素时返回头元素；否则抛出无元素异常。注意该方法不同于头部移除方法，其获取的是元素而非延迟到期元素，因此即使头元素延迟尚未到期也会将之返回，故而只会在延迟工作队列为空时抛出无元素异常。

• public E peek() —— 窥视 —— 从当前延迟工作队列的头部获取剩余延迟时间最小的元素。该方法是检查方法头部位置“特殊值”形式的实现，当当前延迟工作队列存在元素时返回头元素；否则返回null。注意该方法不同于头部移除方法，其获取的是元素而非延迟到期元素，因此即使头元素延迟尚未到期也会将之返回，故而只会在延迟工作队列为空时抛出无元素异常。
   

 流失

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

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

 查询

• public int size() —— 大小 —— 获取当前延迟工作队列的元素总数。注意是元素，而非延迟到期元素。

• public boolean isEmpty() —— 是否为空 —— 判断当前延迟工作队列是否为空，是则返回true；否则返回false。

• public int remainingCapacity() —— 剩余容量 —— 获取当前延迟工作队列的剩余容量。由于延迟工作队列类是无界队列，因此该方法将永远返回Integer.MAX_VALUE。

• public Object[] toArray() —— 转化数组 —— 获取按迭代器顺序包含当前延迟工作队列中所有元素的新数组。注意是元素，而非延迟到期元素。

• public T[] toArray(T[] a) —— 转化数组 —— 获取按迭代器顺序包含当前延迟工作队列中所有元素的泛型数组。如果参数泛型数组长度足以容纳所有元素，则令之承载所有元素后返回。并且如果参数泛型数组的长度大于当前延迟工作队列的元素总数，则将已承载所有元素的参数泛型数组的size索引位置设置为null，表示从当前延迟工作队列中承载的元素到此为止。当然，该方案只对不允许保存null元素的集有效。如果参数泛型数组的长度不足以承载所有元素，则重分配一个相同泛型且长度与当前延迟工作队列元素总数相同的新泛型数组以承载所有元素后返回。注意是元素，而非延迟到期元素。
   

 迭代器

• public Iterator<E> iterator() —— 迭代器 —— 创建可遍历当前延迟工作队列中元素的迭代器。注意是元素，而非延迟到期元素。

    事实上，上文中只列举了大部分常用方法。由于延迟工作队列类是集接口的实现类，因此其也实现了其定义的所有方法，例如contains(Object o)、removeAll(Collection<?> c)、containsAll(Collection<?> c)等。但由于这些方法的执行效率不高，并且与延迟工作队列类的主流使用方式并不兼容/兼容性差，因此通常是不推荐使用的，有兴趣的童鞋可以去查看源码实现。
 
 

优化

 可运行调度未来接口

    延迟工作队列实际只会保存可运行调度未来。虽然泛型被指定为可运行接口，但由于延迟工作队列类实际只在调度线程池执行器类中被使用，并且调度线程池执行器类限定任务必须为可运行调度未来接口类型，因此延迟工作队列实际只会保存可运行调度未来。这不禁令人产生疑惑…延迟工作队列类为什么不直接将泛型设置为可运行调度未来接口呢？

    这确实是一个非常令人费解的问题，因为从设计上看，延迟工作队列类的元素类型需要具备两方面的特性：一是可以代表任务，因为延迟工作队列具体就是在线程池执行器作为任务容器使用的；二是可以实现延迟，因为这本就是延迟工作队列类所提供的基本功能。因此无论从什么角度上看可运行调度未来接口同时作为可运行接口/延迟接口的子接口都更合适作为延迟工作队列类的泛型…但实际情况显然不是如此。

    将可运行接口作为延迟工作队列类的泛型最大的问题在于需要对每个插入的元素都强制转化为可运行调度未来接口类型，因为首先延迟工作队列类设计用于保存元素的[queue @ 队列/元素数组]本就是可运行调度未来接口类型，因此可运行接口对象并无法直接插入；此外实现元素延迟也需要调用compareTo(T o)方法进行元素间剩余延迟时间的比较以实现排序，而可运行显然也并不存在该方法。我们先不考虑这种父类至子类的强行转化可能导致失败，单单从问题上看就完全可以通过将泛型指定为可运行调度未来接口的方式解决，所以强转这一步行为理论上是完全可以不必要的。

    将可运行接口作为延迟工作队列类的泛型主要是基于扩展/兼容性的考量。该说法实际上只是我个人的主观猜测，因为对于一个难以理解的问题，通常可以从实现/性能/开销/结构/使用五个方向去考虑。其中对于实现/性能/开销/使用是可以直接排除的，因为泛型指定为可运行接口不但增加了实现的复杂度，还导致强转降低了性能/增大了开销，很显然这都是负面影响，因此唯有在结构方面还可能带来正面收益，因为可运行接口作为可运行调度未来接口的父接口是契合“面向接口编程”的思想的。

    “面向接口编程”思想的本质是“面向父/超类/接口编程”，其推荐使用父/超类/接口类型的变量来承接子/实现类的实例以降低代码的耦合度并提升扩展/兼容性。虽然在JDK1.8的源码中延迟工作队列类并没有被调度线程池执行器类以外的API所使用，但很显然作者也并未打算将之彻底锁死在调度线程池执行器类中，该论点的依据有二：一是延迟工作队列类的访问权限为default而非protected，这使得延迟工作队列类可以被调度线程池执行器类的兄弟类所使用；二是开发者可以在外部通过getQueue()方法获取到内置在调度线程池执行器中的延迟工作队列实例并执行操作。在上述情况下保证插入的元素一定为可运行调度任务接口对象是无法/难以做到的…由此我们就可以猜测之所以使用可运行接口会被作为泛型就是作者为后期在调度线程池执行器类以外的API中使用延迟工作队列类所做出的预留/提示/标记。而如果真是如此，那到时候延迟工作队列类必然还需要进行再一次的改版。因为目前除了强转外，延迟工作队列类的内部逻辑完全是基于元素为可运行调度任务接口对象的前提下实现的，后期显然还需要再增加对非可运行调度任务接口对象的支持。

/**
 * 主方法
 *
 * @param args 参数集
 */
public static void main(String[] args) {
    // 获取内置于调度线程池执行器中的延迟工作队列实例。
    ScheduledThreadPoolExecutor scheduledThreadPoolExecutor = new ScheduledThreadPoolExecutor(20);
    BlockingQueue<Runnable> blockingQueue = scheduledThreadPoolExecutor.getQueue();
    // 向延迟工作队列中添加一个可运行，该行为会抛出转化异常。
    Runnable runnable = () -> System.out.println("我是一个无法被强转为可运行调度未来的可运行...");
    blockingQueue.add(runnable);
}

 调度未来任务类

    延迟工作队列类基于ScheduledFutureTask @ 调度未来任务类对元素定位进行了优化。调度未来任务类是可运行调度未来接口的实现类，也是调度线程池执行器类默认使用的可运行调度未来接口实现类，即调度线程池执行器会将递交的任务封装为调度未来任务后执行。开发者可以通过“装饰”令调度线程池执行器类使用其它可运行调度未来接口实现类，该知识点会在调度线程池执行器类的专项文章中详述，但是并不建议这么做，因为延迟工作队列类优化了对调度未来任务类型元素的定位，即如果元素为调度未来任务则延迟工作队列可以在常数时间内快速定位到其在[队列/元素数组]中的位置，换句话说就是查找的时间复杂度为O(1)。这种优化虽然付出了一个额外字段的开销，但对查找性能的提升却非常明显，因为在正常情况下想要定位一个指定元素就只能通过时间复杂度为O(n)的遍历操作实现。延迟工作队列类之所以会设计该类优化是因为调度线程池执行器在运行过程中可能会因为周期性任务的取消而相对频繁地对元素进行内部移除，而由于内部移除需要先对元素进行定位，因此大量遍历必然会对调度线程池执行器的整体性能造成影响。而[堆索引]的存在避免了调度未来任务的遍历定位，从而就使得调度未来任务的内部移除流程可以与头部移除的流程相近，故而在时间复杂度上也由原本的O(n)下降为了O(log n)。O(log n)是元素被内部移除后延迟工作队列在移除位置的基础上对剩余元素进行下排序的时间复杂度，虽说与头部移除的时间复杂度相同，但实际由于下排序的起点位于[队列/元素数组]内部而非头部，因此实际时间消耗会比头部移除更少。

    调度未来任务在[队列/元素数组]中的所在位置会保存在[heapIndex @ 堆索引]中，并随着在上/下排序而更新。调度未来任务的[堆索引]是其可被直接定位的核心原因，这使得其在需要被定位时可直接通过[堆索引]在[队列/元素数组]的指定位置上进行查找。但这并不意味着找到的调度未来任务与指定调度未来任务就是相同的，因为上文虽然说过延迟工作队列类是调度线程池执行器类的内部类，并且实例也只会在其内部创建，但开发者依然可以通过执行器的getQueue()方法获取到延迟工作队列。因此从一个延迟工作队列中获取调度未来任务并将之从另一个延迟工作队列中移除的情况是可能存在的…故而如果发现并不相同则依然要进行遍历定位。此外，由于[堆索引]只能唯一保存，因此一个调度未来任务“在被移除前”不允许再次插入同一个延迟工作队列中。因为后一次插入会覆盖前一次插入维护的[堆索引]，而这可能导致操作出现异常…以内部移除为例：内部移除的作用是移除指定元素迭代器顺序的首个实例，而如果一个调度未来任务在一个延迟工作队列中被多次保存，那就可能出现移除非首个实例的情况。当然，如果是非调度未来任务类型的元素那也没有这种要求。

    [堆索引]可以间接减少延迟工作队列中的垃圾遗留。所谓的垃圾是指无效元素及其关联的相应对象，[堆索引]的存在并无法直接减少垃圾在延迟工作队列中的遗留，即其在内部运行流程方面并不会对GC产生额外收益。而之所以说[堆索引]可以间接减少延迟工作队列中的垃圾遗留是因为其大幅优化调度未来任务的定位后使得内部移除不再是一个低性能的操作，因此调度线程池执行器完全可以通过频繁调用延迟工作队列的remove(Object x)方法将无效调度未来任务内部移除来降低其中垃圾遗留的总量，而无需等待其被自然排序到[队列/元素数组]的顶部后再头部移除。