VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
D1: CS & Systems Foundations · Operating Systems — Sharing One Machine Between Many Programs
Phase 1/Domain 1/Lesson 19

Operating Systems — Sharing One Machine Between Many Programs

10 min read·Foundational·Free lesson
Operating Systems — Sharing One Machine Between Many Programs

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)
two process boxes, each with its own "memory" region; inside process A, three thread lanes all pointing at the same memory.
Diagram— two process boxes, each with its own "memory" region; inside process A, three thread lanes all pointing at the same memory.

Real-life analogy. Processes are separate apartments; threads are people living in the same apartment, sharing the fridge.

Worked example.

python
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.

a timeline with one CPU core; coloured slices A, B, C, A, C… with small grey "switch" gaps between them; thread B shown as "waiting for network" during part of the timeline.
Diagram— a timeline with one CPU core; coloured slices A, B, C, A, C… with small grey "switch" gaps between them; thread B shown as "waiting for network" during part of the timeline.

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).
left, a tidy column of virtual pages 0–5 for "Process A"; middle, a page table; right, physical frames with A's pages scattered among another process's pages. Arrows show the mapping.
Diagram— left, a tidy column of virtual pages 0–5 for "Process A"; middle, a page table; right, physical frames with A's pages scattered among another process's pages. Arrows show the mapping.

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:

python
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.

Diagram, two GPU-memory strips. Top "contiguous": large reserved blocks per request with big unused tails and unusable gaps. Bottom "paged": small equal blocks for requests A, B, C interleaved with no gaps, plus a small per-request block table.
Diagram— Diagram, two GPU-memory strips. Top "contiguous": large reserved blocks per request with big unused tails and unusable gaps. Bottom "paged": small equal blocks for requests A, B, C interleaved with no gaps, plus a small per-request block table.

Worked example — contiguous vs paged reservation:

python
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).

two thread lanes both reading count = 10, both writing 11 (one update lost); below, the same with a padlock around the read-add-write, giving 12.
Diagram— two thread lanes both reading count = 10, both writing 11 (one update lost); below, the same with a padlock around the read-add-write, giving 12.

Worked example.

python
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 — mmap maps 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:

python
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?

  1. It makes attention mathematically exact
  2. 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
  3. GPUs require fixed-size blocks
  4. Blocks are faster to compute
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

  1. Recall: What two things does a virtual address split into?
  2. Apply: Eight threads each do pure-Python CPU work on an 8-core machine. Will this use all 8 cores?
  3. Predict: With 16-token blocks, how many tokens are reserved for a 33-token reply?
Answers
  1. A page number and an offset within the page.
  2. No — in standard CPython the GIL lets only one thread run Python bytecode at a time. Use processes.
  3. 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
python
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).