1. Introduction
In this tutorial, we’ll take a look at multi-level page tables. We’ll analyze how they help us reduce main memory usage.
2. Paging
Paging is a memory management technique operating systems use to manage physical and virtual memory efficiently.
When a process requires a page not in main memory, the operating system fetches it from secondary storage (typically a hard drive). It places it into an available page frame in RAM. At the same time, virtual addresses are translated to physical.
The operating system maintains a page table that maps the virtual memory to physical memory addresses, allowing processes to access data in physical memory through these mappings indirectly.
2.1. Page Table Size
The main problem with page tables is that they can get pretty big. Let’s check out an example to see how big a page table can get. We’ll focus on a 32-bit machine using 4kB page sizes.
Our page table is an array consisting of multiple page table entries (PTEs):
Each entry includes a page base address followed by some control bits. Some important control bits are the protection, present, and dirty bits among others:
They inform the OS about who can access the page, whether it is currently present in memory, and if it has been modified, respectively.
To find information inside each page, a PTE allocates some page address bits for the page offset and uses the rest for the actual page number. With a 4kB page size, we need 12 bits for the page offset to reach the entire page. That leaves 20 bits for pages. With 20 bits that can be either 0 or 1, we have 2^20 combinations. So, This means that we need $2^20 \approx$ 1 million page table entries.
For each PTE, we need about 4 bytes. So, this works out to 1 million PTEs times 4 bytes, which is a 4MB. Although that’s not that bad, the problem is that each program needs its page table. For a system running 100 applications (which is typical on modern computers), this racks up to 400MB. This is a significant amount of memory to store page tables, and this information mustn’t be swapped out to the disk. It has to stay in RAM.
To counter this problem, systems incorporate multi-level page tables.
3. Multi-Level Page Tables
There’s no way to limit the space a page table can require since any process using virtual memory has to keep the translation information between address spaces somewhere. What can be done is not having each process’s page table in RAM at all times. We can achieve that by using multi-layered page tables or hierarchical paging.
3.1. Idea
The idea behind multi-level page tables is pretty simple. Instead of keeping all the information in a single table, we split it between smaller tables. The system can then swap unnecessary tables to disk storage and only bring them to RAM when needed.
The highest-level page table often called the page directory or page directory pointer table, contains page directory entries (PDEs). A PDE includes two main elements. The first one points to the base addresses of different page tables in disk or RAM. The second one consists of some control bits, such as an indicator of whether the pointed table is currently in memory.
3.2. Example
Let’s check out an example of a system using two layers of page tables:
The first-level table contains PDEs that point to the various other page tables. So, the operating system now doesn’t have one flat table in memory containing millions of entries. Instead, we split the translation information into page tables having 1024 entries. Some page tables are in memory, whereas others are swapped out to disk.
In the above example, the first level page table must be in RAM as long as the process runs. If the process can’t find this first table, it will be unable to locate any data using virtual addresses.
This way, we store around 1000 entries of the first-level page table in RAM instead of a vast flat table with millions of entries.
3.3. Translation With Multi-Level Page Tables
Instead of using page tables that point directly to pages in physical memory or disk storage, multi-level PTEs point to other page tables. How does a process navigate this hierarchy to find the wanted page?
Let’s consider a 32-bit system with 4kB page sizes. If using a single flat page table with all the translation information, a virtual address will have two components:
The last 12 bits are the page offset (we need 12 bits to reach every address in a 4kB page), and the first 20 bits are used as a key to find the correct page in the page table.
What happens if we use two-layer page tables? We split the virtual page number. We use some bits as a key for the entry in the first-level page table, while the rest serve as the key for the corresponding second-level page table:
For example, we can use the first 10 bits to find the entry in the first-level table and the second 10 bits for the second table. We only need 10 bits because these tables are usually small (usually, only $2^10=1024$ entries).
We further divide the virtual address if we have more than two layers of page tables. We’ll have as many components as levels.
4. How Many Layers to Have?
Choosing between a different number of page layers is essential in balancing flexibility and performance.
Too few layers will limit fine-grained mapping, while too many layers can introduce complexity and slow down memory access. Factors like the size of the virtual address space, available memory for page tables, and the system’s specific needs play a significant role in this decision.
It’s worth noting that in practice, the most commonly used are two- and three-level systems, as they provide a compromise between memory efficiency and address translation speed.
Ultimately, the choice of page layers entirely depends on the system’s demands and the performance we need to get out of it.
5. Conclusion
In this article, we discussed multi-level page tables.
They save space in the physical memory by splitting the virtual-to-physical-address translation information into multiple smaller page tables. In this approach, page tables are organized into hierarchical layers where each layer points to the tables on the first layer below. We save space because page tables that aren’t currently needed are swapped out to the disk.