You already know: stack vs heap, pointers as addresses, and cache locality (C++ §1, §2, §5); priority queues and lookup tables (Data structures §2–3).
Why this matters for Atlas. Atlas runs a web server, background workers and a model on one machine. The operating system (OS) decides who runs, who gets memory, and how they communicate. And one OS idea — paging — is exactly how modern LLM servers manage GPU memory.
1. Processes and threads
The question. What is a "running program", really?
Start from nothing. A process is a program in execution with its own private resources: its own memory space, open files and at least one thread. A thread is one sequence of instructions running inside a process. All threads in a process share that process's memory.
| Process | Thread | |
|---|---|---|
| Memory | Private (isolated) | Shared with other threads in the process |
| Cost to create | Higher | Lower |
| A crash affects | Only that process | The whole process |
| Talk to others via | IPC (pipes, sockets, shared memory) | Shared variables (needs locks) |
Real-life analogy. Processes are separate apartments; threads are people living in the same apartment, sharing the fridge.
Worked example.
import os
import threading
from multiprocessing import Process
def show(label):
print(f"{label}: process id {os.getpid()}, thread {threading.current_thread().name}")
if __name__ == "__main__":
show("main")
t = threading.Thread(target=show, args=("thread",), name="worker-thread")
t.start(); t.join() # same process id as main
p = Process(target=show, args=("process",))
p.start(); p.join() # a different process id
In production. Python web servers run several worker processes (each with its own GIL) and use threads or asyncio inside each worker for waiting on I/O — combining both models.
2. Scheduling and context switches
The question. A machine with 8 cores runs hundreds of threads. How?
Start from nothing. The OS scheduler gives each runnable thread a short time slice on a core (often a few milliseconds), then switches to another. A context switch saves the current thread's registers and program counter and loads another's. It looks simultaneous because switches happen hundreds of times a second — but each switch costs time and pollutes the CPU cache.
Threads that are waiting (for disk, network, a lock) don't need the CPU, so the scheduler skips them. That's why one core can serve many I/O-heavy threads.
Real-life analogy. One chess master playing 20 boards: a few seconds at each board, then moves on; boards waiting for the opponent don't take the master's time.
Common trap. More threads than cores for CPU-heavy work makes things slower: more switching, more cache misses, no extra compute.
In production / interviews. Inference servers pin heavy threads to cores and size thread pools to the core count. Interview question: "What does a context switch cost, and why does it matter for latency-sensitive services?"
3. Virtual memory and page tables
The question. Two programs both use memory address 0x7f00…. How don't they overwrite each other?
Start from nothing. Every process sees its own virtual address space — one long, private range of addresses starting from zero. The OS splits that space into fixed-size pages (commonly 4 KB) and physical RAM into equal-size frames. A per-process page table maps virtual page numbers to physical frames. The CPU's memory unit translates every address on the fly:
virtual address = (page number, offset) → page table → (frame number, offset) = physical address
Benefits:
- Isolation — processes can't see each other's memory.
- No need for contiguous RAM — a process's pages can be scattered anywhere physically.
- Lazy allocation — a page gets a real frame only when first touched.
- Swapping — rarely used pages can be moved to disk (a page fault brings them back, slowly).
Real-life analogy. A hotel: guests are told "room 12" (virtual address). The front desk's ledger (page table) knows which physical room that is today and can move guests without them noticing.
Worked example — a toy address translator:
PAGE_SIZE = 4096
page_table = {0: 7, 1: 3, 2: 9} # virtual page -> physical frame
def translate(virtual_address):
page, offset = divmod(virtual_address, PAGE_SIZE)
if page not in page_table:
raise MemoryError(f"page fault: virtual page {page} not mapped")
return page_table[page] * PAGE_SIZE + offset
for va in [0, 5000, 8200]:
print(f"virtual {va:>5} -> physical {translate(va):>5}")
try:
translate(4 * PAGE_SIZE)
except MemoryError as e:
print(e)
Math. Address 5000 → page 5000 // 4096 = 1, offset 5000 % 4096 = 904. Page 1 → frame 3, so physical = 3 × 4096 + 904 = 13192.
Common trap. "Virtual memory means using disk as RAM." Swapping is one feature; the core idea is address translation with pages.
4. Allocation, fragmentation — and PagedAttention
The question. Why do LLM servers run out of GPU memory even when lots of it is free?
Start from nothing. If every request must get one contiguous block sized for its maximum length, two kinds of waste appear:
- Internal fragmentation — reserving 2,048 tokens of space for a reply that uses 200.
- External fragmentation — free memory exists, but in gaps too small for a new contiguous block.
Paging fixes both: hand out small fixed-size pages on demand, and track them with a table. That's precisely what PagedAttention (the core idea of vLLM, Kwon et al., 2023) does for the model's KV cache (D12): each request's cache is a list of small blocks that can live anywhere in GPU memory, allocated as the reply grows. The vLLM paper reports this cut KV-cache waste dramatically and let far more requests run at once.
Worked example — contiguous vs paged reservation:
import math
BLOCK = 16 # tokens per block
max_len = 2048
actual_lengths = [180, 950, 60, 1400, 300]
contiguous = len(actual_lengths) * max_len
paged = sum(math.ceil(n / BLOCK) * BLOCK for n in actual_lengths)
used = sum(actual_lengths)
print(f"tokens actually used: {used}")
print(f"contiguous reserve : {contiguous} (waste {100 * (1 - used / contiguous):.0f}%)")
print(f"paged reserve : {paged} (waste {100 * (1 - used / paged):.1f}%)")
Real-life analogy. Restaurant seating: instead of reserving a 12-person table for every booking "just in case", seat guests at small tables and add another as more arrive.
5. Locks, semaphores and deadlocks
The question. Two threads add to the same counter. Why can the total come out wrong?
Start from nothing. count += 1 is really three steps: read, add, write. If two threads interleave — both read 10, both write 11 — one update is lost: a race condition. A lock (mutex) lets only one thread into a critical section at a time. A semaphore is a counter that allows up to N at once — useful for "at most 4 concurrent GPU jobs". A deadlock happens when threads wait on each other forever (A holds lock 1 and wants 2; B holds 2 and wants 1).
Worked example.
import threading
import time
count = 0
lock = threading.Lock()
def unsafe_add(n):
global count
for _ in range(n):
current = count
time.sleep(0) # yield, making the interleaving visible
count = current + 1
def safe_add(n):
global count
for _ in range(n):
with lock:
current = count
time.sleep(0)
count = current + 1
for fn in (unsafe_add, safe_add):
count = 0
threads = [threading.Thread(target=fn, args=(1000,)) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print(f"{fn.__name__}: expected 4000, got {count}")
# Semaphore: at most 2 "GPU jobs" at a time
gpu_slots = threading.Semaphore(2)
active, peak = 0, 0
def job():
global active, peak
with gpu_slots:
with lock:
active += 1; peak = max(peak, active)
time.sleep(0.05)
with lock:
active -= 1
jobs = [threading.Thread(target=job) for _ in range(6)]
for j in jobs: j.start()
for j in jobs: j.join()
print("peak concurrent jobs:", peak) # 2
Avoiding deadlock. Always take multiple locks in the same global order; hold locks briefly; use timeouts (lock.acquire(timeout=1)).
Real-life analogy. A single-occupancy bathroom with a lock (mutex); a parking lot with 4 spaces and a counter at the gate (semaphore); two cars meeting on a one-lane bridge, each waiting for the other (deadlock).
6. Files, shared memory and talking between processes
The question. Atlas's tokenizer process and model process must pass large arrays quickly. What are the options?
Start from nothing. Processes are isolated, so the OS offers inter-process communication (IPC):
- Pipes and sockets — stream bytes from one process to another (copying them).
- Shared memory — map the same physical pages into both processes' address spaces: zero copies.
- Files and memory-mapped files —
mmapmaps a file's pages directly into memory, loaded lazily by the page-fault mechanism from section 3. Model weights are often loaded this way, which is why a huge model can "open" instantly.
Worked example — two processes sharing one array without copying:
import numpy as np
from multiprocessing import Process, shared_memory
def worker(name, n):
shm = shared_memory.SharedMemory(name=name)
arr = np.ndarray((n,), dtype=np.float32, buffer=shm.buf)
arr *= 2 # modifies the shared pages in place
shm.close()
if __name__ == "__main__":
n = 5
shm = shared_memory.SharedMemory(create=True, size=n * 4)
data = np.ndarray((n,), dtype=np.float32, buffer=shm.buf)
data[:] = [1, 2, 3, 4, 5]
p = Process(target=worker, args=(shm.name, n))
p.start(); p.join()
print(data) # [ 2. 4. 6. 8. 10.] changed by the other process
shm.close(); shm.unlink()
In production / interviews. PyTorch's DataLoader workers pass batches through shared memory; formats like safetensors are designed to be memory-mapped so weights load without extra copies.
Quick check
Why does PagedAttention store the KV cache in fixed-size blocks rather than one contiguous buffer per request?
Show the answer
B. Like virtual-memory pages, blocks avoid reserving the maximum length up front and eliminate external fragmentation, so many more concurrent requests fit in GPU memory — Contiguous per-request buffers waste memory on unused capacity and fragmentation; paging allocates on demand and shares blocks.
Check yourself
- Recall: What two things does a virtual address split into?
- Apply: Eight threads each do pure-Python CPU work on an 8-core machine. Will this use all 8 cores?
- Predict: With 16-token blocks, how many tokens are reserved for a 33-token reply?
Answers
- A page number and an offset within the page.
- No — in standard CPython the GIL lets only one thread run Python bytecode at a time. Use processes.
- 48 (three blocks: ⌈33/16⌉ = 3).
Exercise
Write BlockAllocator(total_blocks, block_size) with allocate(request_id, n_tokens), append_token(request_id) (adds a block only when the last one is full) and free(request_id). Report utilization (used tokens ÷ reserved tokens) after a mix of requests.
Solution
class BlockAllocator:
def __init__(self, total_blocks, block_size=16):
self.free_blocks = list(range(total_blocks))
self.block_size = block_size
self.tables, self.lengths = {}, {}
def _grow(self, rid):
if not self.free_blocks:
raise MemoryError("out of blocks")
self.tables[rid].append(self.free_blocks.pop())
def allocate(self, rid, n_tokens):
self.tables[rid], self.lengths[rid] = [], 0
for _ in range(n_tokens):
self.append_token(rid)
def append_token(self, rid):
if self.lengths[rid] % self.block_size == 0: # last block full (or none yet)
self._grow(rid)
self.lengths[rid] += 1
def free(self, rid):
self.free_blocks.extend(self.tables.pop(rid))
self.lengths.pop(rid)
def utilization(self):
reserved = sum(len(t) for t in self.tables.values()) * self.block_size
return sum(self.lengths.values()) / reserved if reserved else 1.0
a = BlockAllocator(total_blocks=100)
a.allocate("r1", 33); a.allocate("r2", 100); a.allocate("r3", 7)
for _ in range(20):
a.append_token("r3")
a.free("r2")
print(f"utilization {a.utilization():.0%}, free blocks {len(a.free_blocks)}")
This unlocks:
- Networking — sockets are the OS's door to other machines.
- D12 KV cache & tiered KV storage — PagedAttention and moving blocks between GPU, CPU and disk.
- D13 GPU memory hierarchy — the same "fast-small vs slow-big" trade-off.
Sources: Arpaci-Dusseau, Operating Systems: Three Easy Pieces (paging, concurrency chapters); Python docs — threading, multiprocessing.shared_memory, mmap; Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023).