On this page

Design a Task Scheduler (LLD)

Every backend service has work that must happen later. A password-reset email goes out in five seconds, unless the user clicks "resend" first. A report is built every night at 02:30. Expired sessions are purged every ten minutes. A webhook that failed gets retried in a minute, then in two, then in four. You could start a thread and call sleep for each of these, and for one job that even works. With fifty jobs, retries, cancellation and a deploy that restarts the process twice a day, you need a component whose only job is deciding what runs when, on which thread.

That component is the subject of this case study: a job scheduler library that a service embeds in its own process. Java's ScheduledExecutorService is the smallest real example of it, Quartz is the large one, and Python's sched and APScheduler and Node's node-cron sit in between. The interview question asks you to design the class structure of such a library. It's popular because the domain is tiny (jobs, schedules, a queue, some threads), so almost all the difficulty is in the details: time, concurrency and failure. A candidate who draws a Job class and a PriorityQueue in five minutes and then can't say what happens when a recurring job runs longer than its period has drawn the easy 20% of the design.

Keep the scope honest from the start. This isn't an operating-system scheduler that picks which process gets the CPU, and it isn't cron on a host or a distributed job system with a database and many machines. Those are separate problems, and the background jobs section covers the distributed one. Everything here lives inside one process, in memory, and the interesting decisions are about classes, locks and clocks.

The final code is about 450 lines per language plus a self-check, runs as-is, and checks every rule it claims.

1. Requirements

Clarifying questions worth asking

QuestionAnswer we design forWhy it matters
Library inside one process, or a service?A library. One process, in memory.No persistence or network. The hard part is threads and time.
What kinds of schedule?One-off at a time, one-off after a delay, fixed rate, fixed delay, and a simple five-field cron expression.Three different "next time" rules, which is the first hint of a Strategy.
Fixed rate or fixed delay, if a run is slow?Both exist. Fixed rate measures from the scheduled start, fixed delay from the finish.Decides which timestamp the next run is computed from.
May one recurring job run twice at the same time?No. A recurring job never overlaps itself.Rules out "just enqueue the next run when this one starts".
How many jobs run at once?At most workers, a fixed pool size chosen at construction.Bounds threads, and makes "due but no free worker" a real state.
What if a job throws?Retry with exponential backoff and jitter, up to a limit, chosen per job. Then the run counts as failed.Retry is a policy, so it belongs outside the job's own code.
What if the process was paused and a job is very late?A per-job misfire policy: fire once now, skip, or catch up on every missed run.Without a policy, a laptop that wakes from sleep fires 500 reminder emails at once.
Can jobs be cancelled?Yes, at any time. A running job is asked to stop and never runs again.Cancellation has to win against a dispatcher that is about to fire.
Do we need results or a history?The last run and a run count per job, plus an event stream for anything else.Keeps memory bounded for jobs that run forever.
How do we test time-based code?Every time read goes through an injected Clock. Tests use a fake one.This one decision makes every other rule testable in milliseconds.
What happens on shutdown?Stop firing, cancel queued work, let running jobs finish within a timeout.The difference between a clean deploy and half-sent emails.

Functional requirements

  1. schedule(name, task, trigger, options) returns a job id. A trigger is one of:
    • at a timestamp (one-off);
    • after a delay (one-off);
    • fixed rate: every period, measured from each run's scheduled time;
    • fixed delay: delay after each run finishes;
    • cron: five UTC fields (minute hour day-of-month month day-of-week) with *, numbers, ranges, steps and lists.
  2. A job runs no earlier than its scheduled time and, if workers are free, as soon after it as possible.
  3. At most workers jobs run at once. A recurring job never runs twice at the same time.
  4. A failing run is retried according to the job's retry policy. The default is no retry. The provided policy is exponential backoff with a cap and jitter.
  5. A one-off job ends COMPLETED or FAILED. A recurring job keeps going after a failed run.
  6. A run is a misfire when it starts more than misfireThreshold after its scheduled time. Each job picks FIRE_NOW, SKIP or CATCH_UP.
  7. cancel(id) stops a scheduled job at once. A running job is told to stop (cooperatively) and is not rescheduled.
  8. Listeners receive an event for every state change: scheduled, started, run succeeded, run failed, retrying, misfired, completed, failed and cancelled.
  9. shutdown(timeout) stops dispatching, cancels queued jobs, waits for running ones and reports whether they all finished.

Non-functional requirements

  • Thread-safe. schedule and cancel may be called from any thread, including from inside a running job.
  • No job runs under the scheduler lock. A slow job never blocks scheduling, cancelling or other jobs.
  • Prompt. Adding a job that's due sooner than everything else must wake the dispatcher. It must not wait for the dispatcher's current sleep to end.
  • Deterministic tests. No test sleeps to "let time pass". Fake time moves only when the test says so.
  • Bounded memory. One queue entry per live job, plus that job's last run.

Out of scope

Persistence across restarts, several processes sharing one schedule, time zones other than UTC for cron, seconds in cron expressions, and job results returned to the caller as futures. Each is a reasonable follow-up, and section 11 answers the common ones. Say this list out loud in the interview, so the interviewer knows you saw these and chose to leave them out.

2. Core entities and relationships

Pull the nouns out of the requirements and most of them become classes:

EntityResponsibilityNotes
SchedulerThe facade. Owns the queue, the lock, the dispatcher thread, the worker pool and the job table.The only class callers talk to.
JobScheduling state for one registered job: its state, the scheduled time of the current occurrence, the attempt number and its single live queue entry.Mutable. Touched only under the scheduler lock. Callers get an immutable JobInfo snapshot.
TaskThe work itself: run(ctx).The Command. The scheduler never knows what it does.
TriggerAnswers "when first?" and "when next?". Once, FixedRate, FixedDelay, Cron.Strategy. Stateless, so one trigger can be shared.
RetryPolicyAnswers "how long until the next attempt, or give up?". NoRetry, ExponentialBackoff.Strategy.
MisfireFIRE_NOW, SKIP, CATCH_UP.An enum. Three fixed behaviours, each two lines, all inside the scheduler.
JobOptionsRetry policy and misfire policy for one job.A value object, so new options don't widen schedule().
Entry(dueTime, seq, job) in the priority queue.The tie-breaking seq keeps equal times FIFO.
WorkerPoolA fixed set of threads that run tasks.The JDK's fixed thread pool, Python's ThreadPoolExecutor, and in TypeScript a slot counter on the event loop.
JobRunOne attempt: scheduled, started and finished times, attempt number, error.Immutable. The "result".
JobContextWhat a running task may see: id, attempt, scheduled time and a cancellation flag.Passed into run.
JobEvent, JobListenerA state change, and whoever wants to hear about it.Observer.
Clocknow() in epoch milliseconds. SystemClock and FakeClock.The seam that makes everything testable.

The relationships that matter:

  • A Scheduler owns many Jobs, a priority queue of Entrys, one WorkerPool and one dispatcher thread. Jobs don't outlive their scheduler.
  • A Job has exactly one Task, one Trigger and one JobOptions. It holds zero or one live Entry. That "or one" is the rule that prevents double execution, and it's the most important line in the design.
  • A Job produces many JobRuns over its life but keeps only the last.
  • The Scheduler depends on a Clock, a set of Triggers and RetryPolicys, all interfaces. It never calls System.currentTimeMillis() or time.time() directly.

Two modelling choices deserve a sentence each. First, the trigger computes times but doesn't hold any per-job state. "When did this run last?" lives in Job, so a trigger can be shared and is trivially thread-safe. Second, Job (the mutable record) is separate from JobInfo (the snapshot callers see). Handing callers the live Job would let them read half-updated state from another thread. A snapshot taken under the lock never tears.

3. Class diagram

classDiagram
    class Scheduler {
        -clock: Clock
        -queue: priority queue of Entry
        -jobs: map of id to Job
        -pool: WorkerPool
        -lock: mutex plus condition
        -busy: int
        -accepting: boolean
        +schedule(name, task, trigger, options) String
        +cancel(jobId) boolean
        +info(jobId) JobInfo
        +addListener(listener)
        +start()
        +runDue() int
        +awaitIdle(timeout) boolean
        +shutdown(timeout) boolean
        -dispatch(now)
        -fire(entry, now)
        -execute(job, ctx)
        -afterRun(job, run, error)
    }
    class Job {
        +id: String
        +name: String
        +state: JobState
        +anchor: long
        +attempt: int
        +entry: Entry
        +cancelFlag: boolean
        +runs: int
        +lastRun: JobRun
    }
    class Entry {
        <<immutable>>
        +at: long
        +seq: long
        +job: Job
    }
    class Task {
        <<interface>>
        +run(ctx JobContext)
    }
    class Trigger {
        <<interface>>
        +first(now) long
        +next(scheduled, finished) long
    }
    class Once
    class FixedRate {
        +period: long
    }
    class FixedDelay {
        +delay: long
    }
    class Cron {
        +expr: String
    }
    class RetryPolicy {
        <<interface>>
        +delay(attempt, error) long
    }
    class NoRetry
    class ExponentialBackoff {
        +maxAttempts: int
        +baseMs: long
        +maxMs: long
        +rand: random source
    }
    class JobOptions {
        <<value>>
        +retry: RetryPolicy
        +misfire: Misfire
    }
    class Misfire {
        <<enumeration>>
        FIRE_NOW
        SKIP
        CATCH_UP
    }
    class JobState {
        <<enumeration>>
        SCHEDULED
        RUNNING
        RETRY_WAIT
        COMPLETED
        FAILED
        CANCELLED
        MISFIRED
    }
    class JobRun {
        <<immutable>>
        +attempt: int
        +scheduledAt: long
        +startedAt: long
        +finishedAt: long
        +error: String
    }
    class JobContext {
        +jobId: String
        +attempt: int
        +scheduledAt: long
        +isCancelled() boolean
    }
    class JobListener {
        <<interface>>
        +onEvent(event JobEvent)
    }
    class Clock {
        <<interface>>
        +now() long
    }
    class SystemClock
    class FakeClock {
        +advance(ms)
    }
    class WorkerPool {
        +size: int
        +execute(work)
    }

    Scheduler "1" *-- "many" Job : owns
    Scheduler "1" *-- "many" Entry : queue
    Scheduler "1" *-- "1" WorkerPool
    Scheduler --> Clock
    Scheduler --> JobListener : notifies
    Job "1" --> "0..1" Entry : live entry
    Job --> Task
    Job --> Trigger
    Job --> JobOptions
    Job --> JobState
    Job --> JobRun : last run
    JobOptions --> RetryPolicy
    JobOptions --> Misfire
    Task ..> JobContext : receives
    Trigger <|.. Once
    Trigger <|.. FixedRate
    Trigger <|.. FixedDelay
    Trigger <|.. Cron
    RetryPolicy <|.. NoRetry
    RetryPolicy <|.. ExponentialBackoff
    Clock <|.. SystemClock
    Clock <|.. FakeClock

Notice what's not in the diagram: there's no RecurringJob extends Job and no CronJob. Whether a job recurs is entirely the trigger's business. A one-off job is just a job whose trigger returns "never" from next. That keeps the scheduler's code path identical for every kind of job, which is where most of the bugs would otherwise hide.

4. Key flows

Scheduling a job, and waking the dispatcher

sequenceDiagram
    actor C as Caller thread
    participant S as Scheduler
    participant T as Trigger
    participant Q as Priority queue
    participant D as Dispatcher thread
    Note over D: asleep until 02:30, the earliest entry
    C->>S: schedule("reset-email", task, after(5s))
    S->>S: acquire lock
    S->>T: first(now)
    T-->>S: now + 5s
    S->>Q: push Entry(now + 5s, seq, job)
    S->>S: job.entry = that Entry, state SCHEDULED
    S->>D: signalAll on the condition
    S->>S: release lock
    S-->>C: "job-7"
    S-->>C: listeners get SCHEDULED
    D->>S: wakes, reacquires lock
    D->>Q: peek gives now + 5s
    D->>D: await(5s) instead of await(until 02:30)

The dispatcher was asleep with a timeout computed for the old head of the queue. If schedule didn't signal, the new five-second job would wait until 02:30. The signal costs one system call and is always safe, because a woken dispatcher simply recomputes its sleep. The listener notification happens after the lock is released, so a listener that calls back into the scheduler can't deadlock it.

Firing a due job

sequenceDiagram
    participant D as Dispatcher thread
    participant S as Scheduler state
    participant Q as Priority queue
    participant W as Worker thread
    actor J as Task
    D->>S: lock, now = clock.now()
    D->>D: busy is less than workers
    D->>Q: pop head, due at or before now
    D->>D: entry still equals job.entry, so it is live
    D->>D: late? check misfire policy
    D->>S: state RUNNING, entry = null, busy + 1
    D->>W: execute(job, ctx)
    D->>S: unlock, emit STARTED
    W->>J: run(ctx) with no lock held
    J-->>W: returns or throws
    W->>S: lock, busy - 1, record JobRun
    W->>S: next = trigger.next(scheduled, finished)
    W->>Q: push Entry(next) if there is a next
    W->>S: signalAll, unlock, emit events

Two things to say while drawing it. The task runs between two short critical sections, never inside one. And the next occurrence of a recurring job is enqueued when the current run finishes, not when it starts. That's the whole mechanism behind "a recurring job never overlaps itself", and section 7 comes back to it.

A failing run, retried with backoff

sequenceDiagram
    participant W as Worker thread
    actor J as Task
    participant S as Scheduler
    participant R as RetryPolicy
    participant Q as Priority queue
    W->>J: run(ctx), attempt 1
    J-->>W: throws ConnectionError
    W->>S: lock, record failed JobRun
    S->>R: delay(attempt 1, error)
    R-->>S: 1000 ms with jitter, say 730
    S->>Q: push Entry(finished + 730), state RETRY_WAIT, attempt 2
    S->>S: unlock, emit RUN_FAILED and RETRYING
    Note over W: the worker is free for other jobs during the wait
    Note over Q: 730 ms later the dispatcher fires attempt 2
    W->>J: run(ctx), attempt 2
    J-->>W: returns normally
    W->>S: lock, attempt resets to 1, compute next occurrence
    S->>S: unlock, emit RUN_SUCCEEDED, then COMPLETED or SCHEDULED

The retry goes back into the same priority queue as an ordinary entry. It doesn't sleep on the worker. A worker that sleeps through a backoff is a worker nobody else can use, and with four workers and four failing jobs, the whole scheduler would stall. The retry keeps the occurrence's original scheduled time, so a fixed-rate job's phase doesn't drift because of one bad run.

The job lifecycle

stateDiagram-v2
    [*] --> SCHEDULED: schedule()
    SCHEDULED --> RUNNING: due and a worker is free
    SCHEDULED --> MISFIRED: late, SKIP policy, no next occurrence
    SCHEDULED --> SCHEDULED: late, SKIP policy, next on-time occurrence
    SCHEDULED --> CANCELLED: cancel() or shutdown()
    RUNNING --> SCHEDULED: run ends, trigger has a next time
    RUNNING --> RETRY_WAIT: run failed, policy allows another attempt
    RUNNING --> COMPLETED: run succeeded, no next time
    RUNNING --> FAILED: run failed, no retry left, no next time
    RUNNING --> CANCELLED: cancel() during the run, or shutdown
    RETRY_WAIT --> RUNNING: backoff elapsed and a worker is free
    RETRY_WAIT --> CANCELLED: cancel() or shutdown()
    COMPLETED --> [*]
    FAILED --> [*]
    CANCELLED --> [*]
    MISFIRED --> [*]

A recurring job never reaches COMPLETED unless its trigger runs out. It cycles between SCHEDULED and RUNNING (with detours through RETRY_WAIT) until someone cancels it. A recurring job whose run fails with no retries left goes back to SCHEDULED, not to FAILED. Tonight's report failing is no reason to cancel tomorrow's.

The diagram is also the specification for cancel. From SCHEDULED and RETRY_WAIT it's immediate. From RUNNING it's a request, honoured when the run ends. From a terminal state it returns false.

Misfires: what "late" means

A job is late when now - scheduledTime > misfireThreshold at the moment the dispatcher picks it up. That happens when the process was paused (a laptop sleeps, a container is frozen, a long stop-the-world GC runs), when every worker was busy for a while, or when a fixed-rate job's run took longer than its period. Take a fixed-rate job every second, starting at t = 1 s, and a process that stalls until t = 5.5 s:

PolicyWhat runs at 5.5 sNext scheduledGood for
FIRE_NOW (default)The 1 s occurrence, once. 2 s to 5 s are coalesced into it.6 sCleanup, cache refresh, polling. Doing it once catches up fully.
SKIPNothing. A MISFIRED event is emitted.6 sTime-sensitive work where a late run is wrong, such as "send the 9:00 market-open alert".
CATCH_UP1 s, 2 s, 3 s, 4 s and 5 s, back to back.6 sWork where every occurrence matters, such as one billing rollup per hour.

A one-off job under SKIP that's late has no next occurrence, so it ends as MISFIRED. That's its own terminal state, because "we deliberately didn't run it" and "it ran and failed" call for different alerts.

The threshold matters too. Without one, a job that starts 3 ms late because the dispatcher was busy would count as a misfire. A default of one second is generous for an in-process scheduler. Quartz uses 60 seconds by default, because it's usually backed by a database.

5. Patterns, why, and the alternatives rejected

Strategy for triggers

