9.6.Address Translation
\(9.6.\)Address Translation
1.Summary of Translation Symbols
2.Basic Struction
TThe following figure shows how the MMU uses the page table to perform the mapping \(MAP:VAS \rightarrow PAS \cup \emptyset\):
The page table base register(PTBR) points to the current page table.
The n-bit virtual address has two components: a \(p\)-bit virtual page offset(VPO) and an \((n−p)\)-bit virtual page number(VPN).
The MMU uses the VPN to select the appropriate PTE. For example, VPN 0 selects PTE 0, VPN 1 selects PTE 1.
The corresponding physical address is the concatenation of the physical page number(PPN) from the page table entry and the VPO from the virtual address.
Since the physical and virtual pages are both \(P\) bytes, the physical page offset(PPO) is identical to the VPO.
3.CPU Hardware Performance for Page Hit & Page Fault
The CPU performs the following steps when there's a page hit:
The processor generates a virtual address and sends it to the MMU.
The MMU generates the PTE address and requests it from the cache/ main memory.
The cache/main memory returns the PTE to the MMU.
The MMU constructs the physical address and sends it to the cache/main memory.
The cache/main memory returns the requested data word to the processor.
When there's a page fault, step 1~3 are the same:
The valid bit in the PTE is zero, so the MMU triggers an exception, which transfers control in the CPU to a page fault exception handler in the operating system kernel.
The fault handler identifies a victim page in physical memory, and if that page has been modified, pages it out to disk.
The fault handler pages in the new page and updates the PTE in memory.
The fault handler returns to the original process, causing the faulting instruction to be restarted. The CPU resends the offending virtual address to the MMU. Because the virtual page is now cached in physical memory, there is a hit.
4. Integrating Caches and VM
- The main idea is that the address translation occurs before the cache lookup.
5.Translation Lookaside Buffer
When we meet a page fault, we will need to do an additional fetch from memory. Many systems try to eliminate this cost by including a small cache of PTEs in the MMU called a translation lookaside buffer(TLB).
- A TLB is a small, virtually addressed cache where each line holds a block consisting of a single PTE:
The index and tag fields that are used for set selection and line matching are extracted from the virtual page number in the virtual address.
- If the TLB has \(T = 2^t\) sets, then the TLB index(TLBI) consists of the \(t\) least significant bits of the VPN, and the TLB tag(TLBT) consists of the remaining bits in the VPN.
For a TLB hit, the mMU fetches the appropriate PTE from the TLB:
6.Multi-Level Page Tables
\(a.\)An example
The common approach for compacting the page table is to use a hierarchy of page tables. The following is an example of a page table, which has a 32-bit address space, 4 KB pages, and a 4-byte PTE:
For the page table:
Each PTE in the level 1 table is responsible for mapping a 4 MB chunk of the virtual address space.
Each chunk consists of 1,024 contiguous pages.
This scheme reduces memory requirements in two ways:
If a PTE in the level 1 table is null, then the corresponding level 2 page table does not even have to exist.
Only the level 1 table needs to be in main memory at all times. The level 2 page tables can be created and paged in and out by the VM system as they are needed.
\(b.\)Address translation for k-level page table hierarchy
The virtual address is partitioned into \(k\) VPNs and a VPO.
Each VPN \(i\)(\(1 \leq i \leq k\)) is an index into a page table at level \(i\).
Each PTE in a level \(j\) table(\(1 \leq j \leq k - 1\)) points to the base of some page table at level \(j + 1\).
Each PTE in a level \(k\) table contains either the PPN of some physical page or the address of a disk block.
As with a single-level hierarchy, the PPO is identical to the VPO.