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.
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.
When to use it
- Interview prompt: 'Design a job or task scheduler'.
- Delayed actions: reminders, hold expiry, retries.
- Periodic jobs: reports, cleanup, polling.
Where it shows up in interviews
Recognize it when: run X at time T or every N minutes.
- Design a job scheduler
- Design a cron service
- Design a reminder system
Recognize it when: tasks depend on others or have priorities.
- Task Scheduler (LeetCode 621)
- Course Schedule (topological order)
Where it is used in real software
Java's delayed work queue backed by a heap, with fixed-rate and fixed-delay scheduling.
Job schedulers with cron triggers, persistence, and retries.
Cluster-level and durable workflow scheduling.
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.
How it works, step by step
- 1Model a task
id, action (Command), schedule, priority, retries, state.
- 2Store in a min-heap
Keyed by nextRunAt (tie-break by priority).
- 3Dispatcher loop
Wait until the head is due or a new earlier task arrives.
- 4Hand off to workers
Executor pool runs the action.
- 5Reschedule or retry
Recurring: compute next run; failure: backoff or mark failed.
Scheduler timeline
Now = 10:00:00
| Task | Schedule | Next run | Heap position |
|---|---|---|---|
| sendReminder | once at 10:00:05 | 10:00:05 | 1st |
| cleanup | every 10 s | 10:00:10 | 2nd |
| report | once at 10:01:00 | 10:01:00 | 3rd |
| after cleanup runs | every 10 s | 10:00:20 | reinserted |
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.
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); }}Complexity and performance
Heap insert.
Heap.
Or lazy cancel flag: O(1).
Trade-offs
In-memory schedulers lose tasks on restart; durable schedulers store tasks in a database and use leader election.
Fixed rate keeps a steady cadence but tasks can pile up if slow; fixed delay spaces runs after completion.
Variants and related techniques
O(1) scheduling for huge numbers of timers (Kafka, Netty).
Topological ordering for tasks with prerequisites (Airflow).
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.
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.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| Delayed task executor with cancel | Medium | Heap and dispatcher. |
| Recurring jobs with retries and states | Hard | Lifecycle. |
| Task Scheduler (LeetCode 621) | Medium | Greedy cooldown. |