ava

DelayQueue【源码】》学习过程/多有漏误/仅作参考/不再更新相关系列《Java

Collection/Executor

DelayQueue【总结】》学习总结/最新最准/持续更新相关系列《Java

Collection/Executor

DelayQueue【问题】》学习解答/持续更新涉及内容《Java

Collection

DelayQueue延迟队列类是BlockingQueue阻塞队列接口的实现类之一基于数组实现特点是元素会被延迟头部移除。

延迟队列类不支持任意类型的元素其元素被强制指定为Delayed延迟接口对象即延迟接口实现类对象否则会抛出类型转换异常。

之所以强制类型是因为延迟队列会调用延迟接口定义的getDelay(TimeUnit

unit)方法来获取元素的剩余延迟来实现精确延迟因此延迟接口实现类必须实现该方法以返回有效的剩余延迟。

除此之外由于底层使用PriorityQueue优先级队列类的原因延迟接口实现类还必须实现Comparable比较能力接口定义的compareTo(T

o)方法以实现元素之间剩余延迟时间的比较该知识点的详细内容会在下文详述。

延迟队列类不允许存null值或者说阻塞队列接口的所有实现类都不允许存null值。

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

延迟队列类是无界队列意味着其最大容量理论上只受限于堆内存的大小。

延迟队列类底层使用优先级队列类实现由于其扩容机制的存在延迟队列类也被纳入无界队列的范围中。

但虽说如此优先级队列类在实现中还受到数组实现与int类型影响因此延迟队列的最大容量实际上为Integer.MAX_VALUE。

由于其无界队列的定义为了掩盖实际实现中受到的限制当其保存的元素总数触达上限时会模拟堆内存不足的场景手动抛出内存溢出错误。

延迟队列类是线程安全的或者说阻塞队列接口的所有实现类都是线程安全的其接口定义中强制要求实现类必须线程安全。

延迟队列类采用“单锁”线程安全机制即使用一个ReentrantLock可重入锁类对象来保证整体的线程安全。

延迟队列类的迭代器是弱一致性即可能迭代到已移除的元素及无法迭代到新插入的元素。

延迟队列的迭代器实现非常直接或者说过于直接了其会直接将数据拷贝一份快照存入生成的迭代器中以进行迭代。

这么做的好处是迭代器的实现非常的简单但缺点也明显当延迟队列的元素总数较大或生成的迭代器数量较多时对内存的消耗会非常严重。

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

方法的不同形式实际上是BlockingQueue阻塞队列接口的定义链接阻塞双端队列只是继承了这个定义而已。

所谓方法的不同形式是指方法在保证自身核心操作不变的情况下实现了多种不同的回应形式来应对不同场景下的使用要求。

例如对于插入当容量不足时有些场景希望在失败时抛出异常而有些场景则希望能直接返回失败的标记值而有些场景又希望可以等待直至有可用空间后成功新增为止…正因如此BlockingQueue阻塞队列接口特意提供了四种不同的形式风格以满足不同场景下的使用需求因此一个方法最多并非所有方法都实现了四种形式可能有四种不同回应形式。

具体四种回应形式如下

队列接口定义

当不满足操作条件时直接返回失败标记值。

例如之所以不允许存null值就是因为null被作为了操作失败时的标记值

阻塞无限等待

当不满足操作条件时有限等待如果在指定等待时间之前满足操作条件则执行否则返回失败标记值。

public

需要提前说明的是本文中的元素与延迟到期元素在概念上并不相同元素指延迟队列中的所有元素而延迟到期元素指的是延迟队列中已延迟到期的元素因此延迟到期元素是元素的子集在下文中要时刻注意这两者的区别。

public

向当前延迟队列的尾部插入指定元素并根据指定元素的剩余延迟按小顶堆规则将之排序到合适位置。

该方法是尾部插入方法“异常”形式的实现当当前延迟队列存在剩余容量时插入并返回true否则抛出非法状态异常。

虽说定义如此但实际由于延迟队列类是真正的无界队列最大容量只受限于堆内存的大小故而永远不会抛出非法状态异常而只会在堆内存不足时抛出内存溢出错误。

