8. Runtime Scheduling

Event Loop with Timers

midconcurrencydata-structures

A single-threaded event loop's timer mechanism decides which callback fires next purely by comparing scheduled fire times -- no real clock involved in this exercise, which is exactly what makes it deterministic and testable. time here is an explicit value the caller controls throughout.

schedule(delay, callback_id) (given) registers a timer to fire at self.current_time + delay -- delay is relative to whenever schedule() is CALLED, not a fixed origin.

Implement EventLoop.run_until(target_time): advance the virtual clock to target_time, firing (returning, in order) every timer whose fire time is <= target_time.

  • Timers fire in fire-time order.
  • Ties (identical fire times) break by scheduling order -- whichever schedule() call happened first fires first.
  • Fired timers are removed from self.timers.
  • self.current_time advances to target_time before returning.

Example

loop = EventLoop()
loop.schedule(10, "late")
loop.schedule(3, "early")
loop.schedule(7, "middle")
loop.run_until(10)   # -> ["early", "middle", "late"]

Constraints

  • A timer scheduled AFTER a run_until call measures its delay from the NEW current_time, not from 0 -- see the last test.
  • A timer not yet due must be left in self.timers untouched, to potentially fire on a later run_until call.

Real-world grounding

  • Node's timer implementation (a similar "list of due callbacks, sorted by fire time" structure, backed by libuv underneath): lib/internal/timers.js

Real event loops also have to interleave timers with I/O readiness and other event sources, and libuv specifically uses a more efficient data structure (a min-heap) than a linear scan for large numbers of timers -- but "find what's due, fire it in time order" is the core operation underneath all of it.

hints
event_loop.pysign in to run
Loading...
test result

This is a preview. Sign in to run this exercise against the real tests.