Design a task scheduler

“Design a task scheduler. Code can ask for a task to run after a delay, or every few minutes.” Then, sooner or later: “What happens when a job takes longer than its period?”

A task scheduler holds work that should happen later. One part of a program says “send this reminder email in 24 hours”, or “refresh this cache every five minutes”. The scheduler makes sure it happens at the right time. In this problem, the scheduler lives inside one program, in memory.

The first version is a list of jobs, and a loop that checks it every second. It works for a demo. But it reads every job on every check. It runs jobs up to a second late. And one slow job makes all the others late. Each of those becomes a design decision, and the interviewer wants to hear each one made.

The framework

1. 01Answer
2. 02Scope
3. 03Build
4. 04Full design
5. 05Stress
6. 06Wrap up

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains how we get here.

1. Jobs wait in a timetable sorted by run time. It’s a min-heap, so the next job due is always on top. The scheduler never looks at jobs that aren’t due, and it knows exactly how long to sleep.
2. Cancel just marks the job. A cancelled job is thrown away when it reaches the top. That keeps cancel cheap, because a heap is slow at removing from the middle.
3. “Every five minutes” means one of two things. Fixed rate keeps to the clock, and skips a run instead of overlapping. Fixed delay waits five minutes after each run finishes.
4. A failed one-off job is retried, with growing waits. The retry is just the job back on the timetable, at a later time. Every job has a status that callers can ask for.
5. One thread waits, and a pool of workers runs. The waiting thread sleeps until the next run time. It’s woken whenever a sooner job is added. Workers run jobs without holding any lock.

We’ll build this in four stages, then run it with real threads.

Scope it

Before drawing anything, we ask a few questions. Each answer changes a class. Anything that doesn’t, we assume and move on.

Interviewerminute 0

Design a task scheduler.

What they are testing

Whether you pin down one process or many before drawing anything. In one process, the hard parts are the data structure and the threads. Across machines, the hard part is that two machines might run the same job, which is a system design question.

Here are the questions that matter:

• One process, or many machines? One process, in memory. Many machines need a shared store, so that only one machine runs each job.
• Must jobs survive a restart? No. Surviving a restart would need a jobs table in a database.
• Which kinds of job? Once after a delay, and repeating, at a fixed rate or with a fixed delay.
• How exact must timing be? Within milliseconds, and never early.
• What if a job fails? One-off jobs retry with growing waits. Repeating jobs just carry on.

These answers give us one promise that matters more than the others: no job runs early, and none runs much late. A job runs as soon as it’s due, unless every worker is busy. Three smaller promises come with it. A slow or failing job never delays or stops the others. The work per job doesn’t grow with the number of jobs waiting. And two runs of the same repeating job never overlap.

We leave out saving to disk, running across machines, and cron expressions (like “9:00 every Monday”). They come up at the end.

Go deeperThree more questions, and what each changes1 min

Question	We assume	If the answer were different
Priorities between jobs?	No, only run time	The heap sorts by (run time, priority, sequence number)
Can a job be changed once scheduled?	Cancel and schedule again	Rescheduling is a cancel plus a schedule, the same cost
A limit on jobs running at once?	Yes, the worker count	Unlimited means one thread per run, which the first busy minute breaks

Common mistake

A thread per job, sleeping until its time

new Thread(() -> { sleep(delay); task.run(); }) is the first idea, and it works for ten jobs. For a hundred thousand reminders, it’s a hundred thousand sleeping threads, each with its own memory, and no way to see or cancel what’s waiting. The scheduler exists so that waiting is cheap, and the number of jobs running at once has a limit.

Build it

We’ll build the design in four stages. Each stage adds only the classes that a new requirement needs. In each diagram, the new parts are outlined, and the colors show what each class does (the key is under every diagram). Time is a number of milliseconds from a clock the scheduler is given, so the tests can move time by hand.

Stage 1: A list and a loop

Interviewerminute 3

Start simple: an order service wants an email sent 24 hours after an order. What are your classes?

What they are testing

Whether you get a working shape in two minutes, and then say what’s wrong with it yourself. The scan on every check and the one-second lateness are the two things they’re waiting for you to notice.

Start with the smallest thing that works. A Job is a task plus the time it should run. The Scheduler keeps a list of jobs. A loop calls tick every second, and tick takes out every job whose time has come, and runs it.

The task is a function with no arguments. This is the Command pattern: the scheduler holds work to be done later, without knowing what the work is.

Stage 1: a scheduler with a list of jobs

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JScheduler.javaPyscheduler.pyC#Scheduler.csGoscheduler.goTSscheduler.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// A task and when it should run, in milliseconds on the scheduler's clock.
record Job(String id, long runAt, Runnable task) {}

class Scheduler {
    private final List<Job> jobs = new ArrayList<>();
    private final LongSupplier clock;
    private final Supplier<String> ids;

    Scheduler(LongSupplier clock, Supplier<String> ids) {
        this.clock = clock;
        this.ids = ids;
    }

    String schedule(Runnable task, long delayMillis) {
        Job j = new Job(ids.get(), clock.getAsLong() + delayMillis, task);
        jobs.add(j);
        return j.id();
    }

    // Called by a loop that wakes up every second.
    // flaw 1: every tick scans every job, due or not. A million jobs scheduled for next week are
    // read every second.
    // flaw 2: a job due at 10:00:00.1 runs at 10:00:01, because nothing happens between ticks.
    // flaw 3: jobs run one after another on this thread, so a slow one makes every other job
    // late, and one that throws stops the rest of this tick.
    // flaw 4: no repeating jobs, and no way to cancel one.
    void tick() {
        long now = clock.getAsLong();
        List<Job> due = jobs.stream().filter(j -> j.runAt() <= now).toList();
        jobs.removeAll(due);
        for (Job j : due) j.task().run();
    }
}

It works, but it has four problems, and we leave them in on purpose. First, every check reads every job. So a million reminders for next week are read every second. Second, a job due just after a check waits almost a full second. Third, jobs run on the loop’s thread, one after another. One slow job makes every job after it late, and one that throws an error stops the rest. And fourth, nothing repeats, and nothing can be cancelled.

Stage 2: A timetable in a min-heap

Interviewerminute 6

There are a million jobs waiting, most of them days away. How does the scheduler find the ones that are due, without reading them all?

What they are testing

Whether you reach for a priority queue sorted by run time, and know what each operation costs. Senior candidates also ask how cancel works, because removing from the middle of a heap is what a heap is bad at.

The scheduler always asks the same question: “which job is earliest?” A min-heap answers it by looking at the top, without searching. A min-heap is a tree where every item is smaller than the items below it, so the smallest is always on top. Adding a job costs O(log n), and taking the earliest costs O(log n). Nothing else is touched.

There’s a bonus. The scheduler now knows exactly when the next job is due, so the loop can sleep until then, instead of checking every second. That fixes both the scan and the lateness.

Two jobs can be due at the same millisecond. So the heap sorts by run time, then by a sequence number taken from a counter when each job is scheduled. Jobs due together run in the order they were scheduled. Without it, their order would depend on how the heap happens to be arranged.

Stage 2: the earliest job is always on top

Scroll or pinch to zoom, drag to pan

• Color key
• The earliest job, read in O(1)
• Cache

Cancel is the catch. To remove a job from the middle of a heap, we’d first have to find it, and that’s a search through everything. So cancel only marks the job, using a map from id to job. A cancelled job is thrown away when it reaches the top. Cancel costs O(1). The price is that cancelled jobs use memory until their time comes. This trick is called lazy deletion.

