Foundations · Lesson 3/8

Memory Management & Virtual Memory — A Private Map for Every Process

43 min 1 quiz Graded labs: 3

What you'll learn

Why every process sees its own private virtual address space
How paging splits an address into a page number and an offset, and how the page table maps pages to physical frames
What the TLB and a page fault are, and why a page fault is not always an error
How page replacement (FIFO vs LRU) decides what to evict, and what Belady's anomaly is
Fragmentation, and how first-fit and best-fit allocation behave

You will code three exercises: an address translator in C, a FIFO vs LRU fault counter in Python and a first-fit/best-fit allocator in Go.

A library with a private catalog 📚

Imagine a huge library where every reader gets their own private catalog. In your catalog, books are numbered 0, 1, 2, 3... as if you owned the whole library. Another reader's catalog also starts at 0, and "book 0" there is a different book. A librarian keeps a ledger that says "your book 7 is on shelf 42, their book 7 is on shelf 9".

Your catalog numbers are virtual addresses
The shelves are physical memory (RAM), divided into equal slots called frames
The librarian's ledger is the page table, and the librarian is the OS together with the CPU's MMU (memory management unit)
Only the books you are using sit on the reading desk (RAM); the rest live in the storage room (disk)

This gives three gifts:

Isolation: your catalog simply cannot name another reader's books, so one buggy program cannot overwrite another
Convenience: every program can be compiled as if it owned addresses starting from 0
More than fits: the sum of all address spaces can be larger than RAM, because rarely used parts wait on disk

What lives in an address space

A process's virtual address space holds its code, global data, the heap (grows with malloc/new), the stack (grows with function calls) and memory-mapped files and libraries. On Linux you can see the real layout of a running process in /proc/<pid>/maps.

Paging: pages, frames and the page table

Virtual memory is cut into equal blocks called pages; physical memory is cut into blocks of the same size called frames. A common page size is 4 KiB (4096 bytes). Any page can sit in any frame, so the OS never needs one big contiguous hole.

A virtual address is split in two:

virtual address = | page number | offset |
page number = address / page_size      (which page)
offset      = address % page_size      (which byte inside the page)

When the page size is a power of two (4096 = 2^12) this is just bit slicing: the low 12 bits are the offset and the rest is the page number.

Example, address 0x1A2B with 4 KiB pages: 0x1A2B >> 12 = 0x1 is page 1, and 0x1A2B & 0xFFF = 0xA2B is the offset (2603).

The page table (one per process) maps page numbers to frame numbers. The MMU builds the physical address like this:

physical address = frame number * page_size + offset

The offset never changes; only the page number is replaced by a frame number. If page 1 lives in frame 2, then virtual 0x1A2B becomes 2 * 4096 + 2603 = 10795.

Page tables are big, so they are trees

With 32-bit addresses and 4 KiB pages there are 2^20 pages; a flat table with 4-byte entries would take 4 MiB per process. For 64-bit machines it would be impossible. So real systems use multi-level page tables (for example 4 levels on x86-64 with 48-bit virtual addresses: 4 levels of 9 bits plus a 12-bit offset). Whole unused regions need no table at all.

Entries carry more than a frame number

Each page table entry (PTE) also holds flag bits: present/valid (is the page in RAM?), read/write/execute permissions, user/supervisor and dirty/accessed bits. The hardware checks these on every access, which is how the OS makes code pages non-writable and keeps user programs out of kernel memory.

Translate some addresses yourself:

The offset is copied unchanged while the page number is swapped for a frame number. Address 8192 is page 2, which has no entry, so the access would trigger a page fault. Try adding 2: 9 to page_table or a bigger PAGE_SIZE.

PAGE_SIZE = 4096                      # 4 KiB = 2**12 bytes
page_table = {0: 5, 1: 2, 3: 7}       # virtual page number -> physical frame number

