◷

Timer Scheduler

LLDAdvanced45 minData structures Concurrency

All changes saved Not started

Timer Scheduler · Analysis · designlab

Analysis

Reason about the problem

Approach

Turn it into a plan

Solution

The complete design

01 · Frame the problem

Understand the central challenge

Design a single-process timer scheduler for one-shot callbacks. Tasks can cancel or reschedule while the dispatcher waits. Callbacks may throw or schedule more timers.

Timer semantics depend on monotonic deadlines and a precise cancellation boundary. Analyse rescheduling, stale heap entries and callbacks that reenter the scheduler before choosing the dispatcher mechanism.

02 · Find the design pressure

Start simple, then identify the gap

Begin with a deadline heap and generation-tagged timer records. Removing arbitrary heap entries is avoidable if stale generations are rejected. Claim callbacks under lock and invoke them outside it, distinguishing cancellation before start from work already running.

Use a min-heap of monotonic deadlines and generation-tagged timer records. A dispatcher condition loop claims due callbacks under lock and invokes them outside the lock with explicit cancellation semantics. Schedule creates an active timer and pushes (deadline, insertionSequence, id, generation). Equal deadlines follow insertion order; relative delays become monotonic deadlines once. Reschedule increments generation and pushes a new entry. Cancel transitions an unclaimed active record to canceled. Wake the dispatcher whenever the effective earliest deadline may change. The dispatcher skips stale entries, waits until the live earliest deadline and atomically claims a due callback. Cancel after claim returns TooLate. The callback runner invokes outside the lock and reports exceptions separately. Shutdown stops new admission, wakes waits and cancels pending timers under this policy. Claimed callbacks finish/cooperatively stop; obsolete heap entries are periodically compacted to bound memory.

03 · Define success

Requirements to preserve

Use monotonic deadlines and deterministic tie ordering.
Wake the dispatcher when the earliest deadline changes.
Reject stale canceled/rescheduled generations.
Invoke callbacks outside the scheduler lock and define shutdown.

04 · Identify the correctness boundary

Invariants, representation and mutation boundaries

Heap entries carry identity and generation, allowing cancelled/rescheduled stale entries to be ignored. Claim callbacks under the lock but invoke them outside it so callbacks can safely schedule more timers. Cancellation distinguishes not-yet-started work from a callback already executing; it cannot rewind an external side effect.

05 · Make it concrete

Reason through a worked example

Timer T is scheduled for 10, then rescheduled for 20. Its old heap entry at 10 is discarded by generation comparison. If cancellation races callback claiming, the contract determines which wins. A callback adding an immediate timer does not deadlock by reentering a held scheduler lock.

Continue to the approach Try my own design