Stage 2: a timetable and cancel by id

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JScheduler.javaPyscheduler.pyC#Scheduler.csGoscheduler.goTSscheduler.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// A job is mutable now: cancelling marks it instead of searching the timetable for it.
class Job {
    final String id;
    final Runnable task;
    final long seq;  // breaks ties: two jobs due at the same moment run in the order scheduled
    long runAt;
    boolean cancelled;

    Job(String id, Runnable task, long seq, long runAt) {
        this.id = id;
        this.task = task;
        this.seq = seq;
        this.runAt = runAt;
    }
}

// The timetable is a min-heap ordered by run time, so the next job due is always on top. Adding
// a job and taking the next one are O(log n), and asking "when is the next one?" is a peek.
// Nothing scans the jobs that aren't due.
class Scheduler {
    private final PriorityQueue<Job> timetable =
        new PriorityQueue<>(Comparator.comparingLong((Job j) -> j.runAt).thenComparingLong(j -> j.seq));
    private final Map<String, Job> jobs = new HashMap<>();
    private final LongSupplier clock;
    private final Supplier<String> ids;
    private long nextSeq;

    Scheduler(LongSupplier clock, Supplier<String> ids) {
        this.clock = clock;
        this.ids = ids;
    }

    String schedule(Runnable task, long delayMillis) {
        Job j = new Job(ids.get(), task, nextSeq++, clock.getAsLong() + delayMillis);
        jobs.put(j.id, j);
        timetable.add(j);
        return j.id;
    }

    // Removing from the middle of a heap means finding the job first, which is a scan. So a
    // cancelled job is only marked, and it is thrown away when it reaches the top.
    boolean cancel(String id) {
        Job j = jobs.remove(id);
        if (j == null) return false;
        j.cancelled = true;
        return true;
    }

    // When the next live job is due, so the loop can sleep exactly until then.
    OptionalLong nextRunAt() {
        dropCancelled();
        return timetable.isEmpty() ? OptionalLong.empty() : OptionalLong.of(timetable.peek().runAt);
    }

    // Takes every job that is due, earliest first. Deciding what is due is separate from running
    // it, so stage 5 can hand the jobs to worker threads.
    List<Job> takeDue() {
        long now = clock.getAsLong();
        List<Job> due = new ArrayList<>();
        for (dropCancelled(); !timetable.isEmpty() && timetable.peek().runAt <= now; dropCancelled()) {
            Job j = timetable.poll();
            jobs.remove(j.id);
            due.add(j);
        }
        return due;
    }

    // Runs due jobs on the caller's thread. One that throws doesn't stop the others.
    // flaw: a slow job still makes the next one late. Stage 5 runs them on workers.
    int runDue() {
        List<Job> due = takeDue();
        for (Job j : due) {
            try {
                j.task.run();
            } catch (RuntimeException e) {
                // stage 4 decides what a failure means
            }
        }
        return due.size();
    }

    private void dropCancelled() {
        while (!timetable.isEmpty() && timetable.peek().cancelled) timetable.poll();
    }
}

Choosing what’s due (takeDue) is kept separate from running it (runDue). That separation is where we’ll later hand jobs to workers instead.

Go deeperWhen marking is the wrong choice1 min

	Mark, and skip it at the top	Remove from the heap now
Cost of cancel	O(1)	O(n) to find it, or O(log n) if every job tracks its spot
Memory	Cancelled jobs stay until due	Freed at once
Code	One flag, and a loop at the top	The heap must track every job’s position
Best when	Cancels are rare, or jobs are short-lived	Many long-lived jobs are cancelled

We mark. The timetable can fill up with cancelled jobs, for example reminders cancelled weeks ahead. So once more than half are cancelled, the scheduler rebuilds the heap without them.

Go deeperWhy a heap, and not a sorted list or a tree2 min

Three structures can keep jobs in time order. Here is what each costs with a million jobs.

Structure	Add a job	Take the earliest	Cancel by id
Sorted list (array)	O(n)	O(1)	O(n)
Min-heap	O(log n)	O(log n)	O(1) by marking
Balanced tree	O(log n)	O(log n)	O(log n), really removed

A sorted list is fast to read but slow to add to: every new job shifts, on average, half a million entries to make room. Reminders arrive all day, so that’s the wrong trade.

A balanced tree, such as Java’s TreeMap or a skip list, does everything in O(log n), and it can really remove a cancelled job. It’s a fine answer, and the better one when most jobs are cancelled long before they’re due. The price is more memory per job, and more code to get right.

A heap is the simplest structure that answers the only question the scheduler asks often, “what’s earliest?”, cheaply. It’s a plain array, so it’s small and fast in practice. With marking, its one weak spot, cancel, costs O(1). That’s why most schedulers in standard libraries use one.

Stage 3: Repeating jobs

Interviewerminute 12

The cache refresh should run every five minutes. Sometimes it takes six. What happens?

What they are testing

Whether you know there are two meanings of “every five minutes”, and say which one you’re building. One red flag is a slow run letting the next one start while it’s still going. Another is a paused scheduler that fires the job ten times in a row when it resumes.

“Every five minutes” means one of two things:

• Fixed rate: start at 10:00, 10:05, 10:10, on the clock, however long each run takes. A report that must arrive on the hour wants this.
• Fixed delay: wait five minutes after each run finishes. A run that takes two minutes pushes the next one to 10:07. A job that checks a mailbox wants this, because there’s no point checking again before the last check is done.

Both kinds go back on the timetable after each run, but at different moments. A fixed-rate job is put back as soon as it’s taken, at its next slot. So its next run time doesn’t depend on how long the run takes. A fixed-delay job is put back only when the run finishes, at the finish time plus the delay.

Two cases decide whether fixed rate is correct. First, if a run is still going when the next slot comes, that slot is skipped and counted, so runs never overlap. Second, suppose the scheduler was paused for three periods, by a long garbage collection pause or a closed laptop lid. The job then runs once to catch up, and goes back to its slots. Firing three times in a row would hit whatever the job talks to, all at once, for no benefit.

Stage 3: repeating jobs

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

A job’s running flag tells the scheduler that a fixed-rate run is still going, and finished(job) is the one place that clears it. A repeating job keeps its id across runs, so cancel works on the whole series: the current run finishes, and no more start.

JScheduler.javaPyscheduler.pyC#Scheduler.csGoscheduler.goTSscheduler.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// How a job repeats, if at all.
enum Repeat {
    ONCE,
    FIXED_RATE,  // starts every period on the clock: 10:00, 10:05, 10:10, however long each run takes
    FIXED_DELAY  // waits a delay after each run finishes: a run that takes 2 minutes pushes the next one back
}

class Job {
    final String id;
    final Runnable task;
    final Repeat repeat;
    final long every;  // the period or the delay; unused for ONCE
    long seq;
    long runAt;
    boolean running;
    boolean cancelled;

    Job(String id, Runnable task, Repeat repeat, long every, long runAt) {
        this.id = id;
        this.task = task;
        this.repeat = repeat;
        this.every = every;
        this.runAt = runAt;
    }
}

class Scheduler {
    private final PriorityQueue<Job> timetable =
        new PriorityQueue<>(Comparator.comparingLong((Job j) -> j.runAt).thenComparingLong(j -> j.seq));
    private final Map<String, Job> jobs = new HashMap<>();
    private final LongSupplier clock;
    private final Supplier<String> ids;
    private long nextSeq;
    long skipped;  // fixed-rate runs skipped because the previous one was still going

