java►并发

Java并发编程的艺术-第6章3-DelayQueue

DelayQueue: JDK提供的延迟获取元素的无界阻塞队列。
应用场景:

  1. 缓存有效期: 能取到的时候过期.
  2. 定时任务: 能取到的时候执行。

DelayQueue的两个特性:
无界: 说明底层至少使用了链表。
阻塞: 为底层实现时，利用访问线程干活埋下伏笔(leader)。

底层实现机制

底层用一个优先级队列存储delay元素(比如定时任务),排序依据是延迟的时长。
可以看出，这里用的是一个支持无界阻塞的优先级队列实现(例如PriorityBlockingQueue)。

时间复杂度: O(logN)。由于使用的是优先级队列(最小堆),插入新元素(任务)的时间复杂度是O(logN)。

take流程:

  1. lock.lockInterruptibly();
  2. delay = 队首元素延时;
  3. delay<=0: 取出该元素;
  4. delay>0: 尝试设置自己线程为leader，然后等待delay时间。
  5. finnally: lock.unlock();

这里leader的职责是等待delay时间，以及唤醒其他等待线程。
注意第四步里, 由于leader只能有一个,所以如果尝试成为leader失败，就直接await就好,会被leader叫醒的。

offer: offer就是简单地把元素插入堆中。如果正好是延迟最小，则此时之前的leader等待时间太长了，因此需要叫醒所有等待线程。

总结

DelayQueue
优点:
资源开销小: 本质上只需一个线程负责等待;每次等待间隔都是delay时间,cpu空转少。
缺点
插入删除延时元素时间复杂度为O(logN)，对于成千上万的延时任务时间开销大,有待优化。

优化思路:
如果要比O(logN)更好,很自然的思路就是使用哈希表O(1)，空间换时间。

优化方案

需求: 降低插入删除延时元素的时间复杂度。
方案:

  1. 保留优先级队列,但里面的元素改成链表引用(比如从Task到List<Task>);
  2. 引入辅助哈希表,保存的也是链表引用(List<Task>)，hash函数的输入为延时时长。

这里即使List<Task>长期只有1个元素也没有关系,这里只是为了起到C++中指针的效果，方便从哈希表里直接修改(插入删除)优先级队里的数据。

take/offer流程: 与之前相似,唯一不同就是取到List<Task>后，遍历其中所有Task。

插入延时元素(任务)：（删除也类似）

  1. 根据延时,通过哈希函数找到哈希表中的槽位;
  2. 如果以前有过相同延时: 直接插入List;
  3. 如果以前没有相同延时: 新建List，并且插入优先级队列。

可以看出这里优化的重要条件是能合并多个Task到List。
为了达到这个条件，可以使用进一步的优化方案: 时间轮。

推荐文章