The three recurring rules differ only in which timestamp the next one is computed from: the scheduled time for fixed rate and cron, the finish time for fixed delay. The scheduler shouldn't care which. So Trigger is an interface with first(now) and next(scheduled, finished), and the scheduler always passes both timestamps. Each implementation uses the one it needs. That's the Strategy pattern in its plainest form: a family of interchangeable algorithms behind one signature, chosen by the caller.

Rejected alternatives:

  • An enum of schedule types and a switch in the scheduler. It works for three types. The fourth (cron), then "business days only", then "every 15 minutes but not on public holidays", each reopen the scheduler's most delicate method. With Strategy, a new trigger is a new class, and the dispatcher stays untouched. That's the open-closed principle earning its keep.
  • Subclasses of Job (OneOffJob, RecurringJob, CronJob). Now what runs and when it runs are welded together. A report that moves from fixed delay to cron has to change class, and you can't share a trigger between jobs. Composition beats inheritance here. The job has a trigger.
  • Precomputing a list of fire times. Fine for "the next five runs", impossible for "forever", and wrong for fixed delay, whose times depend on how long each run takes.

Strategy for retry policy

Retry is the same move. The scheduler asks delay(attempt, error) and gets a number of milliseconds or "give up". Backoff, the cap, jitter and "only retry network errors" all live behind that one method.

Rejected alternatives:

  • Retrying inside the task. A for loop with sleep in every task that needs retries means every task re-implements backoff, slightly differently. Worse, the sleeping task holds a worker for the whole backoff, and nothing can cancel it cleanly.
  • A Decorator around the task (RetryingTask(task, policy)). Neater than an in-task loop, and good when the retries must happen within one run. But it still sleeps on the worker, and the scheduler can't see the attempts, so there are no RETRYING events and no RETRY_WAIT state for cancel to act on. Putting retry in the scheduler turns "wait 4 seconds" into a queue entry that costs nothing while it waits.
  • Fixed retry count as a scheduler-wide setting. Different jobs need different policies. A password reset email should retry fast and briefly. A nightly export can retry for an hour. That's why the policy is per job, in JobOptions.

Command for jobs

The scheduler stores a Task and later calls run(ctx) on some other thread, without knowing anything about what it does. Packaging a request as an object, so it can be queued, delayed, retried and cancelled by code that doesn't understand it, is the Command pattern. It's the same idea as Runnable handed to an executor, with a richer parameter. JobContext gives the command what a scheduled job needs and a plain Runnable lacks: which attempt this is, which occurrence it belongs to, and whether it has been cancelled.

Rejected alternatives:

  • A job type string plus a big switch in the scheduler ("send_email", "purge_sessions"). This couples the scheduler to every feature in the service.
  • Looking up a class by name, the way Quartz stores a job class name in JobDetail. Quartz does that because it persists jobs to a database and has to recreate them after a restart. We don't persist anything, so a reference to the object is simpler and type-safe. If the interviewer adds persistence, this is the change you'd make, and it's worth saying so.
  • Returning a result from run. A one-off job could hand back a future with a value, the way ScheduledExecutorService.schedule(Callable) does. A recurring job has no single result, though. The event stream carries outcomes for both, and a caller that wants a value can complete its own future inside the task.

Observer for job events

Metrics, logging, alerting on FAILED, an admin page that shows the last run, and job dependencies (extension C) all want to know when a job's state changes. The scheduler shouldn't know about any of them. So it publishes JobEvents to registered listeners, which is the Observer pattern.

Three implementation rules turn a textbook Observer into one that survives production:

  1. Notify outside the lock. Events are collected into a list while the lock is held, then delivered after it's released. A listener that calls schedule() or cancel() therefore can't deadlock.
  2. Isolate failures. A listener that throws is caught and ignored. A logging bug must not stop jobs from being rescheduled.
  3. Keep listeners fast. They run on the dispatcher or a worker thread. A slow listener delays that thread. If you need slow processing, have the listener put the event on a queue.

Rejected alternatives: polling info() (callers miss states between polls, and it's wasted work), one callback per job (it can't express cross-job concerns like metrics), and logging directly from the scheduler (that hard-codes one consumer and makes tests read log output).

The rest of the design, and what we chose not to use

ChoiceWhereWhyAlternative rejected
FacadeSchedulerOne entry point guards the invariants. No caller can push to the queue directly.Exposing the queue and the job table
Injected ClockConstructorEvery rule about time becomes testable in milliseconds. See designing for testability.Mocking the system clock globally, or sleeping in tests
Enum for misfire policyMisfireThree fixed behaviours of two lines each, which need scheduler internalsA MisfirePolicy interface. It would need access to the trigger, the threshold and the queue. Revisit if policies multiply.
Enum plus one transition method for job stateJobState, afterRunEvery transition lives in one method that holds the lockThe State pattern. Seven state classes would split one critical section across seven files. The transitions are simple, so the diagram plus one method is clearer.
Snapshot DTOJobInfoCallers never see a half-updated JobReturning the live Job
No SingletonAnywhereTests need fresh schedulers, and two schedulers in one process (say, one for emails with 16 workers and one for reports with 2) are perfectly reasonableA global Scheduler.getInstance()
No Template MethodTaskbefore, run, after hooks would turn a one-method interface into a base class every task must extendabstract class AbstractJob

6. The code

All three versions implement the same design and end with a self-check that exercises every rule: one-off, fixed rate versus fixed delay, retries and backoff values, all three misfire policies, no double execution, the pool bound, cancelling a running job, cron, shutdown and the early wake-up.

  • Java 24: javac Scheduler.java && java SchedulerDemo.
  • Python 3.12: save as scheduler.py, then python scheduler.py. The tests and extensions below import it.
  • TypeScript: npx tsx scheduler.ts. It typechecks with tsc --strict --noEmit --target es2022 --lib es2022,dom.
import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.time.temporal.ChronoUnit;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.BooleanSupplier;
import java.util.function.DoubleSupplier;

// ---------- Clock: the one source of "now", injectable for tests ----------
interface Clock { long now(); } // epoch milliseconds

final class SystemClock implements Clock {
    public long now() { return System.currentTimeMillis(); }
}

final class FakeClock implements Clock {
    private final AtomicLong t;
    FakeClock(long start) { t = new AtomicLong(start); }
    public long now() { return t.get(); }
    void advance(long ms) { t.addAndGet(ms); }
}

// ---------- Triggers (Strategy): when does a job fire next? null means never ----------
interface Trigger {
    Long first(long now);
    Long next(long scheduled, long finished);
}

record Once(Long at, long delay) implements Trigger {
    static Once at(long epochMs) { return new Once(epochMs, 0); }
    static Once after(long delayMs) { return new Once(null, delayMs); }
    public Long first(long now) { return at != null ? at : now + delay; }
    public Long next(long scheduled, long finished) { return null; }
}

/** Every period ms, measured from the previous scheduled time. */
record FixedRate(long period, long initialDelay) implements Trigger {
    FixedRate { if (period <= 0) throw new IllegalArgumentException("period must be positive"); }
    FixedRate(long period) { this(period, 0); }
    public Long first(long now) { return now + initialDelay; }
    public Long next(long scheduled, long finished) { return scheduled + period; }
}

/** delay ms after the previous run finished. */
record FixedDelay(long delay, long initialDelay) implements Trigger {
    FixedDelay { if (delay < 0) throw new IllegalArgumentException("delay must not be negative"); }
    FixedDelay(long delay) { this(delay, 0); }
    public Long first(long now) { return now + initialDelay; }
    public Long next(long scheduled, long finished) { return finished + delay; }
}

/** Five UTC fields: minute hour day-of-month month day-of-week (0 = Sunday). */
final class Cron implements Trigger {
    private static final int[][] RANGES = {{0, 59}, {0, 23}, {1, 31}, {1, 12}, {0, 6}};
    private final String expr;
    private final BitSet[] fields = new BitSet[5];
    private final boolean anyDay, anyWeekday;

    Cron(String expr) {
        String[] parts = expr.trim().split("\\s+");
        if (parts.length != 5) throw new IllegalArgumentException("cron needs 5 fields: " + expr);
        this.expr = expr;
        for (int i = 0; i < 5; i++) fields[i] = parse(parts[i], RANGES[i][0], RANGES[i][1]);
        anyDay = parts[2].equals("*");
        anyWeekday = parts[4].equals("*");
    }

    private static BitSet parse(String text, int lo, int hi) {
        BitSet out = new BitSet();
        for (String item : text.split(",")) {
            String[] rs = item.split("/", 2);
            int step = rs.length == 2 ? Integer.parseInt(rs[1]) : 1;
            int a, b;
            if (rs[0].equals("*")) { a = lo; b = hi; }
            else if (rs[0].contains("-")) {
                String[] ab = rs[0].split("-", 2);
                a = Integer.parseInt(ab[0]); b = Integer.parseInt(ab[1]);
            } else { a = Integer.parseInt(rs[0]); b = rs.length == 2 ? hi : a; }
            if (step < 1 || a < lo || b > hi || a > b) throw new IllegalArgumentException("bad cron field " + text);
            for (int v = a; v <= b; v += step) out.set(v);
        }
        return out;
    }

    private boolean dayMatches(LocalDateTime d) {
        boolean dom = fields[2].get(d.getDayOfMonth());
        boolean dow = fields[4].get(d.getDayOfWeek().getValue() % 7);
        return anyDay || anyWeekday ? dom && dow : dom || dow; // classic cron: restricted day fields OR together
    }

    private long search(long t, boolean inclusive) {
        LocalDateTime d = LocalDateTime.ofEpochSecond(Math.floorDiv(t, 1000), Math.floorMod(t, 1000) * 1_000_000, ZoneOffset.UTC);
        LocalDateTime m = d.truncatedTo(ChronoUnit.MINUTES);
        if (m.isBefore(d) || !inclusive) m = m.plusMinutes(1);
        LocalDateTime limit = m.plusDays(366 * 5);
        while (m.isBefore(limit)) {
            if (!fields[3].get(m.getMonthValue())) m = m.withDayOfMonth(1).truncatedTo(ChronoUnit.DAYS).plusMonths(1);
            else if (!dayMatches(m)) m = m.truncatedTo(ChronoUnit.DAYS).plusDays(1);
            else if (!fields[1].get(m.getHour())) m = m.truncatedTo(ChronoUnit.HOURS).plusHours(1);
            else if (!fields[0].get(m.getMinute())) m = m.plusMinutes(1);
            else return m.toEpochSecond(ZoneOffset.UTC) * 1000;
        }
        throw new IllegalArgumentException("cron never fires: " + expr);
    }

    public Long first(long now) { return search(now, true); }
    public Long next(long scheduled, long finished) { return search(scheduled, false); }
}

// ---------- Retry policies (Strategy): wait before attempt n+1, or null to give up ----------
interface RetryPolicy {
    Long delay(int attempt, Throwable error);
    RetryPolicy NONE = (attempt, error) -> null;
}

/** Attempt n waits base * 2^(n-1), capped at maxMs, with equal jitter in [cap/2, cap]. */
record ExponentialBackoff(int maxAttempts, long baseMs, long maxMs, DoubleSupplier rand) implements RetryPolicy {
    public Long delay(int attempt, Throwable error) {
        if (attempt >= maxAttempts) return null;
        long cap = Math.min(maxMs, baseMs << Math.min(attempt - 1, 30));
        long half = cap / 2;
        return half + (long) (rand.getAsDouble() * (cap - half));
    }
}

enum Misfire { FIRE_NOW, SKIP, CATCH_UP }

enum JobState {
    SCHEDULED, RUNNING, RETRY_WAIT, COMPLETED, FAILED, CANCELLED, MISFIRED;
    boolean terminal() { return this == COMPLETED || this == FAILED || this == CANCELLED || this == MISFIRED; }
}

enum EventType { SCHEDULED, STARTED, RUN_SUCCEEDED, RUN_FAILED, RETRYING, MISFIRED, COMPLETED, FAILED, CANCELLED }

record JobRun(String jobId, int attempt, long scheduledAt, long startedAt, long finishedAt, String error) {
    boolean ok() { return error == null; }
}

record JobEvent(EventType type, String jobId, String name, JobRun run, Long nextRunAt) {}

record JobInfo(String jobId, String name, JobState state, Long nextRunAt, int runs, JobRun lastRun) {}

record JobOptions(RetryPolicy retry, Misfire misfire) {
    static final JobOptions DEFAULT = new JobOptions(RetryPolicy.NONE, Misfire.FIRE_NOW);
}

final class JobContext {
    final String jobId; final int attempt; final long scheduledAt;
    private final AtomicBoolean cancel;
    JobContext(String jobId, int attempt, long scheduledAt, AtomicBoolean cancel) {
        this.jobId = jobId; this.attempt = attempt; this.scheduledAt = scheduledAt; this.cancel = cancel;
    }
    boolean isCancelled() { return cancel.get(); } // long tasks poll this to stop early
}

@FunctionalInterface interface JobTask { void run(JobContext ctx) throws Exception; } // the Command
@FunctionalInterface interface JobListener { void onEvent(JobEvent event); }        // the Observer

/** Mutable scheduling state. Only touched while holding the scheduler's lock. */
final class Job {
    final String id, name; final JobTask task; final Trigger trigger; final JobOptions options;
    final AtomicBoolean cancelFlag = new AtomicBoolean();
    JobState state = JobState.SCHEDULED;
    long anchor;          // scheduled time of the current occurrence
    int attempt = 1;
    Long nextRunAt;
    Entry entry;          // the one live queue entry, or null
    int runs;
    JobRun lastRun;
    Job(String id, String name, JobTask task, Trigger trigger, JobOptions options) {
        this.id = id; this.name = name; this.task = task; this.trigger = trigger; this.options = options;
    }
}

record Entry(long at, long seq, Job job) {}

final class SchedulerClosedException extends IllegalStateException {
    SchedulerClosedException() { super("scheduler is shut down"); }
}

final class Scheduler {
    static final long MAX_SLEEP_MS = 1000; // re-check at least once a second, so a wall-clock jump can't oversleep
    private final Clock clock;
    private final int workers;
    private final long threshold;
    private final ExecutorService pool;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition changed = lock.newCondition();
    private final PriorityQueue<Entry> heap =
        new PriorityQueue<>(Comparator.comparingLong(Entry::at).thenComparingLong(Entry::seq));
    private final Map<String, Job> jobs = new HashMap<>();
    private final List<JobListener> listeners = new CopyOnWriteArrayList<>();
    private long seq, ids;
    private int busy;
    private boolean accepting = true;
    private Thread dispatcher;

    Scheduler(Clock clock, int workers, long misfireThresholdMs) {
        if (workers < 1) throw new IllegalArgumentException("need at least one worker");
        this.clock = clock; this.workers = workers; this.threshold = misfireThresholdMs;
        AtomicLong n = new AtomicLong();
        this.pool = Executors.newFixedThreadPool(workers, r -> {
            Thread t = new Thread(r, "job-" + n.incrementAndGet());
            t.setDaemon(true);
            return t;
        });
    }

    void addListener(JobListener l) { listeners.add(l); }

    String schedule(String name, JobTask task, Trigger trigger) { return schedule(name, task, trigger, JobOptions.DEFAULT); }

    String schedule(String name, JobTask task, Trigger trigger, JobOptions options) {
        List<JobEvent> events = new ArrayList<>();
        Job job;
        lock.lock();
        try {
            if (!accepting) throw new SchedulerClosedException();
            Long first = trigger.first(clock.now());
            if (first == null) throw new IllegalArgumentException("trigger never fires");
            job = new Job("job-" + (++ids), name, task, trigger, options);
            jobs.put(job.id, job);
            job.anchor = first;
            enqueue(job, first, JobState.SCHEDULED, EventType.SCHEDULED, events);
            changed.signalAll(); // the dispatcher may be asleep waiting for a later job
        } finally { lock.unlock(); }
        emit(events);
        return job.id;
    }

    boolean cancel(String jobId) {
        List<JobEvent> events = new ArrayList<>();
        lock.lock();
        try {
            Job job = jobs.get(jobId);
            if (job == null || job.state.terminal()) return false;
            job.cancelFlag.set(true);
            if (job.state != JobState.RUNNING) { // a running job finishes as CANCELLED when it returns
                job.entry = null;                // the heap entry is now stale and gets skipped
                finish(job, JobState.CANCELLED, EventType.CANCELLED, events);
            }
        } finally { lock.unlock(); }
        emit(events);
        return true;
    }

    JobInfo info(String jobId) {
        lock.lock();
        try {
            Job j = jobs.get(jobId);
            return new JobInfo(j.id, j.name, j.state, j.nextRunAt, j.runs, j.lastRun);
        } finally { lock.unlock(); }
    }

    /** Dispatch everything due now. The dispatcher thread calls this. Tests with a FakeClock call it directly. */
    int runDue() {
        List<JobEvent> events;
        lock.lock();
        try { events = dispatch(clock.now()); } finally { lock.unlock(); }
        emit(events);
        return (int) events.stream().filter(e -> e.type() == EventType.STARTED).count();
    }

    boolean awaitIdle(long timeoutMs) throws InterruptedException {
        lock.lock();
        try { return awaitUntil(() -> busy == 0, timeoutMs); } finally { lock.unlock(); }
    }

    void start() {
        lock.lock();
        try {
            if (dispatcher != null || !accepting) return;
            dispatcher = new Thread(this::loop, "dispatcher");
            dispatcher.setDaemon(true);
            dispatcher.start();
        } finally { lock.unlock(); }
    }