    Scheduler(LongSupplier clock, Supplier<String> ids) {
        this.clock = clock;
        this.ids = ids;
    }

    String schedule(Runnable task, long delayMillis) { return add(task, Repeat.ONCE, 0, delayMillis); }

    String scheduleAtFixedRate(Runnable task, long initialDelay, long period) {
        return add(task, Repeat.FIXED_RATE, period, initialDelay);
    }

    String scheduleWithFixedDelay(Runnable task, long initialDelay, long delay) {
        return add(task, Repeat.FIXED_DELAY, delay, initialDelay);
    }

    // A running job finishes its current run; cancelling stops the ones after it.
    boolean cancel(String id) {
        Job j = jobs.remove(id);
        if (j == null) return false;
        j.cancelled = true;
        return true;
    }

    OptionalLong nextRunAt() {
        dropCancelled();
        return timetable.isEmpty() ? OptionalLong.empty() : OptionalLong.of(timetable.peek().runAt);
    }

    List<Job> takeDue() {
        long now = clock.getAsLong();
        List<Job> due = new ArrayList<>();
        for (dropCancelled(); !timetable.isEmpty() && timetable.peek().runAt <= now; dropCancelled()) {
            Job j = timetable.poll();
            if (j.repeat == Repeat.FIXED_RATE) {
                // The next run goes on the timetable now, at the next slot after now. A scheduler
                // that was paused for three periods runs the job once, not three times in a row.
                long next = j.runAt + j.every;
                if (next <= now) next += (now - next) / j.every * j.every + j.every;
                requeue(j, next);
                if (j.running) {  // the last run is still going: skip this one rather than overlap
                    skipped++;
                    continue;
                }
            }
            j.running = true;
            due.add(j);
        }
        return due;
    }

    // Called when a run ends. A fixed-delay job is only now put back, a delay after it finished.
    void finished(Job j) {
        j.running = false;
        if (j.cancelled) return;
        if (j.repeat == Repeat.ONCE) jobs.remove(j.id);
        if (j.repeat == Repeat.FIXED_DELAY) requeue(j, clock.getAsLong() + j.every);
    }

    int runDue() {
        List<Job> due = takeDue();
        for (Job j : due) {
            try {
                j.task.run();
            } catch (RuntimeException e) {
                // stage 4
            }
            finished(j);
        }
        return due.size();
    }

    private String add(Runnable task, Repeat repeat, long every, long delay) {
        Job j = new Job(ids.get(), task, repeat, every, 0);
        jobs.put(j.id, j);
        requeue(j, clock.getAsLong() + delay);
        return j.id;
    }

    private void requeue(Job j, long runAt) {
        j.runAt = runAt;
        j.seq = nextSeq++;
        timetable.add(j);
    }

    private void dropCancelled() {
        while (!timetable.isEmpty() && timetable.peek().cancelled) timetable.poll();
    }
}

Common mistake

Computing the next run from when the run started

For fixed rate, next = startTime + period drifts. A run that starts 20 ms late pushes every later run 20 ms later, and after a day the report runs minutes off the hour. The next slot comes from the previous slot, runAt + period, so lateness never adds up.

Go deeperA six-minute run, with a five-minute period2 min

Let’s follow the cache refresh with both kinds, when one run takes six minutes.

With fixed rate, the slots are 10:00, 10:05 and 10:10. The 10:00 run starts, and goes on until 10:06. At 10:05, the scheduler sees that the job is still running. So it skips the 10:05 slot, counts the skip, and puts the job back for 10:10. At 10:10, the run starts on time. The clock stays the same, and one run was lost. The skip count shows it.

With fixed delay, the 10:00 run finishes at 10:06, and the next run is put on the timetable for 10:11. Nothing is skipped, but the whole series slides later.

Sequence: a run that takes 6 minutes, with a 5-minute period

Scroll or pinch to zoom, drag to pan

• Color key
• Background worker
• Facade

Why not let fixed-rate runs overlap, if the job is slow? Because most jobs aren’t written to run twice at once. Two cache refreshes at the same time double the load on the database. And they do it when the database is already slow, which is often why the run was slow in the first place. Skipping and counting the skip makes the problem visible, without making it worse.

Stage 4: Failures, retries and status

Interviewerminute 18

The reminder email fails because the mail server is down. What happens to it? And how does the order service find out?

What they are testing

Whether you retry with growing waits instead of right away, and treat a repeating job differently from a one-off. They also check that a failure is visible: a status someone can ask for, and the error that caused it.

A one-off job that fails is retried, with growing waits: up to three attempts in all, waiting one second, then two. Retrying right away would hit a mail server that’s down three times in a millisecond. After the last attempt, the job is failed, and its last error is kept.

A repeating job is not retried. Its next run is its retry, and one failed refresh shouldn’t end a series that runs again in five minutes. The error is still recorded.

Where does a retry wait? It goes back on the timetable, at a later time. So the worker is free for other jobs while it waits, cancel still works during the wait, and the status honestly says “scheduled”. A retry is just a job with a later run time, and the timetable already knows how to wait for those.

Every job now has a status, and the scheduler keeps finished jobs in its map, so callers can ask for it. A job that has ended can’t be cancelled. A running job can be: it finishes its current run, but never runs again.

Stage 4: the life of a one-off job

Scroll or pinch to zoom, drag to pan

• Color key
• State
• Ends well
• Fails or stops

Stage 4: retry policy and status

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JScheduler.javaPyscheduler.pyC#Scheduler.csGoscheduler.goTSscheduler.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Where a job is in its life. SUCCEEDED, FAILED and CANCELLED are final.
enum Status { SCHEDULED, RUNNING, SUCCEEDED, FAILED, CANCELLED }

// How a one-off job retries: up to maxAttempts runs in all, waiting backoff, then twice that,
// then four times, so a struggling service isn't hammered.
record Retry(int maxAttempts, long backoffMillis) {}

// One scheduled job and its bookkeeping. runAt is when it runs next. seq breaks ties: jobs due
// at the same moment run in the order they were queued. running is true while a run is in
// progress, and cancelled is only a mark, because taking a job out of the middle of the
// timetable is slow.
class Job {
    final String id;
    final Runnable task;
    final Repeat repeat;
    final long every;
    long seq;
    long runAt;
    boolean running;
    boolean cancelled;
    Status status = Status.SCHEDULED;
    int attempts;      // runs started so far
    String lastError;

    Job(String id, Runnable task, Repeat repeat, long every, long runAt) {
        this.id = id;
        this.task = task;
        this.repeat = repeat;
        this.every = every;
        this.runAt = runAt;
    }
}

// The timetable. A priority queue keeps the job due soonest at the front, so finding what is
// due never scans every job. It has no threads of its own: tests drive it with a fake clock,
// and a separate runner drives it for real.
class Scheduler {
    private final PriorityQueue<Job> timetable =
        new PriorityQueue<>(Comparator.comparingLong((Job j) -> j.runAt).thenComparingLong(j -> j.seq));
    private final Map<String, Job> jobs = new HashMap<>();  // kept after they end, so status can be asked
    private final LongSupplier clock;
    private final Supplier<String> ids;
    private final Retry retry;
    private long nextSeq;
    // Fixed-rate runs skipped because the previous run of the same job was still going.
    long skipped;

    Scheduler(LongSupplier clock, Supplier<String> ids, Retry retry) {
        this.clock = clock;
        this.ids = ids;
        this.retry = retry;
    }

    String schedule(Runnable task, long delayMillis) { return add(task, Repeat.ONCE, 0, delayMillis); }

    String scheduleAtFixedRate(Runnable task, long initialDelay, long period) {
        return add(task, Repeat.FIXED_RATE, period, initialDelay);
    }

    String scheduleWithFixedDelay(Runnable task, long initialDelay, long delay) {
        return add(task, Repeat.FIXED_DELAY, delay, initialDelay);
    }

    // Only a job that hasn't ended can be cancelled. A running job finishes its current run, but
    // it is reported as cancelled and never runs again.
    boolean cancel(String id) {
        Job j = jobs.get(id);
        if (j == null || j.cancelled || j.status == Status.SUCCEEDED || j.status == Status.FAILED) return false;
        j.cancelled = true;
        j.status = Status.CANCELLED;
        return true;
    }

    Status status(String id) { return jobs.get(id).status; }

    String lastError(String id) { return jobs.get(id).lastError; }

    // When the next job is due, or nothing if the timetable is empty. Cancelled jobs at the
    // front are dropped first, so they can't cause a pointless wake-up.
    OptionalLong nextRunAt() {
        dropCancelled();
        return timetable.isEmpty() ? OptionalLong.empty() : OptionalLong.of(timetable.peek().runAt);
    }

    // Every job due by now, marked as running. A fixed-rate job is put back for its next slot
    // at once, counted from its schedule, not from now. Slots missed while the machine was busy
    // are skipped, not run in a burst. If its last run is still going, this run is skipped too,
    // so two runs of one job never overlap.
    List<Job> takeDue() {
        long now = clock.getAsLong();
        List<Job> due = new ArrayList<>();
        for (dropCancelled(); !timetable.isEmpty() && timetable.peek().runAt <= now; dropCancelled()) {
            Job j = timetable.poll();
            if (j.repeat == Repeat.FIXED_RATE) {
                long next = j.runAt + j.every;
                if (next <= now) next += (now - next) / j.every * j.every + j.every;
                requeue(j, next);
                if (j.running) {
                    skipped++;
                    continue;
                }
            }
            j.running = true;
            j.status = Status.RUNNING;
            j.attempts++;
            due.add(j);
        }
        return due;
    }

    // error is null when the run succeeded. A one-off job that fails is retried with growing
    // waits, then marked FAILED. A repeating job isn't retried: its next run is the retry, and
    // one bad run doesn't end the series.
    void finished(Job j, Throwable error) {
        j.running = false;
        if (error != null) j.lastError = String.valueOf(error.getMessage());
        if (j.cancelled) return;
        long now = clock.getAsLong();
        switch (j.repeat) {
            case ONCE -> {
                if (error == null) {
                    j.status = Status.SUCCEEDED;
                } else if (j.attempts < retry.maxAttempts()) {
                    j.status = Status.SCHEDULED;
                    requeue(j, now + (retry.backoffMillis() << (j.attempts - 1)));
                } else {
                    j.status = Status.FAILED;
                }
            }
            case FIXED_RATE -> j.status = Status.SCHEDULED;
            case FIXED_DELAY -> {
                j.status = Status.SCHEDULED;
                requeue(j, now + j.every);
            }
        }
    }

    // Runs every due job on the calling thread, one after another. Tests use this with a fake
    // clock.
    int runDue() {
        List<Job> due = takeDue();
        for (Job j : due) {
            Throwable error = null;
            try {
                j.task.run();
            } catch (RuntimeException e) {
                error = e;
            }
            finished(j, error);
        }
        return due.size();
    }

    // Every schedule call ends here. The job is remembered by id even after it ends, so its
    // status can still be asked.
    private String add(Runnable task, Repeat repeat, long every, long delay) {
        Job j = new Job(ids.get(), task, repeat, every, 0);
        jobs.put(j.id, j);
        requeue(j, clock.getAsLong() + delay);
        return j.id;
    }

    // Each requeue takes the next seq, so jobs due at the same moment run in the order they
    // were queued.
    private void requeue(Job j, long runAt) {
        j.runAt = runAt;
        j.seq = nextSeq++;
        timetable.add(j);
    }

    // Cancel only marks a job. Marked jobs are thrown away here, once they reach the front.
    private void dropCancelled() {
        while (!timetable.isEmpty() && timetable.peek().cancelled) timetable.poll();
    }
}

This is enough for a mid-level answer. A heap sorted by run time, repeating jobs, and errors caught so one job can’t stop the others. The rest of the page is what makes it a senior answer.

The full design

Here is everything together. RunningScheduler is what the application calls, and it owns the threads. Scheduler is the timetable and every rule about what runs next. It has no threads of its own, which is why the tests can drive it with a clock moved by hand.

Task scheduler: full class diagram

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

</>task-scheduler· read only

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

Explorer

• JAllInOne.java
• src
• JJob.java
• JRepeat.java
• JRetry.java
• JRunningScheduler.java
• JScheduler.java
• JStatus.java

JAllInOne.java

AllInOne.javasrc/Job.javasrc/Repeat.javasrc/Retry.javasrc/RunningScheduler.javasrc/Scheduler.javasrc/Status.java

AllInOne.java

// The complete design, built from every stage on this page.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
import java.util.function.*;

// One scheduled job and its bookkeeping. runAt is when it runs next. seq breaks ties: jobs due
// at the same moment run in the order they were queued. running is true while a run is in
// progress, and cancelled is only a mark, because taking a job out of the middle of the
// timetable is slow.
class Job {
    final String id;
    final Runnable task;
    final Repeat repeat;
    final long every;
    long seq;
    long runAt;
    boolean running;
    boolean cancelled;
    Status status = Status.SCHEDULED;
    int attempts;      // runs started so far
    String lastError;

    Job(String id, Runnable task, Repeat repeat, long every, long runAt) {
        this.id = id;
        this.task = task;
        this.repeat = repeat;
        this.every = every;
        this.runAt = runAt;
    }
}

// The timetable. A priority queue keeps the job due soonest at the front, so finding what is
// due never scans every job. It has no threads of its own: tests drive it with a fake clock,
// and a separate runner drives it for real.
class Scheduler {
    private final PriorityQueue<Job> timetable =
        new PriorityQueue<>(Comparator.comparingLong((Job j) -> j.runAt).thenComparingLong(j -> j.seq));
    private final Map<String, Job> jobs = new HashMap<>();  // kept after they end, so status can be asked
    private final LongSupplier clock;
    private final Supplier<String> ids;
    private final Retry retry;
    private long nextSeq;
    // Fixed-rate runs skipped because the previous run of the same job was still going.
    long skipped;

    Scheduler(LongSupplier clock, Supplier<String> ids, Retry retry) {
        this.clock = clock;
        this.ids = ids;
        this.retry = retry;
    }

    String schedule(Runnable task, long delayMillis) { return add(task, Repeat.ONCE, 0, delayMillis); }

    String scheduleAtFixedRate(Runnable task, long initialDelay, long period) {
        return add(task, Repeat.FIXED_RATE, period, initialDelay);
    }

    String scheduleWithFixedDelay(Runnable task, long initialDelay, long delay) {
        return add(task, Repeat.FIXED_DELAY, delay, initialDelay);
    }

    // Only a job that hasn't ended can be cancelled. A running job finishes its current run, but
    // it is reported as cancelled and never runs again.
    boolean cancel(String id) {
        Job j = jobs.get(id);
        if (j == null || j.cancelled || j.status == Status.SUCCEEDED || j.status == Status.FAILED) return false;
        j.cancelled = true;
        j.status = Status.CANCELLED;
        return true;
    }