def translate(vaddr):
    page, offset = divmod(vaddr, PAGE_SIZE)
    if page not in page_table:
        return f"{vaddr:>6} -> page {page}, offset {offset:>4}: PAGE FAULT (no mapping)"
    paddr = page_table[page] * PAGE_SIZE + offset
    return f"{vaddr:>6} -> page {page}, offset {offset:>4}: frame {page_table[page]} -> physical {paddr}"

for vaddr in [100, 4106, 8192, 16383, 0x1A2B]:
    print(translate(vaddr))

Open in Code Lab

The TLB and page faults

Why we need a cache for translations

If every load and store needed several page-table reads in RAM, programs would crawl. The CPU therefore keeps a tiny, very fast cache of recent translations: the TLB (translation lookaside buffer). On a TLB hit the physical frame is known immediately. On a TLB miss the hardware (or the OS, on some architectures) walks the page table and refills the TLB. Because programs show locality (they reuse nearby addresses), hit rates are typically very high. When the OS switches to another process, TLB entries of the old one must be discarded or tagged with an address-space ID so they are not reused by mistake.

Page faults

A page fault is an exception raised when the CPU touches a virtual page that has no usable mapping right now: the present bit is clear, or the access violates the permissions. The OS fault handler then decides:

Valid page, not in RAM yet (a "minor/major" fault): find or free a frame, load the page from disk if needed, update the page table, and restart the instruction. The program never notices, apart from the delay. This is demand paging: a program's pages are loaded only when first touched.
Copy-on-write: after fork parent and child share frames marked read-only; the first write faults and the kernel gives the writer its own copy. That is why fork is cheap.
Invalid access (unmapped address or a write to read-only memory): the OS sends the process a SIGSEGV, the famous segmentation fault.

So "page fault" is a normal, frequent event, while "segmentation fault" is the fatal outcome of an invalid one.

Thrashing

If the combined working sets of the running programs do not fit in RAM, pages are evicted just before they are needed again. The system spends its time swapping pages in and out instead of running code, which is thrashing. The cures are more RAM, fewer running programs, or better replacement.

Now practise the mapping logic you just saw in code:

Lab exercise 1

CGraded in Code Lab

Write an address translator for a single-level page table.

Input:

Line 1: page_size m, the page size in bytes and the number of mappings (m is at most 1000)
Next m lines: vpn frame, meaning virtual page vpn is stored in physical frame frame
Then zero or more virtual addresses (decimal, one per line) until the end of input

Output: one line per address:

<vaddr> -> <paddr> where paddr = frame * page_size + vaddr % page_size, if the page is mapped
<vaddr> -> PAGE FAULT if the page has no mapping

Use unsigned long long so that large addresses work. Example:

prints

100 -> 20580
4106 -> 8202
8192 -> PAGE FAULT
16383 -> 32767

Visible tests (5)

Lesson example
Page boundaries and frame 0
A different page size
No addresses to translate
Addresses beyond 32 bits

Example run

Input: 4096 3 0 5 1 2 3 7 100 4106 8192 16383
Expected output: 100 -> 20580 4106 -> 8202 8192 -> PAGE FAULT 16383 -> 32767

Starter code

#include <stdio.h>

#define MAX_MAPPINGS 1000