    /** Stop firing, cancel everything queued, let running jobs finish. True if they all did in time. */
    boolean shutdown(long timeoutMs) throws InterruptedException {
        List<JobEvent> events = new ArrayList<>();
        boolean drained;
        lock.lock();
        try {
            accepting = false;
            for (Job job : jobs.values()) {
                if (job.state == JobState.SCHEDULED || job.state == JobState.RETRY_WAIT) {
                    job.entry = null;
                    finish(job, JobState.CANCELLED, EventType.CANCELLED, events);
                }
            }
            heap.clear();
            changed.signalAll();
            drained = awaitUntil(() -> busy == 0, timeoutMs);
            if (!drained) for (Job job : jobs.values()) if (job.state == JobState.RUNNING) job.cancelFlag.set(true);
        } finally { lock.unlock(); }
        if (dispatcher != null) dispatcher.join(timeoutMs);
        if (drained) pool.shutdown(); else pool.shutdownNow(); // shutdownNow interrupts the stragglers
        emit(events);
        return drained;
    }

    // ----- dispatcher internals: everything below runs with the lock held, except execute() -----
    private boolean awaitUntil(BooleanSupplier done, long timeoutMs) throws InterruptedException {
        long nanos = TimeUnit.MILLISECONDS.toNanos(timeoutMs);
        while (!done.getAsBoolean()) {
            if (nanos <= 0) return false;
            nanos = changed.awaitNanos(nanos);
        }
        return true;
    }

    private void loop() {
        while (true) {
            List<JobEvent> events;
            lock.lock();
            try {
                if (!accepting) return;
                events = dispatch(clock.now());
                if (events.isEmpty()) changed.await(sleepMs(), TimeUnit.MILLISECONDS);
            } catch (InterruptedException e) {
                return;
            } finally { lock.unlock(); }
            emit(events);
        }
    }

    private long sleepMs() {
        if (busy >= workers || heap.isEmpty()) return MAX_SLEEP_MS; // a completion or schedule() signals sooner
        return Math.max(0, Math.min(MAX_SLEEP_MS, heap.peek().at() - clock.now()));
    }

    private List<JobEvent> dispatch(long now) {
        List<JobEvent> events = new ArrayList<>();
        while (accepting && busy < workers) {
            Entry e = popRunnable(now);
            if (e == null) break;
            fire(e, now, events);
        }
        return events;
    }

    private Entry popRunnable(long now) {
        while (!heap.isEmpty() && heap.peek().at() <= now) {
            Entry e = heap.poll();
            if (e.job().entry == e) return e; // cancelled or replaced entries are skipped here
        }
        return null;
    }

    private void enqueue(Job job, long at, JobState state, EventType kind, List<JobEvent> events) {
        job.state = state;
        job.nextRunAt = at;
        job.entry = new Entry(at, ++seq, job);
        heap.add(job.entry);
        events.add(new JobEvent(kind, job.id, job.name, job.lastRun, at));
    }

    private void finish(Job job, JobState state, EventType kind, List<JobEvent> events) {
        job.state = state;
        job.nextRunAt = null;
        events.add(new JobEvent(kind, job.id, job.name, job.lastRun, null));
    }

    private Long nextOnTime(Job job, Long t, long now) {
        // Simplification: walks missed occurrences one by one. Fine unless a tiny period meets a long pause.
        while (t != null && now - t > threshold) t = job.trigger.next(t, now);
        return t;
    }

    private void fire(Entry e, long now, List<JobEvent> events) {
        Job job = e.job();
        job.entry = null;
        boolean late = now - e.at() > threshold;
        if (late && job.attempt == 1 && job.options.misfire() == Misfire.SKIP) {
            events.add(new JobEvent(EventType.MISFIRED, job.id, job.name, job.lastRun, null));
            Long next = nextOnTime(job, job.trigger.next(job.anchor, now), now);
            if (next == null) finish(job, JobState.MISFIRED, EventType.MISFIRED, events);
            else { job.anchor = next; enqueue(job, next, JobState.SCHEDULED, EventType.SCHEDULED, events); }
            return;
        }
        job.state = JobState.RUNNING;
        job.nextRunAt = null;
        busy++;
        JobContext ctx = new JobContext(job.id, job.attempt, job.anchor, job.cancelFlag);
        events.add(new JobEvent(EventType.STARTED, job.id, job.name, job.lastRun, null));
        pool.execute(() -> execute(job, ctx, now));
    }

    private void execute(Job job, JobContext ctx, long started) {
        Throwable error = null;
        try {
            job.task.run(ctx); // no lock held: a slow job never blocks scheduling
        } catch (Throwable t) { // any job failure is data. Catching Throwable keeps busy accurate.
            error = t;
        }
        List<JobEvent> events = new ArrayList<>();
        lock.lock();
        try {
            busy--;
            JobRun run = new JobRun(job.id, ctx.attempt, ctx.scheduledAt, started, clock.now(),
                error == null ? null : error.getClass().getSimpleName() + ": " + error.getMessage());
            job.runs++;
            job.lastRun = run;
            events.add(new JobEvent(run.ok() ? EventType.RUN_SUCCEEDED : EventType.RUN_FAILED, job.id, job.name, run, null));
            afterRun(job, run, error, events);
            changed.signalAll(); // a worker is free, and awaitIdle may be waiting
        } finally { lock.unlock(); }
        emit(events);
    }

    private void afterRun(Job job, JobRun run, Throwable error, List<JobEvent> events) {
        if (job.cancelFlag.get()) { finish(job, JobState.CANCELLED, EventType.CANCELLED, events); return; }
        if (error != null) {
            Long delay = job.options.retry().delay(job.attempt, error);
            if (delay != null) {
                if (!accepting) { finish(job, JobState.CANCELLED, EventType.CANCELLED, events); return; }
                job.attempt++;
                enqueue(job, run.finishedAt() + delay, JobState.RETRY_WAIT, EventType.RETRYING, events);
                return;
            }
        }
        job.attempt = 1;
        Long next = job.trigger.next(job.anchor, run.finishedAt());
        if (job.options.misfire() != Misfire.CATCH_UP) next = nextOnTime(job, next, run.finishedAt());
        if (next == null) {
            if (error == null) finish(job, JobState.COMPLETED, EventType.COMPLETED, events);
            else finish(job, JobState.FAILED, EventType.FAILED, events);
        } else if (!accepting) {
            finish(job, JobState.CANCELLED, EventType.CANCELLED, events);
        } else {
            job.anchor = next;
            enqueue(job, next, JobState.SCHEDULED, EventType.SCHEDULED, events);
        }
    }

    private void emit(List<JobEvent> events) {
        for (JobEvent e : events)
            for (JobListener l : listeners) {
                try { l.onEvent(e); } catch (RuntimeException ignored) { } // a broken listener can't break scheduling
            }
    }
}

// ---------- self-check: javac Scheduler.java && java SchedulerDemo ----------
final class SchedulerDemo {
    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    static long utc(int y, int mo, int d, int h, int mi) { return LocalDateTime.of(y, mo, d, h, mi).toEpochSecond(ZoneOffset.UTC) * 1000; }

    public static void main(String[] args) throws Exception {
        // One-off, fixed rate and fixed delay with a fake clock. The tasks "take" 300 ms by advancing it.
        FakeClock fc = new FakeClock(0);
        Scheduler s = new Scheduler(fc, 2, 100);
        List<JobEvent> events = new CopyOnWriteArrayList<>();
        s.addListener(events::add);
        String once = s.schedule("once", ctx -> { }, Once.at(1000));
        String rate = s.schedule("rate", ctx -> fc.advance(300), new FixedRate(1000));
        s.runDue(); s.awaitIdle(2000);
        check(s.info(rate).nextRunAt() == 1000, "fixed rate counts from scheduled time");
        String delay = s.schedule("delay", ctx -> fc.advance(300), new FixedDelay(1000));
        s.runDue(); s.awaitIdle(2000);
        check(s.info(delay).nextRunAt() == 600 + 1000, "fixed delay counts from finish time");
        fc.advance(400); // t = 1000
        check(s.runDue() == 2, "once and rate both due at 1000");
        s.awaitIdle(2000);
        check(s.info(once).state() == JobState.COMPLETED, "one-off completes");
        check(s.cancel(rate) && s.cancel(delay) && !s.cancel(once), "cancel scheduled jobs, not finished ones");
        check(s.shutdown(1000), "clean shutdown");

        // Retries: exponential backoff with jitter pinned to 1.0 for determinism.
        FakeClock clock = new FakeClock(0);
        s = new Scheduler(clock, 2, 100);
        List<Integer> attempts = new CopyOnWriteArrayList<>();
        String flaky = s.schedule("flaky", ctx -> {
            attempts.add(ctx.attempt);
            if (ctx.attempt < 3) throw new java.io.IOException("smtp down");
        }, Once.after(0), new JobOptions(new ExponentialBackoff(3, 100, 10_000, () -> 1.0), Misfire.FIRE_NOW));
        s.runDue(); s.awaitIdle(2000);
        check(s.info(flaky).state() == JobState.RETRY_WAIT && s.info(flaky).nextRunAt() == 100, "first retry after 100");
        clock.advance(100); s.runDue(); s.awaitIdle(2000);
        check(s.info(flaky).nextRunAt() == 300, "second retry after 200 more");
        clock.advance(200); s.runDue(); s.awaitIdle(2000);
        check(attempts.equals(List.of(1, 2, 3)) && s.info(flaky).state() == JobState.COMPLETED, "succeeds on attempt 3");
        ExponentialBackoff b = new ExponentialBackoff(10, 100, 1000, () -> 0.0);
        check(b.delay(1, null) == 50 && b.delay(5, null) == 500 && b.delay(10, null) == null, "jitter floor and cap");
        String dead = s.schedule("dead", ctx -> { throw new IllegalStateException("bad payload"); }, Once.after(0));
        s.runDue(); s.awaitIdle(2000);
        check(s.info(dead).state() == JobState.FAILED && s.info(dead).lastRun().error().contains("bad payload"), "gives up");
        s.shutdown(1000);

        // Misfire policies after a 5.5 s stall, fixed rate of 1 s starting at 1 s.
        for (Misfire policy : Misfire.values()) {
            FakeClock c = new FakeClock(0);
            Scheduler m = new Scheduler(c, 1, 100);
            List<Long> runs = new CopyOnWriteArrayList<>();
            String id = m.schedule("rate", ctx -> runs.add(ctx.scheduledAt), new FixedRate(1000, 1000), new JobOptions(RetryPolicy.NONE, policy));
            c.advance(5500);
            for (int i = 0; i < 10; i++) { m.runDue(); m.awaitIdle(2000); }
            List<Long> expected = switch (policy) {
                case FIRE_NOW -> List.of(1000L);
                case SKIP -> List.of();
                case CATCH_UP -> List.of(1000L, 2000L, 3000L, 4000L, 5000L);
            };
            check(runs.equals(expected), policy + " ran " + runs);
            check(m.info(id).nextRunAt() == 6000, policy + " next is 6000");
            m.shutdown(1000);
        }

        // No double execution, and the pool bounds concurrency.
        clock = new FakeClock(0);
        s = new Scheduler(clock, 2, 100);
        CountDownLatch release = new CountDownLatch(1);
        List<String> started = new CopyOnWriteArrayList<>();
        s.addListener(e -> { if (e.type() == EventType.STARTED) started.add(e.name()); });
        s.schedule("long", ctx -> release.await(2, TimeUnit.SECONDS), new FixedRate(100));
        for (String n : List.of("a", "b", "c")) s.schedule(n, ctx -> release.await(2, TimeUnit.SECONDS), Once.at(1));
        clock.advance(500);
        check(s.runDue() == 2 && s.runDue() == 0, "two workers: long and a start, b and c wait in the queue");
        release.countDown();
        for (int i = 0; i < 6; i++) { s.awaitIdle(2000); s.runDue(); }
        s.awaitIdle(2000);
        // long ran once at a time: its missed 100..300 were coalesced into 400, then 500 came due.
        check(started.equals(List.of("long", "a", "b", "c", "long", "long")), "order " + started);
        s.shutdown(1000);

        // Cancel a running job: it sees the flag and is not rescheduled.
        clock = new FakeClock(0);
        s = new Scheduler(clock, 1, 100);
        CountDownLatch inside = new CountDownLatch(1), go = new CountDownLatch(1);
        AtomicBoolean sawCancel = new AtomicBoolean();
        String longJob = s.schedule("long", ctx -> { inside.countDown(); go.await(); sawCancel.set(ctx.isCancelled()); }, new FixedRate(100));
        s.runDue();
        inside.await();
        check(s.cancel(longJob) && s.info(longJob).state() == JobState.RUNNING, "still running after cancel");
        go.countDown();
        s.awaitIdle(2000);
        check(sawCancel.get() && s.info(longJob).state() == JobState.CANCELLED, "finishes as cancelled");
        s.shutdown(1000);

        // Cron.
        Cron cron = new Cron("*/15 9-17 * * 1-5");
        check(cron.first(utc(2026, 11, 13, 17, 50)) == utc(2026, 11, 16, 9, 0), "Friday evening rolls to Monday 9:00");
        check(cron.next(utc(2026, 11, 16, 9, 0), 0) == utc(2026, 11, 16, 9, 15), "next quarter hour");
        check(new Cron("0 0 1 * 0").first(utc(2026, 11, 2, 0, 0)) == utc(2026, 11, 8, 0, 0), "day fields OR together");

        // Shutdown waits for running jobs and refuses new ones.
        s = new Scheduler(new FakeClock(0), 1, 100);
        AtomicBoolean finished = new AtomicBoolean();
        s.schedule("slow", ctx -> { Thread.sleep(100); finished.set(true); }, Once.after(0));
        String queued = s.schedule("later", ctx -> { }, Once.after(10_000));
        s.runDue();
        check(s.shutdown(2000) && finished.get(), "drains running work");
        check(s.info(queued).state() == JobState.CANCELLED, "queued work is cancelled");
        try { s.schedule("x", ctx -> { }, Once.after(0)); check(false, "should refuse"); } catch (SchedulerClosedException ok) { }

        // Real clock: an earlier job wakes the sleeping dispatcher.
        Scheduler real = new Scheduler(new SystemClock(), 2, 1000);
        real.start();
        CountDownLatch soon = new CountDownLatch(1);
        real.schedule("far", ctx -> { }, Once.after(3_600_000));
        Thread.sleep(50);
        long t0 = System.nanoTime();
        real.schedule("soon", ctx -> soon.countDown(), Once.after(20));
        check(soon.await(2, TimeUnit.SECONDS), "soon ran");
        check(System.nanoTime() - t0 < 500_000_000L, "woken early, not after the 1 s nap");
        check(real.shutdown(1000), "real shutdown");
        System.out.println("scheduler self-check passed");
    }
}
"""In-process task scheduler: one-off, delayed, fixed-rate, fixed-delay and cron jobs.

Run the self-check with: python scheduler.py
"""
from __future__ import annotations

import heapq
import itertools
import random
import threading
import time
from concurrent.futures import ThreadPoolExecutor
from dataclasses import dataclass, field
from datetime import datetime, timedelta, timezone
from enum import Enum
from typing import Callable, Optional, Protocol

MAX_SLEEP_MS = 1000  # re-check at least once a second, so a wall-clock jump can't oversleep a job


# ---------- Clock: the one source of "now", injectable for tests ----------
class Clock(Protocol):
    def now(self) -> int: ...  # epoch milliseconds


class SystemClock:
    def now(self) -> int:
        return time.time_ns() // 1_000_000


class FakeClock:
    """Time only moves when a test says so."""

    def __init__(self, start: int = 0) -> None:
        self._t = start
        self._lock = threading.Lock()

    def now(self) -> int:
        with self._lock:
            return self._t

    def advance(self, ms: int) -> None:
        with self._lock:
            self._t += ms


# ---------- Triggers (Strategy): when does a job fire next? ----------
class Trigger(Protocol):
    def first(self, now: int) -> Optional[int]: ...
    def next(self, scheduled: int, finished: int) -> Optional[int]: ...


@dataclass(frozen=True)
class Once:
    at: Optional[int] = None
    delay: int = 0

    def first(self, now: int) -> Optional[int]:
        return self.at if self.at is not None else now + self.delay

    def next(self, scheduled: int, finished: int) -> Optional[int]:
        return None


def at(epoch_ms: int) -> Once:
    return Once(at=epoch_ms)


def after(delay_ms: int) -> Once:
    return Once(delay=delay_ms)


@dataclass(frozen=True)
class FixedRate:
    """Fires every `period` ms measured from the previous *scheduled* time."""
    period: int
    initial_delay: int = 0

    def __post_init__(self) -> None:
        if self.period <= 0:
            raise ValueError("period must be positive")

    def first(self, now: int) -> Optional[int]:
        return now + self.initial_delay

    def next(self, scheduled: int, finished: int) -> Optional[int]:
        return scheduled + self.period


@dataclass(frozen=True)
class FixedDelay:
    """Fires `delay` ms after the previous run *finished*."""
    delay: int
    initial_delay: int = 0

    def __post_init__(self) -> None:
        if self.delay < 0:
            raise ValueError("delay must not be negative")

    def first(self, now: int) -> Optional[int]:
        return now + self.initial_delay

    def next(self, scheduled: int, finished: int) -> Optional[int]:
        return finished + self.delay


