Part 3 of 7 · 3 min read
Translation
In plain words: Every virtual address is split into two parts. The high bits are the page number. The low bits are the offset, the position inside the page. For a page size of 2^k bytes, the offset is the low k bits. For 4 KiB pages, k = 12.
The translation keeps the offset unchanged and replaces the page number by a frame number:
- Cut the virtual address into page number and offset.
- Look up the page number in the page table: it holds the frame number.
- Form the physical address as: frame number × page size + offset.
Here is an example with 4 KiB pages. The virtual address 0x12345 has page number 0x12 and offset 0x345. If the table says that page 0x12 is in frame 0x7, the physical address is 0x7345: the frame number 0x7, then the offset 0x345 unchanged.
A smaller example, with made-up numbers, lets you check every step by hand. The page size is 1,024 bytes. The process has four pages, and the table maps page 0 to frame 5, page 1 to frame 9, page 2 to frame 7 and page 3 to frame 2.
#define PAGE 1024
struct pte { int valid; int frame; };
struct pte table[4] = { {1,5}, {1,9}, {1,7}, {1,2} };
int translate(unsigned logical, unsigned *physical) {
unsigned page = logical / PAGE, offset = logical % PAGE;
if (page >= 4 || !table[page].valid) return -1; /* trap: no such page */
*physical = table[page].frame * PAGE + offset;
return 0;
}
Running it on five addresses printed:
logical 0: page 0 offset 0 -> frame 5, physical 5120
logical 1030: page 1 offset 6 -> frame 9, physical 9222
logical 3000: page 2 offset 952 -> frame 7, physical 8120
logical 4095: page 3 offset 1023 -> frame 2, physical 3071
logical 4100: page 4 offset 4 -> trap
Check the third row by hand: 3,000 divided by 1,024 is 2 with remainder 952. Page 2 is in frame 7, and 7 × 1,024 + 952 = 8,120. The last row asks for page 4, but the process has only pages 0 to 3, so the hardware raises a trap. The kernel then decides what to do (page 7 shows this; for a wrong address it ends the process with a segmentation fault).
Notice that the two ranges are not in the same order: logical addresses 0 to 4,095 run through frames 5, 9, 7, 2, which are scattered. The process cannot tell. This is the same trick as page 1, now with many pieces.
Page table
A page table is a per-process table, kept in memory, that holds for each virtual page the number of the frame that contains it, together with control bits; the hardware reads it on every translation that is not found in the TLB (page 5).
Example: the table {5, 9, 7, 2} maps page 0 to frame 5, page 1 to frame 9, page 2 to frame 7 and page 3 to frame 2.
Check yourself: 1. For 4 KiB pages, how many bits are the offset? 2. Translate logical address 1,500 with the table above. 3. What happens for logical address 5,000?