โ Final Challenge
โบ A Mini Runtime with a Virtual Clock
80 ptsTime to combine everything. One piece of the real scheduler remains: time.
When a goroutine calls time.Sleep, the runtime doesn't spin and doesn't
dedicate a thread. It puts a timer into the P's timer heap (a min-heap
ordered by expiry) and parks the G. findRunnable checks the heap on every
pass; and when an M finds nothing runnable anywhere, it computes the delay
until the earliest timer and sleeps in the netpoller with exactly that
timeout. The scheduler literally fast-forwards to the next interesting
moment. Timers, network readiness, and run queues all merge into one
question: what runs next, and if nothing, how long until something does?
Your mini runtime does the same โ but on a virtual clock, which is what
the real runtime would use if it could: no waiting, just jump now to the
next deadline. Virtual time makes the runtime fully deterministic (and is
exactly how simulation testing frameworks and the Go playground's fake time
work: sleep a virtual year, finish in a millisecond).
type Runtime struct { /* ... */ }
type Task struct { /* ... */ }
func New() *Runtime
func (r *Runtime) Go(f func(t *Task)) // register a task
func (r *Runtime) Run() // drive everything to completion
func (r *Runtime) Now() int // current virtual time, in ticks
func (t *Task) Yield() // back of the run queue
func (t *Task) Sleep(ticks int) // park until Now() >= wake-up time
Exact semantics โ the tests assert precise traces, so follow these to the letter:
Rundrives a FIFO run queue, seeded with tasks inGo-call order. Exactly one task executes at any instant (lesson 4's handoff pattern);Runreturns when no tasks remain, runnable or sleeping.Yieldmoves the calling task to the back of the run queue.Sleep(n)withn > 0parks the task with wake-up deadlineNow() + n.Sleep(n)withn <= 0is equivalent toYield.- The clock only advances when the run queue is empty and at least one
task is sleeping: set the clock to the earliest pending deadline, then
move every task whose deadline has arrived (
deadline <= Now()) to the run queue โ multiple tasks waking at the same tick enter the queue in spawn order (the order theirGocalls happened). Gomay also be called from inside a running task: the new task goes to the back of the run queue (it first runs at the current virtual time) and takes the next spawn-order index.- The clock starts at 0, never advances while anything is runnable, and
Now()remains correct afterRunreturns.
Implementation notes: this is lesson 4's scheduler plus a sleepers
collection. The task-side Sleep records its deadline (reading r.now from
a task is safe โ the scheduler is parked while you run, and the channel
handoff orders the accesses), marks itself sleeping, and does the usual
park-send / resume-receive. The scheduler-side loop is:
for {
// 1. drain the run queue (tasks may yield back into it, spawn, sleep)
// 2. no runnable and no sleepers? -> return
// 3. now = earliest deadline; wake all due sleepers in spawn order
}
No real time anywhere: a task that sleeps a million virtual ticks completes instantly โ and the tests check exactly that.
Log in to submit a solution and earn points.