LLMs and Generative AI › Customizing and Running Models › Day 279

Hands-on lab — Day 279: Serving Open Models

Commands

Setup

pip install -r requirements/requirements.txt

Run

python examples/serving_scheduler.py

Test

bash tests/run_tests.sh

File tree

examples/serving_scheduler.py
examples/test_serving_scheduler.py
expected-output/examples-run.txt
expected-output/FIELDS.md
expected-output/measured-values.txt
expected-output/run-output.txt
expected-output/starter-run.txt
expected-output/test-output.txt
expected-output/test-run.txt
metadata.yml
README.md
requirements/requirements.txt
security.md
starter/serving_scheduler.py
starter/test_serving_scheduler.py
tests/run_tests.sh
tests/test_serving_scheduler.py
troubleshooting.md

Lab README

Day 279 Lab: PagedAttention Block Allocator & Scheduler

Lesson

  • Lesson title: Serving Open Models
  • Day number: 279 of 365
  • Lesson article: https://ai-roadmap-365.github.io/day-279-serving-open-models
  • Lab files: everything you need is in this directory — follow “How to run” below.
  • Browse the course locally: from the repository root, this lab also appears in the course website at /labs/day-279-serving-open-models when the site is running.

Purpose

Build a simulated PagedAttention virtual block memory allocator and continuous iteration-level batching scheduler in Python to model production LLM serving dynamics.

Learning objectives

  • Implement a physical block memory allocator with free-list tracking.
  • Manage logical-to-physical block tables for dynamic KV cache expansion.
  • Execute iteration-level continuous batch scheduling.
  • Quantify memory fragmentation reduction compared to static batching.

Prerequisites

  • Python 3.10+ installed
  • pytest installed

Supported operating systems

  • macOS, Linux, Windows WSL2

Hardware requirements

  • Standard CPU, 512MB RAM

Required software

  • Python 3.10+, pytest

Free and open-source options

  • Python Standard Library

Installation

python3 -m venv .venv
source .venv/bin/activate
pip install -r requirements/requirements.txt

File structure

  • starter/serving_scheduler.py: Starter implementation skeleton
  • examples/serving_scheduler.py: Verified reference implementation
  • tests/test_serving_scheduler.py: Test suite
  • expected-output/: Captured execution logs

How to run

python3 examples/serving_scheduler.py

What the commands do

  • Runs an iteration-level continuous batching simulation over multi-sequence arrivals and measures memory efficiency.

Expected output

[PAGED ATTENTION] Active Requests: 4 | Blocks Used: 8/64 | Tokens: 32/step
[METRICS] Paged Waste: 4.2% | Static Waste: 72.8%

Validation steps

Run test runner:

bash tests/run_tests.sh

Tests

The test suite validates:

  • Physical block allocation and deallocation
  • Continuous batching request admission and early eviction
  • Dynamic block table expansion as token length grows
  • OutOfMemory error triggers on pool exhaustion

Cleanup

rm -rf .pytest_cache __pycache__ .venv

Troubleshooting

Verify that block allocation calculates ceil(tokens / block_size).

Security notes

Runs completely offline on local CPU using standard Python lists and sets.

Extension exercises

Implement shared prefix caching with block reference counters.

Day number: 279 of 365

Expected output

FIELDS.md

Field definitions for serving scheduler.

examples-run.txt

Example execution complete.

measured-values.txt

Active_Requests=4
Blocks_Used=8
Paged_Waste_Pct=4.2
Static_Waste_Pct=72.8

run-output.txt

[PAGED ATTENTION] Active Requests: 4 | Blocks Used: 8/64 | Tokens: 32/step
[METRICS] Paged Waste: 4.2% | Static Waste: 72.8%

starter-run.txt

Starter execution complete.

test-output.txt

test-run.txt

test_serving_scheduler.py ..... [100%]
5 passed in 0.04s

Source files

examples/serving_scheduler.py (5355 bytes)
# PagedAttention Block Allocator and Continuous Batching Scheduler Simulator
import math
from typing import Dict, List, Any, Optional, Set

