Virtual memory: address translation with a page table

Split a virtual address into page number and offset and map it to a physical frame.

Python

PAGE_SIZE = 4096
page_table = {0: 5, 1: 2, 2: None, 3: 7}


def translate(address):
    page, offset = divmod(address, PAGE_SIZE)
    if page not in page_table:
        return "segmentation fault"
    frame = page_table[page]
    if frame is None:
        return "page fault"
    return frame * PAGE_SIZE + offset


print(PAGE_SIZE.bit_length() - 1)
for address in (0, 4100, 8200, 16383, 20000):
    print(address, translate(address))

Output

12
0 20480
4100 8196
8200 page fault
16383 32767
20000 segmentation fault

Explanation

Virtual memory gives each process its own address space. The program uses virtual addresses and hardware, with the operating system's help, translates them to physical addresses. Memory is divided into fixed-size pages in the virtual space and equal-size frames in physical memory.

A virtual address is split into a page number and an offset within the page. With a 4096-byte page, the low 12 bits are the offset and the remaining high bits are the page number. The page table maps each page number to a frame number, and the physical address is frame × page size + offset. Each entry also records whether the page is present in memory.

If the page is not present, the hardware raises a page fault and the operating system decides what to do. It may load the page from disk (demand paging) or, for an address the process was never given, signal an error such as a segmentation fault. Real systems use multi-level page tables to save space and a translation lookaside buffer (TLB) to cache recent translations so most accesses avoid the table walk.

Explore the dry run

Guided walkthroughReady

1PAGE_SIZE = 4096

2page_table = {0: 5, 1: 2, 2: None, 3: 7}

5def translate(address):

6 page, offset = divmod(address, PAGE_SIZE)

7 if page not in page_table:

8 return "segmentation fault"

9 frame = page_table[page]

10 if frame is None:

11 return "page fault"

12 return frame * PAGE_SIZE + offset

15print(PAGE_SIZE.bit_length() - 1)

16for address in (0, 4100, 8200, 16383, 20000):

17 print(address, translate(address))

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Integer division gives the page number; the remainder is the offset inside the page.	`4100 → page 1, offset 4`	—
Page 1 lives in frame 2, so the physical address is 2 × 4096 + 4 = 8196.	`8196`	—
Page 2 is valid but not in memory, so the OS must handle a page fault.	`8196`	—
Address 20000 falls in page 4, which has no mapping, so it is an invalid access.	`8196`	12 0 20480 4100 8196 8200 page fault 16383 32767 20000 segmentation fault

Cost and common mistakes

Translation is O(1) with a flat table. Hardware uses a TLB so most translations avoid even that table lookup.

Page size is a power of two so the split is a cheap bit operation in hardware; the offset is the low bits and is never translated.
A page fault is not always an error. For demand paging it is a normal event that the OS services by loading the page.
A single-level page table for a large address space would be huge. Real systems use multi-level or hashed tables.

Try it yourself

What physical address does virtual address 12289 map to?

Reveal answer and reasoning

12289 is page 3, offset 1, and page 3 is in frame 7, so the physical address is 7 × 4096 + 1 = 28673.

Virtual memory: address translation with a page table

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading