Memory & concurrency

1 · Virtual memory & paging

Here's a puzzle that should bother you if you stop to think about it. You open your laptop, launch a browser, an editor, a music player and a terminal — and every single one of them behaves as if it owns the machine's memory outright, addressing bytes from zero on up. Yet they don't crash into each other, they don't read each other's secrets, and together they routinely "use" more memory than the machine physically has installed. Two programs each writing to "address 0" somehow both work. That is not luck. It's one of the most successful illusions in all of computing, and it has a name: virtual memory.

The everyday analogy is a hotel with a front desk. Every guest asks for "room 100" on their own floor and gets served — because the desk quietly translates your "room 100" into a real, unique physical room, and keeps a ledger so nobody is ever double-booked. Each guest lives in a tidy, private numbering scheme; the messy job of mapping those tidy numbers onto the real building is hidden behind the desk. Virtual memory is that front desk for RAM: your program uses clean private addresses, and a translator turns each one into a real physical location on demand.

Why this is worth doing at all — and why it's not free. The illusion buys three enormous things: isolation (one process literally cannot name another's memory, so a bug or an attacker in one can't reach into another — the SD8 protection theme again), the ability to pretend you have more memory than exists (rarely-touched pages get parked on disk and pulled back only when needed), and simplicity (every program is compiled against the same clean layout regardless of what else is running). The cost is a translation step on every memory access — which is why the hardware, not software, does it, and why the OS caches translations aggressively.

The common mistake is to picture your program's addresses as real hardware addresses — to think a pointer holds "where the byte physically lives." It doesn't. A pointer holds a virtual address, a promise the OS must redeem. Sometimes redeeming it is instant (the data is in RAM); sometimes it triggers a trip to disk (a page fault). Keep that gap between "the address I hold" and "where the bytes actually are" in mind — it explains everything from why memory-mapped files work to why a thrashing server crawls. With the intuition in place, here is the precise machinery.

Each process is given a virtual address space: a private, contiguous-looking range of addresses starting at zero. The OS and the CPU's MMU (memory management unit) translate those virtual addresses to real physical RAM addresses. Memory is handled in fixed-size chunks called pages (physical slots are frames). The mapping lives in a page table. When a program touches a page that isn't in RAM, the CPU raises a page fault; the OS fetches the page from disk into a free frame and resumes the program.

paging.py# MODEL: translate virtual pages to physical frames; a miss is a page fault.
class MMU:
    def __init__(self, num_frames):
        self.table = {}                 # virtual page -> frame
        self.free = list(range(num_frames))
        self.faults = 0
    def access(self, page):
        if page in self.table:
            return ("hit", self.table[page])
        self.faults += 1                # page fault: not resident
        if self.free:
            frame = self.free.pop(0)
            self.table[page] = frame
            return ("fault->loaded", frame)
        return ("fault->no-frame", None)  # eviction needed (see Step 2)

mmu = MMU(num_frames=2)
for pg in [1, 1, 2, 3]:
    print(pg, mmu.access(pg))
print("total faults:", mmu.faults)

1 ('fault->loaded', 0)
1 ('hit', 0)
2 ('fault->loaded', 1)
3 ('fault->no-frame', None)
total faults: 3

2 · Page replacement — FIFO, LRU, optimal

Picture your desk when you're deep in a project. It fits maybe six open books at once. A seventh book arrives and you need it — but the desk is full, so one book has to go back on the shelf. Which one? That single decision, made thousands of times a second, is what page replacement is about. RAM is the desk (small, fast, finite); the disk is the shelf (huge, slow). When a needed page isn't on the desk you pay a page fault to fetch it, and if the desk is full you must evict a resident page first. The policy you use to pick the victim decides how often you get stuck waiting on the slow shelf.

Here's why the choice matters so much: fetching from disk can be tens of thousands of times slower than reading RAM. A policy that evicts the wrong page — one you're about to need again — forces an immediate re-fetch, and a run of those (called thrashing) can drop a system from "instant" to "unusable" without any code changing. So the whole game is prediction: evict the page you're least likely to need soon. Nobody can see the future, so real policies are educated guesses about it, and their quality is measured in one number — the page-fault count.

