REUSABLE COMPONENT DESIGN / OBJECT DESIGN BRIEF

Task scheduler design

A task scheduler runs tasks at a future time, periodically, or as soon as workers are free, respecting priorities and dependencies.

AdvancedPhase 08 / Topic 3 of 7ResponsibilitiesCollaborationsExtensibility
01

Overview

A task scheduler runs tasks at a future time, periodically, or as soon as workers are free, respecting priorities and dependencies. The core design is a priority queue (min-heap) of tasks ordered by next run time, a dispatcher thread that sleeps until the earliest task is due, and a worker pool that executes tasks.

A strong design supports one-time and recurring schedules (fixed rate, fixed delay, cron), cancellation, retries with backoff, task states (scheduled, running, succeeded, failed), graceful shutdown, and an injectable clock. Commands represent tasks; Strategy represents schedules; Observer can report task events.

An airport departure board

Flights are ordered by departure time. The next one due is always at the top; gates (workers) handle boarding in parallel, and delayed or cancelled flights update the board.

02

When to use it

  • Interview prompt: 'Design a job or task scheduler'.
  • Delayed actions: reminders, hold expiry, retries.
  • Periodic jobs: reports, cleanup, polling.
03

Where it shows up in interviews

Delayed and periodic execution

Recognize it when: run X at time T or every N minutes.

  • Design a job scheduler
  • Design a cron service
  • Design a reminder system
Priority and dependencies

Recognize it when: tasks depend on others or have priorities.

  • Task Scheduler (LeetCode 621)
  • Course Schedule (topological order)
04

Where it is used in real software

ScheduledThreadPoolExecutor

Java's delayed work queue backed by a heap, with fixed-rate and fixed-delay scheduling.

Quartz, Sidekiq, Celery beat

Job schedulers with cron triggers, persistence, and retries.

Kubernetes CronJobs and Temporal

Cluster-level and durable workflow scheduling.

05

Key terms

Min-heap by run time
O(log n) insert, O(1) peek at the next due task.
Fixed rate vs fixed delay
Every N from start times vs N after each completion.
Worker pool
Threads that execute due tasks.
Idempotent task
Safe to run again on retry.
Graceful shutdown
Stop accepting, finish running tasks.
06

How it works, step by step

  1. 1
    Model a task

    id, action (Command), schedule, priority, retries, state.

  2. 2
    Store in a min-heap

    Keyed by nextRunAt (tie-break by priority).

  3. 3
    Dispatcher loop

    Wait until the head is due or a new earlier task arrives.

  4. 4
    Hand off to workers

    Executor pool runs the action.

  5. 5
    Reschedule or retry

    Recurring: compute next run; failure: backoff or mark failed.

07

Scheduler timeline

Now = 10:00:00

Step 1 / 4
TaskScheduleNext runHeap position
sendReminderonce at 10:00:0510:00:051st
cleanupevery 10 s10:00:102nd
reportonce at 10:01:0010:01:003rd
after cleanup runsevery 10 s10:00:20reinserted

NOWTask: sendReminder | Schedule: once at 10:00:05 | Next run: 10:00:05 | Heap position: 1st

The dispatcher always looks only at the heap top, so scheduling scales to many tasks.

08

Implementation

