Page Table

A Page Table Entry (PTE) is the fundamental unit within a page table, storing the mapping for a single virtual page. Its structure is hardware-defined but typically includes:

• Physical Frame Number (PFN): The starting physical address of the corresponding page frame in RAM.
• Present/Absent Bit: Indicates if the page is currently loaded in physical memory (present) or has been swapped out to disk (absent, triggering a page fault).
• Read/Write Bit: Controls write permissions.
• User/Supervisor Bit: Determines if the page is accessible from user-mode or only kernel-mode.
• Accessed Bit: Set by hardware when the page is read or written; used by page replacement algorithms.
• Dirty Bit: Set by hardware when the page is written to; indicates the page must be written back to disk if evicted.

Multi-Level Page Tables (e.g., two-level, four-level, five-level) are a hierarchical design used to manage the page table's own memory footprint efficiently. Instead of one massive linear table, the virtual address is split into indexes for each level.

• How it works: A top-level Page Directory contains pointers to intermediate Page Middle Directories, which finally point to Page Tables containing the actual PTEs. This creates a tree structure.
• Key Benefit: It saves memory because only the page tables for regions of the address space that are actually allocated need to be allocated and resident. Unused vast regions of the address space consume no intermediate table entries.
• Trade-off: Adds a small latency overhead for address translation, as multiple memory accesses may be needed to walk the hierarchy (mitigated by the TLB).

An Inverted Page Table (IPT) is an alternative page table design where the table is indexed by the physical frame number, not the virtual page number. There is one entry per physical page frame in the entire system, not per virtual page per process.

• Structure: Each IPT entry stores the Process ID (PID) and the Virtual Page Number (VPN) of the process currently occupying that physical frame.
• Translation Process: To find a mapping, the memory management unit (MMU) must perform a hash table lookup on the (PID, VPN) pair to locate the corresponding physical frame. This is slower than a direct lookup in a traditional page table.
• Use Case: Primarily used in 64-bit architectures (e.g., PowerPC, some ARM configurations) where the virtual address space is astronomically large, making per-process multi-level tables potentially wasteful. It guarantees a constant, system-wide page table size proportional to physical RAM.

A Hashed Page Table is a common implementation technique for Inverted Page Tables and large sparse address spaces. It uses a hash function to map a virtual address (often combined with a Process ID) to a chain of entries in a hash table.

• Collision Handling: Uses chaining; each hash bucket contains a linked list of entries for virtual addresses that hash to the same value.
• Performance: Lookup time depends on the hash function quality and chain length. In practice, chains are kept very short.
• Advantage over linear search: Provides O(1) average-case lookup time for translations, making the search of a large inverted table feasible. It is a core component of the translation mechanism in architectures like PowerPC's Real Mode (RP).

The Page Table Base Register (PTBR), also called CR3 on x86/x86-64 architectures, is a privileged CPU register that holds the physical address of the root of the page table hierarchy (e.g., the Page Directory Pointer Table or PML4) for the currently executing process.

• Context Switch Critical: During a process context switch, the operating system kernel must load the PTBR with the physical address of the new process's page table root. This act instantly changes the entire virtual-to-physical address map for the CPU.
• Memory Isolation: Because each process has its own page table and its root address in the PTBR, processes are isolated—they cannot access each other's memory unless explicitly shared via identical mappings.
• Kernel Mapping: The upper portion of the virtual address space (kernel space) is often mapped identically in all process page tables, with protections preventing user-mode access. This allows the kernel to be always "in context."

The Translation Lookaside Buffer (TLB) is a hardware cache, integral to the page table system, that stores recent virtual-to-physical address translations. It is not a component of the page table but is its critical performance accelerator.

• Operation: On a memory access, the MMU first checks the TLB for a cached translation (a TLB hit). If found, the physical address is obtained in ~1 cycle. If not found (a TLB miss), the costly page table walk in memory is initiated.
• Flushing: TLBs are per-CPU and must be flushed (or specific entries invalidated) on events like a context switch (changing the PTBR) or when the OS modifies a page table entry (e.g., swapping a page out). Instructions like INVLPG (x86) handle this.
• Architectures: Modern CPUs have multiple, hierarchical TLBs (L1, L2) and may support large pages (e.g., 2MB, 1GB) to reduce TLB pressure for big, contiguous memory regions.

A hardware component within or alongside the CPU that performs the critical task of virtual-to-physical address translation using the page table. Its primary functions include:

• Walking the page table to resolve addresses.
• Enforcing memory protection by checking permissions (read/write/execute).
• Triggering page faults when a required page is not in RAM.
• Managing the Translation Lookaside Buffer (TLB) cache. The MMU is the physical engine that makes the abstract page table usable by the processor.

A small, high-speed cache inside the MMU that stores recently used virtual-to-physical page translations. It is a critical performance optimization because:

• Accessing the full page table in RAM for every memory reference would be prohibitively slow.
• The TLB provides near-CPU-speed translation for cached entries.
• On a TLB miss, the MMU must perform a slower page table walk.
• Modern CPUs have multi-level TLBs (L1, L2) analogous to data caches. Effective memory locality is key to high TLB hit rates.

An interrupt (exception) raised by the MMU when a process accesses a virtual address that maps to a page which is not currently resident in physical memory (RAM). The operating system's handler must resolve the fault by:

1. Validating the address (is it legal?).
2. Locating the required page on disk (in the swap file or backing store).
3. Loading the page into a free frame in RAM.
4. Updating the page table entry with the new physical address.
5. Resuming the interrupted process. This mechanism enables demand paging and memory swapping.

A memory management technique that provides processes with the illusion of a large, contiguous, private address space, which is larger than the available physical RAM. Key abstractions it provides include:

• Address Space Isolation: Each process has its own independent virtual address space.
• Demand Paging: Pages are loaded into RAM only when needed.
• Swap Space: Uses disk storage as an extension of RAM. The page table is the fundamental data structure that implements the core mapping for virtual memory, translating each process's virtual addresses to system-wide physical addresses.

The process of moving inactive pages of memory between RAM and secondary storage (disk) to free up physical frames for active processes. It works in conjunction with the page table:

• Page Out: The OS copies a modified (dirty) page from RAM to the swap partition/file and marks its page table entry as invalid (not present).
• Page In: When that page is accessed again (causing a page fault), it is read back from disk into RAM.
• The page table tracks the location of each page (RAM vs. disk) via the present bit and, if on disk, its swap identifier and offset.

A hierarchical page table structure used to reduce its memory footprint. Instead of one massive table covering the entire address space, it uses a tree of smaller tables.

• Common Design: A two-level table with a Page Directory and Page Tables.
• Sparse Memory Efficiency: Only allocates memory for page tables covering regions of the address space that are actually in use.
• Trade-off: Requires multiple memory accesses (a page table walk) for translation, making the TLB even more crucial for performance. This is the standard design in modern systems like x86-64, which uses a four-level page table.