定时任务如何实现定时执行

前言

今天的主题就是聊一聊，spring task 和 Quartz 如何实现任务的定时执行的。 关于spring task 和 Quartz 两个任务中间件，之前写过一篇原理分析的，有兴趣的可以看看。

如何实现定时执行

先看看spring task 和 Quartz 的任务调度流程图

Quartz：

quartz 框架实现定时执行的原理很好理解，就是工作线程执行完成之后，会更新任务下次执行的时间，调度线程一直去遍历任务信息，查询到此时需要运行的任务，然后交给教程池执行。

spring task：

spring task没有单独的调度线程去扫描，而是工作线程在执行任务完成之后，计算下次运行的时间（延迟多少ms执行）之后，提交到线程池。

spring task 问题

‍假设我先提交到线程池的任务A，需要等待1个小时才执行，本身线程池设置的线程只有一个，那么我第二任务B10s钟就要一次。那么第二任务难道要等第一个任务执行完成之后才执行？

当然不是了，任务在进入队列中的时候会根据执行时间进行排序，最先执行的任务会被排到前面，这样就不会存在，A任务先执行先进入队列，但是B任务后执行，但是B任务的下次执行时间先与A，而被A阻塞。

DelayedWorkQueue

DelayedWorkQueue 是一种特殊的优先级队列（Priority Queue），用于存放实现了 RunnableScheduledFuture 接口的任务。这些任务的主要特点是有延迟（多久后执行）或周期（每隔多久执行一次）。队列的核心需求是：总是能够快速找到并取出下一个即将到期的任务。

排序算法与数据结构

DelayedWorkQueue 的排序算法紧密依赖于其底层的数据结构——二叉堆（Binary Heap） ，具体来说是一个基于数组实现的最小堆（Min-Heap） 。

1. 数据结构：最小堆

• 什么是堆？  堆是一种特殊的完全二叉树。最小堆的特性是：任何一个父节点的值都小于或等于其左右子节点的值。这意味着整个堆的根节点（即数组的第一个元素）永远是值最小的那个元素。

• 如何存储？  堆使用数组来存储，这使得它非常紧凑且高效。对于数组中任意位置 i 的节点：

  • 其父节点位置：(i - 1) / 2
  • 其左子节点位置：2 * i + 1
  • 其右子节点位置：2 * i + 2

2. 排序/比较依据

队列中的元素（RunnableScheduledFuture 任务）是根据它们的到期时间（Expiration Time）  来进行排序的。

• 延迟任务：schedule(command, delay, unit)

  • 到期时间 = 当前时间(System.nanoTime()) + 延迟时间(delay)

• 周期性任务：scheduleAtFixedRate(...) 和 scheduleWithFixedDelay(...)

  • 到期时间会根据设定的周期和上一次执行时间进行计算。

排序规则很简单：到期时间越早的任务，其“优先级”越高，在堆中的位置就越靠近根部。

3. 核心算法操作

堆排序的逻辑主要体现在元素的插入和取出操作中，这两个操作都需要通过“上浮”和“下沉”来维持堆的特性。

a) 插入任务 - offer(Runnable x)
当一个新任务被加入队列时：

1. 放置：将任务放入数组的下一个可用位置（完全二叉树的最后一个节点）。

2. 上浮 (Sift Up)  ：比较新插入的节点和其父节点的到期时间。

   • 如果新节点的到期时间早于（小于）  父节点，则交换它们的位置。
   • 重复这个过程，直到新节点不再小于其父节点，或者它已经到达根节点为止。
   • 这个过程也叫做 堆化（Heapify） 。

b) 取出任务 - take()
当工作线程需要获取一个任务来执行时：

1. 获取根节点：数组的第一个元素就是下一个要执行的任务（到期时间最早的）。

2. 处理尾节点：将数组的最后一个元素移到根节点的位置。

3. 下沉 (Sift Down)  ：将新的根节点与其左右子节点中到期时间较早的那个进行比较。

   • 如果根节点大于这个子节点，则交换它们的位置。
   • 重复这个过程，直到当前节点不再大于任何子节点，或者它已经到达叶节点为止。

4. 返回第一步获取的根节点任务。

这个过程确保了在取出最优先的任务后，剩下的元素能被重新整理成一个新的最小堆。

总结

一个小小的定时任务，竟然包含者如此多的知识点。说实话这个算法确实让我非常的意外 感谢老铁的一键三连