โ˜… Final Challenge

โ€บ A Mini Runtime with a Virtual Clock

80 pts

Time 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:

  1. Run drives a FIFO run queue, seeded with tasks in Go-call order. Exactly one task executes at any instant (lesson 4's handoff pattern); Run returns when no tasks remain, runnable or sleeping.
  2. Yield moves the calling task to the back of the run queue.
  3. Sleep(n) with n > 0 parks the task with wake-up deadline Now() + n. Sleep(n) with n <= 0 is equivalent to Yield.
  4. 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 their Go calls happened).
  5. Go may 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.
  6. The clock starts at 0, never advances while anything is runnable, and Now() remains correct after Run returns.

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.