Memory management & virtual memory

Programs do not use physical RAM addresses directly. Each process sees its own virtual address space, divided into fixed-size pages (usually 4 KB). Physical RAM is divided into frames of the same size. A page table per process maps each virtual page to a physical frame, and the memory management unit (MMU) in the CPU does this translation on every memory access.

This gives isolation (one process cannot see another's memory), lets programs use more memory than physically exists (rarely used pages live on disk in swap), and allows sharing (for example, one copy of a shared library mapped into many processes). A page fault happens when a program touches a page that is not currently in RAM; the OS loads it and, if RAM is full, first evicts another page using a replacement policy such as LRU.

1. 1A virtual address is split into a page number and an offset. With 4 KB pages (4096 = 2^12 bytes), the lowest 12 bits are the offset and the rest is the page number.
2. 2The MMU first checks the TLB (translation lookaside buffer), a small cache of recent page-to-frame translations. A TLB hit gives the frame immediately.
3. 3On a TLB miss, the hardware or OS walks the page table. If the page table entry is valid, the frame number is found and cached in the TLB.
4. 4If the entry is not present, a page fault occurs: the OS finds the page on disk (swap or the program's file), picks a free frame or evicts a victim page (writing it to disk first if it was modified, the 'dirty' bit), loads the page, updates the table, and restarts the instruction.
5. 5Replacement policies: FIFO evicts the oldest loaded page (and can suffer Belady's anomaly, where more frames cause more faults); LRU evicts the least recently used page; Optimal evicts the page used furthest in the future (not implementable, used as a benchmark). Real systems approximate LRU, for example with the clock algorithm.
6. 6If processes' working sets do not fit in RAM, the system spends most of its time moving pages to and from disk: this is thrashing, and throughput collapses.

from collections import OrderedDict

def lru_page_faults(refs, frames):
    """Count page faults with LRU replacement and `frames` physical frames."""
    memory = OrderedDict()           # pages, least recently used first
    faults = 0
    for page in refs:
        if page in memory:
            memory.move_to_end(page)     # hit: now most recently used
        else:
            faults += 1                  # page fault: load from disk
            if len(memory) == frames:
                memory.popitem(last=False)   # evict least recently used
            memory[page] = True
    return faults

print(lru_page_faults([7, 0, 1, 2, 0, 3, 0, 4], 3))  # 6

An OrderedDict keeps pages in order of last use: a hit moves the page to the end, and eviction removes from the front. Each reference is O(1). For the reference string in the example it reports 6 faults, matching the hand trace.

Cost: A TLB hit adds almost no time; a page table walk costs a few extra memory accesses; a major page fault from disk costs microseconds on SSD to milliseconds on spinning disk, thousands of times slower than RAM.