LLMs and Generative AI › Customizing and Running Models › Day 279
Hands-on lab — Day 279: Serving Open Models
- ← Back to the Day 279 lesson
- Open the hands-on files on GitHub — clone or download them from the public labs repository
- Local path in your clone:
labs/sections/llms-and-generative-ai/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-modelswhen 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 skeletonexamples/serving_scheduler.py: Verified reference implementationtests/test_serving_scheduler.py: Test suiteexpected-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.
Navigation
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.