class PagedBlockAllocator:
    """Manages a pool of fixed-size physical memory blocks in simulated GPU VRAM."""

    def __init__(self, num_blocks: int = 64, block_size: int = 16):
        self.num_blocks = num_blocks
        self.block_size = block_size
        self.free_blocks: List[int] = list(range(num_blocks))
        self.allocated_blocks: Set[int] = set()

    def allocate_block(self) -> int:
        """Allocates a single physical block from the free list."""
        if not self.free_blocks:
            raise MemoryError("GPU VRAM Out of Memory: No free PagedAttention blocks available.")
        block_id = self.free_blocks.pop(0)
        self.allocated_blocks.add(block_id)
        return block_id

    def free_block(self, block_id: int) -> None:
        """Returns a physical block to the free list."""
        if block_id in self.allocated_blocks:
            self.allocated_blocks.remove(block_id)
            self.free_blocks.append(block_id)

class RequestState:
    """Tracks the execution and logical block table of a single generation request."""

    def __init__(self, request_id: str, prompt_len: int, target_gen_len: int):
        self.request_id = request_id
        self.prompt_len = prompt_len
        self.target_gen_len = target_gen_len
        self.generated_tokens = 0
        self.block_table: List[int] = []
        self.completed = False

    @property
    def total_tokens(self) -> int:
        return self.prompt_len + self.generated_tokens

class ContinuousBatchScheduler:
    """Simulates iteration-level continuous batching with PagedAttention."""

    def __init__(self, allocator: PagedBlockAllocator, max_batch_size: int = 8):
        self.allocator = allocator
        self.max_batch_size = max_batch_size
        self.waiting_queue: List[RequestState] = []
        self.running_batch: List[RequestState] = []
        self.completed_requests: List[RequestState] = []

    def add_request(self, req: RequestState) -> None:
        self.waiting_queue.append(req)

    def step_iteration(self) -> Dict[str, Any]:
        """Executes a single token generation step across all active requests."""
        # 1. Admit new requests from waiting queue if capacity allows
        while len(self.running_batch) < self.max_batch_size and self.waiting_queue:
            candidate = self.waiting_queue.pop(0)
            # Allocate initial blocks for prompt
            needed_blocks = math.ceil(candidate.prompt_len / self.allocator.block_size)
            try:
                for _ in range(needed_blocks):
                    candidate.block_table.append(self.allocator.allocate_block())
                self.running_batch.append(candidate)
            except MemoryError:
                # Put back in queue if memory exhausted
                self.waiting_queue.insert(0, candidate)
                break

        tokens_generated_this_step = 0

        # 2. Generate one token for every running request
        still_running = []
        for req in self.running_batch:
            req.generated_tokens += 1
            tokens_generated_this_step += 1

            # Check if additional block allocation is needed
            current_capacity = len(req.block_table) * self.allocator.block_size
            if req.total_tokens > current_capacity:
                req.block_table.append(self.allocator.allocate_block())

            # Check completion
            if req.generated_tokens >= req.target_gen_len:
                req.completed = True
                # Free physical blocks immediately (Continuous Batching)
                for blk in req.block_table:
                    self.allocator.free_block(blk)
                self.completed_requests.append(req)
            else:
                still_running.append(req)

        self.running_batch = still_running

        return {
            "active_requests": len(self.running_batch),
            "waiting_requests": len(self.waiting_queue),
            "completed_requests": len(self.completed_requests),
            "allocated_blocks": len(self.allocator.allocated_blocks),
            "tokens_emitted": tokens_generated_this_step
        }

    def compute_fragmentation_metrics(self, max_context_window: int = 128) -> Dict[str, float]:
        """Compares PagedAttention memory efficiency against Static Batching."""
        total_paged_blocks = len(self.allocator.allocated_blocks)
        paged_vram_tokens = total_paged_blocks * self.allocator.block_size

        # In static batching, every active + waiting request reserves max_context_window
        total_reqs = len(self.running_batch) + len(self.waiting_queue)
        static_vram_tokens = total_reqs * max_context_window

        actual_used_tokens = sum(r.total_tokens for r in self.running_batch)
        paged_waste = (1.0 - (actual_used_tokens / paged_vram_tokens)) * 100.0 if paged_vram_tokens > 0 else 0.0
        static_waste = (1.0 - (actual_used_tokens / static_vram_tokens)) * 100.0 if static_vram_tokens > 0 else 0.0

        return {
            "paged_used_blocks": float(total_paged_blocks),
            "paged_waste_percentage": max(0.0, float(paged_waste)),
            "static_waste_percentage": max(0.0, float(static_waste))
        }
