Address Translation - CS 61C Course Notes

1Learning 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.

Accessing memory

A “memory manager” (see this section) retrieves data by translating virtual addresses to physical addresses as follows:

A process requests a memory access at a given virtual address (VA).
Translate the virtual address to the physical address:
- Extract virtual page number (VPN) from VA
- Access the page table entry corresponding to this VPN to look up the corresponding physical page number (PPN).
Construct the physical address (PA):
- If the corresponding page table entry is valid, obtain the PPN from the page table entry and construct the PA by concatenating the PPN and the page offset.
- If the corresponding page table entry is not valid, trigger a page fault. After the page is loaded from disk into memory, repeat this step.
Access memory at the physical address in memory and return to the process.

The middle two steps are address translation. The last step is data access.

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.

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

2Address Translation, Conceptually¶

2.1Case 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 Figure 1’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”.

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

Explanation for Figure 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).
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¹² B pages), so the VPN is the upper 20 bits of VA, or 0xFFFFF.
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.
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.

2.2Case 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 Figure 2’s animation.

Figure 2: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 Figure 2

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).
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¹² B pages), so the VPN is the upper 20 bits of VA, or 0x60000.
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^[1]), 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.
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.

2.3Revisiting 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.

3Practice¶

Footnotes¶

Jim Gray’s analogy figure for your reference.
↩