class Cron:
    """Five UTC fields: minute hour day-of-month month day-of-week (0 = Sunday).
    Each field accepts *, n, a-b, */s, a-b/s, n/s and comma lists."""

    RANGES = ((0, 59), (0, 23), (1, 31), (1, 12), (0, 6))

    def __init__(self, expr: str) -> None:
        parts = expr.split()
        if len(parts) != 5:
            raise ValueError(f"cron needs 5 fields: {expr!r}")
        self.expr = expr
        self.minutes, self.hours, self.days, self.months, self.weekdays = (
            self._parse(p, lo, hi) for p, (lo, hi) in zip(parts, self.RANGES))
        self.any_day, self.any_weekday = parts[2] == "*", parts[4] == "*"

    @staticmethod
    def _parse(text: str, lo: int, hi: int) -> frozenset[int]:
        out: set[int] = set()
        for item in text.split(","):
            rng, slash, step_text = item.partition("/")
            step = int(step_text) if slash else 1
            if rng == "*":
                a, b = lo, hi
            elif "-" in rng:
                a, b = (int(x) for x in rng.split("-", 1))
            else:
                a = int(rng)
                b = hi if slash else a
            if step < 1 or not lo <= a <= b <= hi:
                raise ValueError(f"bad cron field {text!r}")
            out.update(range(a, b + 1, step))
        return frozenset(out)

    def _day_matches(self, d: datetime) -> bool:
        dom = d.day in self.days
        dow = d.isoweekday() % 7 in self.weekdays
        # Classic cron rule: if both day fields are restricted, either one may match.
        return dom or dow if not (self.any_day or self.any_weekday) else dom and dow

    def _search(self, t_ms: int, inclusive: bool) -> int:
        d = datetime.fromtimestamp(t_ms / 1000, tz=timezone.utc)
        m = d.replace(second=0, microsecond=0)
        if m < d or not inclusive:
            m += timedelta(minutes=1)
        limit = m + timedelta(days=366 * 5)
        while m < limit:  # skips whole months, days and hours, so this is a few hundred steps at most
            if m.month not in self.months:
                m = (m.replace(day=1, hour=0, minute=0) + timedelta(days=32)).replace(day=1)
            elif not self._day_matches(m):
                m = m.replace(hour=0, minute=0) + timedelta(days=1)
            elif m.hour not in self.hours:
                m = m.replace(minute=0) + timedelta(hours=1)
            elif m.minute not in self.minutes:
                m += timedelta(minutes=1)
            else:
                return int(m.timestamp()) * 1000
        raise ValueError(f"cron {self.expr!r} never fires")

    def first(self, now: int) -> Optional[int]:
        return self._search(now, inclusive=True)

    def next(self, scheduled: int, finished: int) -> Optional[int]:
        return self._search(scheduled, inclusive=False)


# ---------- Retry policies (Strategy): how long to wait before attempt n+1? ----------
class RetryPolicy(Protocol):
    def delay(self, attempt: int, error: BaseException) -> Optional[int]: ...  # None = give up


class NoRetry:
    def delay(self, attempt: int, error: BaseException) -> Optional[int]:
        return None


@dataclass(frozen=True)
class ExponentialBackoff:
    """Attempt n waits base * 2^(n-1), capped at max_ms, with equal jitter in [cap/2, cap]."""
    max_attempts: int = 3
    base_ms: int = 1000
    max_ms: int = 60_000
    rand: Callable[[], float] = random.random

    def delay(self, attempt: int, error: BaseException) -> Optional[int]:
        if attempt >= self.max_attempts:
            return None
        cap = min(self.max_ms, self.base_ms * 2 ** (attempt - 1))
        half = cap // 2
        return half + int(self.rand() * (cap - half))


class Misfire(Enum):
    FIRE_NOW = "fire_now"  # run the late occurrence once, coalesce any others that were missed
    SKIP = "skip"          # drop late occurrences and wait for the next on-time one
    CATCH_UP = "catch_up"  # run every missed occurrence, back to back


class JobState(Enum):
    SCHEDULED = "scheduled"
    RUNNING = "running"
    RETRY_WAIT = "retry_wait"
    COMPLETED = "completed"
    FAILED = "failed"
    CANCELLED = "cancelled"
    MISFIRED = "misfired"


TERMINAL = {JobState.COMPLETED, JobState.FAILED, JobState.CANCELLED, JobState.MISFIRED}


class EventType(Enum):
    SCHEDULED = "scheduled"
    STARTED = "started"
    RUN_SUCCEEDED = "run_succeeded"
    RUN_FAILED = "run_failed"
    RETRYING = "retrying"
    MISFIRED = "misfired"
    COMPLETED = "completed"
    FAILED = "failed"
    CANCELLED = "cancelled"


@dataclass(frozen=True)
class JobRun:
    job_id: str
    attempt: int
    scheduled_at: int
    started_at: int
    finished_at: int
    error: Optional[str] = None

    @property
    def ok(self) -> bool:
        return self.error is None


@dataclass(frozen=True)
class JobEvent:
    type: EventType
    job_id: str
    name: str
    run: Optional[JobRun] = None
    next_run_at: Optional[int] = None


@dataclass(frozen=True)
class JobInfo:
    job_id: str
    name: str
    state: JobState
    next_run_at: Optional[int]
    runs: int
    last_run: Optional[JobRun]


@dataclass(frozen=True)
class JobContext:
    job_id: str
    attempt: int
    scheduled_at: int
    _cancel: threading.Event

    @property
    def cancelled(self) -> bool:  # long tasks poll this to stop early
        return self._cancel.is_set()


Task = Callable[[JobContext], None]  # the Command
Listener = Callable[[JobEvent], None]  # the Observer


@dataclass(frozen=True)
class JobOptions:
    retry: RetryPolicy = field(default_factory=NoRetry)
    misfire: Misfire = Misfire.FIRE_NOW


class Job:
    """Mutable scheduling state. Only touched while holding the scheduler's lock."""

    def __init__(self, job_id: str, name: str, task: Task, trigger: Trigger, options: JobOptions) -> None:
        self.id, self.name, self.task, self.trigger, self.options = job_id, name, task, trigger, options
        self.state = JobState.SCHEDULED
        self.anchor = 0                     # scheduled time of the current occurrence
        self.attempt = 1
        self.next_run_at: Optional[int] = None
        self.entry: Optional[_Entry] = None  # the one live queue entry, or None
        self.cancel_flag = threading.Event()
        self.runs = 0
        self.last_run: Optional[JobRun] = None


@dataclass(order=True)
class _Entry:
    at: int
    seq: int
    job: Job = field(compare=False)


class SchedulerClosed(RuntimeError):
    pass


class Scheduler:
    def __init__(self, clock: Optional[Clock] = None, workers: int = 4, misfire_threshold_ms: int = 1000) -> None:
        if workers < 1:
            raise ValueError("need at least one worker")
        self._clock = clock or SystemClock()
        self._workers = workers
        self._pool = ThreadPoolExecutor(max_workers=workers, thread_name_prefix="job")
        self._threshold = misfire_threshold_ms
        self._cond = threading.Condition()
        self._heap: list[_Entry] = []
        self._seq = itertools.count(1)  # FIFO tie-break for entries due at the same millisecond
        self._ids = itertools.count(1)
        self._jobs: dict[str, Job] = {}
        self._busy = 0
        self._listeners: list[Listener] = []
        self._accepting = True
        self._thread: Optional[threading.Thread] = None

    # ----- public API -----
    def add_listener(self, listener: Listener) -> None:
        with self._cond:
            self._listeners.append(listener)

    def schedule(self, name: str, task: Task, trigger: Trigger, options: Optional[JobOptions] = None) -> str:
        events: list[JobEvent] = []
        with self._cond:
            if not self._accepting:
                raise SchedulerClosed("scheduler is shut down")
            first = trigger.first(self._clock.now())
            if first is None:
                raise ValueError("trigger never fires")
            job = Job(f"job-{next(self._ids)}", name, task, trigger, options or JobOptions())
            self._jobs[job.id] = job
            job.anchor = first
            self._enqueue(job, first, JobState.SCHEDULED, EventType.SCHEDULED, events)
            self._cond.notify_all()  # the dispatcher may be asleep waiting for a later job
        self._emit(events)
        return job.id

    def cancel(self, job_id: str) -> bool:
        events: list[JobEvent] = []
        with self._cond:
            job = self._jobs.get(job_id)
            if job is None or job.state in TERMINAL:
                return False
            job.cancel_flag.set()
            if job.state is not JobState.RUNNING:  # a running job finishes as CANCELLED when it returns
                job.entry, job.next_run_at = None, None  # the heap entry is now stale and gets skipped
                self._finish(job, JobState.CANCELLED, EventType.CANCELLED, events)
        self._emit(events)
        return True

    def info(self, job_id: str) -> JobInfo:
        with self._cond:
            j = self._jobs[job_id]
            return JobInfo(j.id, j.name, j.state, j.next_run_at, j.runs, j.last_run)

    def run_due(self) -> int:
        """Dispatch everything due at clock.now(). The dispatcher thread calls this in a loop.
        Tests with a FakeClock call it directly instead of starting the thread."""
        with self._cond:
            events = self._dispatch(self._clock.now())
        self._emit(events)
        return sum(e.type is EventType.STARTED for e in events)

    def await_idle(self, timeout_s: float = 5.0) -> bool:
        with self._cond:
            return self._cond.wait_for(lambda: self._busy == 0, timeout_s)

    def start(self) -> None:
        with self._cond:
            if self._thread is None and self._accepting:
                self._thread = threading.Thread(target=self._loop, name="dispatcher", daemon=True)
                self._thread.start()

    def shutdown(self, timeout_s: float = 5.0) -> bool:
        """Stop firing, cancel everything queued, let running jobs finish. True if they all did."""
        events: list[JobEvent] = []
        with self._cond:
            self._accepting = False
            for job in self._jobs.values():
                if job.state in (JobState.SCHEDULED, JobState.RETRY_WAIT):
                    job.entry, job.next_run_at = None, None
                    self._finish(job, JobState.CANCELLED, EventType.CANCELLED, events)
            self._heap.clear()
            self._cond.notify_all()
            drained = self._cond.wait_for(lambda: self._busy == 0, timeout_s)
            if not drained:  # ask stragglers to stop. Python can't kill a thread.
                for job in self._jobs.values():
                    if job.state is JobState.RUNNING:
                        job.cancel_flag.set()
        if self._thread is not None:
            self._thread.join(timeout_s)
        self._pool.shutdown(wait=drained)
        self._emit(events)
        return drained

    # ----- dispatcher internals (all called with the lock held) -----
    def _loop(self) -> None:
        while True:
            with self._cond:
                if not self._accepting:
                    return
                events = self._dispatch(self._clock.now())
                if not events:
                    self._cond.wait(self._sleep_ms() / 1000)
            self._emit(events)

    def _sleep_ms(self) -> int:
        if self._busy >= self._workers or not self._heap:
            return MAX_SLEEP_MS  # a completion or a schedule() call will notify us sooner
        return max(0, min(MAX_SLEEP_MS, self._heap[0].at - self._clock.now()))

    def _dispatch(self, now: int) -> list[JobEvent]:
        events: list[JobEvent] = []
        while self._accepting and self._busy < self._workers:
            entry = self._pop_runnable(now)
            if entry is None:
                break
            self._fire(entry, now, events)
        return events

    def _pop_runnable(self, now: int) -> Optional[_Entry]:
        """Next due, still-live entry. Extensions override this to change the order."""
        while self._heap and self._heap[0].at <= now:
            entry = heapq.heappop(self._heap)
            if entry.job.entry is entry:  # cancelled or replaced entries are skipped here
                return entry
        return None

    def _enqueue(self, job: Job, at_ms: int, state: JobState, kind: EventType, events: list[JobEvent]) -> None:
        job.state, job.next_run_at = state, at_ms
        job.entry = _Entry(at_ms, next(self._seq), job)
        heapq.heappush(self._heap, job.entry)
        events.append(JobEvent(kind, job.id, job.name, job.last_run, at_ms))

    def _finish(self, job: Job, state: JobState, kind: EventType, events: list[JobEvent]) -> None:
        job.state, job.next_run_at = state, None
        events.append(JobEvent(kind, job.id, job.name, job.last_run))

    def _next_on_time(self, job: Job, t: Optional[int], now: int) -> Optional[int]:
        # Simplification: walks missed occurrences one by one. Fine unless a tiny period meets a long pause.
        while t is not None and now - t > self._threshold:
            t = job.trigger.next(t, now)
        return t

    def _fire(self, entry: _Entry, now: int, events: list[JobEvent]) -> None:
        job = entry.job
        job.entry = None
        late = now - entry.at > self._threshold
        if late and job.attempt == 1 and job.options.misfire is Misfire.SKIP:
            events.append(JobEvent(EventType.MISFIRED, job.id, job.name, job.last_run))
            nxt = self._next_on_time(job, job.trigger.next(job.anchor, now), now)
            if nxt is None:
                self._finish(job, JobState.MISFIRED, EventType.MISFIRED, events)
            else:
                job.anchor = nxt
                self._enqueue(job, nxt, JobState.SCHEDULED, EventType.SCHEDULED, events)
            return
        job.state, job.next_run_at = JobState.RUNNING, None
        self._busy += 1
        ctx = JobContext(job.id, job.attempt, job.anchor, job.cancel_flag)
        events.append(JobEvent(EventType.STARTED, job.id, job.name, job.last_run))
        self._pool.submit(self._execute, job, ctx, now)

    def _execute(self, job: Job, ctx: JobContext, started: int) -> None:
        error: Optional[BaseException] = None
        try:
            job.task(ctx)  # no lock held: a slow job never blocks scheduling
        except Exception as exc:  # noqa: BLE001 - any job failure is data, not a crash
            error = exc
        events: list[JobEvent] = []
        with self._cond:
            self._busy -= 1
            run = JobRun(job.id, ctx.attempt, ctx.scheduled_at, started, self._clock.now(),
                         None if error is None else f"{type(error).__name__}: {error}")
            job.runs += 1
            job.last_run = run
            events.append(JobEvent(EventType.RUN_SUCCEEDED if run.ok else EventType.RUN_FAILED,
                                   job.id, job.name, run))
            self._after_run(job, run, error, events)
            self._cond.notify_all()  # a worker is free, and await_idle may be waiting
        self._emit(events)

    def _after_run(self, job: Job, run: JobRun, error: Optional[BaseException], events: list[JobEvent]) -> None:
        if job.cancel_flag.is_set():
            self._finish(job, JobState.CANCELLED, EventType.CANCELLED, events)
            return
        if error is not None:
            delay = job.options.retry.delay(job.attempt, error)
            if delay is not None:
                if not self._accepting:  # shutting down: no new attempts
                    self._finish(job, JobState.CANCELLED, EventType.CANCELLED, events)
                    return
                job.attempt += 1
                self._enqueue(job, run.finished_at + delay, JobState.RETRY_WAIT, EventType.RETRYING, events)
                return
        job.attempt = 1
        nxt = job.trigger.next(job.anchor, run.finished_at)
        if job.options.misfire is not Misfire.CATCH_UP:
            nxt = self._next_on_time(job, nxt, run.finished_at)
        if nxt is None:
            if error is None:
                self._finish(job, JobState.COMPLETED, EventType.COMPLETED, events)
            else:
                self._finish(job, JobState.FAILED, EventType.FAILED, events)
        elif not self._accepting:  # shutting down: no next occurrence
            self._finish(job, JobState.CANCELLED, EventType.CANCELLED, events)
        else:
            job.anchor = nxt
            self._enqueue(job, nxt, JobState.SCHEDULED, EventType.SCHEDULED, events)

    def _emit(self, events: list[JobEvent]) -> None:
        if not events:
            return
        with self._cond:
            listeners = list(self._listeners)
        for event in events:
            for listener in listeners:
                try:
                    listener(event)
                except Exception:  # noqa: BLE001 - a broken listener must not break scheduling
                    pass


# ---------- self-check ----------
def _wait_for(pred: Callable[[], bool], timeout_s: float = 3.0) -> bool:
    deadline = time.monotonic() + timeout_s
    while time.monotonic() < deadline:
        if pred():
            return True
        time.sleep(0.005)
    return pred()


def main() -> None:
    # 1. Deterministic: fake clock, run_due() driven by hand.
    clock = FakeClock(0)
    s = Scheduler(clock, workers=2, misfire_threshold_ms=100)
    seen: list[tuple[str, int]] = []
    report = s.schedule("report", lambda c: seen.append(("report", clock.now())), FixedRate(1000))
    flaky_calls = []

    def flaky(ctx: JobContext) -> None:
        flaky_calls.append(ctx.attempt)
        if ctx.attempt < 3:
            raise ConnectionError("smtp down")

    email = s.schedule("email", flaky, after(500),
                       JobOptions(retry=ExponentialBackoff(max_attempts=5, base_ms=200, rand=lambda: 0.0)))
    assert s.run_due() == 1 and s.await_idle()  # report at t=0
    clock.advance(500)
    assert s.run_due() == 1 and s.await_idle()  # email attempt 1 fails
    assert s.info(email).state is JobState.RETRY_WAIT and s.info(email).next_run_at == 600
    clock.advance(100)
    s.run_due(); s.await_idle()                 # attempt 2 fails, waits 200
    assert s.info(email).next_run_at == 800
    clock.advance(400)                          # t=1000: email attempt 3 and report both due
    assert s.run_due() == 2 and s.await_idle()
    assert flaky_calls == [1, 2, 3] and s.info(email).state is JobState.COMPLETED
    assert seen == [("report", 0), ("report", 1000)]
    assert s.cancel(report) and s.info(report).state is JobState.CANCELLED
    clock.advance(5000)
    assert s.run_due() == 0
    assert s.shutdown(1)

    # 2. Real clock: the dispatcher thread wakes early when an earlier job arrives.
    s = Scheduler(workers=2)
    s.start()
    hits: list[str] = []
    s.schedule("later", lambda c: hits.append("later"), after(60_000))
    s.schedule("soon", lambda c: hits.append("soon"), after(30))
    assert _wait_for(lambda: hits == ["soon"]), hits
    assert s.shutdown(1)
    assert Cron("0 9 * * 1").first(0) == 4 * 86_400_000 + 9 * 3_600_000  # 1970-01-01 was a Thursday
    print("scheduler self-check passed")


