How Spring Task and Quartz Schedule Jobs: Inside the DelayedWorkQueue and Heap Algorithm

Preface

Today we discuss how Spring Task and Quartz implement scheduled task execution. A previous article covered their principles; this one dives into the implementation details.

How to Implement Scheduled Execution

First, look at the scheduling flow diagrams for Spring Task and Quartz.

Quartz:

quartz

works by having worker threads update the next execution time after completing a task; a scheduler thread continuously scans tasks, finds those due, and hands them to the thread pool.

Spring Task:

spring task

does not have a dedicated scheduler thread; after a task finishes, the worker thread calculates the next run time (delay in ms) and submits it back to the thread pool.

Running worker threads constantly try to fetch tasks; if none are available they sleep, then retry.

Spring Task Issue

Assume task A is submitted to a single‑thread pool and must wait one hour before execution, while task B should run after 10 seconds. Does task B have to wait for task A to finish?

No. Tasks are ordered by their scheduled execution time, so the earliest task is placed at the front of the queue, preventing blockage.

Understanding the ordering requires looking at the DelayedWorkQueue implementation.

DelayedWorkQueue

DelayedWorkQueue

is a special priority queue that stores tasks implementing RunnableScheduledFuture. These tasks have a delay (time until execution) or a period (interval between executions). The queue must always be able to quickly locate and remove the next expiring task.

Sorting Algorithm and Data Structure

The sorting algorithm of DelayedWorkQueue relies on a binary heap , specifically a min‑heap implemented with an array .

1. Data Structure: Min‑Heap

What is a heap? A heap is a special complete binary tree where each parent node’s value is less than or equal to its children’s values, making the root the smallest element.

How is it stored? The heap uses an array. For any index i:

2. Sorting / Comparison Basis

Elements ( RunnableScheduledFuture tasks) are sorted by their expiration time .

Delayed tasks: expiration = System.nanoTime() + delay Periodic tasks: expiration is calculated from the fixed rate or fixed delay settings and the previous execution time.

Thus, tasks with earlier expiration have higher priority and are positioned closer to the root of the heap.

3. Core Algorithm Operations

Heap ordering is maintained through sift‑up when inserting and sift‑down when removing.

a) Insert task – offer(Runnable x)

Place the new task at the next free array position (the last node of the complete binary tree).

Sift‑up: Compare the new node’s expiration with its parent’s; if it is earlier, swap them.

Repeat until the node is no longer earlier than its parent or it reaches the root (heapify).

b) Remove task – take()

Get root: The first array element is the next task to execute (earliest expiration).

Replace root: Move the last element to the root position.

Sift‑down: Compare the new root with its children; swap with the child that has the earlier expiration.

Repeat until the node is not larger than any child or it becomes a leaf.

Return the original root task.

This process ensures that after extracting the highest‑priority task, the remaining elements are re‑organized into a valid min‑heap.

Key Source Code

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);
}

Conclusion

A seemingly simple scheduled task involves many concepts: delayed work queues, binary min‑heaps, and precise ordering algorithms. Understanding these internals reveals the elegance and efficiency of Spring Task and Quartz scheduling mechanisms.