The three policies here are best understood as three different bets on the future. FIFO bets that the oldest-loaded page is the stalest — evict whatever's been resident longest, regardless of use. It's dead simple but naïve: a page loaded long ago might be the one you hammer constantly. LRU (least-recently-used) makes a smarter bet — the page you touched longest ago is probably the one you'll want least — which is the same recency intuition behind the SD5 cache, now applied to RAM. And optimal cheats: it evicts the page whose next use is furthest in the future. That's genuinely the best any policy could do, but it needs to see the future, so no real OS can run it.

The common trap is asking "which policy is best?" as if optimal were a goal to reach. It isn't a goal — it's a ruler. Because optimal is unimplementable, its only job is to tell you the floor: the fewest faults physically achievable on a given workload. You then judge FIFO and LRU by how close they get to that floor. If LRU is within a hair of optimal, you stop tuning; if it's miles off, your access pattern is fighting the policy and you rethink. Read the simulator below as a measuring exercise, not a contest — it prints three fault counts and the story is in the gaps between them.

The picture below shows the one moment that separates the three policies: the desk (frames) is full, a new page is needed, and each policy points its finger at a different victim.

page_replace.py# MODEL: count page faults for a reference string under three policies.
def simulate(refs, frames, policy):
    mem, faults = [], 0
    for i, page in enumerate(refs):
        if page in mem:
            if policy == "LRU":         # mark as most-recently used
                mem.remove(page); mem.append(page)
            continue
        faults += 1
        if len(mem) < frames:
            mem.append(page); continue
        if policy == "FIFO":
            victim = mem[0]
        elif policy == "LRU":
            victim = mem[0]             # front = least recently used
        else:  # OPTIMAL: page used furthest in the future (or never)
            future = refs[i + 1:]
            victim = max(mem, key=lambda p: future.index(p)
                         if p in future else float("inf"))
        mem.remove(victim); mem.append(page)
    return faults

refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
for pol in ("FIFO", "LRU", "OPTIMAL"):
    print(f"{pol:8s} faults={simulate(refs, 3, pol)}")

FIFO     faults=10
LRU      faults=9
OPTIMAL  faults=7

3 · The concurrency problem & race conditions

This is the bug that ruins weekends. You write code that increments a counter every time a request comes in. It passes every test. It runs fine in staging for a month. Then one Friday, under real traffic, the numbers are quietly wrong — the counter says 998,341 when you know 1,000,000 requests came in. Nothing threw an error. Nothing logged. Just… less than it should be, by an amount that changes every time you look. You've met a race condition, and the reason it hid for a month is exactly why it's so dangerous: it depends on timing, and timing is different on every run.

The analogy that makes it click: two roommates share a fridge and a rule — "if we're out of milk, buy some." Roommate A opens the fridge, sees no milk, and heads to the shop. While A is walking, roommate B opens the fridge, also sees no milk, and also heads to the shop. You end up with two cartons. Neither did anything wrong individually — each read the shared state ("no milk"), decided, and acted. The bug lives in the gap between reading and acting, where the other party can sneak in. Threads do this millions of times a second.

The reason a line as innocent as counter += 1 is a landmine is that it isn't one action to the CPU — it's three: read the current value, add one, write the result back. Two threads can both read 41, both compute 42, and both write 42 — so two increments produce one. That's a lost update. The stretch of code that must not be interleaved like this — here, all three sub-steps together — is the critical section. Naming it matters, because the fix (next section) is precisely "let only one thread run the critical section at a time."

The dangerous mistake is trusting a clean test run. Because interleavings are non-deterministic, a race can pass a thousand times and fail the thousand-and-first — and in CPython the GIL can mask short races entirely, so you might see the correct total on your laptop and a wrong one in production on different hardware. "It worked when I ran it" proves nothing about a race; the only real defence is to reason about which memory is shared and written, mark those regions, and protect them. The lab below is deliberately built to race, so run it a few times and watch the total wobble — that wobble is the whole lesson.

The diagram below zooms into that "gap between reading and acting" — two threads interleaving one counter += 1 and quietly losing an update.

race.py# REAL threads: this genuinely races. counter += 1 is read-modify-write,
# so concurrent increments lose updates. Output varies per run.
import threading

counter = 0
def bump():
    global counter
    for _ in range(100_000):
        counter += 1            # NOT atomic: read, +1, write

