Design a Task Scheduler

Description

A task scheduler runs work later - once after a delay, or repeatedly at a fixed rate or with a fixed delay - which is what ScheduledExecutorService, cron and every job system do. The design round tests a priority queue ordered by due time, one dispatcher thread instead of a thread per task, a task lifecycle that makes cancellation exact, and an injected clock so it can be tested without waiting. This skill builds each of those.

"Run this later" and "run this every minute" look easy to hand-roll:

void schedule(Runnable task, long delayMillis) {
    new Thread(() -> {
        try { Thread.sleep(delayMillis); } catch (InterruptedException e) { return; }
        task.run();
    }).start();
}

import threading
import time


def schedule(task: Callable[[], None], delay_millis: int) -> None:
    def run() -> None:
        time.sleep(delay_millis / 1000)
        task()
    threading.Thread(target=run).start()

A hundred thousand reminders means a hundred thousand sleeping threads, each with its own stack. Cancelling needs a handle to the thread and an interrupt. A periodic version sleeps after each run, so a slow run quietly shifts every later one. An exception kills the thread and the task silently stops repeating. And testing "runs every night at 2 a.m." means waiting for 2 a.m. The same problems appear in a single-threaded loop that scans a list of tasks every millisecond: it's O(n) per tick, and one slow task delays everything behind it.

We'll go from simple to more technical:

1. The model: tasks with due times in a min-heap, a dispatcher and workers.
2. Scheduling, cancelling and running, with a task state machine.
3. Fixed rate versus fixed delay for repeating tasks.
4. The bugs around time and ownership, and the tradeoffs.

The approach

1. Clarify. One-shot and periodic? For periodic: a steady rhythm (every 10 s on the dot) or a gap between runs (10 s after the last one finished)? What happens to runs missed while the system was busy or asleep? Can a task be cancelled while it runs? What if a task throws? How many workers - and how many servers?
2. Model. A Task: id, body, kind (ONCE, FIXED_RATE, FIXED_DELAY), period, next due time, and a state (PENDING, RUNNING, DONE, CANCELLED). A priority queue of pending tasks ordered by due time. An injected Clock.
3. API. schedule(task, delay), scheduleAtFixedRate(task, initialDelay, period), scheduleWithFixedDelay(task, initialDelay, delay) - each returning an id - plus cancel(id), and a runDueTasks() that a worker calls.
4. Core. Repeatedly take the earliest task whose due time has come, claim it under the lock, run it without the lock, then decide - under the lock again - whether and when it runs next.

The pieces in code

public int runDueTasks() {
    int ran = 0;
    while (true) {
        Task t;
        synchronized (lock) {                                   // claim the next due task...
            Task head = queue.peek();
            if (head == null || head.due.isAfter(clock.instant())) return ran;
            t = queue.poll();
            t.state = State.RUNNING;
        }
        try {                                                   // ...run it without the lock...
            t.body.run();
        } catch (RuntimeException failure) {
            synchronized (lock) { failures++; }                 // one bad task doesn't stop the rest
        }
        ran++;
        synchronized (lock) {                                   // ...then decide what happens next
            if (t.state == State.CANCELLED) continue;           // cancelled while it ran
            switch (t.kind) {
                case ONCE -> t.state = State.DONE;
                case FIXED_RATE -> reschedule(t, t.due.plus(t.period));              // from the due time
                case FIXED_DELAY -> reschedule(t, clock.instant().plus(t.period));   // from the finish
            }
        }
    }
}

def run_due_tasks(self) -> int:
    ran = 0
    while True:
        with self._lock:                                         # claim the next due task...
            if not self._queue or self._queue[0].due > self._now():
                return ran
            t = heapq.heappop(self._queue)
            t.state = State.RUNNING
        try:                                                     # ...run it without the lock...
            t.body()
        except Exception:
            with self._lock:
                self._failures += 1                              # one bad task doesn't stop the rest
        ran += 1
        with self._lock:                                         # ...then decide what happens next
            if t.state is State.CANCELLED:
                continue                                         # cancelled while it ran
            match t.kind:
                case Kind.ONCE:
                    t.state = State.DONE
                case Kind.FIXED_RATE:
                    self._reschedule(t, t.due + t.period)        # from the due time
                case Kind.FIXED_DELAY:
                    self._reschedule(t, self._now() + t.period)  # from the finish