    Status status(String id) { return jobs.get(id).status; }

    String lastError(String id) { return jobs.get(id).lastError; }

    // When the next job is due, or nothing if the timetable is empty. Cancelled jobs at the
    // front are dropped first, so they can't cause a pointless wake-up.
    OptionalLong nextRunAt() {
        dropCancelled();
        return timetable.isEmpty() ? OptionalLong.empty() : OptionalLong.of(timetable.peek().runAt);
    }

    // Every job due by now, marked as running. A fixed-rate job is put back for its next slot
    // at once, counted from its schedule, not from now. Slots missed while the machine was busy
    // are skipped, not run in a burst. If its last run is still going, this run is skipped too,
    // so two runs of one job never overlap.
    List<Job> takeDue() {
        long now = clock.getAsLong();
        List<Job> due = new ArrayList<>();
        for (dropCancelled(); !timetable.isEmpty() && timetable.peek().runAt <= now; dropCancelled()) {
            Job j = timetable.poll();
            if (j.repeat == Repeat.FIXED_RATE) {
                long next = j.runAt + j.every;
                if (next <= now) next += (now - next) / j.every * j.every + j.every;
                requeue(j, next);
                if (j.running) {
                    skipped++;
                    continue;
                }
            }
            j.running = true;
            j.status = Status.RUNNING;
            j.attempts++;
            due.add(j);
        }
        return due;
    }

    // error is null when the run succeeded. A one-off job that fails is retried with growing
    // waits, then marked FAILED. A repeating job isn't retried: its next run is the retry, and
    // one bad run doesn't end the series.
    void finished(Job j, Throwable error) {
        j.running = false;
        if (error != null) j.lastError = String.valueOf(error.getMessage());
        if (j.cancelled) return;
        long now = clock.getAsLong();
        switch (j.repeat) {
            case ONCE -> {
                if (error == null) {
                    j.status = Status.SUCCEEDED;
                } else if (j.attempts < retry.maxAttempts()) {
                    j.status = Status.SCHEDULED;
                    requeue(j, now + (retry.backoffMillis() << (j.attempts - 1)));
                } else {
                    j.status = Status.FAILED;
                }
            }
            case FIXED_RATE -> j.status = Status.SCHEDULED;
            case FIXED_DELAY -> {
                j.status = Status.SCHEDULED;
                requeue(j, now + j.every);
            }
        }
    }

    // Runs every due job on the calling thread, one after another. Tests use this with a fake
    // clock.
    int runDue() {
        List<Job> due = takeDue();
        for (Job j : due) {
            Throwable error = null;
            try {
                j.task.run();
            } catch (RuntimeException e) {
                error = e;
            }
            finished(j, error);
        }
        return due.size();
    }

    // Every schedule call ends here. The job is remembered by id even after it ends, so its
    // status can still be asked.
    private String add(Runnable task, Repeat repeat, long every, long delay) {
        Job j = new Job(ids.get(), task, repeat, every, 0);
        jobs.put(j.id, j);
        requeue(j, clock.getAsLong() + delay);
        return j.id;
    }

    // Each requeue takes the next seq, so jobs due at the same moment run in the order they
    // were queued.
    private void requeue(Job j, long runAt) {
        j.runAt = runAt;
        j.seq = nextSeq++;
        timetable.add(j);
    }

    // Cancel only marks a job. Marked jobs are thrown away here, once they reach the front.
    private void dropCancelled() {
        while (!timetable.isEmpty() && timetable.peek().cancelled) timetable.poll();
    }
}

// How a job repeats, if at all.
enum Repeat {
    ONCE,
    FIXED_RATE,  // starts every period on the clock: 10:00, 10:05, 10:10, however long each run takes
    FIXED_DELAY  // waits a delay after each run finishes: a run that takes 2 minutes pushes the next one back
}

// Where a job is in its life. SUCCEEDED, FAILED and CANCELLED are final.
enum Status { SCHEDULED, RUNNING, SUCCEEDED, FAILED, CANCELLED }

// How a one-off job retries: up to maxAttempts runs in all, waiting backoff, then twice that,
// then four times, so a struggling service isn't hammered.
record Retry(int maxAttempts, long backoffMillis) {}

// The scheduler running for real: one thread watches the timetable, and a pool of workers runs
// the jobs, so a slow job only occupies its own worker. Everything that touches the timetable
// (schedule, cancel, taking due jobs, a worker reporting a finished run) holds one lock, so a
// cancel can't slip in between "this job is due" and "this job is running".
//
// The watcher sleeps until the next job is due, but a job scheduled for sooner must wake it.
// It waits on a condition under the same lock that schedule() takes to add the job and signal,
// so the signal can't arrive in the gap between checking the timetable and starting to wait.
class RunningScheduler {
    private final Scheduler timetable;
    private final LongSupplier clock;
    private final ExecutorService workers;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition changed = lock.newCondition();
    private final Thread watcher = new Thread(this::watch, "scheduler");
    private boolean stopped;

    RunningScheduler(Scheduler timetable, LongSupplier clock, int workerCount) {
        this.timetable = timetable;
        this.clock = clock;
        this.workers = Executors.newFixedThreadPool(workerCount);
        watcher.start();
    }

    // Every change goes through changing(), which wakes the watcher, because the new job may be
    // due sooner than what it is waiting for.
    String schedule(Runnable task, long delayMillis) { return changing(() -> timetable.schedule(task, delayMillis)); }

    String scheduleAtFixedRate(Runnable task, long initialDelay, long period) {
        return changing(() -> timetable.scheduleAtFixedRate(task, initialDelay, period));
    }

    String scheduleWithFixedDelay(Runnable task, long initialDelay, long delay) {
        return changing(() -> timetable.scheduleWithFixedDelay(task, initialDelay, delay));
    }

    boolean cancel(String id) { return changing(() -> timetable.cancel(id)); }

    // Read under the lock too, because workers change a job's status from their own threads.
    Status status(String id) { return changing(() -> timetable.status(id)); }

    // Stops taking new runs; runs already started finish.
    void shutdown() throws InterruptedException {
        changing(() -> stopped = true);
        watcher.join();
        workers.shutdown();
        workers.awaitTermination(1, TimeUnit.MINUTES);
    }

