How Schedulers Work: ScheduledThreadPoolExecutor and Leader–Follower

Many services run jobs on a schedule: send a daily report, retry failed payments every five minutes, clean up expired sessions at midnight. This module covers scheduling, ending with the problem microservices add: a job meant to run once runs on every instance.

First, what a scheduler is. Stripped down, a scheduler is a background thread that sleeps until a given time, wakes up, runs a task, and sleeps again. Spring Boot's @Scheduled (chapter 21) adds no magic: underneath it is Java's ScheduledThreadPoolExecutor. This chapter looks inside it; its API and shutdown methods are covered in Core Java.

Scheduling a task

ScheduledThreadPoolExecutor executor = new ScheduledThreadPoolExecutor(3);   // 3 worker threads
Runnable task = () -> System.out.println("Hello!");
executor.schedule(task, 5, TimeUnit.SECONDS);

ScheduledThreadPoolExecutor implements ScheduledExecutorService, which has three scheduling methods.

schedule(task, delay, unit): once

Runs the task once, delay after it was submitted. schedule(task, 5, SECONDS) runs it at 5 s.

scheduleAtFixedRate(task, initialDelay, period, unit): on a fixed timetable

Runs the task first after initialDelay, then on a fixed timetable: each next run is due at the previous run's scheduled start time + period. With scheduleAtFixedRate(task, 2, 4, SECONDS): 2 s, 6 s, 10 s, 14 s...

After each run, the executor computes the next due time and puts the same task object back in the queue. So one task never runs concurrently with itself, even with several worker threads.

What if a run takes longer than the period? Measured with a 400 ms period, where the first run (at 200 ms) takes 1 s:

run 1   200 ms    (takes 1000 ms)
run 2  1207 ms    \ due at 600 and 1000 ms, both already past:
run 3  1208 ms    / they run back to back, immediately
run 4  1403 ms    back on the original timetable (1400)
run 5  1803 ms    (1800)

The next due time is the previous scheduled time + period: 600 ms, already in the past, so run 2 starts as soon as run 1 finishes. Then 1000 ms, also past, so run 3 starts right after. Then 1400 ms, in the future, so the timetable resumes. Missed runs are not skipped; they are made up immediately, one after another. A task that keeps overrunning therefore runs continuously.

scheduleWithFixedDelay(task, initialDelay, delay, unit): a gap between runs

Each next run starts delay after the previous run finished. The same experiment:

run 1   201 ms    (takes 1000 ms, ends ~1201)
run 2  1601 ms    1201 + 400
run 3  2002 ms    ~1601 + 400

No catching up: there is always a full gap between runs.

	Next run due at
fixed rate	previous scheduled start + period (catches up after an overrun)
fixed delay	previous end + delay

Inside: the DelayedWorkQueue

new ScheduledThreadPoolExecutor(3) creates a pool of 3 worker threads and a DelayedWorkQueue. Each call to schedule... wraps the task and its due time in a ScheduledFutureTask and inserts it into the queue.

The DelayedWorkQueue is a min-heap ordered by due time: the task due soonest is always at the head, queue[0].

Worker threads loop on take(), which waits for the head task to become due and then hands it to the thread. Here is the algorithm, step by step.

Step 1: empty queue

No tasks: every worker finds queue[0] == null and calls available.await(), waiting indefinitely until signalled. Waiting threads use no CPU.

Step 2: a task arrives

offer() inserts the task (growing the array by 50% when full, then re-heapifying with siftUp). If the new task ended up at the head, it signals one waiting worker. (If it is not at the head, a sooner task is already being waited on, so no one needs waking.)

if (queue[0] == e) {
    leader = null;
    available.signal();     // wake one waiting worker
}

Step 3: the woken worker checks the head

long delay = first.getDelay(NANOSECONDS);
if (delay <= 0L)
    return finishPoll(first);       // due: remove it and run it
...
available.awaitNanos(delay);         // not due: sleep exactly until it is