threads = [threading.Thread(target=bump) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print("counter:", counter, "(expected 400000)")

counter: 400000 (expected 400000)   # or LESS, and it varies per run

4 · Mutexes & semaphores

Think of the single-occupancy toilet on an aeroplane. There's exactly one, everyone needs it, and the whole system works because of one small mechanism: the lock on the door that flips the sign to "occupied." Whoever's inside has exclusive use; everyone else sees the sign, waits in the aisle, and goes in one at a time when it flips back to "vacant." No schedule, no negotiation — just a lock that guarantees one person at a time. That door lock is a mutex, and it's the direct fix for the race you just watched: wrap the critical section in a lock and the interleaving that lost your updates simply cannot happen.

The word mutex is short for mutual exclusion, and that's exactly the promise: threads mutually exclude each other from the guarded region. A thread acquires the lock before entering (if someone else holds it, this thread blocks and waits), does its work, then releases it so the next waiter can proceed. In Python you almost always use a with lock: block, because it acquires on the way in and — crucially — releases on the way out even if an exception is thrown. That "even if it crashes" guarantee is the whole reason to prefer with over manual acquire/release: forget to release once and every other thread waits forever.

Now widen the picture. Sometimes "one at a time" is too strict — you don't need exclusive access, you just need to cap how many at once. Picture a parking garage with a sign out front showing spaces remaining: it lets cars in until the count hits zero, then holds new arrivals until someone leaves. That counter is a semaphore — a lock generalised from "one" to "up to N." It's the right tool for "at most 3 downloads at once," "no more than 10 open database connections," or any concurrency ceiling. The neat unifying idea: a mutex is just a semaphore with N=1 — a garage with a single space is a toilet with a door lock.

The classic mistake is reaching for a semaphore when you meant a mutex, or vice versa. If the invariant is "this data must never be touched by two threads at once," you want a mutex (N=1) — a semaphore with N=2 would happily let a race back in. If the invariant is "don't overwhelm the downstream service," you want a semaphore sized to the ceiling — a mutex would serialise everything and throw away all your parallelism. Ask "am I protecting correctness of shared state, or bounding a resource?" and the choice falls out. The lab shows the mutex fixing the counter; the tip after it shows the semaphore capping concurrency.

The picture below puts the two side by side: a mutex is a door that admits one, a semaphore is a garage that admits up to N — and a mutex is just the N=1 garage.

mutex.py# REAL threads: the lock serialises the critical section, so no update is lost.
import threading

counter = 0
lock = threading.Lock()
def bump():
    global counter
    for _ in range(100_000):
        with lock:              # only one thread in here at a time
            counter += 1

threads = [threading.Thread(target=bump) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print("counter:", counter)     # always 400000

counter: 400000

5 · Deadlock — the four conditions & the banker's algorithm

You've lived this at a four-way stop. Four cars arrive at once, each waiting for the car on its right to go first. Everyone is being polite. Everyone is following the rule. And nobody moves — forever, in principle — because each is waiting on someone who is waiting on someone who is waiting back on them. That frozen circle is a deadlock, and it's the concurrency failure that's arguably worse than a race: a race gives you a wrong answer, but a deadlock gives you no answer at all. The threads don't crash, don't error, don't burn CPU — they just hang, holding their locks, waiting on each other until you kill the process.

In software the cars are threads and the intersection is a set of locks. Thread A grabs lock 1 and reaches for lock 2; thread B has already grabbed lock 2 and is reaching for lock 1. Each holds what the other needs and neither will let go. What makes deadlock especially nasty is that, like a race, it's timing-dependent — A and B have to interleave just so — so it can hide for months and then strike under the exact load that lines the timing up. You cannot test your way to confidence; you have to reason about it.

Here's the tool that makes reasoning tractable. Coffman proved that deadlock can only happen when all four of these hold at once: mutual exclusion (a resource is held exclusively), hold-and-wait (you keep what you have while reaching for more), no preemption (nobody can force you to let go), and circular wait (the closed loop of "A waits for B waits for … waits for A"). The word "all" is the gift here: because every one is necessary, you don't have to defeat the whole problem — breaking any single condition makes deadlock impossible. That's why the standard cure is so cheap: impose a global lock ordering (always acquire lock 1 before lock 2), which kills circular wait outright — no cycle can form if everyone reaches in the same direction.

The subtle mistake is confusing avoidance with detection. Detecting a deadlock after it happens (then killing a victim to break it) is one strategy; avoiding ever entering one is another, and stricter. The banker's algorithm is avoidance: named for a banker who won't lend so much that he couldn't cover every client, it grants a resource request only if the resulting state is still safe — meaning there exists some order in which every process can get everything it might still need and finish. If no such order exists, the request is refused even though the resources are physically available right now. The lab models exactly this check; read "safe" as "there's a guaranteed way out," and "grant only if the post-grant state is still safe" as "never step somewhere you can't step back from."

The picture below draws the circular wait at the heart of every deadlock — and shows how imposing a lock order snaps the cycle open.

bankers.py# MODEL of the banker's algorithm: is the current allocation state SAFE?
# Safe = there exists an order in which all processes can finish.
def is_safe(available, maximum, allocation):
    n = len(maximum)                       # processes
    need = [[maximum[i][j] - allocation[i][j] for j in range(len(available))]
            for i in range(n)]
    work = list(available)
    finish = [False] * n
    order = []
    made_progress = True
    while made_progress:
        made_progress = False
        for i in range(n):
            if not finish[i] and all(need[i][j] <= work[j]
                                     for j in range(len(work))):
                for j in range(len(work)):   # this process can finish; it frees its
                    work[j] += allocation[i][j]  # resources back to the pool
                finish[i] = True
                order.append(i)
                made_progress = True
    return all(finish), order

# 3 resource types, 5 processes (classic textbook state)
available  = [3, 3, 2]
maximum    = [[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
allocation = [[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
safe, order = is_safe(available, maximum, allocation)
print("safe?", safe)
print("safe sequence:", order)

safe? True
safe sequence: [1, 3, 4, 0, 2]

6 · Producer–consumer & bounded buffers

Watch a short-order kitchen at lunch rush. One cook fires plates; the servers carry them out. But the pass — that heated shelf where finished plates wait — only holds so many. When it's jammed full, the cook has to pause (no room to set the next plate down); when it's empty, the servers stand around waiting. Nobody yells across the kitchen "are you ready yet?" every second — the shelf itself coordinates them. That shelf is a bounded buffer, and this whole pattern — makers on one side, takers on the other, a limited holding area between — is the producer–consumer problem. It's the single most common shape in all of concurrent systems.

The reason you build it this way instead of having the cook hand plates directly to servers is decoupling: production and consumption almost never run at the same speed, and they shouldn't have to. A fast producer and a slow consumer, or bursty arrivals against steady processing — the buffer absorbs the mismatch so neither side has to match the other's rhythm moment to moment. That absorption has a natural ceiling, and the ceiling is the point: a bounded buffer is what gives you backpressure. When it fills, the producer is forced to wait, which is exactly what you want — it stops a fast producer from consuming all your memory buffering work nobody's ready to handle yet.

Three things must be true at once, and they're what make this genuinely hard by hand. The producer must block when the buffer is full (not spin, not drop data). The consumer must block when it's empty (not busy-wait burning CPU, not crash on nothing). And the buffer's own internal state must survive concurrent access from both sides without corruption — every push and pop is a critical section. Get any one wrong and you have lost items, a wedged pipeline, or a subtle corruption that (say it with me) passes every test and fails in production.

The classic mistake is rolling your own with a plain list, a lock, and a busy-wait loop — checking while buffer_full: pass pins a core at 100% for nothing, and hand-rolled blocking is where the sleep-forever bugs live. Python hands you the correct, battle-tested answer: queue.Queue(maxsize=N) bundles the lock and the condition variables that put waiting threads properly to sleep and wake them at the right moment. It solves all three requirements in one object, which is why the lab uses it rather than reinventing it — and why the same primitive scales from a two-thread demo to a real service's work queue.

The picture below is the whole pattern in one line: a producer fills a bounded buffer, a consumer drains it, and the two ends block when the buffer is full or empty.

producer_consumer.py# REAL threads: Queue(maxsize=...) blocks the producer when full and the
# consumer when empty, and is internally thread-safe.
import threading, queue

buf = queue.Queue(maxsize=5)
DONE = object()

def producer():
    for i in range(10):
        buf.put(i)              # blocks if buffer is full
    buf.put(DONE)

def consumer(out):
    while True:
        item = buf.get()        # blocks if buffer is empty
        if item is DONE:
            break
        out.append(item)

out = []
p = threading.Thread(target=producer)
c = threading.Thread(target=consumer, args=(out,))
p.start(); c.start(); p.join(); c.join()
print("consumed:", out)

consumed: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Knowledge check

def fifo_faults(refs, frames):
    mem, faults = [], 0
    for page in refs:
        if page in mem:
            continue                 # hit
        faults += 1                  # fault
        if len(mem) < frames:
            mem.append(page)
        else:
            mem.pop(0)               # evict oldest-loaded
            mem.append(page)
    return faults

print(fifo_faults([7,0,1,2,0,3,0,4,2,3,0,3,2], 3))   # 10

def simulate(refs, frames, policy):
    mem, faults = [], 0
    for i, page in enumerate(refs):
        if page in mem:
            if policy == "LRU":
                mem.remove(page); mem.append(page)
            continue
        faults += 1
        if len(mem) < frames:
            mem.append(page); continue
        if policy in ("FIFO", "LRU"):
            victim = mem[0]          # oldest / least-recently-used at front
        else:                        # OPTIMAL
            future = refs[i+1:]
            victim = max(mem, key=lambda p: future.index(p)
                         if p in future else float("inf"))
        mem.remove(victim); mem.append(page)
    return faults

refs = [7,0,1,2,0,3,0,4,2,3,0,3,2]
for pol in ("FIFO", "LRU", "OPTIMAL"):
    print(pol, simulate(refs, 3, pol))

import threading

def run(use_lock):
    counter = 0
    lock = threading.Lock()
    def bump():
        nonlocal counter
        for _ in range(200_000):
            if use_lock:
                with lock:
                    counter += 1
            else:
                counter += 1
    ts = [threading.Thread(target=bump) for _ in range(4)]
    for t in ts: t.start()
    for t in ts: t.join()
    return counter

expected = 4 * 200_000
print("no lock:", run(False), "expected", expected)   # may be < expected
print("with lock:", run(True), "expected", expected)  # always == expected

import copy

def is_safe(available, maximum, allocation):
    n, m = len(maximum), len(available)
    need = [[maximum[i][j]-allocation[i][j] for j in range(m)] for i in range(n)]
    work, finish = list(available), [False]*n
    progress = True
    while progress:
        progress = False
        for i in range(n):
            if not finish[i] and all(need[i][j] <= work[j] for j in range(m)):
                for j in range(m): work[j] += allocation[i][j]
                finish[i] = True; progress = True
    return all(finish)

def request(pid, req, available, maximum, allocation):
    m = len(available)
    need = [maximum[pid][j]-allocation[pid][j] for j in range(m)]
    if any(req[j] > need[j] for j in range(m)):
        return "DENY: exceeds declared need"
    if any(req[j] > available[j] for j in range(m)):
        return "DENY: not enough available now"
    av2 = [available[j]-req[j] for j in range(m)]
    al2 = copy.deepcopy(allocation)
    for j in range(m): al2[pid][j] += req[j]
    return "GRANT" if is_safe(av2, maximum, al2) else "DENY: would be unsafe"

available  = [3,3,2]
maximum    = [[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
allocation = [[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
print("P1 asks [1,0,2]:", request(1, [1,0,2], available, maximum, allocation))
print("P0 asks [0,2,2]:", request(0, [0,2,2], available, maximum, allocation))

import threading, time, random

N = 3
sem = threading.Semaphore(N)
live = 0
peak = 0
meter = threading.Lock()

def worker():
    global live, peak
    with sem:                       # at most N threads past this point
        with meter:
            live += 1; peak = max(peak, live)
        time.sleep(random.uniform(0.005, 0.02))
        with meter:
            live -= 1

ts = [threading.Thread(target=worker) for _ in range(50)]
for t in ts: t.start()
for t in ts: t.join()
print("peak concurrency:", peak, "cap:", N)
assert peak <= N

import threading, queue

NUM_CONSUMERS = 3
work = queue.Queue(maxsize=8)      # bounded -> backpressure on the producer
results = []
results_lock = threading.Lock()
SENTINEL = object()

def producer(n):
    for i in range(n):
        work.put(i)                # blocks when full
    for _ in range(NUM_CONSUMERS):
        work.put(SENTINEL)         # one poison pill per consumer

def consumer():
    while True:
        item = work.get()
        if item is SENTINEL:
            work.task_done(); break
        with results_lock:
            results.append(item * item)
        work.task_done()

N = 100
p = threading.Thread(target=producer, args=(N,))
cs = [threading.Thread(target=consumer) for _ in range(NUM_CONSUMERS)]
p.start()
for c in cs: c.start()
p.join()
for c in cs: c.join()
print("processed:", len(results), "of", N)
print("exactly once:", sorted(results) == [i*i for i in range(N)])