int main(void) {
    unsigned long long page_size, m;
    unsigned long long vpn[MAX_MAPPINGS], frame[MAX_MAPPINGS];

    if (scanf("%llu %llu", &page_size, &m) != 2) return 0;

    // TODO 1: read the m "vpn frame" pairs into the two arrays

More lines in Code Lab: 8

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

When RAM is full: page replacement

Eventually a page fault needs a free frame and there is none. The OS must evict a victim page (writing it to disk first if its dirty bit is set) and reuse its frame. The goal is the fewest page faults, because a fault costs about as much as millions of CPU instructions when it goes to disk.

We compare policies by running them on a reference string: the sequence of page numbers a program touches.

FIFO: evict the page that has been in memory the longest. Trivial to implement, but it may throw out a page that is used all the time just because it was loaded early.
LRU (Least Recently Used): evict the page not used for the longest time. It exploits locality and usually performs well, but exact LRU needs bookkeeping on every access.
Optimal (Belady's MIN): evict the page that will not be needed for the longest time in the future. It cannot be built (nobody knows the future) but is the benchmark.
Clock (second chance): the practical approximation of LRU used in real kernels. Pages sit in a circle with a reference bit set by hardware on access; the clock hand clears bits and evicts the first page whose bit is already 0.

A worked example

With 3 frames and the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1, FIFO causes 15 faults and LRU causes 12.

Belady's anomaly

Surprisingly, with FIFO more frames can mean more faults. This is Belady's anomaly. Run it:

Going from 3 to 4 frames raises the faults from 9 to 10, which is Belady's anomaly. LRU and the optimal policy never behave like this: more memory can only help them.

// Count FIFO page faults for a reference string and a number of frames.
function fifoFaults(refs, frames) {
  const memory = [];                 // oldest page first
  let faults = 0;
  for (const page of refs) {
    if (memory.includes(page)) continue;   // hit
    faults++;
    if (memory.length === frames) memory.shift();   // evict the oldest arrival
    memory.push(page);
  }
  return faults;
}

const refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5];
for (const frames of [1, 2, 3, 4, 5]) {
  console.log(frames + " frames -> " + fifoFaults(refs, frames) + " faults");
}

Open in Code Lab

Lab exercise 2

PythonGraded in Code Lab

Count the page faults of FIFO and LRU on the same reference string.

Input: the number of frames k (an integer, at least 1) on the first line, then the reference string on the following lines: space-separated page numbers (it may be empty).

Rules:

A reference is a hit if the page is already in memory, otherwise it is a fault.
On a fault with all k frames full, evict one page, then load the new one. FIFO evicts the page that arrived first; LRU evicts the page whose last use is oldest. A hit changes the order for LRU only.

Output: two lines:

FIFO faults=<n>
LRU faults=<n>

Example: k = 3 and the reference string 1 2 3 4 1 2 5 1 2 3 4 5 print FIFO faults=9 and LRU faults=10.

Visible tests (6)

Belady string, 3 frames (FIFO wins)
Belady string, 4 frames (anomaly)
Textbook string, 3 frames
Empty reference string
One frame and repeated pages
A single page, plenty of frames

Example run

Input: 3 1 2 3 4 1 2 5 1 2 3 4 5
Expected output: FIFO faults=9 LRU faults=10

Starter code

import sys

tokens = sys.stdin.read().split()
k = int(tokens[0])
refs = [int(t) for t in tokens[1:]]

def fifo_faults(refs, k):
    # TODO 1: keep a list of the pages in memory (oldest arrival first)
    # TODO 2: on a hit do nothing; on a fault count it, evict the oldest if full, then add the page
    return 0

def lru_faults(refs, k):

More lines in Code Lab: 6

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Fragmentation and allocation

Memory gets wasted in two different ways:

Internal fragmentation: space wasted inside an allocated block. With 4096-byte pages, a 10,000-byte program needs 3 pages (12,288 bytes), so 2,288 bytes in the last page are wasted. On average about half a page per region is lost.
External fragmentation: enough free memory exists in total, but only in small scattered holes, so a large request fails. Imagine 30 free bytes as three holes of 10: a request for 15 cannot be served.

Paging removes external fragmentation for process memory (any free frame will do) at the price of a little internal fragmentation. Allocators that need contiguous regions (a malloc heap, a kernel buffer pool, simple partition schemes) still face external fragmentation, and use placement policies:

First-fit: take the first hole (lowest address) that is big enough. Fast.
Best-fit: take the smallest hole that is big enough, leaving the biggest holes intact. It must search every hole and tends to leave many tiny, useless slivers.
Worst-fit: take the largest hole, hoping the leftover is still useful. It usually performs worse in practice.

None of them wins in every case; first-fit is often as good as best-fit and faster. Compaction (moving allocations together) fixes external fragmentation but is expensive and needs relocation.

Classic example

Holes in address order are 100, 500, 200, 300, 600 KB. Requests are 212, 417, 112, 426 KB:

First-fit: 212 goes to the 500 hole (288 left), 417 to the 600 hole (183 left), 112 to the 288 hole (176 left), and 426 fails although plenty is free in total
Best-fit: 212 to 300, 417 to 500, 112 to 200 and 426 to 600: everything fits

Simulate such an allocator in the last lab.

Lab exercise 3

GoGraded in Code Lab

Simulate a contiguous-memory allocator that serves requests with first-fit or best-fit.

Input (whitespace-separated tokens, spread over any number of lines):

the policy: first or best
h, the number of free holes, then h hole sizes in address order (h may be 0)
then zero or more request sizes (positive integers) until the end of input

Rules:

first: use the lowest-index hole whose size is at least the request.
best: use the smallest hole that is big enough; on a tie take the lowest index.
The chosen hole shrinks by the request size (a hole of size 0 stays in the list and never fits anything). Nothing is ever freed or merged.

Output: one line per request, <size> -> hole <index> (0-based) or <size> -> FAIL. Finish with one line free=<total free> largest=<largest hole> (both 0 when there are no holes).

Example: best, holes 100 500 200 300 600, requests 212 417 112 426 print

212 -> hole 3
417 -> hole 1
112 -> hole 2
426 -> hole 4
free=533 largest=174

Visible tests (6)

Classic example, best-fit
Classic example, first-fit
External fragmentation
Exact fit leaves an empty hole; best-fit tie
No holes at all
No requests

Example run

Input: best 5 100 500 200 300 600 212 417 112 426
Expected output: 212 -> hole 3 417 -> hole 1 112 -> hole 2 426 -> hole 4 free=533 largest=174

Starter code

package main

import "fmt"

// pickHole returns the index of the hole that serves a request of the given
// size under the policy ("first" or "best"), or -1 if no hole is big enough.
func pickHole(policy string, holes []int, size int) int {
	// TODO 1: first-fit - return the first index whose hole is >= size
	// TODO 2: best-fit - return the index of the smallest hole that is >= size
	//         (on a tie keep the lowest index)
	return -1
}

More lines in Code Lab: 35

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Quick quiz

Question 1 of 5

With 4 KiB (4096-byte) pages, what are the page number and offset of virtual address 0x3FFF?

Question 2 of 5

What does the TLB cache?

Question 3 of 5

What is a page fault?

Question 4 of 5

Which statement about Belady's anomaly is true?

Question 5 of 5

A program needs 10,000 bytes and pages are 4096 bytes. How many pages does it use and how much memory is wasted?

Summary

Every process has a private virtual address space; the MMU and the OS translate it to physical memory, which gives isolation, convenience and more address space than RAM
Paging: address = page number + offset; the page table maps pages to frames; the offset is copied unchanged. Real page tables are multi-level trees, and the TLB caches translations
A page fault is routine (demand paging, copy-on-write, swapping); an invalid access ends in SIGSEGV. Too much paging is thrashing
Replacement: FIFO is simple but can suffer Belady's anomaly; LRU exploits locality; real kernels approximate it with Clock
Internal fragmentation is waste inside blocks, external fragmentation is scattered holes; first-fit is fast, best-fit keeps big holes but leaves slivers
You wrote an address translator, a FIFO vs LRU fault counter and a first-fit/best-fit allocator

Practice: run cat /proc/self/maps and free -h on a Linux machine, and add an optimal policy to the replacement lab to see how far FIFO and LRU are from the best possible. Next: the shell, files and permissions, or concurrency and locks.