    // The watcher thread. It hands every due job to a worker, then sleeps until the next job is
    // due or a change wakes it. Waiting lets go of the lock, so schedule and cancel can get in
    // while it sleeps.
    private void watch() {
        lock.lock();
        try {
            while (!stopped) {
                for (Job j : timetable.takeDue()) workers.execute(() -> run(j));
                OptionalLong next = timetable.nextRunAt();
                if (next.isEmpty()) changed.await();
                else changed.await(Math.max(1, next.getAsLong() - clock.getAsLong()), TimeUnit.MILLISECONDS);
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            lock.unlock();
        }
    }

    // On a worker, with no lock held while the task runs.
    private void run(Job j) {
        Throwable error = null;
        try {
            j.task.run();
        } catch (RuntimeException e) {
            error = e;
        }
        Throwable result = error;
        changing(() -> {
            timetable.finished(j, result);
            return null;
        });
    }

    // Runs a change under the lock and wakes the watcher, whose next wake-up may now be sooner.
    private <T> T changing(Supplier<T> change) {
        lock.lock();
        try {
            T result = change.get();
            changed.signal();
            return result;
        } finally {
            lock.unlock();
        }
    }
}

Read onlyJava 21Every file builds in CI7 files285 lines

Explorer

• Pyall_in_one.py
• task_scheduler
• Pycommon.py
• Pyjob.py
• Pyrepeat.py
• Pyretry.py
• Pyrunning_scheduler.py
• Pyscheduler.py
• Pystatus.py

Pyall_in_one.py

all_in_one.pytask_scheduler/common.pytask_scheduler/job.pytask_scheduler/repeat.pytask_scheduler/retry.pytask_scheduler/running_scheduler.pytask_scheduler/scheduler.pytask_scheduler/status.py

all_in_one.py

Read onlyPython 3.12Every file builds in CI8 files262 lines

Explorer

• C#AllInOne.cs
• src
• C#Job.cs
• C#Repeat.cs
• C#Retry.cs
• C#RunningScheduler.cs
• C#Scheduler.cs
• C#Status.cs

C#AllInOne.cs

AllInOne.cssrc/Job.cssrc/Repeat.cssrc/Retry.cssrc/RunningScheduler.cssrc/Scheduler.cssrc/Status.cs

AllInOne.cs

Read onlyC# · .NET 10Every file builds in CI7 files279 lines

Explorer

• Goall_in_one.go
• Gojob.go
• Gorepeat.go
• Goretry.go
• Gorunning_scheduler.go
• Goscheduler.go
• Gostatus.go
• Gotimetable.go

Goall_in_one.go

all_in_one.gojob.gorepeat.goretry.gorunning_scheduler.goscheduler.gostatus.gotimetable.go

all_in_one.go

Read onlyGo 1.24Every file builds in CI8 files351 lines

Explorer

• TSall-in-one.ts
• src
• TSjob.ts
• TSmin-heap.ts
• TSrepeat.ts
• TSretry.ts
• TSrunning-scheduler.ts
• TSscheduler.ts
• TSstatus.ts
• TStask.ts

TSall-in-one.ts

all-in-one.tssrc/job.tssrc/min-heap.tssrc/repeat.tssrc/retry.tssrc/running-scheduler.tssrc/scheduler.tssrc/status.tssrc/task.ts

all-in-one.ts

Read onlyTypeScript, strictEvery file builds in CI9 files325 lines

Three ideas hold it together:

• The timetable never searches. Every question it answers, “what’s next, and when?”, is a look at the top of the heap (a priority queue). Every change is one add or one removal at the top.
• Every run ends in finished. Success, failure, retry, the next fixed-delay run, and the end of a cancelled job are all decided in one method. So the rules live in one place.
• Deciding is separate from running. Scheduler decides what runs and when. The threads only carry jobs to workers and results back (producer-consumer). The task itself is a Command.

Stress it

So far, our tests call runDue by hand. Now we run the scheduler for real, with threads.

A sooner job, while the scheduler sleeps

Interviewerminute 24

Now run it for real. Jobs come in from many threads, and a job can take a minute. A job scheduled for one second from now must not wait behind one due in an hour. How do the threads work?

What they are testing

Whether the thread that sleeps until the next job is woken when a sooner job arrives, without losing the wake-up. The red flags are a plain sleep(nextRunAt - now), which can’t be woken, and running tasks while holding the scheduler’s lock.

The clearly correct design has one watcher thread that owns the waiting. It takes the jobs that are due, hands them to a fixed pool of workers, and sleeps until the next run time. A slow job holds one worker, and the watcher and the other workers carry on.

The watcher’s sleep is where the bugs are. Suppose it’s sleeping until a job an hour away, and a job for one second from now is scheduled. A plain sleep would run that new job an hour late. So the watcher waits on a condition with a time limit. A condition is a way for one thread to wait until another says “something changed”. Every change to the timetable signals it. The watcher wakes, looks at the top of the heap again, and goes back to sleep for the new, shorter time.

The better fix makes the signal impossible to miss. Picture this timing:

1. The watcher checks the timetable: the next job is an hour away.
2. Another thread adds a job for one second from now, and signals.
3. Only then does the watcher start waiting.

The signal in step 2 went to nobody, and the watcher sleeps an hour. This is called a lost wake-up. The fix: checking and starting to wait happen under the same lock that schedule holds while it adds a job and signals. And waiting on the condition releases that lock as one step. So there’s no gap for the signal to fall into.

Sequence: a sooner job wakes the watcher

Scroll or pinch to zoom, drag to pan

• Color key
• Background worker
• Facade

Option	How	Wakes for a sooner job?	Cost
1. One watcher, a condition, a worker pool (our choice)	Wait until the next run time, signalled on change	Yes	One lock shared by callers, the watcher and workers
2. Check every second	Stage 1’s loop, with a heap	Within a second	Up to a second late, and wakes when there’s nothing to do
3. A DelayQueue that workers take from	Workers wait on the queue until the top job is due	Yes, built in	Repeat, retry and status logic moves into the workers
4. A plain sleep until the next run	The watcher sleeps; nothing can wake it	No	A sooner job waits behind the earliest one
5. A thread per job	Each sleeps until its own time	Yes	A thread per waiting job

JRunningScheduler.javaPyrunning_scheduler.pyC#RunningScheduler.csGorunning_scheduler.goTSrunning-scheduler.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// The scheduler running for real: one thread watches the timetable, and a pool of workers runs
// the jobs, so a slow job only occupies its own worker. Everything that touches the timetable
// (schedule, cancel, taking due jobs, a worker reporting a finished run) holds one lock, so a
// cancel can't slip in between "this job is due" and "this job is running".
//
// The watcher sleeps until the next job is due, but a job scheduled for sooner must wake it.
// It waits on a condition under the same lock that schedule() takes to add the job and signal,
// so the signal can't arrive in the gap between checking the timetable and starting to wait.
class RunningScheduler {
    private final Scheduler timetable;
    private final LongSupplier clock;
    private final ExecutorService workers;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition changed = lock.newCondition();
    private final Thread watcher = new Thread(this::watch, "scheduler");
    private boolean stopped;

    RunningScheduler(Scheduler timetable, LongSupplier clock, int workerCount) {
        this.timetable = timetable;
        this.clock = clock;
        this.workers = Executors.newFixedThreadPool(workerCount);
        watcher.start();
    }

    // Every change goes through changing(), which wakes the watcher, because the new job may be
    // due sooner than what it is waiting for.
    String schedule(Runnable task, long delayMillis) { return changing(() -> timetable.schedule(task, delayMillis)); }

    String scheduleAtFixedRate(Runnable task, long initialDelay, long period) {
        return changing(() -> timetable.scheduleAtFixedRate(task, initialDelay, period));
    }

    String scheduleWithFixedDelay(Runnable task, long initialDelay, long delay) {
        return changing(() -> timetable.scheduleWithFixedDelay(task, initialDelay, delay));
    }

    boolean cancel(String id) { return changing(() -> timetable.cancel(id)); }

    // Read under the lock too, because workers change a job's status from their own threads.
    Status status(String id) { return changing(() -> timetable.status(id)); }

    // Stops taking new runs; runs already started finish.
    void shutdown() throws InterruptedException {
        changing(() -> stopped = true);
        watcher.join();
        workers.shutdown();
        workers.awaitTermination(1, TimeUnit.MINUTES);
    }

