Task Scheduler

Job Scheduling System

Design an in-process scheduler that runs one-time and recurring tasks at the right moment on a pool of worker threads, with cancellation, failure handling and no busy waiting.

Overview

A scheduler holds tasks that should run later: once at a given time, or again and again at an interval. When a task's time comes it runs on a worker thread, so a slow task never delays the others. Tasks can be canceled before they run. A task that raises must not take the scheduler down. This is what cron, Java's ScheduledExecutorService and Python's sched module do; you are designing the small version.

Interviewers use it to see whether you know the two ideas that make a scheduler correct and cheap: a min-heap keyed by run time, so the next task is always at the top, and a condition variable, so the scheduler thread sleeps exactly until that task is due or a new task arrives. They then push on the details that separate a toy from a real one: what a recurring interval means when a run is slow, how cancellation works when the task is buried in the heap, and what happens on failure.

Scoping the problem

One-time, recurring, or both? — Recurring tasks need a rule for the next run time — Both
Fixed rate or fixed delay for recurring tasks? — Different arithmetic and different behavior when a run is slow — Support both; explain the difference
How many tasks run at once? — A worker pool; the scheduler thread never runs a task itself — A small pool, configurable
Can a task be canceled? While running? — Cancellation before the run is easy; during the run needs cooperation — Before; a running task finishes
What if a task raises? — Mark it failed; keep the scheduler alive; recurring tasks continue or stop — Continue, count failures
Does the schedule survive a restart? — In-memory only, or persisted — In memory here; persistence is a follow-up
Which clock? — Wall-clock time jumps; a monotonic clock does not — Monotonic

The scheduler loop

The scheduler thread does one thing: wait until the top of the heap is due, pop it, hand it to the pool. The waiting is the whole trick. Condition.wait(timeout) releases the lock and sleeps until either the timeout passes or another thread calls notify. schedule() notifies, so a task added for two seconds from now wakes a scheduler that was sleeping for an hour. The Python docs say to re-check your condition in a loop after wait returns, because the wake-up may be for a different reason; the loop below does that.

Why a heap, and how cancellation works with it

The heap gives the next task in O(1) and inserts in O(log n). Its weakness is that you cannot remove an arbitrary element cheaply. The fix the heapq docs recommend is lazy deletion: mark the entry as removed and skip it when it reaches the top. A dict from id to task gives O(1) lookup for the mark.

Sorted list — O(1) — O(n) shift — O(n) search, or O(1) with a dict plus O(n) removal
Min-heap alone — O(1) — O(log n) — O(n) search
Min-heap plus dict, lazy deletion (this code) — O(1) — O(log n) — O(1) mark; the entry is discarded when it surfaces
Timing wheel (buckets per tick) — O(1) — O(1) — O(1)

Heap entries are tuples (run_at, seq, task). The sequence number breaks ties so two tasks due at the same instant run in the order they were scheduled, and so the heap never has to compare two Task objects; the heapq docs describe this entry-count trick.

Fixed rate against fixed delay

A recurring task needs a rule for its next run time. Two rules are common, and Java's ScheduledExecutorService offers both by name.

Fixed rate — previous due time + interval — Runs bunch up to catch up (this code skips the missed slots instead) — Things that must happen N times per minute: metrics, heartbeats
Fixed delay — finish time + interval — The gap stays constant; the schedule drifts later — Things that must not overlap and need breathing room: polling a queue, cleanup

Here is a 30 ms interval when the third run takes 50 ms and every other run takes almost no time. Times are in ms from the first due time.

1 — 0 — 0
2 — 30 — 30
3 (takes 50 ms, 60 to 110) — 60 — 60
4 — 90 is already past, so 120 — 110 + 30 = 140
5 — 150 — 170

Java's fixed-rate variant states that a slow run may make later runs start late but never run concurrently. This design gets the same guarantee a different way: a recurring task is re-inserted only after its run finishes, so a task never overlaps with itself even though other tasks run in parallel.

Clocks

Use a monotonic clock for scheduling. The Python docs say time.monotonic() cannot go backwards and is not affected by system clock updates, while time.time() can return a lower value than a previous call if the system clock is set back. A scheduler keyed on wall-clock time would fire everything at once after a clock jump forward, or stall after a jump back. Wall-clock time is still what a user means by 'run at 09:00', so convert once at scheduling time and store the monotonic deadline.

What you will be able to do

Draw the scheduler thread's loop and explain why it never busy-waits.
Use a heap plus a dict and explain lazy cancellation.
Define fixed rate and fixed delay and say what each does when a run is slow.
Keep a failing task from killing the scheduler and decide what a failure means for a recurring task.
Say why the clock is monotonic and where wall-clock time still belongs.

Functional requirements

Schedule a one-time task for a given time
Schedule a recurring task at a fixed rate or with a fixed delay
Run due tasks on a pool of worker threads; the scheduler thread never runs a task itself
Cancel a task by id before it runs; a running task finishes and is not rescheduled
Notify listeners of task events: due, started, completed, failed, canceled
Track each task's status, run count and failure count

Non-functional requirements

No busy waiting: the scheduler thread sleeps until the next due time or until a new task arrives, whichever is first
Thread-safe: one Condition guards the heap and the task dict; every state change to a task happens under it
A task that raises is marked failed; the worker, the scheduler and the other tasks keep going
Tasks due at the same instant run in the order they were scheduled
Next run time O(1), schedule O(log n), cancel O(1)
Scheduling uses a monotonic clock; the clock is injectable

Interview questions

Why a condition variable instead of a loop that sleeps 100 ms and checks?
What is the difference between fixed rate and fixed delay, and which drifts?
What happens when a task raises, and when a recurring task keeps raising?
How would you add dependencies between tasks, so B runs only after A succeeds?
How would the schedule survive a restart, or run on more than one machine?
Why is the clock injectable, and why monotonic?