The Completely Fair Scheduler's core idea: every runnable task accumulates "virtual runtime" (vruntime) roughly proportional to the CPU time it's actually used, and the scheduler always runs whichever task has the smallest vruntime -- i.e. whichever task has fallen furthest behind. Real CFS keeps its runqueue as an augmented red-black tree (cfs_rq->tasks_timeline in kernel/sched/fair.c) ordered by vruntime, specifically so "find the minimum" and "insert" both stay fast even with thousands of runnable tasks.

You don't need a hand-rolled red-black tree for this exercise -- a binary heap gives you the same O(log n) insert / O(log n) pick-and-reinsert behavior with far less code, while preserving the one property that actually matters: whoever has the smallest vruntime always runs next. This exercise uses Python's built-in heapq for exactly that reason -- it's modeling CFS's vruntime-ordering property, not literally reimplementing a red-black tree.

The missing link: removing a task that isn't at the top

A runnable task can block (I/O wait, a syscall, exit) at any moment, and it has to leave the runqueue right then -- not just whenever it happens to reach the top. But a binary heap only gives cheap access to the MINIMUM element; finding and removing an arbitrary task buried somewhere in the middle would cost O(n), since there's no index from task_id to its position. Real schedulers (and this exercise) solve this with lazy deletion: mark the task as gone in a side set, and only actually pop it out of the heap once it would otherwise have surfaced to the top on its own. pick_next() and run_slice() both need this same "skip anything marked removed, right at the top" check before they can trust heap[0].

CFSRunqueue.enqueue(task_id, vruntime) (given) adds a new task with a starting vruntime. Implement:

• dequeue(task_id) -- the task blocks or exits and must leave the runqueue, even if it's currently buried deep in the heap. A task_id that was never enqueued (or was already dequeued) is a no-op. (This exercise doesn't model reusing a task_id after it's been dequeued.)
• pick_next() -- return (without removing) the task_id with the smallest vruntime among tasks still actually in the runqueue -- the task CFS would run next. Return None if the runqueue is empty (or everything left in it has been dequeued).
• run_slice(vruntime_delta) -- run the task pick_next() would return for one time slice: remove it, add vruntime_delta to its vruntime (how much running for that slice cost it), and reinsert it at its new position. Return the task_id that ran, or None if the runqueue was empty.

Example

rq = CFSRunqueue()
rq.enqueue("a", 0)
rq.enqueue("b", 10)
rq.run_slice(3)     # -> "a" (smallest vruntime); a's vruntime is now 3
rq.pick_next()      # -> "a" (3 is still < 10)
rq.dequeue("a")     # a blocks on I/O
rq.pick_next()      # -> "b" (the only one left)

Constraints

• Ties (equal vruntime) break by insertion/reinsertion order -- whichever task got its current position in the heap first wins the tie.
• run_slice must actually remove-then-reinsert the task (not just mutate its vruntime in place) -- its position relative to every other task needs to be re-evaluated after the update, exactly like a real tree rebalance after a key changes.

Real-world grounding

• CFS's vruntime-ordered runqueue: kernel/sched/fair.c (see cfs_rq->tasks_timeline, an rb_root_cached keyed on vruntime, and rb_leftmost for O(1) access to the minimum). Modern kernels layer EEVDF (Earliest Eligible Virtual Deadline First) scheduling logic on top of this same vruntime-ordered tree -- the file still literally contains the structure this exercise models, even though the pick-next rule it now implements is a refinement of plain "always pick the global minimum."

A real red-black tree keeps insert/delete/find-min all at guaranteed O(log n) even under adversarial insertion patterns, which is why the kernel uses one instead of a heap (a heap's run_slice-equivalent operation -- decrease-then- reinsert-a-key -- is also O(log n), but a red-black tree additionally supports efficient "find the task just left/right of this one," which CFS's scheduling logic also relies on). The property this exercise actually tests -- always run the minimum, re-rank in O(log n) after each run -- is the part that carries over exactly.