Virtual Memory

Sharing one memory

Last lesson, many processes took turns on the CPU. They also share one RAM, all loaded at once, and that raises two problems ¹:

• Protection. A buggy or hostile program mustn’t be able to read or overwrite another program’s memory, or the kernel’s.
• Convenience. A program shouldn’t need to know where in RAM it was put, or what else is there.

The answer is virtual memory: each process gets its own private address space, a range of addresses from 0 up to some maximum, that it uses as if it had the whole memory to itself. The kernel, with help from the CPU, maps those addresses to wherever the data really is ^{1 2}.

Address spaces

A process’s address space holds everything it uses, in a few regions ^{1 2}:

• code: the program’s instructions, loaded from its file;
• data: its global variables;
• the heap: memory requested while running, such as every object a Python program creates, which grows as the program asks for more;
• the stack: each function call’s local variables and return address, which grows and shrinks as functions are called and return.

The heap and stack sit far apart, with a huge unused gap between, so each has room to grow ². The gap costs nothing: as you’ll see, only the parts actually used get real memory.

Every address a program ever sees is one of these virtual addresses ¹. In Python, id(x) on the standard interpreter gives the memory address of the object x ³: a virtual address. Run the same program twice, at the same time, and each process has its own copy of each variable, even at the same virtual address; changing one doesn’t touch the other ². Where they really sit in RAM, only the kernel and the hardware know ¹.

Pages and frames

Mapping each byte separately would take more memory than the data itself, so memory is mapped in fixed-size blocks. The kernel divides each address space into pages and divides physical RAM into frames of the same size; 4 KB (4,096 bytes) is the usual size ². Any page can go in any frame, a process’s pages needn’t be next to each other in RAM, and not every page needs to be in RAM at all ².

An address then has two parts ^{1 2}:

• the page number, which page it’s in, from the high bits;
• the offset, which byte within that page, from the low bits.

A 4 KB page is 2^12 bytes, so the low 12 bits are the offset, and since each hex digit is 4 bits (module 1), that’s simply the last three hex digits. In 0x400A7C, the page is 0x400 and the offset 0xA7C.

Each process has a page table, kept by the kernel in RAM, listing which frame holds each of its pages ². On every memory access, a part of the CPU called the memory management unit (MMU) looks up the page number in the current process’s page table, swaps in the frame number, and keeps the offset as it was ². On each context switch, the kernel points the MMU at the next process’s page table ². That’s the protection: a process can only name its own virtual addresses, and its page table leads only to its own frames.

Translating an address

This program does what the MMU does, with two made-up page tables. Save it as translate.py:

# translate.py: turn virtual addresses into physical ones, with 4 KB pages.
PAGE_SIZE = 4096        # 2**12 bytes, so the low 12 bits (3 hex digits) are the offset

# Each process has its own page table: virtual page number -> physical frame number.
page_tables = {
    "editor":  {0x400: 0x1A2, 0x401: 0x0B7, 0x7FF: 0x3C0},
    "browser": {0x400: 0x2E9, 0x7FF: 0x015},
}

def translate(process, address):
    page, offset = divmod(address, PAGE_SIZE)
    frame = page_tables[process].get(page)
    if frame is None:
        return f"page {page:#x}: no frame, page fault"
    return f"page {page:#x} -> frame {frame:#x} -> {frame * PAGE_SIZE + offset:#x}"

for process, address in [("editor", 0x400A7C), ("editor", 0x401004),
                         ("browser", 0x400A7C), ("browser", 0x401004)]:
    print(f"{process:<8} {address:#x}   {translate(process, address)}")

divmod(address, 4096) gives the page number and the offset in one step: dividing by 2^12 is the same as cutting off the last three hex digits.

me@linuxbox:~$ python3 translate.py
editor   0x400a7c   page 0x400 -> frame 0x1a2 -> 0x1a2a7c
editor   0x401004   page 0x401 -> frame 0xb7 -> 0xb7004
browser  0x400a7c   page 0x400 -> frame 0x2e9 -> 0x2e9a7c
browser  0x401004   page 0x401: no frame, page fault

The same virtual address, 0x400a7c, leads to two different places in RAM, one per process. The offset a7c comes through unchanged. And the browser has nothing at page 0x401, so that access can’t be translated: a page fault.

Making it fast

A page table lives in RAM, so every memory access would need a second access first, to read the table: twice the work ². So the MMU keeps a small, very fast cache of recent translations, the translation lookaside buffer or TLB. Thanks to locality, the same few pages get used over and over, so nearly every lookup hits the TLB and costs almost nothing ². Real page tables, on x86 for example, are also built in several levels, like a tree, so that the unused gap in an address space takes no page-table space at all ¹.

More memory than RAM

Since not every page has to be in RAM, the kernel can keep some on disk, in swap space, and run programs whose memory adds up to more than the RAM installed ¹. Each page-table entry has a valid bit saying whether the page is in a frame ². When a program touches a page that isn’t, the MMU raises a page fault, and the kernel ²:

1. finds a free frame, or makes one by evicting some other page, writing it out to disk first if it has been changed;
2. reads the needed page from disk into that frame;
3. updates the page table;
4. restarts the instruction, which now succeeds.

The program never knows, except for the time: reading from disk takes thousands of times longer than a memory access, or more (last module). If the running programs actively need more memory than there is, the system spends its time moving pages in and out and gets almost nothing done, which is called thrashing ¹. Linux’s last resort when memory is exhausted is the out-of-memory killer, which picks a memory-hungry process and kills it ¹.

A different case: an address that isn’t part of the process’s address space at all, such as following a null pointer. Then there’s nothing to load, and the kernel stops the program with a segmentation fault, the signal SIGSEGV ². Python programs almost never hit these; programs written in C can.

Seeing it on Linux

• getconf PAGESIZE prints the page size in bytes.
• ps -o pid,vsz,rss,comm: VSZ is a process’s virtual memory size, everything in its address space, and RSS, the resident set size, is how much of it is actually in RAM, both in KiB ⁴. VSZ is usually far bigger: much of an address space is mapped but never touched, or shared, or out in swap.
• free -h shows physical memory and swap, on its Mem: and Swap: lines ⁵. If swap use keeps climbing and everything slows to a crawl, the system is probably thrashing.

Your turn

So

Virtual memory gives each process a private address space of code, data, heap, and stack, and every address a program uses is virtual. Memory is handled in 4 KB pages: an address is a page number plus an offset (with 4 KB pages, the last three hex digits), and each process’s page table maps its pages to frames anywhere in RAM. The CPU’s MMU translates every access, the TLB caches recent translations, and switching page tables on each context switch keeps processes apart. Pages can also live on disk in swap, loaded on demand by page faults; too much of that is thrashing, and an address outside the address space is a segmentation fault.