1. Introduction

In a paging system, every process requires a page table to translate logical addresses into physical addresses. For large address spaces such as 32-bit and 64-bit systems, a single page table can become extremely large, consuming a significant amount of memory.

Multilevel Paging solves this problem by dividing a large page table into multiple smaller page tables organized in a hierarchical structure.

Instead of keeping one huge page table in memory, only the required portions of the hierarchy are created and maintained.

2. Problem with Single-Level Paging

Consider a system with:

Logical Address Space = 32 bits
Page Size = 4 KB = 2^12 bytes

Number of Pages

Number of Pages
=
2^(32-12)
=
2^20
=
1,048,576 pages

If each page table entry requires:

4 bytes

Then page table size becomes:

1,048,576 × 4
=
4 MB

for a single process.

Problems

• Large memory overhead

• Most entries remain unused

• Wastage for sparse address spaces

• Poor scalability

3. What is Multilevel Paging?

Multilevel paging is a paging technique in which the page table is divided into multiple levels of smaller page tables.

Key Idea

Large Page Table
        ↓
Split into Smaller Tables
        ↓
Organized Hierarchically

Only the page tables that are actually needed are created.

This significantly reduces memory consumption.

4. Basic Concept

Instead of:

Page Number
        ↓
Single Page Table
        ↓
Frame Number

we use:

Page Number
        ↓
Outer Page Table
        ↓
Inner Page Table
        ↓
Frame Number

This creates a hierarchy.

5. Two-Level Paging

The simplest multilevel paging scheme is Two-Level Paging.

The logical address is divided into:

Logical Address
=
p1 + p2 + offset

6. Components of Logical Address

p1 (Outer Page Table Index)

Used to locate an entry in the outer page table.

p2 (Inner Page Table Index)

Used to locate an entry in the inner page table.

Offset

Used to locate the exact byte within the page.

7. Logical Address Structure

Suppose:

Logical Address = 32 bits
Page Size = 4 KB

Since:

4 KB = 2^12

Offset requires:

12 bits

Remaining bits:

32 - 12
=
20 bits

Split page number into:

p1 = 10 bits
p2 = 10 bits

Thus:

| p1 | p2 | Offset |
|10b|10b|12 bits|

8. Structure of Two-Level Paging

Outer Page Table

Contains pointers to inner page tables.

Example:

Inner Page Table

Contains frame mappings.

Example:

9. Address Translation Steps

Suppose the CPU generates:

(p1, p2, offset)

Translation occurs as follows.

Step 1

Use p1 to access the outer page table.

Outer Page Table[p1]

This provides the address of an inner page table.

Step 2

Use p2 to access the inner page table.

Inner Page Table[p2]

This provides the frame number.

Step 3

Combine frame number and offset.

Physical Address
=
Frame Number + Offset

10. Address Translation Flow

Logical Address
(p1, p2, offset)

        ↓

Outer Page Table

        ↓

Inner Page Table

        ↓

Frame Number

        ↓

Physical Address

11. Numerical Example

Suppose:

Logical Address Structure

p1 = 2
p2 = 3
offset = 100

Outer Page Table:

Thus:

p1 = 2

points to:

Inner Table C

Inner Table C:

Thus:

p2 = 3

gives:

Frame = 10

Final Physical Address:

(Frame 10, Offset 100)

12. Why Multilevel Paging Saves Memory

In single-level paging:

Entire Page Table
must exist

even if most pages are never used.

In multilevel paging:

Create Inner Tables
only when required

Unused portions of the address space consume no page table memory.

13. Sparse Address Space Example

Suppose a process uses only:

10 MB

out of a possible:

4 GB

address space.

Single-level paging still requires a huge page table.

Multilevel paging creates page tables only for the used regions.

This results in major memory savings.

14. Advantages of Multilevel Paging

Reduced Memory Usage

Only required page tables are created.

Efficient for Sparse Address Spaces

Unused address regions consume little or no memory.

Better Scalability

Suitable for large logical address spaces.

Supports Large Systems

Works well for 32-bit and 64-bit architectures.

Reduced Waste

Avoids storing millions of unused page table entries.

15. Disadvantages of Multilevel Paging

Increased Address Translation Time

Multiple page table lookups are required.

More Complexity

Hierarchical management is more complicated.

Additional Memory Accesses

Every level adds another lookup.

Dependency on TLB

Performance relies heavily on TLB efficiency.

16. Performance Analysis

Consider a system without TLB.

Single-Level Paging

Page Table Access
+
Memory Access
=
2 accesses

Two-Level Paging

Outer Page Table Access
+
Inner Page Table Access
+
Memory Access
=
3 accesses

Thus translation becomes slower.

17. Solution: TLB

To overcome this overhead, modern systems use a:

Translation Lookaside Buffer (TLB)

The TLB caches recently used page table entries.

When a TLB hit occurs:

Logical Address
        ↓
TLB
        ↓
Frame Number
        ↓
Memory

Most page table accesses are avoided.

18. Multilevel Paging in Modern Systems

32-bit Systems

Typically use:

• Two-Level Paging

64-bit Systems

Typically use:

• Three-Level Paging

• Four-Level Paging

• Five-Level Paging

because address spaces are much larger.

19. Single-Level vs Multilevel Paging

20. Real-World Analogy

Think of a large library.

Single-Level System

One massive index containing every book.

Finding information becomes cumbersome and the index occupies a lot of space.

Multilevel System

Library Index
      ↓
Section Index
      ↓
Shelf Index
      ↓
Book

You first find the section, then the shelf, then the book.

This hierarchical indexing is exactly how multilevel paging works.

Most Important Point

Multilevel paging reduces the memory overhead of large page tables by organizing them into a hierarchy, creating only the portions that are actually needed while still supporting efficient address translation.