由于延迟队列类基于优先级队列类实现因此最大容量实际还受限于Integer.MAX_VALUE。

当元素总数触达该上限时为了掩盖实际实现上的限制会手动抛出内存溢出错误。

public

向当前延迟队列的尾部插入指定元素并根据指定元素的剩余延迟按小顶堆规则将之排序到合适位置。

该方法是尾部插入方法“特殊值”形式的实现当当前延迟队列存在剩余容量时插入并返回true否则返回false。

虽说定义如此但实际由于延迟队列类是真正的无界队列最大容量只受限于堆内存的大小故而永远不会抛出非法状态异常而只会在堆内存不足时抛出内存溢出错误。

由于延迟队列类基于优先级队列类实现因此最大容量实际还受限于Integer.MAX_VALUE。

当元素总数触达该上限时为了掩盖实际实现上的限制会手动抛出内存溢出错误。

public

向当前延迟队列的尾部插入指定元素并根据指定元素的剩余延迟按小顶堆规则将之排序到合适位置。

该方法是尾部插入方法“阻塞”形式的实现当当前延迟队列存在剩余容量时插入否则无限等待至存在剩余容量为止。

虽说定义如此但实际由于延迟队列类是真正的无界队列最大容量只受限于堆内存的大小故而永远不会抛出非法状态异常而只会在堆内存不足时抛出内存溢出错误。

由于延迟队列类基于优先级队列类实现因此最大容量实际还受限于Integer.MAX_VALUE。

当元素总数触达该上限时为了掩盖实际实现上的限制会手动抛出内存溢出错误。

public

向当前延迟队列的尾部插入指定元素并根据指定元素的剩余延迟按小顶堆规则将之排序到合适位置。

该方法是尾部插入方法“超时”形式的实现当当前延迟队列存在剩余容量时插入并返回true否则在指定等待时间内有限等待至存在剩余容量为止超出指定等待时间则返回false。

虽说定义如此但实际由于延迟队列类是真正的无界队列最大容量只受限于堆内存的大小故而永远不会抛出非法状态异常而只会在堆内存不足时抛出内存溢出错误。

由于延迟队列类基于优先级队列类实现因此最大容量实际还受限于Integer.MAX_VALUE。

当元素总数触达该上限时为了掩盖实际实现上的限制会手动抛出内存溢出错误。

public

从当前延迟队列的头部移除并获取剩余延迟最小的延迟到期元素并触发后续元素的重排序。

该方法是头部移除方法“异常”形式的实现当当前延迟队列存在延迟到期元素时移除并返回头延迟到期元素否则抛出无元素异常。

延迟队列类并没有自实现remove()方法而是直接使用了父类AbstractQueue抽象队列抽象类的实现。

在实现中其调用了头部移除方法“特殊值”形式的poll()方法来达成目的使得所有抽象队列抽象类的子类只需实现poll()方法后就可以正常调用remove()方法。

这种代码结构是设计模式的一种被称为“模板模式”。