if __name__ == "__main__":
    main()
// In-process task scheduler. Run: npx tsx scheduler.ts
// Typecheck: npx tsc --strict --noEmit --target es2022 --lib es2022,dom scheduler.ts

const MAX_SLEEP_MS = 1000; // re-check at least once a second, so a wall-clock jump can't oversleep a job

// ---------- Clock: the one source of "now", injectable for tests ----------
export interface Clock { now(): number } // epoch milliseconds

export class SystemClock implements Clock {
  now(): number { return Date.now(); }
}

export class FakeClock implements Clock {
  constructor(private t = 0) {}
  now(): number { return this.t; }
  advance(ms: number): void { this.t += ms; }
}

// ---------- Triggers (Strategy): when does a job fire next? null means never ----------
export interface Trigger {
  first(now: number): number | null;
  next(scheduled: number, finished: number): number | null;
}

export class Once implements Trigger {
  private constructor(private readonly at: number | null, private readonly delay: number) {}
  static at(epochMs: number): Once { return new Once(epochMs, 0); }
  static after(delayMs: number): Once { return new Once(null, delayMs); }
  first(now: number): number { return this.at ?? now + this.delay; }
  next(): null { return null; }
}

/** Every `period` ms, measured from the previous scheduled time. */
export class FixedRate implements Trigger {
  constructor(readonly period: number, readonly initialDelay = 0) {
    if (period <= 0) throw new RangeError("period must be positive");
  }
  first(now: number): number { return now + this.initialDelay; }
  next(scheduled: number): number { return scheduled + this.period; }
}

/** `delay` ms after the previous run finished. */
export class FixedDelay implements Trigger {
  constructor(readonly delay: number, readonly initialDelay = 0) {
    if (delay < 0) throw new RangeError("delay must not be negative");
  }
  first(now: number): number { return now + this.initialDelay; }
  next(_scheduled: number, finished: number): number { return finished + this.delay; }
}

/** Five UTC fields: minute hour day-of-month month day-of-week (0 = Sunday). */
export class Cron implements Trigger {
  private static readonly RANGES: [number, number][] = [[0, 59], [0, 23], [1, 31], [1, 12], [0, 6]];
  private readonly fields: Set<number>[];
  private readonly anyDay: boolean;
  private readonly anyWeekday: boolean;

  constructor(readonly expr: string) {
    const parts = expr.trim().split(/\s+/);
    if (parts.length !== 5) throw new RangeError(`cron needs 5 fields: ${expr}`);
    this.fields = parts.map((p, i) => Cron.parse(p, ...Cron.RANGES[i]));
    this.anyDay = parts[2] === "*";
    this.anyWeekday = parts[4] === "*";
  }

  private static parse(text: string, lo: number, hi: number): Set<number> {
    const out = new Set<number>();
    for (const item of text.split(",")) {
      const [rng, stepText] = item.split("/", 2);
      const step = stepText === undefined ? 1 : Number(stepText);
      let a: number, b: number;
      if (rng === "*") [a, b] = [lo, hi];
      else if (rng.includes("-")) [a, b] = rng.split("-", 2).map(Number);
      else { a = Number(rng); b = stepText === undefined ? a : hi; }
      if (!Number.isInteger(a) || !Number.isInteger(b) || !Number.isInteger(step) || step < 1 || a < lo || b > hi || a > b) {
        throw new RangeError(`bad cron field ${text}`);
      }
      for (let v = a; v <= b; v += step) out.add(v);
    }
    return out;
  }

  private dayMatches(d: Date): boolean {
    const dom = this.fields[2].has(d.getUTCDate());
    const dow = this.fields[4].has(d.getUTCDay());
    return this.anyDay || this.anyWeekday ? dom && dow : dom || dow; // classic cron: restricted day fields OR together
  }

  private search(t: number, inclusive: boolean): number {
    let m = Math.floor(t / 60_000) * 60_000;
    if (m < t || !inclusive) m += 60_000;
    const limit = m + 366 * 5 * 86_400_000;
    while (m < limit) {
      const d = new Date(m);
      const [y, mo, day, h] = [d.getUTCFullYear(), d.getUTCMonth(), d.getUTCDate(), d.getUTCHours()];
      if (!this.fields[3].has(mo + 1)) m = Date.UTC(y, mo + 1, 1);
      else if (!this.dayMatches(d)) m = Date.UTC(y, mo, day + 1);
      else if (!this.fields[1].has(h)) m = Date.UTC(y, mo, day, h + 1);
      else if (!this.fields[0].has(d.getUTCMinutes())) m += 60_000;
      else return m;
    }
    throw new RangeError(`cron never fires: ${this.expr}`);
  }

  first(now: number): number { return this.search(now, true); }
  next(scheduled: number): number { return this.search(scheduled, false); }
}

// ---------- Retry policies (Strategy): wait before attempt n+1, or null to give up ----------
export interface RetryPolicy { delay(attempt: number, error: unknown): number | null }

export const NO_RETRY: RetryPolicy = { delay: () => null };

/** Attempt n waits base * 2^(n-1), capped at maxMs, with equal jitter in [cap/2, cap]. */
export class ExponentialBackoff implements RetryPolicy {
  constructor(readonly maxAttempts = 3, readonly baseMs = 1000, readonly maxMs = 60_000,
              private readonly rand: () => number = Math.random) {}
  delay(attempt: number): number | null {
    if (attempt >= this.maxAttempts) return null;
    const cap = Math.min(this.maxMs, this.baseMs * 2 ** (attempt - 1));
    const half = Math.floor(cap / 2);
    return half + Math.floor(this.rand() * (cap - half));
  }
}

export type Misfire = "FIRE_NOW" | "SKIP" | "CATCH_UP";
export type JobState = "SCHEDULED" | "RUNNING" | "RETRY_WAIT" | "COMPLETED" | "FAILED" | "CANCELLED" | "MISFIRED";
export type EventType = "SCHEDULED" | "STARTED" | "RUN_SUCCEEDED" | "RUN_FAILED" | "RETRYING"
  | "MISFIRED" | "COMPLETED" | "FAILED" | "CANCELLED";
const TERMINAL: ReadonlySet<JobState> = new Set<JobState>(["COMPLETED", "FAILED", "CANCELLED", "MISFIRED"]);

export interface JobRun {
  readonly jobId: string; readonly attempt: number; readonly scheduledAt: number;
  readonly startedAt: number; readonly finishedAt: number; readonly error: string | null;
}
export interface JobEvent {
  readonly type: EventType; readonly jobId: string; readonly name: string;
  readonly run: JobRun | null; readonly nextRunAt: number | null;
}
export interface JobInfo {
  readonly jobId: string; readonly name: string; readonly state: JobState;
  readonly nextRunAt: number | null; readonly runs: number; readonly lastRun: JobRun | null;
}
export interface JobContext {
  readonly jobId: string; readonly attempt: number; readonly scheduledAt: number;
  readonly signal: AbortSignal; // long tasks check signal.aborted, or pass it to fetch()
}
export type Task = (ctx: JobContext) => void | Promise<void>; // the Command
export type Listener = (event: JobEvent) => void;             // the Observer
export interface JobOptions { retry?: RetryPolicy; misfire?: Misfire }

interface Entry { at: number; seq: number; job: Job }

/** Mutable scheduling state, owned by the Scheduler. */
class Job {
  state: JobState = "SCHEDULED";
  anchor = 0;           // scheduled time of the current occurrence
  attempt = 1;
  nextRunAt: number | null = null;
  entry: Entry | null = null; // the one live queue entry, or null
  cancel = new AbortController();
  runs = 0;
  lastRun: JobRun | null = null;
  readonly retry: RetryPolicy;
  readonly misfire: Misfire;
  constructor(readonly id: string, readonly name: string, readonly task: Task, readonly trigger: Trigger,
              options: JobOptions) {
    this.retry = options.retry ?? NO_RETRY;
    this.misfire = options.misfire ?? "FIRE_NOW";
  }
}