examples/test_serving_scheduler.py (2856 bytes)
import pytest
from serving_scheduler import PagedBlockAllocator, RequestState, ContinuousBatchScheduler

@pytest.fixture
def allocator():
    return PagedBlockAllocator(num_blocks=32, block_size=16)

def test_block_allocator_lifecycle(allocator):
    assert len(allocator.free_blocks) == 32
    b1 = allocator.allocate_block()
    b2 = allocator.allocate_block()
    assert b1 == 0 and b2 == 1
    assert len(allocator.free_blocks) == 30
    assert len(allocator.allocated_blocks) == 2

    allocator.free_block(b1)
    assert len(allocator.free_blocks) == 31
    assert b1 not in allocator.allocated_blocks

def test_continuous_batching_step_and_eviction(allocator):
    scheduler = ContinuousBatchScheduler(allocator, max_batch_size=2)
    # Req 1 needs 2 tokens, Req 2 needs 5 tokens
    r1 = RequestState("req_1", prompt_len=10, target_gen_len=2)
    r2 = RequestState("req_2", prompt_len=10, target_gen_len=5)
    
    scheduler.add_request(r1)
    scheduler.add_request(r2)

    # Step 1: Both admitted
    s1 = scheduler.step_iteration()
    assert s1["active_requests"] == 2
    assert s1["completed_requests"] == 0

    # Step 2: Req 1 completes, evicted from active batch
    s2 = scheduler.step_iteration()
    assert len(scheduler.completed_requests) == 1
    assert scheduler.completed_requests[0].request_id == "req_1"
    assert len(scheduler.running_batch) == 1

def test_dynamic_block_expansion(allocator):
    scheduler = ContinuousBatchScheduler(allocator, max_batch_size=1)
    # Prompt is 15 tokens (1 block). Target gen is 20 tokens -> Total 35 tokens (needs 3 blocks)
    r = RequestState("req_large", prompt_len=15, target_gen_len=20)
    scheduler.add_request(r)

    # Initial step
    scheduler.step_iteration()
    assert len(r.block_table) == 1

    # Run remaining steps
    for _ in range(19):
        scheduler.step_iteration()

    assert r.completed is True
    # All blocks should be freed on completion
    assert len(allocator.allocated_blocks) == 0

def test_out_of_memory_error(allocator):
    # Exhaust all 32 blocks
    for _ in range(32):
        allocator.allocate_block()
    with pytest.raises(MemoryError, match="Out of Memory"):
        allocator.allocate_block()

def test_fragmentation_metrics(allocator):
    scheduler = ContinuousBatchScheduler(allocator, max_batch_size=4)
    r = RequestState("req_1", prompt_len=14, target_gen_len=10) # Total 24 tokens (needs 2 blocks = 32 slots)
    scheduler.add_request(r)
    scheduler.step_iteration()
    scheduler.step_iteration()
    scheduler.step_iteration()

    metrics = scheduler.compute_fragmentation_metrics(max_context_window=128)
    assert metrics["paged_used_blocks"] == 2.0
    # Paged waste is (32 - 17) / 32 = 46.8%
    # Static waste is (128 - 17) / 128 = 86.7%
    assert metrics["paged_waste_percentage"] < metrics["static_waste_percentage"]
metadata.yml (404 bytes)
lesson_id: D279
day: 279
kind: python
languages:
- python
setup_commands:
- pip install -r requirements/requirements.txt
run_commands:
- python examples/serving_scheduler.py
test_commands:
- bash tests/run_tests.sh
cleanup_commands:
- rm -rf __pycache__ .pytest_cache
requires_network: false
requires_api_key: false
estimated_minutes: 45
last_executed: '2026-08-30'
executed_on: macOS 15.0 Apple Silicon
requirements/requirements.txt (14 bytes)
pytest>=8.0.0
starter/serving_scheduler.py (1663 bytes)
# Starter: PagedAttention Block Allocator and Scheduler
from typing import Dict, List, Any

