Paging, TLB and Page Tables
Table of Contents
1. Overview of Paging
Paging is built on top of the idea of segmentation. It breaks a virtual address space into fixed-size segments, called pages. For convenience of managing free space, the physical memory is also chopped up into segments of same size as pages, called page frames, or frames.
In the context of paging, a physical address can be regarded as a physical frame number (PFN) (that help locates the address of the physical frame) plus an offset within the frame. The virtual address can be regarded as a virtual page number (VPN) plus an offset.
In the case of 4KB page size, if the system is byte-addressable, since 4KB = \(2^{12}\) bytes, then the offset is \(12\) bits.
The duty of address translation is to convert the VPN to PFN to get the physical address. Here, we need to help of page tables to help maintain the mapping from VPN to PFN. Also, to accelerate address translation, translation-lookaside buffers (TLBs) are introduced to cache the mapping.
1.1. Procedure of a Full Translation
Here, we include TLBs and multi-level page tables.
- Extract VPN from virtual address
- Consult TLB for VPN
2. Page Table Entry
A page table is a linear array of page table entries (PTEs), indexed by VPN. OS checks PTEs to find out PFN, given VPN. A page table usually fits a single page (frame), meaning their sizes are equal.
Each page table entry maintains PFN and extra bits that convey information.
3. Translation-Lookaside Buffer (TLB)
3.1. TLB Miss
What happens when TLB miss occurs?
If hardware is responsible for handling TLB miss (usually the case of CISC), then the hardware needs to know the address of page table. This requires a page-table base register.
If TLB miss is handled by OS, the invocation chain is “TLB Miss -> Hardware raise exception -> Trap handler of TLB Miss -> Look up page tables”.
Thus, the return-from-trap should be different. Upon TLB miss, return-from-trap should re-executate the instruction rather than execute next instruction; second, TLB miss cannot recurse infinitely. A solution to this is to record the physical address (not virtual) of TLB handler into TLB.
3.2. TLB at Context Switch
TLB entries should only be valid for the current-running process. A simple solution is to simply flush by setting valid bits of all entries to \(0\).
A better solution is to share TLBs across processes but will require hardware support. The approach is to add an extra field Address Space Identifier (ASID), which is similar to process ID that marks which process this entry belongs to, but usually takes less bits (e.g., 8 bits).
Therefore, TLBs can store translation caches for multiple processes, as well as sharing physical frames across processes.
4. Multi-Level Page Tables
Multi-level page tables are to reduce the size of page tables by further ignoring unallocated pages through breaking up page tables into pages. MLPT chops up a page table into page-sized units. If all entries in the unit are invalid (which means that, none of the pages are allocated), then we don’t need to allocate memory to store these entries.
These units are called page directory, and each unit is called page directory entry (PDE). PDE tracks whether a page of the page table is valid, along with its address in memory.