/** Binary min-heap. The standard library doesn't have one. */
class MinHeap<T> {
  private items: T[] = [];
  constructor(private readonly less: (a: T, b: T) => boolean) {}
  get size(): number { return this.items.length; }
  peek(): T | undefined { return this.items[0]; }
  clear(): void { this.items = []; }
  push(x: T): void {
    const a = this.items;
    a.push(x);
    for (let i = a.length - 1; i > 0;) {
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T | undefined {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0 && last !== undefined) {
      a[0] = last;
      for (let i = 0; ;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

export class SchedulerClosedError extends Error {}

export class Scheduler {
  private readonly heap = new MinHeap<Entry>((a, b) => a.at < b.at || (a.at === b.at && a.seq < b.seq));
  private readonly jobs = new Map<string, Job>();
  private readonly listeners: Listener[] = [];
  private idleWaiters: (() => void)[] = [];
  private seq = 0;
  private ids = 0;
  private busy = 0;
  private accepting = true;
  private started = false;
  private timer: ReturnType<typeof setTimeout> | undefined;

  constructor(private readonly clock: Clock = new SystemClock(), private readonly workers = 4,
              private readonly threshold = 1000) {
    if (workers < 1) throw new RangeError("need at least one worker");
  }

  addListener(l: Listener): void { this.listeners.push(l); }

  schedule(name: string, task: Task, trigger: Trigger, options: JobOptions = {}): string {
    if (!this.accepting) throw new SchedulerClosedError("scheduler is shut down");
    const first = trigger.first(this.clock.now());
    if (first === null) throw new RangeError("trigger never fires");
    const job = new Job(`job-${++this.ids}`, name, task, trigger, options);
    this.jobs.set(job.id, job);
    job.anchor = first;
    const events: JobEvent[] = [];
    this.enqueue(job, first, "SCHEDULED", "SCHEDULED", events);
    this.wake(); // the timer may be set for a later job
    this.emit(events);
    return job.id;
  }

  cancel(jobId: string): boolean {
    const job = this.jobs.get(jobId);
    if (!job || TERMINAL.has(job.state)) return false;
    job.cancel.abort();
    const events: JobEvent[] = [];
    if (job.state !== "RUNNING") { // a running job finishes as CANCELLED when it settles
      job.entry = null;           // the heap entry is now stale and gets skipped
      this.finish(job, "CANCELLED", "CANCELLED", events);
    }
    this.emit(events);
    return true;
  }

  info(jobId: string): JobInfo {
    const j = this.jobs.get(jobId);
    if (!j) throw new RangeError(`unknown job ${jobId}`);
    return { jobId: j.id, name: j.name, state: j.state, nextRunAt: j.nextRunAt, runs: j.runs, lastRun: j.lastRun };
  }

  /** Dispatch everything due now. The timer calls this. Tests with a FakeClock call it directly. */
  runDue(): number {
    const events: JobEvent[] = [];
    const now = this.clock.now();
    while (this.accepting && this.busy < this.workers) {
      const e = this.popRunnable(now);
      if (!e) break;
      this.fire(e, now, events);
    }
    this.emit(events);
    return events.filter(e => e.type === "STARTED").length;
  }

  awaitIdle(timeoutMs = 5000): Promise<boolean> {
    if (this.busy === 0) return Promise.resolve(true);
    return new Promise(resolve => {
      const t = setTimeout(() => resolve(false), timeoutMs);
      this.idleWaiters.push(() => { clearTimeout(t); resolve(true); });
    });
  }

  start(): void {
    if (this.started || !this.accepting) return;
    this.started = true;
    this.wake();
  }

  /** Stop firing, cancel everything queued, let running jobs settle. True if they all did in time. */
  async shutdown(timeoutMs = 5000): Promise<boolean> {
    this.accepting = false;
    clearTimeout(this.timer);
    const events: JobEvent[] = [];
    for (const job of this.jobs.values()) {
      if (job.state === "SCHEDULED" || job.state === "RETRY_WAIT") {
        job.entry = null;
        this.finish(job, "CANCELLED", "CANCELLED", events);
      }
    }
    this.heap.clear();
    this.emit(events);
    const drained = await this.awaitIdle(timeoutMs);
    if (!drained) for (const job of this.jobs.values()) if (job.state === "RUNNING") job.cancel.abort();
    return drained;
  }

  // ----- dispatcher internals -----
  private wake(): void { // the event-loop version of "signal the condition variable"
    if (!this.started || !this.accepting) return;
    clearTimeout(this.timer);
    this.timer = setTimeout(() => { this.runDue(); this.wake(); }, this.sleepMs());
  }

  private sleepMs(): number {
    const head = this.heap.peek();
    if (this.busy >= this.workers || !head) return MAX_SLEEP_MS;
    return Math.max(0, Math.min(MAX_SLEEP_MS, head.at - this.clock.now()));
  }

  private popRunnable(now: number): Entry | null {
    while (this.heap.size > 0 && this.heap.peek()!.at <= now) {
      const e = this.heap.pop()!;
      if (e.job.entry === e) return e; // cancelled or replaced entries are skipped here
    }
    return null;
  }

  private enqueue(job: Job, at: number, state: JobState, kind: EventType, events: JobEvent[]): void {
    job.state = state;
    job.nextRunAt = at;
    job.entry = { at, seq: ++this.seq, job };
    this.heap.push(job.entry);
    events.push({ type: kind, jobId: job.id, name: job.name, run: job.lastRun, nextRunAt: at });
  }

  private finish(job: Job, state: JobState, kind: EventType, events: JobEvent[]): void {
    job.state = state;
    job.nextRunAt = null;
    events.push({ type: kind, jobId: job.id, name: job.name, run: job.lastRun, nextRunAt: null });
  }

  private nextOnTime(job: Job, t: number | null, now: number): number | null {
    // Simplification: walks missed occurrences one by one. Fine unless a tiny period meets a long pause.
    while (t !== null && now - t > this.threshold) t = job.trigger.next(t, now);
    return t;
  }

  private fire(e: Entry, now: number, events: JobEvent[]): void {
    const job = e.job;
    job.entry = null;
    if (now - e.at > this.threshold && job.attempt === 1 && job.misfire === "SKIP") {
      events.push({ type: "MISFIRED", jobId: job.id, name: job.name, run: job.lastRun, nextRunAt: null });
      const next = this.nextOnTime(job, job.trigger.next(job.anchor, now), now);
      if (next === null) this.finish(job, "MISFIRED", "MISFIRED", events);
      else { job.anchor = next; this.enqueue(job, next, "SCHEDULED", "SCHEDULED", events); }
      return;
    }
    job.state = "RUNNING";
    job.nextRunAt = null;
    this.busy++;
    const ctx: JobContext = { jobId: job.id, attempt: job.attempt, scheduledAt: job.anchor, signal: job.cancel.signal };
    events.push({ type: "STARTED", jobId: job.id, name: job.name, run: job.lastRun, nextRunAt: null });
    // Start on a later microtask, so a task that calls schedule() never re-enters this loop.
    Promise.resolve().then(() => job.task(ctx)).then(
      () => this.settle(job, ctx, now, null),
      (err: unknown) => this.settle(job, ctx, now, err ?? new Error("rejected")),
    );
  }

  private settle(job: Job, ctx: JobContext, started: number, error: unknown): void {
    this.busy--;
    const run: JobRun = {
      jobId: job.id, attempt: ctx.attempt, scheduledAt: ctx.scheduledAt, startedAt: started,
      finishedAt: this.clock.now(), error: error === null ? null : String(error),
    };
    job.runs++;
    job.lastRun = run;
    const events: JobEvent[] = [{ type: error === null ? "RUN_SUCCEEDED" : "RUN_FAILED", jobId: job.id, name: job.name, run, nextRunAt: null }];
    this.afterRun(job, run, error, events);
    this.emit(events);
    if (this.busy === 0) { const w = this.idleWaiters; this.idleWaiters = []; w.forEach(f => f()); }
    this.wake(); // a worker is free
  }

  private afterRun(job: Job, run: JobRun, error: unknown, events: JobEvent[]): void {
    if (job.cancel.signal.aborted) { this.finish(job, "CANCELLED", "CANCELLED", events); return; }
    if (error !== null) {
      const delay = job.retry.delay(job.attempt, error);
      if (delay !== null) {
        if (!this.accepting) { this.finish(job, "CANCELLED", "CANCELLED", events); return; }
        job.attempt++;
        this.enqueue(job, run.finishedAt + delay, "RETRY_WAIT", "RETRYING", events);
        return;
      }
    }
    job.attempt = 1;
    let next = job.trigger.next(job.anchor, run.finishedAt);
    if (job.misfire !== "CATCH_UP") next = this.nextOnTime(job, next, run.finishedAt);
    if (next === null) this.finish(job, error === null ? "COMPLETED" : "FAILED", error === null ? "COMPLETED" : "FAILED", events);
    else if (!this.accepting) this.finish(job, "CANCELLED", "CANCELLED", events);
    else { job.anchor = next; this.enqueue(job, next, "SCHEDULED", "SCHEDULED", events); }
  }

  private emit(events: JobEvent[]): void {
    for (const e of events) {
      for (const l of [...this.listeners]) {
        try { l(e); } catch { /* a broken listener can't break scheduling */ }
      }
    }
  }
}

// ---------- self-check ----------
function check(ok: boolean, what: string): void { if (!ok) throw new Error(`check failed: ${what}`); }
const same = (a: unknown, b: unknown) => JSON.stringify(a) === JSON.stringify(b);
const sleep = (ms: number) => new Promise<void>(r => setTimeout(r, ms));

async function main(): Promise<void> {
  // One-off, fixed rate and fixed delay with a fake clock. Tasks "take" 300 ms by advancing it.
  const clock = new FakeClock(0);
  let s = new Scheduler(clock, 2, 100);
  const once = s.schedule("once", () => {}, Once.at(1000));
  const rate = s.schedule("rate", () => clock.advance(300), new FixedRate(1000));
  s.runDue(); await s.awaitIdle();
  check(s.info(rate).nextRunAt === 1000, "fixed rate counts from scheduled time");
  const delay = s.schedule("delay", () => clock.advance(300), new FixedDelay(1000));
  s.runDue(); await s.awaitIdle();
  check(s.info(delay).nextRunAt === 1600, "fixed delay counts from finish time");
  clock.advance(400);
  check(s.runDue() === 2, "once and rate both due at 1000");
  await s.awaitIdle();
  check(s.info(once).state === "COMPLETED", "one-off completes");
  check(s.cancel(rate) && s.cancel(delay) && !s.cancel(once), "cancel scheduled, not finished");
  check(await s.shutdown(), "clean shutdown");

  // Retries with backoff, jitter pinned for determinism. Async tasks reject instead of throwing.
  const c2 = new FakeClock(0);
  s = new Scheduler(c2, 2, 100);
  const attempts: number[] = [];
  const flaky = s.schedule("flaky", async ctx => {
    attempts.push(ctx.attempt);
    if (ctx.attempt < 3) throw new Error("smtp down");
  }, Once.after(0), { retry: new ExponentialBackoff(3, 100, 10_000, () => 1) });
  s.runDue(); await s.awaitIdle();
  check(s.info(flaky).state === "RETRY_WAIT" && s.info(flaky).nextRunAt === 100, "first retry after 100");
  c2.advance(100); s.runDue(); await s.awaitIdle();
  check(s.info(flaky).nextRunAt === 300, "second retry 200 later");
  c2.advance(200); s.runDue(); await s.awaitIdle();
  check(same(attempts, [1, 2, 3]) && s.info(flaky).state === "COMPLETED", "succeeds on attempt 3");
  const b = new ExponentialBackoff(10, 100, 1000, () => 0);
  check(b.delay(1) === 50 && b.delay(5) === 500 && b.delay(10) === null, "jitter floor and cap");
  const dead = s.schedule("dead", () => { throw new Error("bad payload"); }, Once.after(0));
  s.runDue(); await s.awaitIdle();
  check(s.info(dead).state === "FAILED" && (s.info(dead).lastRun?.error ?? "").includes("bad payload"), "gives up");
  await s.shutdown();

  // Misfire policies after a 5.5 s stall, fixed rate of 1 s starting at 1 s.
  const expected: Record<Misfire, number[]> = { FIRE_NOW: [1000], SKIP: [], CATCH_UP: [1000, 2000, 3000, 4000, 5000] };
  for (const policy of ["FIRE_NOW", "SKIP", "CATCH_UP"] as Misfire[]) {
    const c = new FakeClock(0);
    const m = new Scheduler(c, 1, 100);
    const runs: number[] = [];
    const id = m.schedule("rate", ctx => { runs.push(ctx.scheduledAt); }, new FixedRate(1000, 1000), { misfire: policy });
    c.advance(5500);
    for (let i = 0; i < 10; i++) { m.runDue(); await m.awaitIdle(); }
    check(same(runs, expected[policy]), `${policy} ran ${runs}`);
    check(m.info(id).nextRunAt === 6000, `${policy} next is 6000`);
    await m.shutdown();
  }

  // No double execution, and the pool bounds concurrency.
  const c3 = new FakeClock(0);
  s = new Scheduler(c3, 2, 100);
  let release!: () => void;
  const gate = new Promise<void>(r => { release = r; });
  const started: string[] = [];
  s.addListener(e => { if (e.type === "STARTED") started.push(e.name); });
  s.schedule("long", () => gate, new FixedRate(100));
  for (const n of ["a", "b", "c"]) s.schedule(n, () => gate, Once.at(1));
  c3.advance(500);
  check(s.runDue() === 2 && s.runDue() === 0, "two workers: long and a start, b and c wait");
  release();
  for (let i = 0; i < 6; i++) { await s.awaitIdle(); s.runDue(); }
  await s.awaitIdle();
  check(same(started, ["long", "a", "b", "c", "long", "long"]), `order ${started}`);
  await s.shutdown();

  // Cancel a running job: it sees the abort signal and is not rescheduled.
  s = new Scheduler(new FakeClock(0), 1, 100);
  let sawAbort = false;
  const longJob = s.schedule("long", async ctx => { await sleep(20); sawAbort = ctx.signal.aborted; }, new FixedRate(100));
  s.runDue();
  check(s.cancel(longJob) && s.info(longJob).state === "RUNNING", "still running after cancel");
  await s.awaitIdle();
  check(sawAbort && s.info(longJob).state === "CANCELLED", "finishes as cancelled");
  await s.shutdown();

  // Cron.
  const utc = (y: number, mo: number, d: number, h = 0, mi = 0) => Date.UTC(y, mo - 1, d, h, mi);
  const cron = new Cron("*/15 9-17 * * 1-5");
  check(cron.first(utc(2026, 11, 13, 17, 50)) === utc(2026, 11, 16, 9, 0), "Friday evening rolls to Monday");
  check(cron.next(utc(2026, 11, 16, 9, 0)) === utc(2026, 11, 16, 9, 15), "next quarter hour");
  check(new Cron("0 0 1 * 0").first(utc(2026, 11, 2)) === utc(2026, 11, 8), "day fields OR together");
  check(new Cron("0 12 29 2 *").first(utc(2026, 3, 1)) === utc(2028, 2, 29, 12), "leap day");

  // Shutdown waits for running jobs and refuses new ones.
  s = new Scheduler(new FakeClock(0), 1, 100);
  let finished = false;
  s.schedule("slow", async () => { await sleep(50); finished = true; }, Once.after(0));
  const queued = s.schedule("later", () => {}, Once.after(10_000));
  s.runDue();
  check(await s.shutdown(2000) && finished, "drains running work");
  check(s.info(queued).state === "CANCELLED", "queued work is cancelled");
  let refused = false;
  try { s.schedule("x", () => {}, Once.after(0)); } catch (e) { refused = e instanceof SchedulerClosedError; }
  check(refused, "refuses after shutdown");

  // Real clock: an earlier job wakes the sleeping timer.
  const real = new Scheduler(new SystemClock(), 2, 1000);
  real.start();
  let soonAt = 0;
  real.schedule("far", () => {}, Once.after(3_600_000));
  await sleep(50);
  const t0 = Date.now();
  real.schedule("soon", () => { soonAt = Date.now(); }, Once.after(20));
  await sleep(300);
  check(soonAt > 0 && soonAt - t0 < 250, "woken early, not after the 1 s nap");
  check(await real.shutdown(), "real shutdown");
  console.log("scheduler self-check passed");
}

main().catch(err => { console.error(err); throw err; });

Walking through the important decisions

runDue() is the heart, and it's public. The dispatcher thread is a short loop: lock, call the same dispatch step runDue() uses, then wait on the condition for min(head.at - now, 1 s). Tests never start that thread. They advance a FakeClock and call runDue() themselves, then awaitIdle() to let the workers finish. All the logic (ordering, misfire, retry, rescheduling) runs in the test exactly as it would in production. Only the "sleep until the next job" part is skipped. This is the humble object idea: make the hard-to-test piece, the waiting thread, so thin that it barely needs a test.

One live entry per job, checked by identity. job.entry points at the one queue entry that's allowed to fire this job. cancel sets it to null. Rescheduling replaces it. When the dispatcher pops an entry, it fires only if entry.job.entry is entry. Anything else is stale and is silently dropped. That's lazy deletion: removing an arbitrary element from a binary heap is O(n), while skipping a dead one when it surfaces is O(log n). The cost is that a cancelled job's entry stays in the heap until its due time. For a scheduler that cancels a lot of far-future jobs, rebuild the heap when stale entries pass half its size. That's an optimisation for later.

The dispatcher only fires when a worker is free. dispatch stops as soon as busy == workers, so due jobs wait in the priority queue, not in the pool's internal FIFO. That has three consequences, all good. Cancelling a due-but-waiting job still works, because it hasn't left our control. Misfire decisions use the real start time. And extension A (priorities) can reorder jobs that are waiting for a worker, which is impossible once they've been handed to the pool.

The retry keeps the occurrence's scheduled time. job.anchor is the scheduled time of the current occurrence. A retry changes when the next attempt runs, but not anchor. When the occurrence finally succeeds or gives up, trigger.next(anchor, finished) computes the next one. So a fixed-rate job at :00, :10, :20 that needs two retries at :00 still runs next at :10, not at :10 plus the retry delays.

Misfire is checked in two places. At dispatch, a late first attempt under SKIP doesn't run. At completion, FIRE_NOW and SKIP both skip forward past occurrences that are already too late (nextOnTime), which is what "coalesce" means. CATCH_UP skips that step, so the missed occurrences come due immediately, one after another. Retries are exempt from SKIP. Dropping a retry because the pool was busy would turn a transient failure into a silent loss.

Equal jitter, with an injectable random source. The delay for attempt n is drawn uniformly from [cap/2, cap], where cap = min(max, base × 2^(n-1)). Full jitter ([0, cap]) spreads load better but sometimes retries almost instantly. Equal jitter keeps a minimum wait. Both are standard. See timeouts, retries and backoff for the trade-off. The random source is a constructor parameter so tests can pin it to 0 or 1 and assert exact delays.

Cron searches by skipping whole units. Rather than testing every minute for five years (2.6 million checks), the search jumps to the next month when the month doesn't match, the next day when the day doesn't, and the next hour when the hour doesn't. Typical expressions resolve in a few dozen steps. An impossible expression such as 0 0 31 2 * (31 February) hits the five-year limit and raises, which is better than looping forever. Day-of-month and day-of-week follow the classic cron rule: if both are restricted, a day matching either one fires.

Wall clock, and the one-second nap. The dispatcher's wait uses the platform's monotonic timer internally, but now() is wall-clock time, because cron is defined in wall-clock terms. If NTP steps the clock forward by an hour, a dispatcher sleeping for "40 minutes" would oversleep its jobs. Capping every sleep at one second bounds that error at a negligible cost of one wake-up per second. Section 11 discusses the cleaner split into two clocks.

Shutdown is graceful, with a deadline. It stops accepting work, cancels everything queued, wakes the dispatcher so it exits, and waits for busy == 0 up to the timeout. If running jobs don't finish in time, it sets their cancellation flags. Java goes further with shutdownNow(), which interrupts the worker threads. Python can't kill a thread, and TypeScript can't stop a promise, so they rely on the job checking ctx.cancelled or ctx.signal. Say that difference out loud. It's a good signal that you know your runtime.

TypeScript has no threads, but it has the same shape. "Workers" are concurrency slots on the event loop: busy counts running promises, and the dispatcher won't start more than workers. The condition variable becomes wake(), which clears the timer and sets a new one for the new head of the queue. Tasks are started on a later microtask (Promise.resolve().then(...)), so a synchronous task that calls schedule() can't re-enter the dispatch loop halfway through.

7. Concurrency

What's shared

StateRead or written byProtected by
Priority queueschedule (push), dispatcher (pop), workers (push next or retry), shutdown (clear)Scheduler lock
Job table and every Job fieldCallers, dispatcher, workersScheduler lock
busy countDispatcher (+1), workers (−1), awaitIdle, shutdownScheduler lock
accepting flagshutdown writes, everyone readsScheduler lock
A job's cancellation flagcancel and shutdown write, the running task readsAtomic (AtomicBoolean, threading.Event, AbortSignal), because the task reads it without the lock
Listener listaddListener writes, emitters readCopy-on-write list in Java, a copy taken under the lock in Python
Triggers, retry policies, options, JobRun, JobEvent, JobInfoMany threadsImmutability
Whatever the task touchesThe taskThe task's own problem. The scheduler only promises a job never runs twice at once.

Guarding the queue

One ReentrantLock (Java) or threading.Condition (Python) guards all of it. Every critical section is a handful of heap and field operations, a few microseconds long. The only slow thing, the task, runs outside the lock. A single lock won't be the bottleneck until you're firing hundreds of thousands of jobs per second, which an in-process scheduler won't see. It also makes the important invariant trivially safe. "A job has at most one live entry, and is never both queued and running" spans the heap, the job and the busy count, and holding one lock while touching all three is the simplest correct way to keep them consistent. Thread-safe class design covers when to split a lock like this.

Why not a PriorityBlockingQueue or DelayQueue and no lock at all? Because the operations that matter are compound. "Pop the head, check it's still live, check a worker is free, mark the job running, increment busy" must happen atomically. A thread-safe queue makes each step safe and the sequence unsafe. DelayQueue also can't express "due, but wait for a free worker", and it can't be cancelled from. You'd end up adding a lock around it anyway.

Preventing double execution of recurring jobs

There are three ways a recurring job could run twice at once, and the design closes each one:

  1. Enqueueing the next run when this one starts. If the next run is enqueued at start time and the run takes longer than the period, the next run fires while this one is still going. Our next occurrence is computed and enqueued only when the run finishes, under the lock, in afterRun. While a job is RUNNING, it has no live entry at all.
  2. Two entries for the same job in the heap. A reschedule that pushed a new entry without retiring the old one would leave two. Every push goes through enqueue, which replaces job.entry. A popped entry that isn't job.entry is stale and ignored.
  3. The dispatcher and cancel racing. The dispatcher pops an entry and is about to fire while another thread cancels the job. Both run under the same lock, so one goes first. If cancel goes first, the entry is stale and won't fire. If the dispatcher goes first, the job is RUNNING, and cancel sets the flag so the job isn't rescheduled.

The cost of the rule is that a slow fixed-rate job drifts. A 1-second job that takes 2.5 seconds runs at 0, 2.5 and 5, not at 0, 1, 2. With FIRE_NOW, the missed occurrences are coalesced. That's also how ScheduledExecutorService.scheduleAtFixedRate behaves: "If any execution of this task takes longer than its period, then subsequent executions may start late, but will not concurrently execute." If a team truly wants overlapping runs, they want several jobs, not one.

Waking the dispatcher when an earlier job arrives

The dispatcher sleeps on a condition variable with a timeout equal to the time until the head of the queue is due. Four events can make that timeout wrong, and each one signals the condition:

EventWhy the dispatcher must re-check
schedule() adds a jobIt may be due before the current head
A run finishesA worker is free, and a next occurrence or retry may be due already
shutdown()The dispatcher must exit
A wall-clock jumpCan't be signalled, so the one-second cap bounds the error

cancel doesn't need to signal. A cancelled head just becomes a stale entry. The dispatcher wakes at its time, finds it stale, drops it and recomputes. Signalling would also be harmless.

Two classic mistakes live here. Waiting without a loop: condition variables have spurious wake-ups, and a wake-up only means "something changed". Our loop recomputes everything on each pass, so a spurious wake-up costs one heap peek. Using signal instead of signalAll: awaitIdle and shutdown wait on the same condition as the dispatcher, for a different predicate. Waking just one waiter could wake the wrong one. signalAll is cheap with this few waiters.

Races we designed out

RaceWhat would go wrongHow the design prevents it
A job is cancelled after the dispatcher read the head but before it firedA cancelled job runsPop, liveness check and state change are one critical section
A job finishes while the dispatcher is computing its sleepThe dispatcher sleeps a full second with a free worker and due workThe worker's signalAll happens under the lock, so the dispatcher is either already waiting (and is woken) or hasn't started waiting yet (and will see busy decreased)
A task calls schedule() or cancel() on its own schedulerDeadlock, if the task ran under the lockTasks never run under the lock
A listener calls back into the schedulerDeadlock, if listeners ran under the lockEvents are emitted after unlocking
A cancel arrives while the job is runningThe job is rescheduled after cancel() returned trueafterRun checks the cancellation flag before computing a next time
Shutdown while a run is in progressThe finished job reschedules itself into a closed schedulerafterRun checks accepting before enqueueing
The task reads the cancellation flagA data race on a plain booleanThe flag is atomic, so the task reads it without the lock

What this design does not promise

Event order across threads. STARTED is emitted by the dispatcher after it unlocks, and RUN_SUCCEEDED by the worker after the run. A very fast task can finish, and its worker emit RUN_SUCCEEDED, before the dispatcher thread gets around to emitting STARTED. Events from one thread are in order. Events from different threads aren't. If a consumer needs a strict order, have listeners stamp each event with a sequence number assigned under the lock, or route all events through one queue drained by a single thread. Saying this unprompted is a strong signal. Most candidates assume Observer delivers events in order.

Exactly-once. A job runs at most once at a time, and the scheduler runs each attempt once. But a process crash in the middle of a run loses it, and a retry after a timeout can repeat side effects the first attempt already made. Tasks with external effects should be idempotent. See idempotent consumers.

TypeScript is different, but not race-free

Node runs all our code on one thread, so no lock is needed: between two awaits, nothing else runs. The races move to the await points instead. A task that reads some shared state, awaits a network call and then writes based on what it read has the same check-then-act problem as a threaded one. Inside the scheduler, every public method does its work synchronously and never awaits in the middle of a state change. That's why runDue, schedule and cancel aren't async. Only awaitIdle and shutdown are, and they only wait, they don't change state after waiting, except for setting the abort signals.

8. Extensibility: "the interviewer adds X"

The extensions are in Python and import the core above. Each one is a small subclass or a separate class, which is a good test of the core design: if adding a feature means editing afterRun, the seams are in the wrong place.

Extension A: job priorities

"Password-reset emails must jump ahead of the nightly cleanup when workers are scarce."

Priority only matters when more jobs are due than workers are free. A job due in an hour shouldn't run before a job due now just because it's more important. So priority can't simply be added to the queue's sort key in front of the time. The clean model is two queues: a timer queue ordered by due time, holding the future, and a ready queue ordered by priority, holding what's due and waiting for a worker. The dispatcher moves due entries from the first to the second, then picks from the second.

The core already has the seam, because dispatch calls _pop_runnable(now) to get the next entry. The extension overrides just that method.

"""Extension A: priorities. Among jobs that are already due, the highest priority runs first."""
import heapq
import threading
from dataclasses import dataclass
from typing import Optional

from scheduler import EventType, FakeClock, JobOptions, Scheduler, _Entry, at


@dataclass(frozen=True)
class PriorityOptions(JobOptions):
    priority: int = 0  # higher runs first. Only matters when more jobs are due than workers are free.


class PriorityScheduler(Scheduler):
    def __init__(self, *args, **kwargs) -> None:
        super().__init__(*args, **kwargs)
        self._ready: list[tuple[int, int, int, _Entry]] = []  # (-priority, due time, seq, entry)

    @staticmethod
    def priority_of(entry: _Entry) -> int:
        return getattr(entry.job.options, "priority", 0)

    def _pop_runnable(self, now: int) -> Optional[_Entry]:
        # Step 1: everything that is due moves from the timer heap to the ready heap.
        while self._heap and self._heap[0].at <= now:
            entry = heapq.heappop(self._heap)
            if entry.job.entry is entry:
                heapq.heappush(self._ready, (-self.priority_of(entry), entry.at, entry.seq, entry))
        # Step 2: the ready heap decides who gets the free worker.
        while self._ready:
            entry = heapq.heappop(self._ready)[-1]
            if entry.job.entry is entry:  # cancelled while waiting for a worker
                return entry
        return None


if __name__ == "__main__":
    clock = FakeClock(0)
    s = PriorityScheduler(clock, workers=1)
    gate = threading.Event()
    s.schedule("blocker", lambda c: gate.wait(2), at(0))
    s.run_due()  # the only worker is now busy
    s.schedule("cleanup", lambda c: None, at(1), PriorityOptions(priority=0))
    s.schedule("digest", lambda c: None, at(2), PriorityOptions(priority=5))
    s.schedule("password-reset", lambda c: None, at(3), PriorityOptions(priority=9))
    started = []
    s.add_listener(lambda e: started.append(e.name) if e.type is EventType.STARTED else None)
    clock.advance(10)
    gate.set()
    for _ in range(4):
        s.await_idle(2)
        s.run_due()
    assert s.await_idle(2)
    assert started == ["password-reset", "digest", "cleanup"], started
    assert s.shutdown(1)
    print("priority checks passed")

Two follow-ups the interviewer may ask. Starvation: a steady stream of priority 9 jobs means a priority 0 job never runs. The usual fix is aging, which raises a waiting job's effective priority with every second it waits, for example priority + waited_ms / 10_000. Because the effective priority changes with time, the ready heap is then rebuilt on each dispatch, which is fine for the few dozen jobs a ready queue normally holds. Pre-emption: a high-priority job can't interrupt a low-priority one that's already running. Cooperative cancellation is the only tool an in-process scheduler has. If that matters, reserve a worker for high-priority jobs, which extension B makes easy.

Extension B: per-type concurrency limits

"We have 8 workers, but our email provider allows only 2 concurrent connections. Reports can use whatever is free."

Now a due job may be skipped temporarily because its type is at its limit, while a lower-priority job of another type runs. That must not lose the skipped job's place, and it mustn't busy-loop either. The extension layers on extension A: it pops from the ready queue, sets aside entries whose type is full, and puts them back afterwards. A running-count per type is incremented when a job starts and decremented when it finishes, both under the scheduler lock.

"""Extension B: per-type concurrency limits, layered on the priority ready queue."""
import heapq
import threading
from collections import Counter
from dataclasses import dataclass
from typing import Optional

from ext_priorities import PriorityOptions, PriorityScheduler
from scheduler import FakeClock, Job, JobRun, JobState, _Entry, after


@dataclass(frozen=True)
class TypedOptions(PriorityOptions):
    job_type: str = "default"


class TypeLimitedScheduler(PriorityScheduler):
    def __init__(self, *args, limits: dict[str, int], **kwargs) -> None:
        super().__init__(*args, **kwargs)
        self._limits = dict(limits)
        self._running_by_type: Counter[str] = Counter()

    @staticmethod
    def type_of(job: Job) -> str:
        return getattr(job.options, "job_type", "default")

    def _pop_runnable(self, now: int) -> Optional[_Entry]:
        held = []  # due, but their type is at its limit: they keep their place in the ready heap
        try:
            while (entry := super()._pop_runnable(now)) is not None:
                kind = self.type_of(entry.job)
                if self._running_by_type[kind] < self._limits.get(kind, self._workers):
                    return entry
                held.append(entry)
            return None
        finally:
            # Simplification: re-scans blocked entries on every pop. Fine for dozens, use a heap per type for thousands.
            for e in held:
                heapq.heappush(self._ready, (-self.priority_of(e), e.at, e.seq, e))

    def _fire(self, entry: _Entry, now: int, events: list) -> None:
        super()._fire(entry, now, events)
        if entry.job.state is JobState.RUNNING:  # not a skipped misfire
            self._running_by_type[self.type_of(entry.job)] += 1

    def _after_run(self, job: Job, run: JobRun, error, events: list) -> None:
        self._running_by_type[self.type_of(job)] -= 1  # still under the lock, before the job can be re-queued
        super()._after_run(job, run, error, events)


if __name__ == "__main__":
    clock = FakeClock(0)
    s = TypeLimitedScheduler(clock, workers=4, limits={"email": 1})
    gate = threading.Event()
    peak, live, lock = [0], [0], threading.Lock()

    def send(ctx):
        with lock:
            live[0] += 1
            peak[0] = max(peak[0], live[0])
        gate.wait(2)
        with lock:
            live[0] -= 1

    ids = [s.schedule(f"email-{i}", send, after(0), TypedOptions(job_type="email")) for i in range(3)]
    ids.append(s.schedule("report", lambda c: gate.wait(2), after(0), TypedOptions(job_type="report")))
    assert s.run_due() == 2  # one email (the limit) plus the report, although 4 workers exist
    assert s.run_due() == 0  # the other two emails wait, even with 2 idle workers
    gate.set()
    for _ in range(6):
        s.await_idle(2)
        s.run_due()
    assert s.await_idle(2)
    assert peak[0] == 1, peak
    assert all(s.info(j).state is JobState.COMPLETED for j in ids)
    assert s.shutdown(1)
    print("type limit checks passed")

Why not just give each type its own scheduler, with its own pool? That's often the right production answer, and you should offer it. Separate pools isolate failures completely: a hung email provider can't tie up report workers. The cost is idle capacity. Two email workers sit idle while reports queue up. A shared pool with per-type limits gives a ceiling without a floor. To guarantee a floor as well, reserve slots per type, which is a small change to the same check.

Notice the ordering detail in _after_run. The type count is decremented before the superclass reschedules the job. The other order is harmless here, because everything is under one lock, but it's the kind of thing an interviewer asks you to justify.

Extension C: job dependencies

"Run transform only after extract succeeds, and load after transform. If anything upstream fails, skip everything downstream."

This one needs no change to the scheduler at all. Dependencies are a reaction to job outcomes, and the scheduler already publishes outcomes as events. A Workflow class listens for COMPLETED, FAILED, CANCELLED and MISFIRED, and schedules a waiting job once all its upstreams have completed. If any upstream ends badly, the dependent and everything below it become skipped. This is Observer paying for itself.

"""Extension C: job dependencies, built on the scheduler's events (Observer) with no core change."""
import threading
from dataclasses import dataclass, field
from typing import Optional

from scheduler import EventType, FakeClock, JobOptions, Scheduler, Task, Trigger, after

OUTCOME = {EventType.COMPLETED: "completed", EventType.FAILED: "failed",
           EventType.CANCELLED: "cancelled", EventType.MISFIRED: "failed"}


@dataclass
class _Node:
    name: str
    task: Task
    trigger: Trigger
    options: Optional[JobOptions]
    upstream: list[str]
    status: str = "waiting"  # waiting -> scheduled -> completed | failed | cancelled, or waiting -> skipped
    job_id: Optional[str] = None
    downstream: list[str] = field(default_factory=list)


class Workflow:
    """Runs a node only after every upstream node COMPLETED. If an upstream fails or is
    cancelled, its dependents are skipped. Upstreams must be added first, so a cycle can't be built."""

    def __init__(self, scheduler: Scheduler) -> None:
        self._s = scheduler
        self._lock = threading.RLock()  # re-entrant: schedule() emits SCHEDULED on this same thread
        self._nodes: dict[str, _Node] = {}
        self._by_job: dict[str, _Node] = {}
        scheduler.add_listener(self._on_event)

    def add(self, name: str, task: Task, trigger: Optional[Trigger] = None,
            options: Optional[JobOptions] = None, upstream: tuple[str, ...] = ()) -> None:
        with self._lock:
            if name in self._nodes:
                raise ValueError(f"duplicate node {name!r}")
            unknown = [u for u in upstream if u not in self._nodes]
            if unknown:
                raise ValueError(f"unknown upstream {unknown}")
            node = _Node(name, task, trigger or after(0), options, list(upstream))
            self._nodes[name] = node
            for u in upstream:
                self._nodes[u].downstream.append(name)
            self._settle(node)

    def status(self, name: str) -> str:
        with self._lock:
            return self._nodes[name].status

    def _settle(self, node: _Node) -> None:
        if node.status != "waiting":
            return
        states = [self._nodes[u].status for u in node.upstream]
        if any(s in ("failed", "cancelled", "skipped") for s in states):
            node.status = "skipped"
            for d in node.downstream:
                self._settle(self._nodes[d])
        elif all(s == "completed" for s in states):
            node.status = "scheduled"
            node.job_id = self._s.schedule(node.name, node.task, node.trigger, node.options)
            self._by_job[node.job_id] = node

    def _on_event(self, event) -> None:
        if event.type not in OUTCOME:
            return
        with self._lock:  # a fast job can finish before schedule() returned its id, the lock orders that
            node = self._by_job.get(event.job_id)
            if node is None:
                return
            node.status = OUTCOME[event.type]
            for d in node.downstream:
                self._settle(self._nodes[d])


if __name__ == "__main__":
    clock = FakeClock(0)
    s = Scheduler(clock, workers=2)
    wf = Workflow(s)
    order: list[str] = []

    def step(name: str, fail: bool = False):
        def task(ctx) -> None:
            order.append(name)
            if fail:
                raise RuntimeError(f"{name} failed")
        return task

    wf.add("extract", step("extract"))
    wf.add("transform", step("transform"), upstream=("extract",))
    wf.add("enrich", step("enrich", fail=True), upstream=("extract",))
    wf.add("load", step("load"), upstream=("transform",))
    wf.add("publish", step("publish"), upstream=("load", "enrich"))
    wf.add("audit", step("audit"), upstream=("publish",))
    for _ in range(6):
        s.run_due()
        s.await_idle(2)
    assert order[0] == "extract" and order[-1] == "load", order
    assert sorted(order[1:3]) == ["enrich", "transform"], order
    assert [wf.status(n) for n in ("extract", "transform", "enrich", "load", "publish", "audit")] == \
        ["completed", "completed", "failed", "completed", "skipped", "skipped"]
    wf.add("late", step("late"), upstream=("load",))  # upstream already done: runs straight away
    s.run_due()
    s.await_idle(2)
    assert wf.status("late") == "completed"
    try:
        wf.add("loop", step("loop"), upstream=("loop",))
        raise AssertionError("self-dependency should be rejected")
    except ValueError:
        pass
    assert s.shutdown(1)
    print("dependency checks passed")

Three details are worth pointing at:

  1. Cycles are impossible by construction. A node can name only upstreams that already exist, so the graph is always built in topological order. No cycle detection is needed. If the interviewer wants nodes declared in any order, add them all first, then run a depth-first search for back edges before releasing anything.
  2. The re-entrant lock. _settle calls schedule() while holding the workflow lock, and schedule() emits SCHEDULED to listeners on the same thread, which re-enters _on_event. A plain lock would deadlock right there. The re-entrant lock also covers the opposite race: a fast job can finish on a worker thread before schedule() has even returned its id. The worker's _on_event blocks on the workflow lock until the id has been recorded.
  3. Only one-off upstreams make sense. A recurring job never emits COMPLETED. "Run B after each run of A" is a different feature: listen for RUN_SUCCEEDED instead and schedule a fresh one-off B each time.

9. Testing approach

The injectable clock is the single most important testing decision in this design. With a FakeClock, "a fixed-rate job doesn't overlap itself even when it runs for five periods" is a test that runs in a few milliseconds and gives the same answer every time. Without it, that test needs real sleeps, takes seconds and fails on a busy CI machine.

The pattern in every test is the same three lines: advance the clock, call run_due(), wait for await_idle(). A task can even make itself "take" 300 ms by advancing the fake clock from inside, which is how the fixed-rate and fixed-delay tests tell the two apart.

What to cover, and why:

  1. A one-off job runs at its time, not before. Advance to 999 ms (nothing happens), then 1 ms more (it runs).
  2. Fixed rate counts from the scheduled time, fixed delay from the finish. The same 300 ms task gives next times of 1000 and 1300.
  3. A recurring job never overlaps itself. Block the task, advance through five periods, assert that run_due() starts nothing.
  4. Cron edge cases. Friday evening rolls over to Monday, inclusive first versus exclusive next, the day-of-month or day-of-week rule, 29 February, and an impossible date.
  5. Backoff values. With jitter pinned to 0 and 0.999, delays double and stop at the cap.
  6. Retry then succeed, give up, and keep recurring after giving up.
  7. All three misfire policies, plus "exactly at the threshold" is not a misfire.
  8. Cancel before running, and cancel while running. The running task sees the flag, and the job isn't rescheduled.
  9. The pool bound. With two workers and five due jobs, two start, and the rest start in due-time order.
  10. A broken listener doesn't break scheduling.
  11. Shutdown drains running work, cancels queued work and refuses new work, and a job that ignores the deadline is signalled.
  12. The dispatcher wakes for an earlier job. This is the one test that uses the real clock and the real dispatcher thread, because that's the behaviour under test. It asserts an upper bound (under 500 ms) rather than an exact time.
"""Run with: python -m unittest test_scheduler -v"""
import threading
import time
import unittest
from datetime import datetime, timezone

from scheduler import (Cron, EventType, ExponentialBackoff, FakeClock, FixedDelay, FixedRate, JobOptions,
                       JobState, Misfire, Scheduler, SchedulerClosed, after, at)


def utc(*args: int) -> int:
    return int(datetime(*args, tzinfo=timezone.utc).timestamp()) * 1000


class Base(unittest.TestCase):
    def setUp(self) -> None:
        self.clock = FakeClock(0)
        self.s = Scheduler(self.clock, workers=2, misfire_threshold_ms=100)
        self.events = []
        self.s.add_listener(self.events.append)

    def tearDown(self) -> None:
        self.s.shutdown(1)

    def tick(self, ms: int = 0) -> int:
        """Advance fake time, dispatch what's due, wait for those runs to finish."""
        self.clock.advance(ms)
        started = self.s.run_due()
        self.assertTrue(self.s.await_idle(2))
        return started

    def kinds(self, job_id):
        return [e.type for e in self.events if e.job_id == job_id]


class OneOffAndDelayed(Base):
    def test_runs_exactly_at_its_time(self):
        ran = []
        job = self.s.schedule("at", lambda c: ran.append(self.clock.now()), at(1000))
        self.assertEqual(self.tick(999), 0)
        self.assertEqual(self.tick(1), 1)
        self.assertEqual(ran, [1000])
        self.assertIs(self.s.info(job).state, JobState.COMPLETED)
        self.assertEqual(self.kinds(job), [EventType.SCHEDULED, EventType.STARTED,
                                           EventType.RUN_SUCCEEDED, EventType.COMPLETED])

    def test_delay_is_relative_to_schedule_time(self):
        self.clock.advance(5000)
        job = self.s.schedule("d", lambda c: None, after(250))
        self.assertEqual(self.s.info(job).next_run_at, 5250)


class Recurring(Base):
    def test_fixed_rate_counts_from_scheduled_time(self):
        def slow(ctx):
            self.clock.advance(300)  # the job "takes" 300 ms of fake time
        job = self.s.schedule("rate", slow, FixedRate(1000))
        self.tick()
        self.assertEqual(self.s.info(job).next_run_at, 1000)

    def test_fixed_delay_counts_from_finish_time(self):
        def slow(ctx):
            self.clock.advance(300)
        job = self.s.schedule("delay", slow, FixedDelay(1000))
        self.tick()
        self.assertEqual(self.s.info(job).next_run_at, 1300)

    def test_recurring_job_is_never_run_twice_at_once(self):
        release = threading.Event()
        running = []

        def blocking(ctx):
            running.append(ctx.scheduled_at)
            release.wait(2)
        job = self.s.schedule("rate", blocking, FixedRate(100))
        self.s.run_due()
        for _ in range(5):
            self.clock.advance(100)
            self.assertEqual(self.s.run_due(), 0)  # still running: no second copy
        release.set()
        self.assertTrue(self.s.await_idle(2))
        self.assertEqual(running, [0])
        # FIRE_NOW coalesced 100, 200 and 300. 400 is within the 100 ms threshold, so it still counts.
        self.assertEqual(self.s.info(job).next_run_at, 400)


class CronExpressions(unittest.TestCase):
    def test_weekday_business_hours(self):
        c = Cron("*/15 9-17 * * 1-5")
        self.assertEqual(c.first(utc(2026, 11, 13, 17, 50)), utc(2026, 11, 16, 9, 0))  # Fri -> Mon
        self.assertEqual(c.next(utc(2026, 11, 16, 9, 0), 0), utc(2026, 11, 16, 9, 15))

    def test_first_is_inclusive_next_is_exclusive(self):
        c = Cron("30 2 * * *")
        self.assertEqual(c.first(utc(2026, 1, 1, 2, 30)), utc(2026, 1, 1, 2, 30))
        self.assertEqual(c.next(utc(2026, 1, 1, 2, 30), 0), utc(2026, 1, 2, 2, 30))

    def test_day_of_month_or_day_of_week(self):
        c = Cron("0 0 1 * 0")  # the 1st, or any Sunday
        self.assertEqual(c.first(utc(2026, 11, 2)), utc(2026, 11, 8))  # Sunday before Dec 1
        self.assertEqual(c.next(utc(2026, 11, 29), 0), utc(2026, 12, 1))

    def test_leap_day_and_impossible_dates(self):
        self.assertEqual(Cron("0 12 29 2 *").first(utc(2026, 3, 1)), utc(2028, 2, 29, 12))
        with self.assertRaises(ValueError):
            Cron("0 0 31 2 *").first(0)
        with self.assertRaises(ValueError):
            Cron("61 * * * *")


class Retries(Base):
    def test_backoff_doubles_and_caps_with_jitter_bounds(self):
        low = ExponentialBackoff(max_attempts=10, base_ms=100, max_ms=1000, rand=lambda: 0.0)
        high = ExponentialBackoff(max_attempts=10, base_ms=100, max_ms=1000, rand=lambda: 0.999)
        self.assertEqual([low.delay(n, None) for n in range(1, 6)], [50, 100, 200, 400, 500])
        self.assertEqual([high.delay(n, None) for n in range(1, 6)], [99, 199, 399, 799, 999])
        self.assertIsNone(low.delay(10, None))

    def test_retry_then_succeed(self):
        attempts = []

        def flaky(ctx):
            attempts.append((ctx.attempt, self.clock.now()))
            if ctx.attempt < 3:
                raise TimeoutError("db")
        policy = ExponentialBackoff(max_attempts=3, base_ms=100, rand=lambda: 1.0)
        job = self.s.schedule("flaky", flaky, after(0), JobOptions(retry=policy))
        self.tick()
        self.assertIs(self.s.info(job).state, JobState.RETRY_WAIT)
        self.tick(100)
        self.tick(200)
        self.assertEqual(attempts, [(1, 0), (2, 100), (3, 300)])
        self.assertIs(self.s.info(job).state, JobState.COMPLETED)
        self.assertEqual(self.kinds(job).count(EventType.RETRYING), 2)

    def test_one_off_gives_up_after_max_attempts(self):
        def boom(ctx):
            raise ValueError("bad payload")
        job = self.s.schedule("boom", boom, after(0),
                              JobOptions(retry=ExponentialBackoff(max_attempts=2, base_ms=10, rand=lambda: 1.0)))
        self.tick()
        self.tick(10)
        info = self.s.info(job)
        self.assertIs(info.state, JobState.FAILED)
        self.assertEqual(info.last_run.error, "ValueError: bad payload")

    def test_recurring_job_moves_on_after_exhausting_retries(self):
        def boom(ctx):
            raise ValueError("x")
        job = self.s.schedule("rate", boom, FixedRate(1000))
        self.tick()
        info = self.s.info(job)
        self.assertIs(info.state, JobState.SCHEDULED)
        self.assertEqual(info.next_run_at, 1000)


class Misfires(Base):
    def schedule_rate(self, policy):
        runs = []
        job = self.s.schedule("rate", lambda c: runs.append(c.scheduled_at), FixedRate(1000, initial_delay=1000),
                              JobOptions(misfire=policy))
        return job, runs

    def test_fire_now_runs_once_and_coalesces(self):
        job, runs = self.schedule_rate(Misfire.FIRE_NOW)
        self.tick(5500)
        self.assertEqual(self.tick(), 0)
        self.assertEqual(runs, [1000])
        self.assertEqual(self.s.info(job).next_run_at, 6000)

    def test_skip_drops_late_occurrences(self):
        job, runs = self.schedule_rate(Misfire.SKIP)
        self.tick(5500)
        self.assertEqual(runs, [])
        self.assertEqual(self.s.info(job).next_run_at, 6000)
        self.assertIn(EventType.MISFIRED, self.kinds(job))

    def test_catch_up_runs_every_missed_occurrence(self):
        job, runs = self.schedule_rate(Misfire.CATCH_UP)
        self.clock.advance(5500)
        for _ in range(10):
            self.tick()
        self.assertEqual(runs, [1000, 2000, 3000, 4000, 5000])
        self.assertEqual(self.s.info(job).next_run_at, 6000)

    def test_late_one_off_with_skip_is_misfired(self):
        job = self.s.schedule("once", lambda c: None, at(1000), JobOptions(misfire=Misfire.SKIP))
        self.tick(2000)
        self.assertIs(self.s.info(job).state, JobState.MISFIRED)

    def test_slightly_late_is_not_a_misfire(self):
        job = self.s.schedule("once", lambda c: None, at(1000), JobOptions(misfire=Misfire.SKIP))
        self.tick(1100)  # exactly at the threshold
        self.assertIs(self.s.info(job).state, JobState.COMPLETED)


class CancellationAndPool(Base):
    def test_cancel_before_it_runs(self):
        ran = []
        job = self.s.schedule("x", lambda c: ran.append(1), after(100))
        self.assertTrue(self.s.cancel(job))
        self.assertFalse(self.s.cancel(job))  # already terminal
        self.tick(500)
        self.assertEqual(ran, [])

    def test_cancel_while_running_stops_recurrence(self):
        started, release = threading.Event(), threading.Event()
        saw_cancel = []

        def long(ctx):
            started.set()
            release.wait(2)
            saw_cancel.append(ctx.cancelled)
        job = self.s.schedule("long", long, FixedRate(100))
        self.s.run_due()
        self.assertTrue(started.wait(2))
        self.assertTrue(self.s.cancel(job))
        self.assertIs(self.s.info(job).state, JobState.RUNNING)
        release.set()
        self.assertTrue(self.s.await_idle(2))
        self.assertEqual(saw_cancel, [True])
        self.assertIs(self.s.info(job).state, JobState.CANCELLED)

    def test_pool_size_bounds_concurrency_and_due_jobs_wait_in_order(self):
        release = threading.Event()
        for i, name in enumerate("abcde"):
            self.s.schedule(name, lambda c: release.wait(2), at(i))  # a is earliest
        self.clock.advance(10)
        self.assertEqual(self.s.run_due(), 2)
        self.assertEqual(self.s.run_due(), 0)  # both workers busy: the rest stay in the queue
        release.set()
        for _ in range(5):
            self.s.run_due()
            self.s.await_idle(2)
        started = [e.name for e in self.events if e.type is EventType.STARTED]
        self.assertEqual(started, ["a", "b", "c", "d", "e"])

    def test_broken_listener_does_not_break_scheduling(self):
        def bad(event):
            raise RuntimeError("listener bug")
        self.s.add_listener(bad)
        job = self.s.schedule("x", lambda c: None, after(0))
        self.tick()
        self.assertIs(self.s.info(job).state, JobState.COMPLETED)


class Shutdown(unittest.TestCase):
    def test_shutdown_drains_running_and_cancels_queued(self):
        clock = FakeClock(0)
        s = Scheduler(clock, workers=1)
        finished = []

        def slow(ctx):
            time.sleep(0.1)
            finished.append(1)
        running = s.schedule("slow", slow, after(0))
        queued = s.schedule("later", lambda c: None, after(10_000))
        s.run_due()
        self.assertTrue(s.shutdown(2))
        self.assertEqual(finished, [1])
        self.assertIs(s.info(running).state, JobState.COMPLETED)
        self.assertIs(s.info(queued).state, JobState.CANCELLED)
        with self.assertRaises(SchedulerClosed):
            s.schedule("x", lambda c: None, after(0))

    def test_shutdown_times_out_and_signals_stragglers(self):
        s = Scheduler(FakeClock(0), workers=1)
        stop_seen = threading.Event()

        def stubborn(ctx):
            while not ctx.cancelled:
                time.sleep(0.01)
            stop_seen.set()
        s.schedule("stubborn", stubborn, after(0))
        s.run_due()
        self.assertFalse(s.shutdown(0.1))
        self.assertTrue(stop_seen.wait(2))


class DispatcherThread(unittest.TestCase):
    def test_earlier_job_wakes_the_sleeping_dispatcher(self):
        s = Scheduler(workers=2)  # real clock
        s.start()
        done = threading.Event()
        s.schedule("far", lambda c: None, after(3_600_000))
        time.sleep(0.05)  # let the dispatcher go to sleep on the far job
        t0 = time.monotonic()
        s.schedule("near", lambda c: done.set(), after(20))
        self.assertTrue(done.wait(2))
        self.assertLess(time.monotonic() - t0, 0.5)
        self.assertTrue(s.shutdown(1))


if __name__ == "__main__":
    unittest.main()

The tests never use sleep to "wait for things to happen". The two exceptions are the shutdown tests, where a task deliberately takes 100 ms of real time, and the dispatcher test, which sleeps 50 ms so the dispatcher is genuinely asleep before the earlier job arrives. Neither has an assertion that depends on the exact sleep length. All 25 tests run in about 0.3 seconds. Run them in a loop a few hundred times in CI to shake out ordering assumptions. The Java and TypeScript self-checks above cover the same rules and were run repeatedly the same way.

10. Common mistakes

  1. Calling System.currentTimeMillis() or time.time() all over the code. It makes every time-based rule untestable without sleeps, and those tests are slow and flaky. Inject a clock from the first line you write. Interviewers notice when you do it before they ask.
  2. Enqueueing the next run of a recurring job when the current one starts. This is the classic double-execution bug. A run that takes longer than its period overlaps the next. Compute the next time when the run finishes.
  3. Running the task while holding the scheduler lock. It looks tidy, and it means one slow job freezes scheduling, and a job that schedules another job deadlocks.
  4. A thread per job, or Timer plus sleep. A thousand jobs become a thousand threads, almost all asleep. One dispatcher plus a fixed pool handles any number of jobs with workers + 1 threads.
  5. A dispatcher that sleeps until the head is due and can't be woken. A new job due sooner than the head waits for the old sleep to end. Use a condition variable with a timeout, and signal it from schedule().
  6. Polling the queue every 10 ms instead. It works and wastes CPU, and the latency is still 10 ms. Sleep exactly until the next due time, and let schedule() wake you.
  7. Retrying by sleeping on the worker. It holds a worker hostage for the backoff and can't be cancelled. Put the retry back in the queue.
  8. Retrying without jitter. When a dependency recovers, every job that failed against it retries at the same instant and knocks it over again. That's the thundering herd. Jitter spreads them out.
  9. No misfire policy. The first time a laptop sleeps overnight, a fixed-rate job fires hundreds of times in a row on wake-up, or the opposite happens and a one-off job silently never runs. Pick a policy per job and make it visible.
  10. Using DelayQueue or PriorityBlockingQueue and calling it thread-safe. Each operation is safe. The sequence "pop, check liveness, check capacity, mark running" isn't. You still need a lock around the compound operation.
  11. Removing cancelled jobs from the heap by search. It's O(n) per cancel. Lazy deletion, skipping stale entries when they're popped, is O(log n) and simpler.
  12. Treating cancel as "kill the thread". Java's Thread.stop now just throws, because it used to leave locks and data in broken states. Python and Node can't kill a running function at all. Cancellation is cooperative: set a flag and let the task check it.
  13. Ignoring shutdown. Without a graceful shutdown, a deploy kills a job halfway through an email batch, and the test suite leaks threads between tests.
  14. Making the scheduler a Singleton. Tests then share state, and you can't have one scheduler for emails and another for reports.

11. Interview follow-ups

"Why a binary heap? What's the complexity?" schedule is O(log n), popping the next due job is O(log n), and peeking at the next due time is O(1). With lazy deletion, cancel is O(1) plus a later O(log n) pop. A sorted list would make insertion O(n). For millions of timers with low precision, a timing wheel gives O(1) insert and expiry by bucketing timers by tick. Netty's HashedWheelTimer is a single wheel, and Kafka's request purgatory uses a hierarchical one. It's worth naming, and it's overkill below a few hundred thousand jobs.

"Fixed rate or fixed delay: when would you use each?" Fixed rate when the job is tied to the clock: sample a metric every 10 seconds, poll every minute. Fixed delay when the job must not hammer something: wait 30 seconds after each sync of a remote API, however long the sync took. A slow fixed-rate job runs back to back (or coalesces). A slow fixed-delay job just runs less often. If in doubt, fixed delay is the safer default for jobs that call other services.

"How does the dispatcher know when to wake up?" It sleeps on a condition variable with a timeout of head.at - now, capped at one second. schedule(), a finished run and shutdown() signal the condition. A wake-up never trusts its reason. It just recomputes what's due and how long to sleep.

"What if the system clock jumps?" Use two clocks. Intervals (after(5s), fixed rate and fixed delay) should be measured on a monotonic clock (System.nanoTime, time.monotonic, performance.now), which never jumps. Cron times are wall-clock times by definition and should be recomputed from the wall clock. The simple design here uses one wall clock for both and caps each sleep at one second, so a jump causes at most a second of lateness. A forward jump makes everything late at once, and the misfire policies then decide what happens. Clock synchronization covers why wall clocks jump.

"How would you support time zones and daylight saving in cron?" Search in the job's zone instead of UTC (ZonedDateTime in Java, zoneinfo in Python). Then decide the two DST edge cases explicitly. In the spring-forward gap, 02:30 doesn't exist, and most schedulers run it at 03:00 or skip it. In the fall-back overlap, 01:30 happens twice, and most run it once, on the first pass. Write tests for both dates. This is where real cron libraries have most of their bugs.

"What happens if a job never returns?" It holds a worker forever. With enough of them, the pool is exhausted and nothing else runs. Defences: a per-job timeout that sets the cancellation flag (and interrupts the thread in Java), a separate pool for jobs known to be slow, and a RUNNING duration metric that alerts. You can't forcibly stop it in Python or Node, which is a strong argument for timeouts on every I/O call inside jobs.

"Why not just use ScheduledExecutorService?" In production Java, you often should. It gives you a heap, a pool, fixed rate, fixed delay and no overlap. It doesn't give you cron, retries with backoff, misfire policies, events, an injectable clock or per-type limits. That gap is exactly this design, and many teams build a thin layer like it on top of the JDK executor.

"How would you make jobs survive a restart?" Persist each job's definition and its next fire time in a table: an id, a task type name plus serialized arguments (because you can't persist a closure), the trigger spec and the next run time. On startup, load them and apply the misfire policy to anything overdue. Every state change is written before it takes effect. At that point the Command needs a registry from type names to factories, which is the change Quartz made. Background job patterns covers the outbox and the durable queue designs around this.

"Two instances of the service run this scheduler. The nightly report now runs twice. What do you do?" That's the boundary of the in-process design. Options, from simplest: elect one instance to run scheduled jobs (leader election). Or take a lock per occurrence, keyed by job and scheduled time, with a lease, before running (leases and fencing). Or move scheduling to a database row that instances claim with SELECT ... FOR UPDATE SKIP LOCKED. Or use a workflow engine. Background job systems compared lists the off-the-shelf choices. Whichever you pick, the job should still be idempotent.

"How do you test the dispatcher thread itself?" Mostly you don't need to, because it only calls the same runDue() the tests call. One integration test with the real clock checks the wake-up behaviour with a generous upper bound. Timing assertions with tight bounds are how flaky tests are born.

"Can the retry policy decide based on the error?" Yes. It already receives the error. A policy that retries ConnectionError and TimeoutError but gives up immediately on ValueError (a bad payload won't get better) is a three-line wrapper around ExponentialBackoff. Retrying non-transient errors only delays the alert.

"How many workers should the pool have?" For I/O-bound jobs (emails, HTTP calls, database queries), more than the number of cores, bounded by what the downstream systems tolerate. That's often the real limit, and it's what extension B is for. For CPU-bound jobs in Java, about the number of cores. In Python, CPU-bound jobs need processes, not threads, because of the GIL, so a ProcessPoolExecutor would replace the thread pool (with picklable tasks). In Node, CPU-bound jobs belong in worker threads, or they block the event loop that the scheduler itself runs on.