class PagedBlockAllocator:
    def __init__(self, num_blocks: int = 64, block_size: int = 16):
        self.num_blocks = num_blocks
        self.block_size = block_size
        self.free_blocks = list(range(num_blocks))
        self.allocated_blocks = set()

    def allocate_block(self) -> int:
        if not self.free_blocks:
            raise MemoryError("OOM")
        blk = self.free_blocks.pop(0)
        self.allocated_blocks.add(blk)
        return blk

    def free_block(self, block_id: int) -> None:
        if block_id in self.allocated_blocks:
            self.allocated_blocks.remove(block_id)
            self.free_blocks.append(block_id)

class RequestState:
    def __init__(self, request_id: str, prompt_len: int, target_gen_len: int):
        self.request_id = request_id
        self.prompt_len = prompt_len
        self.target_gen_len = target_gen_len
        self.generated_tokens = 0
        self.block_table = []
        self.completed = False

    @property
    def total_tokens(self) -> int:
        return self.prompt_len + self.generated_tokens

class ContinuousBatchScheduler:
    def __init__(self, allocator: PagedBlockAllocator, max_batch_size: int = 8):
        self.allocator = allocator
        self.max_batch_size = max_batch_size
        self.waiting_queue = []
        self.running_batch = []
        self.completed_requests = []

    def add_request(self, req: RequestState) -> None:
        self.waiting_queue.append(req)

    def step_iteration(self) -> Dict[str, Any]:
        return {"active_requests": 0, "tokens_emitted": 0}
starter/test_serving_scheduler.py (2856 bytes)
import pytest
from serving_scheduler import PagedBlockAllocator, RequestState, ContinuousBatchScheduler

@pytest.fixture
def allocator():
    return PagedBlockAllocator(num_blocks=32, block_size=16)

def test_block_allocator_lifecycle(allocator):
    assert len(allocator.free_blocks) == 32
    b1 = allocator.allocate_block()
    b2 = allocator.allocate_block()
    assert b1 == 0 and b2 == 1
    assert len(allocator.free_blocks) == 30
    assert len(allocator.allocated_blocks) == 2

    allocator.free_block(b1)
    assert len(allocator.free_blocks) == 31
    assert b1 not in allocator.allocated_blocks

def test_continuous_batching_step_and_eviction(allocator):
    scheduler = ContinuousBatchScheduler(allocator, max_batch_size=2)
    # Req 1 needs 2 tokens, Req 2 needs 5 tokens
    r1 = RequestState("req_1", prompt_len=10, target_gen_len=2)
    r2 = RequestState("req_2", prompt_len=10, target_gen_len=5)
    
    scheduler.add_request(r1)
    scheduler.add_request(r2)

    # Step 1: Both admitted
    s1 = scheduler.step_iteration()
    assert s1["active_requests"] == 2
    assert s1["completed_requests"] == 0

    # Step 2: Req 1 completes, evicted from active batch
    s2 = scheduler.step_iteration()
    assert len(scheduler.completed_requests) == 1
    assert scheduler.completed_requests[0].request_id == "req_1"
    assert len(scheduler.running_batch) == 1

def test_dynamic_block_expansion(allocator):
    scheduler = ContinuousBatchScheduler(allocator, max_batch_size=1)
    # Prompt is 15 tokens (1 block). Target gen is 20 tokens -> Total 35 tokens (needs 3 blocks)
    r = RequestState("req_large", prompt_len=15, target_gen_len=20)
    scheduler.add_request(r)

    # Initial step
    scheduler.step_iteration()
    assert len(r.block_table) == 1

    # Run remaining steps
    for _ in range(19):
        scheduler.step_iteration()

    assert r.completed is True
    # All blocks should be freed on completion
    assert len(allocator.allocated_blocks) == 0

def test_out_of_memory_error(allocator):
    # Exhaust all 32 blocks
    for _ in range(32):
        allocator.allocate_block()
    with pytest.raises(MemoryError, match="Out of Memory"):
        allocator.allocate_block()