/***

检索并移除队列的头。

该方法不同于poll()方法如果队列为空时其会抛出一个异常。

*

This

从当前延迟队列的头部移除并获取剩余延迟最小的延迟到期元素并触发后续元素的重排序。

该方法是头部移除方法“特殊值”形式的实现当当前延迟队列存在延迟到期元素时移除并返回头延迟到期元素否则返回null。

public

从当前延迟队列的头部移除并获取剩余延迟最小的延迟到期元素并触发后续元素的重排序。

该方法是头部移除方法“阻塞”形式的实现当当前延迟队列存在延迟到期元素时移除并返回头延迟到期元素否则无限等待至存在延迟到期元素为止。

public

从当前延迟队列的头部移除并获取剩余延迟最小的延迟到期元素并触发后续元素的重排序。

该方法是头部移除方法“超时”形式的实现当当前延迟队列存在延迟到期元素时移除并返回头延迟到期元素否则在指定等待时间内有限等待至存在延迟到期元素为止超出指定等待时间则返回null。

public

从当前延迟队列中按迭代器顺序移除首个指定元素成功则返回true否则返回false。

注意是元素而非延迟到期元素。

由于指定元素可能处于任意位置不一定是头/尾因此被称为内部移除。

内部移除并不是常用的方法一是其不符合FIFO的数据操作方式二是各类实现为了提高性能可能会使用各种优化策略而remove(Object

public

从当前延迟队列的头部获取剩余延迟最小的元素。

该方法是头部检查方法“异常”形式的实现当当前延迟队列存在元素时返回头元素否则抛出无元素异常。

注意该方法不同于头部移除方法其获取的是元素而非延迟到期元素因此即使头元素延迟尚未到期也会将之返回故而只会在延迟队列为空时抛出无元素异常。

与remove()方法相同延迟队列类并没有自实现element()方法而是直接使用了父类AbstractQueue抽象队列抽象类的实现具体源码如下。

在实现中其调用了检查方法“特殊值”形式的peek()方法来达成目的使得所有抽象队列抽象类的子类只需实现peek()方法后就可以正常调用element()方法。

这种代码结构是设计模式的一种被称为“模板模式”。

/***

检索但不移除队列的头元素。

该方法不同于peek()方法如果队列为空时其会抛出一个异常。

*

This

元素用于返回队列的头元素但不移除。

当队列中不存在元素时抛出无元素异常。

*/

public

从当前延迟队列的头部获取剩余延迟最小的元素。

该方法是头部检查方法“特殊值”形式的实现当当前延迟队列存在元素时返回头元素否则返回null。

注意该方法不同于头部移除方法其获取的是元素而非延迟到期元素因此即使头元素延迟尚未到期也会将之返回故而只会在延迟队列为空时抛出无元素异常。

public

将当前延迟队列中的所有延迟到期元素流失到指定集中并返回流失的延迟到期元素总数。

被流失的延迟到期元素将不再存在于当前延迟队列中。

public

将当前延迟队列中最多指定数量的延迟到期元素流失到指定集中并返回流失的延迟到期元素总数。

被流失的延迟到期元素将不再存在于当前延迟队列中。

public

获取当前延迟队列的剩余容量。

由于延迟队列类是无界队列因此该方法将永远返回Integer.MAX_VALUE。

public

获取按迭代器顺序包含当前延迟队列中所有元素的新数组。

注意是元素而非延迟到期元素。

public

获取按迭代器顺序包含当前延迟队列中所有元素的泛型数组。

如果参数泛型数组长度足以容纳所有元素则令之承载所有元素后返回。

并且如果参数泛型数组的长度大于当前延迟队列的元素总数则将已承载所有元素的参数泛型数组的size索引位置设置为null表示从当前延迟队列中承载的元素到此为止。

当然该方案只对不允许保存null元素的集有效。

如果参数泛型数组的长度不足以承载所有元素则重分配一个相同泛型且长度与当前延迟队列元素总数相同的新泛型数组以承载所有元素后返回。

注意是元素而非延迟到期元素。

迭代器

创建可遍历当前延迟队列中元素的迭代器。

注意是元素而非延迟到期元素。

事实上上文中只列举了大部分常用方法。

由于延迟队列类是集接口的实现类因此其也实现了其定义的所有方法例如contains(Object

c)等。

但由于这些方法的执行效率不高并且与延迟队列类的主流使用方式并不兼容/兼容性差因此通常是不推荐使用的有兴趣的童鞋可以去查看源码实现。

延迟队列类强制元素必须是延迟接口类型即元素必须是延迟接口实现类对象。

如此设计的原因是因为延迟队列类会调用延迟接口定义的getDelay(TimeUnit

unit)方法来获取元素的剩余延迟来实现精确延迟因此元素类必须实现该方法以返回有效的剩余延迟。

除此之外元素类还必须实现比较能力接口定义的compareTo(T

o)方法以实现元素剩余延迟的比较即元素类必须在compareTo(T

unit)方法来比较两个元素剩余延迟的大小这与延迟队列类底层使用优先级队列类实现有关。

元素只有在延迟到期的情况下才允许被头部移除即只有延迟到期元素才能被头部移除这是实现延迟队列类的核心操作。

