Machine-coding case study
Task scheduler
The test is still sleeping. You scheduled a job for T0 plus five seconds, then called Thread.sleep(60_000) so the wall clock could catch up. Cancel never ran cleanly. A slow job on the same thread delayed every later task.
That is the whole problem this page solves. A task scheduler runs jobs at a due , optionally on a period, and supports cancel. The structure is a of due times plus workers that wait for the next job. This is in-process machine coding: a min-heap and a pool, not a distributed cron fleet.
Two roles, two seams
Priority queue ordered by due Instant so the dispatcher takes the next job.
Run work off the heap so a slow job cannot delay later tasks.
and
Inject both so tests freeze time and swap the pool.
Drain due tasks on the test thread instead of sleeping.
What actually happens when a job becomes due
The sleep story above is the naive loop. Each task has an id, a runnable (the work to run), a due , and optionally a period. Cancellation is removing from the or marking a flag the worker checks. What is ordered by time, and who is allowed to run the job, are two different questions. Keeping those two roles apart is the design.
Inject and . Tests schedule a job, advance the clock, and assert it ran once. Sleeping until the deadline in a unit test is not a design: it blocks cancel and makes CI wait on the wall clock (see Numbers to know below). See thread pools and deterministic design.
A object for the job gives you logging, but the heap is the main idea. Do not hide the priority queue behind a List you scan every tick unless you say it is a first draft for tiny N. Shutdown: stop accepting, drain or cancel, await workers. A scheduler that cannot stop is a process leak.
Simple rule of thumb
Once you can name the heap and the pool, three habits keep sleep out of the domain and cancel testable.
1. Heap for when, pool for run. A takes the head of the when says it is due, then submits to the . One thread that both waits and runs long jobs delays every later task.
2. Freeze time; do not sleep. Prefer : schedule, advance a FakeClock, drain due tasks, assert. Production waits on the queue with a timeout derived from Clock. Both share the heap.
3. Say cancel and overlap out loud. Cancel sets a flag the dispatcher checks before submit. A running job is interrupt versus let-finish; pick one. is skip if the last run is still going, or queue another.
Rule of thumb
Order due times on the heap. Run work on the pool. Inject Clock and Executor. tick() in tests. Sleep in the domain is how you fail cancel and CI.
From problem to mechanism
Here is the sleeping test again, slowed down so you can see where the loop fails and what each type is for.
Problem. Run jobs at a due , optionally on a period, and support cancel. Sleeping in a loop until the deadline blocks cancel and makes tests wait on the wall clock.
Naive system. One thread sleeps until due, then runs the job itself. Time comes from the wall clock. Cancel tries to interrupt a sleeping thread. Tests call Thread.sleep (see Numbers to know below).
Break it. You cannot cancel a sleeping thread cleanly, and tests freeze. A slow job delays every later task. Periodic reschedule from wall clock inside the job lets drift accumulate.
Mechanism. A of due Instants. takes the head when says it is due and submits to the . Cancel is a flag checked before submit. Shutdown stops the dispatcher and the pool so threads do not leak. Periodic uses due.plus(period) from the scheduled time, not wall clock inside the job.
The diagram below is that split: the dispatcher waits; workers run. A long job must not block the heap.
Read the diagram definition
sequenceDiagram
participant S as Scheduler
participant Q as Priority queue
participant D as Dispatcher thread
participant W as Worker pool
participant Clock as Clock
S->>Q: offer(task, due)
D->>Clock: now
D->>Q: take when due
D->>W: submit(job)
Note over W: long job must not block the heapWho owns which job
The mechanism names four types. This table is the responsibility split you defend in an interview: the waits; the runs.
| Type | Job |
|---|---|
| ScheduledTask | Holds id, due , job, optional period, and cancelled. Tasks are ordered by due Instant on the . |
| TaskScheduler | API: schedule, cancel, shutdown. It owns the delay queue. |
| Dispatcher | Waits until the next due time (or in tests), submits to a pool, and skips cancelled tasks. |
| ExecutorService | . Inject it so tests can use a direct executor (run on the calling thread). |
Java API sketch
The sketch matches the table: ScheduledTask compares by due Instant, TaskScheduler owns the PriorityBlockingQueue (thread-safe earliest-due queue), and cancel only sets a flag.
class ScheduledTask implements Comparable<ScheduledTask> {
final TaskId id;
final Instant due;
final Runnable job;
final Duration period; // null if one-shot
volatile boolean cancelled;
public int compareTo(ScheduledTask o) { return due.compareTo(o.due); }
}
class TaskScheduler {
private final Clock clock;
private final ExecutorService workers;
private final PriorityBlockingQueue<ScheduledTask> due = new PriorityBlockingQueue<>();
private final ConcurrentHashMap<TaskId, ScheduledTask> byId = new ConcurrentHashMap<>();
TaskId schedule(Instant when, Runnable job) {
ScheduledTask t = new ScheduledTask(TaskId.next(), when, job, null);
byId.put(t.id, t);
due.offer(t);
return t.id;
}
void cancel(TaskId id) {
ScheduledTask t = byId.get(id);
if (t != null) t.cancelled = true;
}
void shutdown() {
workers.shutdownNow();
}
}Worked example: five seconds, then tick
Use the sleeping-test story with numbers so you can walk one due job, then a period, without a new type.
Prefer a test API: schedule(t0+5s, job), clock.advance(5s), , assert ran once. Production uses a thread that waits on the queue with a timeout derived from . Both share the .
Periodic: after run, due = due.plus(period) using the scheduled time, not wall clock inside the job, or you drift. Cancel sets a flag the dispatcher checks before submit. A running job is a separate question: interrupt versus let-finish. Shutdown stops the dispatcher, shuts down the pool, does not leak threads.
Numbers to know
- T0 plus five seconds: the due Instant the FakeClock must cross before tick runs the job.
Thread.sleep(60_000)is the anti-pattern: cancel blocks and CI waits.- Reschedule with due.plus(period) from the scheduled Instant, or drift accumulates.
Invalid cases, races, and what still breaks
The walkthrough assumes a valid due Instant and a split dispatcher. These are the inputs and roles that reject a design, plus the follow-ups interviewers add after the heap works.
Invalid cases
- Sleep until due inside the domain: you cannot cancel cleanly, and tests freeze.
- One thread waits and runs long jobs: a slow job delays every later task.
- Cancel that does not stop a running job: say "do not start" or "interrupt."
- Periodic reschedule from wall clock inside the job: use Clock plus period, or drift accumulates.
schedule(null, job)or a past due without a policy: reject or run immediately; pick one.
Concurrency
PriorityBlockingQueue plus a thread is the usual picture. Workers must not mutate the except through schedule or cancel. For tests, a that drains due tasks on the test thread avoids real waiting. See producer-consumer.
What the follow-up changes
- Cron-like calendars: a next-due function, still a heap of Instants.
- Skip if previous still running: model that as an object.
- wrapper: logging around the Runnable; the heap stays unchanged.
Trade-offs
- Sleep until due is simple, but cancel is ugly and tests freeze.
- One wait-and-run thread is smaller, but a slow job delays later tasks.
- Scan a List every tick only for tiny N, and only if you said so.
Tests that prove the seams
After the split and the flag, this test is the seam you keep: inject and a direct , then before and after advance (see Numbers to know above). Periodic and shutdown can wait until this is green.
@Test
void runsWhenClockAdvances() {
FakeClock clock = new FakeClock(T0);
AtomicInteger n = new AtomicInteger();
TaskScheduler s = new TaskScheduler(clock, Runnable::run);
s.schedule(T0.plusSeconds(5), n::incrementAndGet);
s.tick();
assertEquals(0, n.get());
clock.advance(Duration.ofSeconds(5));
s.tick();
assertEquals(1, n.get());
}Wrap-up
You have the failure, the heap-versus-pool split, and the clock seam. Use the forty-five minute split to practise, then follow the related notes for pools, queues, and frozen time.
How to spend forty-five minutes
- 0–8schedule plus tick plus FakeClock so the job runs once.
- 8–20cancel before due so the job does not run.
- 20–32periodic reschedule with due.plus(period) from the scheduled time.
- 32–40say the pool versus dispatcher split out loud.
- 40–45shutdown the dispatcher and pool with no leaked threads.
Read next
You're done when
Tasks run at or after their scheduled Instant under an injected Clock, recurring tasks reschedule correctly, cancellation prevents execution, and the worker does not busy-spin (loop without waiting) without a wait/notify or delay queue story. Sleep until due is not a scheduler; a heap of due times plus a worker pool is.