Paging

Intermediate

Memory Management

Paging divides virtual memory into fixed-size pages and physical memory into frames, using a page table to translate virtual addresses to physical addresses, eliminating external fragmentation.

Overview

Paging is the foundation of modern virtual memory. Virtual memory is divided into fixed-size pages (typically 4 KB); physical memory is divided into frames of the same size. The OS maintains a page table per process that maps each virtual page number to a physical frame number. When a process accesses a virtual address, the MMU splits it into a page number and an offset, looks up the frame in the page table, and constructs the physical address as frame_number × page_size + offset. Page table entries carry metadata bits: valid (is this page in memory?), dirty (has it been written?), and reference/accessed (has it been read recently?). Multi-level page tables (2-level on 32-bit, 4-level on x86-64) reduce the memory used by the page table itself. The TLB caches recent translations to avoid repeated page table walks.

Address Translation and Page Table Walk

The MMU performs address translation on every memory access. The virtual address is split: the top bits index into the page table to find the frame, the bottom bits (page offset) select the byte within the frame. With 4 KB pages, the offset is 12 bits (2^12 = 4096). On x86-64 with 4-level paging, a 48-bit virtual address is split 9-9-9-9-12 across four levels of page tables.

Java — virtual-to-physical address translation simulation

// Address translation formula
// Virtual Address = [Page Number | Page Offset]
// Physical Address = frame_number × page_size + offset

// Example: page size = 4 KB = 4096 bytes
int PAGE_SIZE = 4096;
int virtualAddress = 0x5A3F;  // example virtual address

int pageNumber = virtualAddress / PAGE_SIZE;   // top bits
int offset     = virtualAddress % PAGE_SIZE;   // bottom 12 bits

System.out.printf("Virtual address: 0x%X%n", virtualAddress);
System.out.printf("Page number:     %d%n", pageNumber);
System.out.printf("Offset:          %d (0x%X)%n", offset, offset);

// Simulated page table: page# → frame#
int[] pageTable = {3, 7, 2, 5, 1};  // page 0 → frame 3, page 1 → frame 7, etc.

if (pageNumber < pageTable.length) {
    int frameNumber   = pageTable[pageNumber];
    int physicalAddr  = frameNumber * PAGE_SIZE + offset;
    System.out.printf("Frame number:    %d%n", frameNumber);
    System.out.printf("Physical addr:   0x%X%n", physicalAddr);
} else {
    System.out.println("Page fault! Page not in table.");
}
// Standard 4KB page: 12-bit offset, remainder = page number

Multi-Level Page Tables

A single-level page table for a 64-bit address space would be enormous (terabytes). Multi-level page tables solve this by making the page table itself hierarchical and sparse — only allocate page table nodes for address ranges that are actually used. x86-64 uses 4-level paging: PGD → PUD → PMD → PTE, each table 512 entries × 8 bytes = 4 KB (one page).

Java — multi-level paging rationale and JVM committed vs max heap

// Why multi-level? Single-level page table size:
// 64-bit virtual address space = 2^48 pages (48-bit used on x86-64)
// 2^48 / 4096 = 2^36 pages × 8 bytes per entry = 512 GB per process!
// → Completely impractical

// Multi-level solution: only allocate page table nodes for used regions
// 4-level x86-64 page table walk (conceptual):
//
// Virtual address (48 bits): [PGD 9b][PUD 9b][PMD 9b][PTE 9b][Offset 12b]
//
// Each level: 512 entries × 8 bytes = 4096 bytes = 1 page
// Total overhead for a sparse process (text + heap + stack):
//   ~5–10 physical pages for page tables (instead of 512 GB)

// Java: measuring JVM memory overhead
// Most of the JVM's virtual address space is unused — multi-level paging
// ensures only mapped regions consume physical page table memory

MemoryMXBean memBean = ManagementFactory.getMemoryMXBean();
MemoryUsage heap = memBean.getHeapMemoryUsage();
System.out.printf("Heap committed: %d MB (actual physical frames allocated)%n",
    heap.getCommitted() / 1_048_576);
System.out.printf("Heap max:       %d MB (virtual address space reserved)%n",
    heap.getMax() / 1_048_576);
// committed < max: virtual pages reserved but physical frames not yet assigned

Key Points to Remember

1Paging divides virtual memory into fixed-size pages (4 KB typical) and physical RAM into same-size frames.
2Page table maps virtual page number → physical frame number; maintained per process by the OS.
3Physical address = frame_number × page_size + page_offset (bottom 12 bits for 4 KB pages).
4Page table entry bits: valid (in memory?), dirty (written?), reference (accessed recently?).
5Multi-level page tables (4-level on x86-64) avoid storing page table entries for unused virtual regions.
6Paging eliminates external fragmentation — any free frame can satisfy any page request.

Interview Questions

How does the MMU translate a virtual address to a physical address using paging?

MediumGoogle

Why are multi-level page tables used instead of a single flat page table?

MediumMicrosoft

What is the purpose of the dirty bit and reference bit in a page table entry?

MediumAmazon

Why does paging eliminate external fragmentation but not internal fragmentation?

HardAtlassian

Ask Aria about Paging

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Virtual Memory & Address Space

Segmentation