Virtual Memory and Paging
How the OS gives every process its own address space, how a virtual address is translated, what a page fault is, and how page replacement works, with a simulator that reproduces Belady's anomaly.
Virtual memory gives each process a private address space that the OS and hardware translate to physical memory using fixed-size pages and a page table mapping virtual pages to frames. A page fault occurs when a needed page is not in RAM. Interviewers expect the TLB, a cache of recent translations, and that FIFO replacement can suffer Belady's anomaly.
Virtual memory gives each process the illusion of a large, private, contiguous memory. The OS splits memory into fixed-size pages, keeps a page table that maps virtual pages to physical frames, and moves pages between RAM and disk on demand. A page fault occurs when a needed page is not in RAM.
- With 4 KiB pages, a virtual address splits into a virtual page number and a 12-bit offset; only the page number is translated, and the offset is copied unchanged.
- A flat page table for 48-bit virtual addresses and 4 KiB pages would have 2^36 entries, 512 GiB per process at 8 bytes each, so x86-64 uses four levels (five on newer CPUs).
- The translation lookaside buffer (TLB) is a small, fast CPU cache of recent virtual-to-physical page translations; a miss requires a page table walk.
- On the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO page replacement has 9 faults with 3 frames and 10 with 4 frames, which is Belady's anomaly.
- On the textbook string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames, FIFO gives 15 faults, LRU 12 and the optimal policy 9.
- Thrashing happens when running processes need more pages than RAM holds, so the CPU mostly waits on disk; a working-set policy is one fix.
01What virtual memory gives you
Without virtual memory, programs would use physical addresses directly. Two programs could overwrite each other, a program would need to know where it was loaded, and everything would have to fit in RAM at once.
With virtual memory, every process uses virtual addresses. The hardware and OS translate them to physical addresses on every access. That gives isolation (a process cannot even name another's memory), relocation (the same virtual address works wherever the pages actually sit), and the ability to run programs whose total size exceeds RAM, because pages not in use can live on disk.
02Pages, frames and address translation
Virtual memory is divided into pages, and physical memory into frames of the same size. 4 KiB (4096 bytes) is the common page size. A virtual address splits into two parts: the virtual page number (the high bits) and the offset within the page (the low 12 bits for 4 KiB pages).
Take virtual address 0x3A7C5:
page = 4096
va = 0x3A7C5
print(va // page, hex(va % page)) # 58 0x7c5It is page 58 at offset 0x7C5. The page table says which frame holds page 58, say frame 9. The physical address is then frame 9 times 4096 plus 0x7C5. The offset is copied unchanged, and only the page number is translated.
A 1 GiB region needs 262,144 pages at this size, which is why the table that tracks them needs thought.
03Page tables and why they are multi-level
The page table has one entry per virtual page, holding the frame number and flag bits: present, writable, user-accessible, accessed, dirty. If the present bit is 0, the access causes a page fault.
A flat table is too big for modern address spaces. With 48-bit virtual addresses and 4 KiB pages there are 2^36 pages. At 8 bytes per entry that is 2^39 bytes, 512 GiB, per process, nearly all of it for pages that are never used.
So page tables are hierarchical. x86-64 uses four levels (five on newer CPUs with large address space support). Each level indexes the next, and whole branches for unused address ranges are simply not allocated. The cost is that a translation can take several memory reads.
04The TLB: caching translations
Reading four table levels for every memory access would make programs several times slower. The CPU keeps a translation lookaside buffer (TLB), a small, fast cache of recent page-number-to-frame mappings. On a TLB hit the translation is nearly free. On a miss the hardware (or the OS, on some architectures) walks the page table and fills the TLB.
Programs with good locality, that reuse nearby addresses, hit the TLB almost every time. This is also why a context switch to a different process has a cost: its translations differ, so the TLB must be flushed or tagged by process, and the first accesses are slower.
05Page faults and demand paging
Under demand paging the OS does not load a whole program at start-up. It maps pages as not present and brings each one in on first use. When the CPU touches a page marked not present, it raises a page fault. The OS then checks the access is legal, finds a free frame (evicting another page if needed), reads the page from disk, updates the page table, and restarts the instruction.
A fault that needs the disk is thousands to hundreds of thousands of times slower than a RAM access, depending on the drive, so the system works only if faults are rare. The same mechanism provides copy-on-write: after fork(), parent and child share frames marked read-only, and the first write triggers a fault that makes a private copy.
06Page replacement and Belady's anomaly
Three standard policies. FIFO evicts the oldest page. LRU evicts the page unused for the longest time. Optimal evicts the page whose next use is furthest in the future, which is the best possible, but needs knowledge of the future and so serves only as a benchmark.
Here is a simulator run on the reference string 1 2 3 4 1 2 5 1 2 3 4 5:
def fifo(refs, frames):
mem, faults = [], 0
for r in refs:
if r not in mem:
faults += 1
if len(mem) == frames:
mem.pop(0)
mem.append(r)
return faults
def lru(refs, frames):
mem, faults = [], 0
for r in refs:
if r in mem:
mem.remove(r); mem.append(r)
else:
faults += 1
if len(mem) == frames:
mem.pop(0)
mem.append(r)
return faults
refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(fifo(refs, 3), fifo(refs, 4)) # 9 10
print(lru(refs, 3), lru(refs, 4)) # 10 8FIFO has 9 faults with 3 frames and 10 faults with 4 frames. Giving it more memory made it worse. That is Belady's anomaly. LRU does not have it, since it belongs to a class of stack algorithms where the set of pages in memory with n frames is always a subset of that with n+1.
On the classic textbook string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames the fifo and lru code above gives 15 and 12 faults, and an optimal policy (evict the page used furthest ahead, not shown here) gives 9. Real systems use approximations of LRU, such as the clock algorithm, because tracking exact recency on every access is too expensive.
07Thrashing and common interview questions
Thrashing happens when processes together need more pages than there is RAM. Every access evicts a page that is needed again almost immediately, so the CPU is mostly idle waiting for disk. The fix is to reduce the number of running processes, add memory, or use a working-set policy, which gives each process enough frames for the pages it is actively using.
Q: What is a page fault and is it an error?
A: It is an exception raised when a page is not present in RAM. Usually it is normal and handled by loading the page. An access to an invalid address is the error case and ends in a segmentation fault.
Q: Paging versus segmentation?
A: Paging uses fixed-size blocks and has no external fragmentation. Segmentation uses variable-size logical units such as code and stack, and can suffer external fragmentation.
Q: What is the TLB?
A: A small cache of recent virtual-to-physical translations.
Q: Which replacement algorithm suffers Belady's anomaly?
A: FIFO. LRU and the optimal policy do not.
Q: What is internal fragmentation in paging?
A: Wasted space inside the last page of an allocation, on average half a page.