定時任務如何實現定時執行❔

我是[提前退休的java猿]，一名7年java開發經驗的開發組長，分享工作中的各種問題！抖音同號🧨

前言

今天的主題就是聊一聊，spring task 和 Quartz 如何實現任務的定時執行的。關於spring task 和 Quartz 這兩個任務中間件，之前寫過一篇原理分析的，有興趣的可以看看。

如何實現定時執行

先看看spring task 和 Quartz 的任務調度流程圖

Quartz：

quartz 框架實現定時執行的原理很好理解，就是工作線程執行完成之後，會更新任務下次執行的時間，調度線程一直去遍歷任務資訊，查詢到此時需要運行的任務，然後交給線程池執行。

spring task：

spring task沒有單獨的調度線程去掃描，而是工作線程在執行任務完成之後，計算下次運行的時間（延遲多少ms執行）之後，提交到線程池。

運行中的工作線程，一直會嘗試著去獲取任務，獲取不到任務就睡眠，然後又去重隊列獲取任務，查看是否有需要執行

spring task 問題

👁‍🗨假設我先提交到線程池的任務A，需要等待1個小時才執行，本身線程池設定的線程只有一個，那麼我第二任務B10秒鐘就要一次。那麼第二任務難道要等第一個任務執行完成之後才執行？ 😱

🔈當然不是了，任務在進入隊列中的時候會根據執行時間進行排序，最先執行的任務會被排到前面，這樣就不會存在，A任務先執行先進入隊列，但是B任務後執行，但是B任務的下次執行時間先於A，而被A阻塞。

先了解是如何進行排序的，就需要看DelayedWorkQueue方法的實現了

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)
當一個新任務被加入隊列時：

放置：將任務放入數組的下一個可用位置（完全二叉樹的最後一個節點）。
上浮 (Sift Up) ：比較新插入的節點和其父節點的到期時間。
- 如果新節點的到期時間早於（小於） 父節點，則交換它們的位置。
- 重複這個過程，直到新節點不再小於其父節點，或者它已經到達根節點為止。
- 這個過程也叫做 堆化（Heapify） 。

b) 取出任務 - take()
當工作線程需要獲取一個任務來執行時：

獲取根節點：數組的第一個元素就是下一個要執行的任務（到期時間最早的）。
處理尾節點：將數組的最後一個元素移到根節點的位置。
下沉 (Sift Down) ：將新的根節點與其左右子節點中到期時間較早的那個進行比較。
- 如果根節點大於這個子節點，則交換它們的位置。
- 重複這個過程，直到當前節點不再大於任何子節點，或者它已經到達葉節點為止。
返回第一步獲取的根節點任務。

這個過程確保了在取出最優先的任務後，剩下的元素能被重新整理成一個新的最小堆。

可以看看關鍵的源碼實現吧：

// 添加元素的時候排序
private void siftUp(int k, RunnableScheduledFuture<?> key) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        RunnableScheduledFuture<?> e = queue[parent];
        if (key.compareTo(e) >= 0)
            break;
        queue[k] = e;
        setIndex(e, k);
        k = parent;
    }
    queue[k] = key;
    setIndex(key, k);
}

/**
 * Sifts element added at top down to its heap-ordered spot.
 * Call only when holding lock.
 */
// 移除元素的時候的排序
private void siftDown(int k, RunnableScheduledFuture<?> key) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;
        RunnableScheduledFuture<?> c = queue[child];
        int right = child + 1;
        if (right < size && c.compareTo(queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo(c) <= 0)
            break;
        queue[k] = c;
        setIndex(c, k);
        k = child;
    }
    queue[k] = key;
    setIndex(key, k);
}