import java.time.*;import java.util.*;import java.util.concurrent.*;import java.util.concurrent.atomic.AtomicLong; public final class TaskScheduler implements AutoCloseable {    public enum Status { SCHEDULED, RUNNING, DONE, FAILED, CANCELLED }     private final class Task implements Comparable<Task> {        final long id = ids.incrementAndGet();        final Runnable action;        final Duration period;        // null for one-shot        Instant nextRun;        volatile Status status = Status.SCHEDULED;        Task(Runnable action, Instant nextRun, Duration period) { this.action = action; this.nextRun = nextRun; this.period = period; }        public int compareTo(Task o) { return nextRun.compareTo(o.nextRun); }    }     private final AtomicLong ids = new AtomicLong();    private final PriorityQueue<Task> queue = new PriorityQueue<>();    private final Map<Long, Task> byId = new ConcurrentHashMap<>();    private final ExecutorService workers;    private final Clock clock;    private final Thread dispatcher;    private volatile boolean running = true;     public TaskScheduler(int workerCount, Clock clock) {        this.workers = Executors.newFixedThreadPool(workerCount);        this.clock = clock;        this.dispatcher = new Thread(this::dispatchLoop, "scheduler-dispatcher");        dispatcher.start();    }     public long schedule(Runnable action, Duration delay) { return add(new Task(action, clock.instant().plus(delay), null)); }    public long scheduleAtFixedRate(Runnable action, Duration initialDelay, Duration period) {        return add(new Task(action, clock.instant().plus(initialDelay), period));    }     public boolean cancel(long id) {        Task t = byId.get(id);        if (t == null) return false;        synchronized (this) { queue.remove(t); notifyAll(); }        t.status = Status.CANCELLED;        return true;    }     public Status status(long id) { return byId.get(id).status; }     private synchronized long add(Task t) {        byId.put(t.id, t);        queue.add(t);        notifyAll();                                   // wake dispatcher: maybe an earlier task        return t.id;    }     private void dispatchLoop() {        while (running) {            Task due;            synchronized (this) {                while (running && (queue.isEmpty() || queue.peek().nextRun.isAfter(clock.instant()))) {                    long waitMs = queue.isEmpty() ? 1000 : Math.max(1, Duration.between(clock.instant(), queue.peek().nextRun).toMillis());                    try { wait(waitMs); } catch (InterruptedException e) { return; }                }                if (!running) return;                due = queue.poll();            }            workers.submit(() -> run(due));        }    }     private void run(Task t) {        if (t.status == Status.CANCELLED) return;        t.status = Status.RUNNING;        try {            t.action.run();            t.status = t.period == null ? Status.DONE : Status.SCHEDULED;        } catch (RuntimeException e) {            t.status = Status.FAILED;        }        if (t.period != null && t.status == Status.SCHEDULED) {            t.nextRun = t.nextRun.plus(t.period);     // fixed rate            add(t);        }    }     @Override    public void close() throws InterruptedException {        running = false;        synchronized (this) { notifyAll(); }        dispatcher.join();        workers.shutdown();        workers.awaitTermination(10, TimeUnit.SECONDS);    }}
09

Complexity and performance

ScheduleO(log n)

Heap insert.

Next due taskO(1) peek, O(log n) pop

Heap.

CancelO(n) with PriorityQueue.remove

Or lazy cancel flag: O(1).

10

Trade-offs

In-memory vs persistent

In-memory schedulers lose tasks on restart; durable schedulers store tasks in a database and use leader election.

Fixed rate vs fixed delay

Fixed rate keeps a steady cadence but tasks can pile up if slow; fixed delay spaces runs after completion.

11

Variants and related techniques

Timing wheel

O(1) scheduling for huge numbers of timers (Kafka, Netty).

Dependency DAG scheduler

Topological ordering for tasks with prerequisites (Airflow).

12

Common mistakes

  • Busy-waiting in the dispatcher.

    Fix: Wait until the head's time or until notified of an earlier task.

  • Running tasks on the dispatcher thread.

    Fix: One slow task delays all others; use a worker pool.

  • Non-idempotent tasks with retries.

    Fix: Make tasks idempotent or track completion.

13

Interview questions

What data structure would you use for a scheduler?

A min-heap keyed by next run time for O(log n) inserts and O(1) access to the next due task, with a dispatcher that waits until that time and a worker pool to execute tasks.

How do you handle a newly added task that is due before the current head?

The dispatcher waits with a timeout on a condition; adding a task notifies it, so it wakes, re-reads the heap top, and recalculates the wait.

14

Practice problems

ProblemDifficultyWhat it trains
Delayed task executor with cancelMediumHeap and dispatcher.
Recurring jobs with retries and statesHardLifecycle.
Task Scheduler (LeetCode 621)MediumGreedy cooldown.