• Due (current time ≥ due time): the worker removes the task from the queue and runs it.
• Not due: it computes the remaining delay and goes into TIMED_WAITING for exactly that long. The JVM parks the thread, which does no busy waiting; an OS timer wakes it when the delay expires, and it checks the head again.

Before leaving take() with a task, the worker signals one more waiting worker if tasks remain, so someone keeps watching the queue while it is busy:

finally {
    if (leader == null && queue[0] != null)
        available.signal();
    lock.unlock();
}

The whole queue is guarded by one ReentrantLock; a thread that waits releases it, and reacquires it when it wakes.

The leader–follower optimization

Picture three workers that have just finished their tasks at 3:00. The head task is due at 4:00. Without any optimization, each worker in turn takes the lock, sees the task is not due, and goes into TIMED_WAITING for an hour. That gives three OS timers for one task, and at 4:00 all three wake up and compete for it, though only one can win.

The fix is the leader–follower pattern: only one thread waits on a timer; the others wait indefinitely until woken. It needs no special leader thread, only one field, leader:

if (delay <= 0L)
    return finishPoll(first);
first = null;                         // don't keep a reference while waiting
if (leader != null)
    available.await();                // a leader exists: wait indefinitely (follower)
else {
    Thread thisThread = Thread.currentThread();
    leader = thisThread;              // become the leader
    try {
        available.awaitNanos(delay);  // the only timed wait
    } finally {
        if (leader == thisThread)
            leader = null;            // woke up: give up leadership
    }
}

The 3:00 scenario again:

1. Worker 1 takes the lock: not due, leader == null, so it becomes the leader and waits until 4:00 (releasing the lock).
2. Worker 2 takes the lock: not due, leader != null, so it waits indefinitely.
3. Worker 3: the same as worker 2.
4. At 4:00 the OS wakes worker 1. It clears leader, loops, finds the task due, and takes it. On its way out, leader == null and tasks remain, so it signals one follower, which becomes the next leader for the next task.

One timer instead of three, and no stampede when it fires. The same idea (one thread waits on the event, the rest stand by) appears in many servers and queues.

Next: Chapter 21 moves to Spring Boot's @Scheduled: fixed rate, fixed delay and cron expressions, and how Spring maps them onto this executor, including why its default pool has a single thread.

Check yourself

1. What is a scheduler, in one sentence?
2. What does Spring Boot use underneath @Scheduled?
3. What is the difference between schedule, scheduleAtFixedRate and scheduleWithFixedDelay?
4. A fixed-rate task with a 400 ms period takes 1 s once. What happens to the runs it missed?
5. Can one fixed-rate task run concurrently with itself? Why?
6. How is the DelayedWorkQueue organized?
7. What does a worker do when the head task is not yet due?
8. Why does a worker signal another waiting worker when it takes a task?
9. What problem does the leader–follower pattern solve?
10. How is the leader chosen, and when does it give up leadership?

Answers

1. A background thread that sleeps until a given time, wakes up to run a task, and sleeps again.
2. Java's ScheduledThreadPoolExecutor.
3. schedule runs once after a delay; scheduleAtFixedRate runs repeatedly on a timetable (previous scheduled start + period); scheduleWithFixedDelay runs repeatedly with a fixed gap after each run ends.
4. They are not skipped: their due times are already past, so they run immediately, back to back, until the timetable is caught up.
5. No. The same task object is put back in the queue only after a run finishes.
6. As a min-heap ordered by due time, so the soonest task is at the head.
7. It waits in TIMED_WAITING for exactly the remaining delay (parked, no CPU), then checks again.
8. So that some thread keeps watching the queue for the next task while it is busy running this one.
9. Several idle threads all setting timers for the same not-yet-due task, and all waking together to compete for it.
10. The first thread to find no leader sets leader to itself and is the only one to wait with a timer; the others wait indefinitely. When it wakes, it clears leader, and when it takes a task it signals a follower to take over.