Multilevel Paging in OS

Introduction

A single-level page table keeps one entry for every virtual page in a process’s virtual address space. This is simple, but it can waste a lot of memory when most of that address space is unused.

Multilevel paging solves this by organizing page tables in levels. Lower-level page tables are created only for the parts of the virtual address space that are actually being used.

Why Multilevel Paging Is Needed

Consider a system with a 32-bit virtual address size, a 4 KB page size, and a 4-byte PTE size.

A 32-bit virtual address space contains 2^32 bytes. Since 4 KB = 2^12 bytes, the number of virtual pages is 2^32 / 2^12 = 2^20 pages

A single-level page table needs one PTE for each virtual page: 2^20 * 4 bytes = 4 MB

So one process may need a 4 MB page table, even if it uses only a small part of its virtual address space. Multilevel paging avoids allocating page-table memory for large unused regions.

Basic Idea of Multilevel Paging

Multilevel paging stores page tables in a tree-like structure.

In a two-level design, the structure is: Page directory => Page table page => PTE => Physical frame

The page directory is the top level. Each valid directory entry points to a second-level page table. That second-level table contains the actual PTEs for a portion of the virtual address space.

If a region of virtual memory is unused, its page-directory entry can remain invalid, and the corresponding second-level page table does not need to be allocated.

Multilevel Paging and its Need

Address Split in Two-Level Paging

In normal single-level paging, a virtual address is divided into: Virtual page number + Offset

In two-level paging, the virtual page number is split again: Outer index + Inner index + Offset

Each part has a role:

Outer index: Selects the page-directory entry.
Inner index: Selects the PTE inside the second-level page table.
Offset: Selects the byte inside the final physical frame.

The offset does not change. Multilevel paging only changes how the virtual page number is looked up.

Finding the Address Split

Suppose a system has a 32-bit virtual address size, a 4 KB page size, a 4-byte PTE size, and a 4 KB page-table page size.

Since page size is 4 KB = 2^12, the offset needs 12 bits.

The remaining bits form the virtual page number: VPN bits = 32 - 12 = 20 bits

Each second-level page table page can store: 4096 / 4 = 1024 = 2^10 PTEs

So the inner index needs 10 bits. The remaining 10 VPN bits become the outer index.

The final split is: 10-bit outer index + 10-bit inner index + 12-bit offset

Compact Virtual Address Example

For the virtual address 0x12345678, using the 10 + 10 + 12 split, the address is divided into an outer index, inner index, and offset:

Offset: 0x678 => the lowest 12 bits.
VPN: 0x12345 => the remaining upper 20 bits.
Outer Index: 0x48 = 72 => the first 10 bits of the VPN.
Inner Index: 0x345 = 837 => the remaining 10 bits of the VPN.

Thus, the 20-bit VPN is split into two 10-bit indexes, while the lowest 12 bits identify the offset within the page.

Virtual Address Example

Page Table Pages: Minimum and Maximum

Assume each second-level page table contains 1024 PTEs, and a process touches 2000 virtual pages.

If those 2000 pages are packed closely, the number of required second-level tables is: ceil(2000 / 1024) = 2

Including the outer page directory: Minimum page-table pages = 1 + 2 = 3

For the maximum case, the used pages may be spread across as many different outer-directory entries as possible. With a 10-bit outer index, there can be at most 2^10 = 1024 second-level tables.

Maximum page-table pages = 1 + 1024 = 1025

The outer page directory must be counted in both cases.

Benefit and Cost

The main benefit of multilevel paging is memory saving. A process does not need lower-level page tables for unused parts of its virtual address space.

The cost is extra translation work. If the translation is not already cached, the system may need to walk through multiple levels before finding the final PTE.

This makes multilevel paging a time-space trade-off: it saves page-table memory, but a TLB miss can make translation slower.

Summary

Multilevel paging reduces page-table memory by organizing page tables into levels. Instead of one large linear table, it uses a page directory and allocates lower-level page tables only for used virtual address regions.

In two-level paging, the virtual address is split into outer index, inner index, and offset. The approach saves memory for sparse address spaces, but translation can require more work when the TLB does not already contain the needed mapping.