Lab L08 · Java + Go

Implementing a delayed task scheduler

Build a timer queue. Callers register a callback under an id with a due time, can replace or cancel it while it is still pending, and a driver calls runDue(now) to execute every callback whose due time has arrived, earliest first. Scheduling an id that is already pending replaces it, so there is at most one pending task per id.

The task

A dispatch service offers a ride to a driver and gives them 15 seconds to accept. Each offer schedules a timeout keyed by trip id. If the driver accepts, the timeout is cancelled; if the offer moves to another driver, the same trip id is rescheduled with a new deadline. When the timeout fires, the callback re-dispatches the trip. Tests drive time manually with runDue(now); production would run the optional run(clock) loop on one owner thread.

Everything left of now is claimed in one locked step and then executed outside the lock; everything right of it stays pending. The ghost at 10 shows that rescheduling a moved its single entry.

What you implement

public final class DelayedScheduler {
    public DelayedScheduler(int capacity);                    // max pending ids
    public void schedule(String id, long due, Runnable run);  // add, or replace the pending task with this id
    public boolean cancel(String id);                         // true if it was pending
    public OptionalLong next();                               // earliest pending due time
    public int runDue(long now);                              // run every task with due <= now; returns count
    public void run(LongSupplier now) throws InterruptedException;  // optional loop; stop by interrupting
}

Rules

One pending task per id: scheduling a pending id replaces its due time and callback atomically.
A new id while capacity tasks are pending → IllegalStateException. Replacing an existing id is allowed at capacity.
runDue(now) removes every task with due <= now under the lock, then runs their callbacks after releasing it, in due order. Callbacks can therefore call schedule/cancel without deadlocking.
cancel only affects pending tasks. Once runDue has claimed a task, cancel returns false and cannot stop it.
next() is empty when nothing is pending. Due times are plain longs in caller-chosen units.
run(now): loop forever — run due tasks, then wait until the next due time or until schedule/cancel wakes it; exit with InterruptedException when interrupted.
Data structure: a map id → task plus a min-heap ordered by due time that supports removal by id (the reference uses an indexed heap; a TreeSet of (due, id) also works).

Worked example

schedule(a, 10), schedule(b, 5), schedule(a, 3) → a now due at 3 (replaced, not duplicated).
next() → 3. runDue(4) → runs a, returns 1.
cancel(b) → true. runDue(100) → 0. cancel(b) → false.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: DelayedScheduler.java · tests: DelayedSchedulerTest.java. Go starter: scheduler.go · tests: driver_test.go, scheduler_test.go.

cd java
./gradlew test --tests 'labs.scheduler.*'

cd go
go test -race -count=1 ./scheduler

Reveal the reference solutions

Java: DelayedScheduler.java
Go: scheduler.go

When to use

Use this lab for a deterministic scheduling core driven by an external owner. Schedule a callback under a string identity and a signed-integer due time in caller-selected units. A positive capacity bounds pending identities. Scheduling the same pending identity replaces its due time and callback atomically. Cancellation removes only pending work. Query the next deadline, then explicitly run work due at or before a supplied time.

The pending queue is an indexed binary heap with one entry per identity. Choose manual drive for deterministic tests or run one owned driver with a monotonic nanosecond source. Go stops through context cancellation; Java stops through interruption. Join the driver before releasing dependencies. There is no durable queue, forced callback termination, or automatic retry.

Steps

Define pending versus claimed. Run-due takes a snapshot under a lock, ordered by due time and then identity, and removes those tasks before invoking callbacks. A concurrent cancellation cannot recall a task already claimed. Rescheduling the same identity after claiming creates new pending work, not an edit to the old callback.
Keep callbacks outside the lock. A callback may schedule another task without deadlocking the component. Newly scheduled work is not part of the current snapshot even if already due, so one invocation cannot loop forever on a self-rescheduling callback.
Expose failure policy. Callback failures propagate to the caller. Because the whole snapshot is claimed first, later callbacks in that snapshot will not run if an earlier one fails. This is deliberately not an at-least-once executor; use task-level failure isolation or an owned worker pool if every claimed callback needs its own outcome.
Own wakeup races. Go retains a buffered wake notification across the check-to-wait boundary and selects between that notification, the timer, and cancellation. Java checks and waits under the same monitor used to schedule and notify. Tests insert an immediately due task ahead of a distant deadline and verify execution and joined termination. Timer execution is not a hard real-time guarantee.
Test the execution clock. Schedule A at ten and B at twenty; move A to thirty and verify the next deadline changes. Cancel B, add a same-deadline B, and verify deterministic identity ordering. Have B schedule C while executing and verify C runs only on the next drive call.
Preserve the indexed invariant. Schedule, reschedule, and cancellation take O(log n) heap work; next-deadline is O(1); claiming m tasks costs O(m log n). Every swap updates key positions. Randomized queue tests compare update/removal behavior with a map oracle and check heap/index agreement after every operation. No stale heap entries accumulate.

Checklist

Recall and variation

Rebuild indexed cancellation before reading Go or Java. Variation: move the root's deadline later, then cancel a non-root task. Acceptance: heap and key positions still agree and the driver wakes for a newly earlier task.

Pending and claimed tasks have distinct cancellation behavior
Rescheduling does not leak additional pending entries
Equal deadlines have deterministic order within a claimed snapshot
Callback failure and reentrant scheduling semantics are explicit
The external owner supplies a tested wakeup and completion protocol

Signals

Working: driving the same schedule with the same times produces the same callback sequence.

Going wrong: a cancelled pending task still runs, a callback deadlocks while rescheduling, or a manual drive loop is presented as proof of real-time execution. Concurrent drive calls can run different claimed snapshots concurrently; use one owner if serialized callbacks are required.

Implementing a Bounded Worker Pool, for executing claimed work with observed outcomes.