The Scheduler

What is a scheduler, and why does it matter?

The GPU is enormously powerful, but expensive and finite. Left unmanaged, it would sit idle between requests, or waste cycles waiting for a slow request while others queue up. The scheduler's one job is to make sure the GPU is always working — processing the right set of requests at every moment, no idle time, no wasted capacity.

This analogy captures the core insight: the old way (static batching) wastes capacity by holding fixed seats for the full journey. The new way (continuous batching) recycles seats the moment they free up. The rest of this chapter explains exactly how nano-vLLM implements the new way.

The problem with waiting for everyone

What is a "batch"?

A batch is a group of requests processed together in a single GPU forward pass. GPUs are designed for parallel computation — running 10 requests simultaneously is barely slower than running 1, up to the hardware limit. So the goal is always to process as many requests as possible at once. The question is: which requests, and when?

Static batching — the old approach

In static batching, a fixed batch of requests is assembled once and processed together from start to finish. Every request in the batch must complete before any new requests can join. If you start with 8 requests and 3 finish early, the GPU processes a batch of 5 for the rest — with 3 slots sitting empty.

Why is this bad? Consider a real scenario: Request A generates 500 tokens (a long essay). Requests B–H each generate 10 tokens (short answers). B–H finish quickly, but the entire batch is held open until A finishes its 500th token. The GPU runs at partial capacity — maybe 15% utilisation — for 490 token steps while waiting for A.

Continuous batching — the key idea

Continuous batching treats the set of running requests as a living, breathing pool. After every single decode step, the scheduler checks: did anyone finish? If yes — free their blocks immediately and pull in the next waiting request. The batch composition changes at every step. No request holds a "seat" beyond what it needs right now.

A request's lifecycle — four states

Every request in nano-vLLM is a Sequence object → Ch.02 with a status field. This status is a state machine — a formal way of saying the request can only be in one of four defined states, and transitions between them follow strict rules. The scheduler reads and writes this status on every step.

A state machine is like a traffic light: it can only be red, yellow, or green — never two at once — and it can only change in specific ways (red → green, not red → yellow). State machines make complex behaviour predictable and debuggable. Here are the four states a request moves through:

What the scheduler does on every single step

The scheduler's schedule() method is called once per engine step → Ch.02 — which means once per generated token across the entire running batch. It executes five actions in a fixed order. Understanding this order is the key to understanding the whole system.

Step through the scheduler — see every decision

Click Run One Step to advance the scheduler one step at a time. Watch requests move between the waiting queue and running set, blocks allocate and free, and states transition. The event log explains every decision the scheduler makes.

Preemption — when memory runs out

What happens if the GPU runs out of free KV cache blocks while sequences are still generating? The scheduler can't crash — that would mean every user's request fails. Instead, it uses preemption to recover gracefully.

What preemption means

Preemption means pausing a currently-running sequence mid-generation, freeing its KV cache blocks back to the pool, and moving it back to the WAITING queue. Its blocks are gone — the KV data is lost. When the sequence gets re-scheduled later, it must re-run its prefill phase from scratch to rebuild its KV cache.

The preemption cost — why it's a last resort

Preemption is expensive for two reasons. First, the evicted sequence must redo its entire prefill phase when re-scheduled — which might be hundreds of tokens of GPU compute. Second, it adds latency for the affected user. The scheduler tries to avoid preemption by promoting waiting requests conservatively — only adding new requests if there's clearly enough memory for them to run to completion without triggering preemption.

The scheduler in code

Here is nano-vLLM's schedule() method, annotated step by step. Notice how short it is — the complexity lives in the BlockManager, not here.

def schedule(self) -> SchedulerOutput:
    # ── STEP 1: collect finished sequences and free their blocks ──
    finished = [s for s in self.running if s.is_finished()]
    for s in finished:
        self.block_mgr.free(s)      # return blocks to free list immediately
        self.running.remove(s)

    # ── STEP 2: append a new slot for every decoding sequence ──
    # Each decode step needs space for 1 new token's K and V vectors
    for s in self.running:
        if not s.is_prefill:
            ok = self.block_mgr.append_slot(s)
            if not ok:
                self._preempt(s)    # no free blocks → preempt this sequence

    # ── STEP 3: promote waiting → running while blocks are available ──
    promoted = []
    while self.waiting:
        seq = self.waiting[0]         # peek at the front of the queue
        if self.block_mgr.allocate(seq):
            self.waiting.pop(0)       # remove from waiting queue
            self.running.append(seq)  # add to running set
            promoted.append(seq)
        else:
            break                      # no memory for this request — stop trying

    # ── STEP 5: return split batch to the engine ──
    return SchedulerOutput(
        prefill=[s for s in self.running if s.is_prefill],
        decode =[s for s in self.running if not s.is_prefill],
    )

def _preempt(self, seq: Sequence) -> None:
    # Emergency valve: free this sequence's blocks and send it back to waiting
    # It will re-run prefill from scratch when re-scheduled
    self.block_mgr.free(seq)          # return all blocks to free list
    seq.output_tokens = []             # discard generated tokens so far
    seq.status = SequenceStatus.WAITING
    self.running.remove(seq)
    self.waiting.appendleft(seq)     # push to front of queue (high priority)

What continuous batching enables

Things beginners get wrong about the scheduler

Quiz

Three questions to test your understanding of the scheduler. Wrong answers explain exactly why they're wrong.

What you now know