Definition
Page Table
A page table is a data structure used by an operating system in a paging system to store the mapping between the logical addresses of a process and its physical addresses in RAM.
Each entry in the page table (PTE) typically contains:
- Frame Number: The physical location of the page.
- Present Bit: Indicates if the page is currently in RAM (see Virtual Memory).
- Modified Bit (Dirty Bit): Indicates if the page has been written to since it was loaded.
- Protection Bits: Specify read, write, or execute permissions.
Architectures
1. Multilevel Page Tables
For large address spaces, a single linear page table would consume too much memory. The table is instead broken into multiple levels (hierarchical paging), allowing parts of the page table themselves to be swapped out to disk.
2. Inverted Page Tables
Instead of one table per process, the system maintains one global table with one entry for each physical frame in memory.
- Entry Structure: Each entry stores the PID and page number currently residing in that frame.
- Address Translation: The CPU uses a hashing function or associative search to find the PID/page pair in the table. The index of the matching entry corresponds to the physical frame number.
- Efficiency: Significantly reduces memory usage for the page table itself, as the table size depends on physical RAM size rather than the sum of all processes’ virtual address spaces.
Performance
Accessing the page table adds an extra memory reference for every data access. To mitigate this, hardware uses a Translation Lookaside Buffer (TLB) to cache the most recently used mappings.