所谓的延迟到期是指元素的剩余延迟小于等于0小于0是因为元素在延迟过期后未能被实时的头部移除。

当移除者执行移除方法的线程到来时该延迟到期元素可被直接头部移除而对于尚未延迟到期的元素则移除者必须等待其延迟到期后方可头部移除。

优先级队列

延迟队列类自身没有实现相关的数据模型其底层使用优先级队列类实现。

优先级队列类不是常规的FIFO实现元素在内部会根据剩余延迟按小顶堆的规则进行排序。

在延迟队列类的实现中会将剩余延迟最小的元素排序在优先级队列的头部即头元素表示其获得了最高的优先级。

这便是元素类必须在compareTo(T

o)方法中实现剩余延迟比较的根本原因因为比较是排序的基本条件。

当移除者到来时会先获取底层优先级队列的头元素并判断。

如果头元素不存在说明延迟队列中没有可头部移除的延迟到期元素令当前移除者进入有限/无限等待状态具体视执行的头部移除方法的形式而定如果头元素存在且延迟到期说明延迟队列中存在可头部移除的延迟到期元素当前移除者可直接将之从底层优先级队列中头部移除并唤醒一个等待中的移除者如果存在的话对底层优先级队列的后续头元素进行头部移除能否移除成功视底层优先级队列后续头元素是否延迟到期而定而如果头元素存在但尚未延迟到期则这是最复杂的情况需要继续判断领导者是否存在。

如果领导者存在令当前移除者进入有限/无限等待状态如果领导者不存在则将当前移除者设置为领导者并令之进入专属有限等待状态即其等待时间与头元素的剩余延迟相同。

以上是头部移除方法“阻塞”形式的流程其它形式的流程与之大致相同但会根据实际需求进行调整。

领导者

所谓领导者本质是专属等待底层优先级队列头元素延迟到期的移除者确保头元素在延迟到期时可被实时头部移除以实现精确延迟。

延迟队列类使用了领导者

追随者模式的变种模式以实现最大限度的减少非必要等待。

即当一个移除者成为领导者后会专属等待底层优先级队列的头元素延迟到期而其它移除者则会进入有限/无限等待状态从而避免大量移除者定时等待同一个头元素的情况。

当领导者超时唤醒后此时的头元素也已经延迟到期而成为了延迟到期元素允许被头部移除。

成功执行头部移除的领导者在结束之前需要唤醒一个等待中的移除者以期望其对底层优先级队列的后续头元素进行专属等待如果后续头元素存在且未延迟到期即成为新的领导者不一定能成功因为存在并发竞争。

领导者无法保证在头元素延迟到期后必然将之头部移除。

由于等待时间与头元素的剩余延迟相同领导者基本可以在头元素延迟到期的同时因为超时而唤醒从而实时头部移除已成为延迟到期元素的头元素。

但这并不是必然的由于程序运行时间消耗、CPU时间片分配、新移除者的外部竞争及其它定时移除者的内部竞争等原因领导者无法保证必然将头元素头部移除甚至无法保证自身是因超时而唤醒。

典型的场景是头元素延迟到期但领导者由于上述列举的各项原因尚未因超时而唤醒。

而此时恰好有新移除者成功头部移除了头元素并对领导者发送了信号使得领导者并非因为等待超时而唤醒。

头部移除头延迟到期元素失败的领导者根据头部移除方法的形式及程序的运行状态会进行再次等待或返回null。

领导者可能在其定时等待期间被撤销。

这是可以预想到的因为领导者是专属等待底层优先级队列头元素延迟到期的线程因此如果在等待期间底层优先级队列头元素发生改变例如尾部插入了一个剩余延更小的元素而将之排序成为新头元素则该领导者就失去了精确等待的作用因为其等待时间与新头元素的剩余延迟未必相同需要将之撤销。

撤销后的领导者会唤醒一个等待中的移除者可能是自己因为其自身也在等待也可能是其它移除者以期望其对底层优先级队列的新头元素进行专属等待即成为新的领导者不一定能成功因为存在并发竞争。

因此移除者必须准备好在等待过程中获得/失去领导地位。