Understanding Virtual Memory, Paging, and MMU: From Basic Concepts to Multi‑Level Page Tables

Introduction

For programmers, memory can be visualized as a series of small cells numbered from 0, each capable of storing a byte (8 bits). These cells are called storage units and their indices are referred to as memory addresses .

Motivation

Two programmers, Dog and Cat, each modify the same memory address with simple assembly‑like instructions:

inc byte [1]    ; Dog increments the value at address 1

dec byte [1]    ; Cat decrements the value at address 1

If Dog runs first and then Cat, the two programs interfere with each other, leading to inefficiency (waiting for I/O) and unfairness (one program must wait for the other to finish).

To solve these problems, the CPU should be able to switch between programs while they wait for I/O, and programs should be allowed to run concurrently without stepping on each other's data.

New Problem

When Dog and Cat execute alternately, Dog may increment address 1, then Cat immediately decrements the same address, effectively undoing Dog's work. This illustrates the need for isolation: each program must see its own private view of memory.

Virtual Memory

"Any problem in computer science can be solved by adding an intermediate layer." – an unnamed source

Originally, the CPU sends the logical address directly to memory, which is called a physical address . To provide isolation, an intermediate layer called the Memory Management Unit (MMU) translates the CPU‑issued address (now called a virtual address ) into a physical address before accessing RAM.

Address Translation Schemes

Scheme 1: One‑to‑One Mapping Table

The OS keeps a table that maps each used virtual address to a physical address. This approach is slow (lookup cost) and cumbersome when programs allocate memory dynamically.

Scheme 2: Full Address Array

For a CPU with 16‑bit virtual addresses, an array of 2¹⁶ entries can be used, allowing direct indexing. However, for 32‑bit addresses the array would require 4 GB of entries (16 GB of storage), which is impractical.

Scheme 3: Paging

Memory is divided into fixed‑size pages. A virtual page number and an offset within the page are used. The OS maintains a page table that maps each virtual page to a physical page. This reduces the amount of bookkeeping dramatically.

Example of Single‑Level Paging

Assume a 32‑bit virtual address with a 4 MB page size (22‑bit offset, 10‑bit page number). A virtual address 0x01C00005 is split into page number 7 and offset 0x5. If the OS maps virtual page 7 to physical page 0x58, the resulting physical address becomes 0x05800005.

Two‑Level Page Tables

With 4 KB pages, a 32‑bit address is divided into a 10‑bit first‑level page number, a 10‑bit second‑level page number, and a 12‑bit offset. The first‑level table (page directory) contains 1 K entries, each pointing to a second‑level page table that also has 1 K entries. Only the second‑level tables needed for actually used virtual pages are allocated, saving memory.

Virtual Memory and Disk Swapping

When the total virtual memory demanded exceeds physical RAM, the OS can move rarely used pages to disk. Each page‑table entry includes a Present (P) flag indicating whether the page resides in RAM. If P=0, a page fault triggers the OS to load the page from disk into a free physical frame and update the page table.

Conclusion

Virtual memory, paging, and multi‑level page tables allow operating systems to provide each process with the illusion of a large, contiguous address space while efficiently managing limited physical memory and ensuring process isolation.