    // The watcher thread. It hands every due job to a worker, then sleeps until the next job is
    // due or a change wakes it. Waiting lets go of the lock, so schedule and cancel can get in
    // while it sleeps.
    private void watch() {
        lock.lock();
        try {
            while (!stopped) {
                for (Job j : timetable.takeDue()) workers.execute(() -> run(j));
                OptionalLong next = timetable.nextRunAt();
                if (next.isEmpty()) changed.await();
                else changed.await(Math.max(1, next.getAsLong() - clock.getAsLong()), TimeUnit.MILLISECONDS);
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            lock.unlock();
        }
    }

    // On a worker, with no lock held while the task runs.
    private void run(Job j) {
        Throwable error = null;
        try {
            j.task.run();
        } catch (RuntimeException e) {
            error = e;
        }
        Throwable result = error;
        changing(() -> {
            timetable.finished(j, result);
            return null;
        });
    }

    // Runs a change under the lock and wakes the watcher, whose next wake-up may now be sooner.
    private <T> T changing(Supplier<T> change) {
        lock.lock();
        try {
            T result = change.get();
            changed.signal();
            return result;
        } finally {
            lock.unlock();
        }
    }
}

Why is this correct? The lock covers everything that touches the timetable: schedule, cancel, taking due jobs, and a worker reporting a finished run. So a cancel can’t slip in between “this job is due” and “this job is running”. And the fixed-rate running flag is always right. The watcher also checks and waits only while holding that lock. So every signal arrives either before it checks (and it sees the new job), or while it waits (and it wakes).

What does it cost? Callers, the watcher and the workers share one lock, but each holds it only for a few heap operations. The lock is never held while a task runs, or one slow job would freeze scheduling for everyone.

Common mistake

Trusting the wall clock

Say run times come from the wall clock. A time sync sets the clock back an hour, and every job runs an hour late. Set it forward, and an hour of jobs fires at once. So delays are measured on a monotonic clock (System.nanoTime, time.monotonic, Environment.TickCount64), which only moves forward. Jobs that must run at a calendar time, like 9:00 every Monday, are the exception. They work out their next run from the wall clock each time.

Go deeperHow each language waits so it can be woken1 min

Java waits on a Condition from the lock, Python on a threading.Condition, and C# on Monitor.Wait. Each one releases the lock and starts waiting as one step. Go has no condition variable with a time limit. So the watcher waits on either a timer or a wake channel with room for one signal. A signal sent while the watcher is busy stays in the channel, which closes the same gap. TypeScript has one thread, so there is no lock. The watcher is a setTimeout, moved earlier when a sooner job arrives. The worker count is a limit on how many tasks run at once.

How you’d prove it works

The scheduler is given a clock, so the tests control time. A test schedules jobs, sets the clock, calls runDue, and checks. A test that sleeps five minutes to check a five-minute job is slow and still flaky. Only one test uses real threads, and it waits on latches (a signal that a thread has reached a point), not sleeps. The tests that matter:

• Jobs run in time order and never early. Jobs due together run in the order scheduled.
• A cancelled job never runs, and cancelling twice is refused.
• Fixed rate keeps to its slots. After a pause through three slots, it runs once, then carries on at the next slot.
• Fixed rate skips a slot while the previous run is still going.
• Fixed delay’s next run is the delay after the run finished.
• A failing one-off job retries after 1 s, then 2 s, then fails with its last error. One that succeeds on a retry ends as succeeded.
• A failed run doesn’t end a repeating job.
• With real threads, a job scheduled sooner wakes a watcher that was sleeping until a minute from now. It runs while a slow job holds the other worker.

Go deeperThe tests in five languages2 min

JMain.javaPyworld.pyC#Program.csGoworld.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

long now = 0;  // the test's clock, in milliseconds
AtomicInteger nextId = new AtomicInteger();
Scheduler s;
List<String> ran = new ArrayList<>();

@BeforeEach
void setUp() { s = new Scheduler(() -> now, () -> "j" + nextId.incrementAndGet(), new Retry(3, 1000)); }

Runnable record(String name) { return () -> ran.add(name); }

void advanceTo(long t) {
    now = t;
    s.runDue();
}

@Test
void jobsRunInTimeOrderAndNeverEarly() {
    s.schedule(record("c"), 300);
    s.schedule(record("a"), 100);
    s.schedule(record("b"), 200);
    advanceTo(99);
    assertEquals(List.of(), ran);
    advanceTo(250);
    assertEquals(List.of("a", "b"), ran);
    assertEquals(300L, s.nextRunAt().getAsLong());
}

@Test
void jobsDueTogetherRunInTheOrderScheduled() {
    s.schedule(record("first"), 100);
    s.schedule(record("second"), 100);
    advanceTo(100);
    assertEquals(List.of("first", "second"), ran);
}

@Test
void aCancelledJobNeverRuns() {
    String id = s.schedule(record("x"), 100);
    assertTrue(s.cancel(id));
    assertFalse(s.cancel(id));
    advanceTo(1000);
    assertEquals(List.of(), ran);
    assertEquals(Status.CANCELLED, s.status(id));
}

@Test
void fixedRateKeepsToTheClockAndSkipsMissedRuns() {
    s.scheduleAtFixedRate(record("tick"), 100, 100);
    advanceTo(100);
    advanceTo(200);
    assertEquals(2, ran.size());
    advanceTo(550);                                // paused through 300, 400 and 500
    assertEquals(3, ran.size());                   // runs once to catch up, not three times
    assertEquals(600L, s.nextRunAt().getAsLong());  // and stays on the 100s
}

@Test
void fixedRateSkipsARunWhileThePreviousOneIsStillGoing() {
    s.scheduleAtFixedRate(record("tick"), 0, 100);
    List<Job> first = s.takeDue();                 // started at 0, still running
    now = 100;
    assertEquals(0, s.takeDue().size());
    assertEquals(1L, s.skipped);
    s.finished(first.get(0), null);
    now = 200;
    assertEquals(1, s.takeDue().size());
}

@Test
void fixedDelayWaitsAfterEachRunFinishes() {
    s.scheduleWithFixedDelay(() -> now += 300, 0, 100);  // each run takes 300 ms
    advanceTo(0);                                       // runs 0 to 300
    assertEquals(400L, s.nextRunAt().getAsLong());       // 100 after it finished, not after it started
}

@Test
void aFailingJobIsRetriedWithGrowingWaitsThenFails() {
    String id = s.schedule(() -> { throw new IllegalStateException("smtp down"); }, 0);
    advanceTo(0);
    assertEquals(Status.SCHEDULED, s.status(id));
    assertEquals(1000L, s.nextRunAt().getAsLong());  // first retry after 1 s
    advanceTo(1000);
    assertEquals(3000L, s.nextRunAt().getAsLong());  // then 2 s
    advanceTo(3000);
    assertEquals(Status.FAILED, s.status(id));
    assertEquals("smtp down", s.lastError(id));
}

@Test
void aRetryThatSucceedsEndsTheJob() {
    AtomicInteger calls = new AtomicInteger();
    String id = s.schedule(() -> { if (calls.incrementAndGet() == 1) throw new IllegalStateException("timeout"); }, 0);
    advanceTo(0);
    advanceTo(1000);
    assertEquals(Status.SUCCEEDED, s.status(id));
    assertTrue(s.nextRunAt().isEmpty());
}

@Test
void aFailedRunDoesNotEndARepeatingJob() {
    AtomicInteger calls = new AtomicInteger();
    String id = s.scheduleAtFixedRate(() -> { if (calls.incrementAndGet() == 1) throw new IllegalStateException("blip"); }, 0, 100);
    advanceTo(0);
    advanceTo(100);
    assertEquals(2, calls.get());
    assertEquals(Status.SCHEDULED, s.status(id));
    assertTrue(s.cancel(id));
    advanceTo(1000);
    assertEquals(2, calls.get());
}

@Test
void workersKeepASlowJobFromDelayingTheNext() throws Exception {
    LongSupplier millis = () -> System.nanoTime() / 1_000_000;  // monotonic: a clock change can't move it
    RunningScheduler live = new RunningScheduler(
        new Scheduler(millis, () -> "j" + nextId.incrementAndGet(), new Retry(1, 0)), millis, 2);
    CountDownLatch release = new CountDownLatch(1);
    CountDownLatch quickRan = new CountDownLatch(1);
    live.schedule(() -> {
        try {
            release.await();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }, 0);
    live.schedule(() -> {}, 60_000);              // the watcher now sleeps toward a minute away
    live.schedule(quickRan::countDown, 20);       // scheduled sooner, so it must wake the watcher
    assertTrue(quickRan.await(5, TimeUnit.SECONDS));  // ran while the slow job holds a worker
    release.countDown();
    live.shutdown();
}

Go deeperEvery edge case, and where it is handled2 min

Case	What happens	Where
Two jobs due at the same moment	Run in the order scheduled	The heap’s seq tie-break
A job scheduled sooner than the next one	The watcher wakes and checks again	changing signals
A delay of zero or less	Due at once, taken on the next check	takeDue
Cancel a running job	The run finishes, no further runs	cancel, then finished
Cancel a finished job	Refused	cancel
Fixed-rate run still going at the next slot	Skipped and counted	takeDue
Scheduler paused for several periods	Fixed rate runs once, then keeps to its slots	takeDue
A task throws	One-off: retried with growing waits, then failed; repeating: carries on	finished
Every worker busy	Due jobs wait for a free worker, in order	the pool’s queue
Shutdown with jobs running	Running jobs finish; waiting jobs don’t start	shutdown
Process crashes	Every waiting job is lost: the timetable is in memory	out of scope

Wrap up

The decisions, and what each one costs

Decision	We chose	We gave up
Finding the next job	A min-heap sorted by run time, then sequence number	O(1) add, which a timing wheel gives
Cancel	Mark, drop at the top	Memory until the cancelled job’s time
Repeating	Fixed rate (skip on overlap, run once after a pause) and fixed delay	Overlapping runs for jobs that could take them
Failures	One-off jobs retry with growing waits on the timetable; repeating jobs carry on	Retries for repeating jobs
Waiting	One watcher on a condition, woken on every change	The simplicity of a one-second check
Running	A fixed pool of workers, no lock held while a task runs	Unlimited parallel runs
Saving to disk	None: in memory, one process	Every waiting job, on a crash

Go deeperGenuinely different designs, and when to pick them2 min

Use the platform’s scheduler. Java’s ScheduledThreadPoolExecutor is this whole design. It has a heap, fixed rate and fixed delay with the same overlap rules, and a worker pool. In a real service you’d use it, or Quartz for cron jobs and saving to disk. The interview asks whether you could build it, and whether you know what it does when a job is slow.

A hashed timing wheel. Netty and Kafka keep timers in a ring of buckets, one bucket per tick, so adding and cancelling cost O(1). The price is precision: a timer fires on the tick after it’s due. It wins when there are millions of timers and most are cancelled, like request timeouts.

A queue with delayed delivery. SQS delay queues, or a Redis sorted set scored by run time, move the timetable out of the process entirely. Workers become plain consumers, and the queue handles saving and claiming jobs. It suits jobs that already cross machines.

How to spend 45 minutes

• 0 to 3. One process, nothing saved to disk, the kinds of job, and what failure means.
• 3 to 5. The promises. Name “never early, and a slow job can’t delay the others” as the hard one.
• 5 to 24. A list and a loop, a min-heap with cancel by marking, fixed rate and fixed delay, then retries and status. Code takeDue and finished.
• 24 to 26. Walk through the full diagram: the timetable decides, the threads carry.
• 26 to 32. The watcher, waking it for a sooner job, and the workers.
• 32 to 45. Saving to disk and several machines, then your own questions.

If time is short, skip retries and spend it on fixed rate versus fixed delay, and on waking the watcher. Those are the two places this question is decided.

Follow-up questions

Interviewerminute 32

The jobs now have to survive a restart, and the service runs on three machines. What changes?

What they are testing

Whether you see that the timetable moves into a database, and that the new problem is two machines running the same job. They want to hear about claiming a job in one step, and what happens when the machine that claimed it dies.

Most extensions fit into one place:

Extension	What changes	Touches the threads?
Survive a restart	A jobs table; startup reloads due and future jobs	No
Several machines	Claim with a lease, SKIP LOCKED, jobs safe to repeat	Yes
Cron expressions	A Trigger that computes the next run time; fixed rate is one kind	No
Priorities	The heap sorts by (run time, priority, sequence number)	No
Millions of timers, rough timing	A hashed timing wheel instead of a heap: O(1) add and cancel	No
Metrics	Lag (start time minus run time), skips, failures per job	No

Go deeperMoving to a database and three machines, step by step2 min

1. The timetable becomes a table. A jobs table with a run_at column and an index on it. The index does what the heap did: it finds the earliest jobs without reading the rest.
2. Each machine asks for due jobs, and claims them in one step. In PostgreSQL: SELECT ... WHERE run_at <= now() ORDER BY run_at LIMIT 10 FOR UPDATE SKIP LOCKED. FOR UPDATE locks the rows it picks, and SKIP LOCKED makes other machines pass over locked rows instead of waiting. So three machines take different jobs, at the same time.
3. A claim is a lease, with an expiry. The machine writes “claimed by me until 10:02”. If it dies in the middle of a run, the lease runs out and another machine takes the job.
4. So a job can run twice. Once on the machine that died, partly or fully, and once on its replacement. Jobs must be safe to repeat, for example by recording “reminder 41 sent” and checking it first.
5. The in-memory design doesn’t go away. It becomes each machine’s local timetable of the jobs it has claimed, with the same watcher and workers.

The new costs are a database query every few seconds per machine, and jobs that must be safe to repeat. Both are the price of not losing jobs on a crash.

Go deeperFour more follow-up questions2 min

Interviewer asksHow do you shut down cleanly?

Stop the watcher, so no new runs start. Then let the workers finish the runs already handed to them, with a deadline. Jobs still waiting on the timetable are dropped, which is fine in memory, and is exactly what a jobs table fixes. That’s what shutdown does, minus the deadline.

Interviewer asksWhat if a task never returns?

It holds its worker forever, and enough of them hold every worker. Give each run a time limit: the worker abandons or interrupts the task after it, records a failure, and the job’s retry rules apply. Interrupting only works if the task cooperates, so the time limit is also a number to alert on.

Interviewer asksHow many workers?

Enough for the jobs that are due at once, and no more than what the jobs talk to can take. Jobs that mostly wait on the network can have many workers. Jobs that use the CPU want about one per core. Lag, the time between a job’s run time and its actual start, is the number that says the pool is too small.

Interviewer asksWhy let the clock be passed in?

So time is an input. The tests set it instead of sleeping. The scheduler can use a monotonic clock for delays. And a simulation can run a week of jobs in a second.

Further reading

• Design a pub-sub system, another set of workers fed from a queue
• Design a rate limiter, which also lets time be injected for tests
• Command pattern, the shape of a task that runs later
• Java ScheduledThreadPoolExecutor, the production version of this design
• Hashed and Hierarchical Timing Wheels, Varghese and Lauck, the timing wheel paper