def test_fragmentation_metrics(allocator):
    scheduler = ContinuousBatchScheduler(allocator, max_batch_size=4)
    r = RequestState("req_1", prompt_len=14, target_gen_len=10) # Total 24 tokens (needs 2 blocks = 32 slots)
    scheduler.add_request(r)
    scheduler.step_iteration()
    scheduler.step_iteration()
    scheduler.step_iteration()

    metrics = scheduler.compute_fragmentation_metrics(max_context_window=128)
    assert metrics["paged_used_blocks"] == 2.0
    # Paged waste is (32 - 17) / 32 = 46.8%
    # Static waste is (128 - 17) / 128 = 86.7%
    assert metrics["paged_waste_percentage"] < metrics["static_waste_percentage"]
tests/run_tests.sh (126 bytes)
#!/usr/bin/env bash
set -e
export PYTHONPATH=examples:.
PYTEST="${PYTEST:-pytest}"
$PYTEST tests/test_serving_scheduler.py -v
tests/test_serving_scheduler.py (2856 bytes)
import pytest
from serving_scheduler import PagedBlockAllocator, RequestState, ContinuousBatchScheduler

@pytest.fixture
def allocator():
    return PagedBlockAllocator(num_blocks=32, block_size=16)

def test_block_allocator_lifecycle(allocator):
    assert len(allocator.free_blocks) == 32
    b1 = allocator.allocate_block()
    b2 = allocator.allocate_block()
    assert b1 == 0 and b2 == 1
    assert len(allocator.free_blocks) == 30
    assert len(allocator.allocated_blocks) == 2

    allocator.free_block(b1)
    assert len(allocator.free_blocks) == 31
    assert b1 not in allocator.allocated_blocks

def test_continuous_batching_step_and_eviction(allocator):
    scheduler = ContinuousBatchScheduler(allocator, max_batch_size=2)
    # Req 1 needs 2 tokens, Req 2 needs 5 tokens
    r1 = RequestState("req_1", prompt_len=10, target_gen_len=2)
    r2 = RequestState("req_2", prompt_len=10, target_gen_len=5)
    
    scheduler.add_request(r1)
    scheduler.add_request(r2)

    # Step 1: Both admitted
    s1 = scheduler.step_iteration()
    assert s1["active_requests"] == 2
    assert s1["completed_requests"] == 0

    # Step 2: Req 1 completes, evicted from active batch
    s2 = scheduler.step_iteration()
    assert len(scheduler.completed_requests) == 1
    assert scheduler.completed_requests[0].request_id == "req_1"
    assert len(scheduler.running_batch) == 1

def test_dynamic_block_expansion(allocator):
    scheduler = ContinuousBatchScheduler(allocator, max_batch_size=1)
    # Prompt is 15 tokens (1 block). Target gen is 20 tokens -> Total 35 tokens (needs 3 blocks)
    r = RequestState("req_large", prompt_len=15, target_gen_len=20)
    scheduler.add_request(r)

    # Initial step
    scheduler.step_iteration()
    assert len(r.block_table) == 1

    # Run remaining steps
    for _ in range(19):
        scheduler.step_iteration()

    assert r.completed is True
    # All blocks should be freed on completion
    assert len(allocator.allocated_blocks) == 0

def test_out_of_memory_error(allocator):
    # Exhaust all 32 blocks
    for _ in range(32):
        allocator.allocate_block()
    with pytest.raises(MemoryError, match="Out of Memory"):
        allocator.allocate_block()

def test_fragmentation_metrics(allocator):
    scheduler = ContinuousBatchScheduler(allocator, max_batch_size=4)
    r = RequestState("req_1", prompt_len=14, target_gen_len=10) # Total 24 tokens (needs 2 blocks = 32 slots)
    scheduler.add_request(r)
    scheduler.step_iteration()
    scheduler.step_iteration()
    scheduler.step_iteration()

    metrics = scheduler.compute_fragmentation_metrics(max_context_window=128)
    assert metrics["paged_used_blocks"] == 2.0
    # Paged waste is (32 - 17) / 32 = 46.8%
    # Static waste is (128 - 17) / 128 = 86.7%
    assert metrics["paged_waste_percentage"] < metrics["static_waste_percentage"]

Troubleshooting

Troubleshooting

If memory leaks occur, ensure free_block is called during request completion.

Security notes

Security

In-memory simulated PagedAttention block allocator. Completely sandboxed without network or OS level GPU memory allocation.