A page table is a data structure stored in physical memory and used by the operating system’s memory manager to map a process’s virtual addresses to physical addresses in a computer’s memory. Each page table has a page table base register (PTBR), which indicates the first address of that page table in physical memory. Each page table entry (PTE) corresponds to a single page, and is therefore indexed by the VPN. A single PTE contains:
The physical page number (PPN), or the address starting which the corresponding virtual page is stored in physical memory.
Additional control metadata, such as:
A valid bit, which records whether the virtual memory is in DRAM (physical memory), or in the disk.
Permission bits, which may serve a variety of functions, from read and write ability to execution permissions.
For a K-byte page with L-byte PTEs, V-byte virtual memory, and an P-byte physical memory, such that the offset is log2(K) bits, the VPN is log2(N)−log2(K) bits, and the PPN is log2(M)−log2(K) bits, the page table can be illustrated as:
\begin{document}\begin{tikzpicture} % Draw the inner boxes for Metadata \draw[thick] (-.5,3) rectangle (3,4) node[midway] {Metadata}; \draw[thick] (-.5,2) rectangle (3,3); \node at (4, 1.5) {$\vdots$}; \draw[thick] (-.5,0) rectangle (3,1); % Draw the inner boxes for Data \draw[thick, fill=darkgray] (3,3) rectangle (5,4) node[midway] {PPN}; \draw[thick, fill=darkgray] (3,2) rectangle (5,3); \node at (1.25, 1.5) {$\vdots$}; \draw[thick, fill=darkgray] (3,0) rectangle (5,1); % Add text labels \node at (-1.25, 4.25) {VPN}; % Add index numbers \node at (-1,3.5) {$0$}; \node at (-1,2.5) {$1$}; \node at (-1, 1.5) {$\vdots$}; \node at (-1.25,0.5) {$\frac{V}{K}-1$}; % Add offset numbers \node at (0, 4.25) {$8L-1$}; \node at (3, 4.25) {$\log_2(P)-1$}; \node at (5, 4.25) {0};\end{tikzpicture}\end{document}
Note! KV−1 comes from the fact that our virtual memory size is V bytes, and each page is K bytes. Then, each page in virtual memory has a unique page table entry.