Address Translation

Learning Outcomes

• Use a pre-populated page table to translate virtual addresses into physical addresses.
• Define a page fault and identify when an address translation scenario triggers a page fault.

In this section we discuss:

• How to do address translation when the data requested is in memory, i.e., no page fault occurs.
• How to do address translation when the data requested is not in memory, i.e., a page fault occurs.

We leave the description of the system performs address translation to this section.

#block-page-table

We discuss the fine-grained details of page tables in another section.

Address Translation, Conceptually

Case I: Page Is In Memory

Consider a scenario where a process has a 32-bit virtual address space, and physical memory is 16 KiB and paged into four 4 KiB pages. There are four steps to address translation, as shown by #fig-address-translation-i’s animation. Fow now, conceptually, a page table entry is valid if it has a physical page number (PPN) and invalid if it is labeled “disk”.

Address Translation, Case I: The target page is in memory.

Explanation for [#fig-address-translation-i](#fig-address-translation-i)

1. Program requests a memory access at a virtual address (VA). Here, load byte @ address 0xFFFF F004 to register t0. The value 0xFFFF F004 is a virtual address (VA).
2. Translate the virtual address to physical address (i.e., location in memory).
   • Extract the virtual page number (VPN) from the VA. The lower 12 bits of each address are reserved for the page offset (4 KiB pages = $2^{12}$ B pages), so the VPN is the upper 20 bits of VA, or 0xFFFFF.
3. Construct the physical address (PA). The entry associated with VPN 0xFFFFF has a valid page table entry. Access the entry for the physical page number (PPN, 0x2) and concatenate it with offset 0x004 to construct physical address 0x1004.
4. Access memory at the physical address in memory and return to the process. Here, the byte @ address 0x1004 is read and returned to the process.

This case is predicated on our page table entry being valid. A valid page table entry means that the virtual page has a corresponding physical page number, and therefore the page is in memory. Next, let’s explore when the page is not in memory.

Case II: Page Fault

We continue our scenario with the same process. Now, suppose that the next memory access triggers a page fault, as shown in #fig-address-translation-ii’s animation.

Address Translation, Case II: The target page is not in memory, triggering a page fault. With demand paging, a page fault means the page is fetched from disk.

Explanation for [#fig-address-translation-ii](#fig-address-translation-ii)

1. Program requests a memory access at a virtual address (VA). Here, load byte @ address 0x6000 0030 to register t0. The value 0x6000 0030 is a virtual address (VA).
2. Translate the virtual address to physical address (i.e., location in memory).
   • Extract the virtual page number (VPN) from the VA. The lower 12 bits of each address are reserved for the page offset (4 KiB pages = $2^{12}$ B pages), so the VPN is the upper 20 bits of VA, or 0x60000.
3. Construct the physical address (PA).
   • The entry associated with VPN 0x60000 does not have a valid page table entry. An invalid page table entry means that the physical page is not in memory.
   • Ask the OS to perform an interrupt to request the page from disk (see details in this section).
   • Once the page is loaded from disk into memory (about a million cycles later¹), resume the address translation.
   • The entry associated with VPN 0x60000 (now) has a valid page table entry. Access the entry for the physical page number (PPN, 0x2) and concanate it with offset 0x030 to construct physical address 0x2030.
4. Access memory at the physical address in memory and return to the process. Here, the byte @ address 0x2030 is read and returned to the process.

Revisiting the Library Analogy

Let’s understand virtual memory using our library analogy of the memory hierarchy.

• The book title is like a virtual address, and the Library of Congress call number is like a physical address. We usually remember a book by its title (VA), and not its call number (PA).
• The card catalog is like a page table, which maps from book title to call number. If we went straight to the bookshelves to find a book number without the call number, we likely wouldn’t find the book. So the card catalog (page table) is important.
• The corresponding card entry in the catalog has useful information:
  • Valid bit: Does the book exist in this library? (Is the page in memory?) Or do you need to request a hold and be notified when the book is available in the library? (Trigger a page fault and notify when page is loaded from disk into memory?)
  • Access bit: Can you check out this book, or is it reference-only? (We discuss memory page access rights more in this section.)

This analogy breaks down slightly because the page table is a page number lookup, not an address lookup. But we hope the weak analogy helps.

Practice

Footnotes

1. Jim Gray’s analogy figure for your reference. ↩