• A heap ordered by due time, then by id. peek is O(1) and poll/add O(log n). The id breaks ties in scheduling order - PriorityQueue itself orders equal elements arbitrarily, which makes runs unpredictable. (Python's heapq needs comparable items: a @dataclass(order=True) task whose first fields are due and id, the rest field(compare=False), or (due, id, task) tuples.)
• Rescheduling happens after poll. Changing due on an element that is still inside a PriorityQueue silently breaks the heap's order; take it out, change it, put it back. (The same holds for a heapq list.)
• The loop re-checks the clock each time, so tasks that become due during the call - scheduled by other tasks, or a fixed-rate task catching up - run in the same call.

Cancellation uses the same state, under the same lock:

public boolean cancel(long taskId) {
    synchronized (lock) {
        Task t = tasks.get(taskId);
        if (t == null) return false;
        if (t.state == State.PENDING) { t.state = State.CANCELLED; queue.remove(t); return true; }
        if (t.state == State.RUNNING && t.kind != Kind.ONCE) { t.state = State.CANCELLED; return true; }
        return false;                                           // already ran, already cancelled, or running once
    }
}

def cancel(self, task_id: int) -> bool:
    with self._lock:
        t = self._tasks.get(task_id)
        if t is None:
            return False
        if t.state is State.PENDING:
            t.state = State.CANCELLED
            self._queue.remove(t)
            heapq.heapify(self._queue)
            return True
        if t.state is State.RUNNING and t.kind is not Kind.ONCE:
            t.state = State.CANCELLED
            return True
        return False                        # already ran, already cancelled, or running once

Because the worker claims a task (PENDING → RUNNING) and cancel checks the state under one lock, every task either runs or is cancelled - never both, never neither. (heapq has no remove: take the task out and heapify again in O(n), as above, or leave it in and skip cancelled tasks when they surface - the lazy way the warm-up uses.)

Fixed rate vs fixed delay

A job with a 10-second period that takes 3 seconds to run:

Fixed rate keeps a rhythm - right for "sample the queue depth every 10 s" - and after a pause it catches up: if 35 seconds passed, the runs due at 10, 20 and 30 s all happen back to back. Fixed delay guarantees a gap and never piles up - right for "poll the server, then wait 10 s" - but drifts by each run's duration.

Where you'll see it

Java's ScheduledThreadPoolExecutor is this design: a heap-ordered delay queue, a small pool of worker threads, System.nanoTime() for delays (so wall-clock jumps don't disturb them), and scheduleAtFixedRate/scheduleWithFixedDelay with exactly these semantics - except that a periodic task that throws is silently never run again, which surprises many teams. Python's standard library has the same core in sched.scheduler - a heap of events with an injectable time function - and asyncio's event loop keeps its timers in a heap too. Cron-style schedulers (Quartz, Kubernetes CronJobs) add calendar rules and time zones. And when an application runs on several servers, each server's scheduler would run the nightly job - so jobs take a lease first (a database row lock or a lock table, as the ShedLock library does) or run on an elected leader, and are written to be safe to run twice.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A job scheduled every 10 seconds takes 3 seconds to run. When do its first three runs start with fixed rate, and with fixed delay?

2. cancel sets a cancelled flag, and the worker checks it just before running a task. How can cancel return true for a task that then runs?

3. Why run a task's body outside the scheduler's lock?

Key takeaways

• Keep pending runs in a heap ordered by due time with an explicit tie-break; poll before changing a due time.
• Fixed rate schedules from the previous due time (rhythm, catch-up); fixed delay from the finish (gaps, drift).
• An explicit task state, changed under one lock, makes "run or cancelled, never both" true.
• Claim under the lock, run outside it, and catch task failures so the scheduler survives them.
• Inject the clock and drive the scheduler with runDueTasks() so every timing rule is testable; on several servers, lease jobs so each runs once.