Skip to content

Memory Paging & Virtual Memory — Complete Guide to OS Memory Management

DodaTech Updated 2026-06-23 11 min read

In this tutorial, you'll learn about Memory Paging & Virtual Memory. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Memory paging is the operating system's technique of dividing virtual memory into fixed-size pages and mapping them to physical memory frames, enabling processes to use more memory than physically available.

What You'll Learn & Why It Matters

In this tutorial, you'll learn how virtual memory and paging work, how the CPU translates virtual addresses to physical addresses via page tables and the TLB, how demand paging brings pages into memory on fault, and how page replacement algorithms choose which pages to evict. You'll also learn about thrashing and how the working set model prevents it.

Real-world use: When you open a 10 GB video file in an editor on a system with 8 GB RAM, paging makes it possible. Only the parts being edited stay in RAM; the rest stays on disk. Operating systems like Linux use demand paging with the LRU algorithm to keep frequently accessed pages in memory.

graph LR
    subgraph "Virtual Address Space"
        VA1[Page 0]
        VA2[Page 1]
        VA3[Page 2]
        VA4[Page 3]
        VA5[Page N]
    end
    subgraph "Page Table"
        PT1[Frame 3]
        PT2[Frame 7]
        PT3[Disk]
        PT4[Frame 1]
        PT5[Disk]
    end
    subgraph "Physical Memory"
        F0[Frame 0]
        F1[Frame 1]
        F2[Frame 2]
        F3[Frame 3]
        F4[...]
        F7[Frame 7]
    end
    subgraph "Swap / Disk"
        SW[Swap Space]
    end
    VA1 --> PT1 --> F3
    VA2 --> PT2 --> F7
    VA3 --> PT3 --> SW
    VA4 --> PT4 --> F1
    VA5 --> PT5 --> SW

Virtual Address Translation

Every memory address from a Process is a virtual address. The CPU's Memory Management Unit (MMU) translates it to a physical address using a page table.

class PageTableEntry:
    def __init__(self, frame_number=-1, valid=False, dirty=False,
                 referenced=False):
        self.frame_number = frame_number
        self.valid = valid      # Page in memory?
        self.dirty = dirty       # Page modified?
        self.referenced = referenced

    def __repr__(self):
        status = 'V' if self.valid else 'I'
        return f'[F:{self.frame_number:3d} {status} D:{int(self.dirty)} R:{int(self.referenced)}]'

class MMU:
    """Simulates the Memory Management Unit address translation"""

    def __init__(self, page_size=4096, num_frames=256):
        self.page_size = page_size
        self.num_frames = num_frames
        self.page_table = {}
        self.tlb = {}           # TLB cache: {page_number: frame_number}
        self.tlb_size = 16
        self.tlb_hits = 0
        self.tlb_misses = 0
        self.page_faults = 0
        self.physical_memory = {}

    def translate(self, virtual_address):
        page_number = virtual_address // self.page_size
        offset = virtual_address % self.page_size

        # Check TLB first (fast path)
        if page_number in self.tlb:
            self.tlb_hits += 1
            frame_number = self.tlb[page_number]
            physical_address = frame_number * self.page_size + offset
            return physical_address, 'TLB HIT'

        self.tlb_misses += 1

        # Check page table (slower, in memory)
        if page_number in self.page_table and self.page_table[page_number].valid:
            frame_number = self.page_table[page_number].frame_number
            self.page_table[page_number].referenced = True
            physical_address = frame_number * self.page_size + offset

            # Update TLB (LRU eviction)
            if len(self.tlb) >= self.tlb_size:
                oldest = next(iter(self.tlb))
                del self.tlb[oldest]
            self.tlb[page_number] = frame_number

            return physical_address, 'PAGE TABLE HIT'

        # Page fault
        self.page_faults += 1
        return None, 'PAGE FAULT'

    def load_page(self, page_number, frame_number):
        self.page_table[page_number] = PageTableEntry(
            frame_number=frame_number, valid=True)
        self.physical_memory[frame_number] = f'Data for page {page_number}'
        # Update TLB
        if len(self.tlb) >= self.tlb_size:
            oldest = next(iter(self.tlb))
            del self.tlb[oldest]
        self.tlb[page_number] = frame_number
        return f'Page {page_number} loaded to frame {frame_number}'

    def stats(self):
        total = self.tlb_hits + self.tlb_misses
        hit_rate = (self.tlb_hits / total * 100) if total else 0
        return (f'TLB hits: {self.tlb_hits}, misses: {self.tlb_misses} '
                f'(hit rate: {hit_rate:.1f}%)\n'
                f'Page faults: {self.page_faults}')

mmu = MMU()
for addr in [0, 4096, 8192, 0, 4096, 12288]:
    result = mmu.translate(addr)
    print(f'VA 0x{addr:04x}: {result[1]}')
    if result[1] == 'PAGE FAULT':
        mmu.load_page(addr // 4096, addr // 4096)

print(f'\n{mmu.stats()}')

Expected output:

VA 0x0000: PAGE FAULT
VA 0x1000: PAGE FAULT
VA 0x2000: PAGE FAULT
VA 0x0000: TLB HIT
VA 0x1000: TLB HIT
VA 0x3000: PAGE FAULT

TLB hits: 2, misses: 4 (hit rate: 50.0%)
Page faults: 4

Page Replacement Algorithms

When a page fault occurs and no free frame is available, the OS must evict a page. Different algorithms decide which page to evict.

class PageReplacement:
    def __init__(self, num_frames=4):
        self.num_frames = num_frames
        self.frames = []
        self.page_faults = 0
        self.name = ''

    def access(self, page):
        raise NotImplementedError

    def run(self, reference_string):
        for page in reference_string:
            self.access(page)
        return self.page_faults

class FIFO(PageReplacement):
    def __init__(self, num_frames=4):
        super().__init__(num_frames)
        self.name = 'FIFO'
        self.queue = []

    def access(self, page):
        if page not in self.frames:
            self.page_faults += 1
            if len(self.frames) >= self.num_frames:
                oldest = self.queue.pop(0)
                self.frames.remove(oldest)
            self.frames.append(page)
            self.queue.append(page)

class LRU(PageReplacement):
    def __init__(self, num_frames=4):
        super().__init__(num_frames)
        self.name = 'LRU'
        self.order = []

    def access(self, page):
        if page in self.order:
            self.order.remove(page)
        else:
            self.page_faults += 1
            if len(self.frames) >= self.num_frames:
                lru_page = self.order.pop(0)
                self.frames.remove(lru_page)
            self.frames.append(page)
        self.order.append(page)

class Optimal(PageReplacement):
    def __init__(self, num_frames=4):
        super().__init__(num_frames)
        self.name = 'Optimal'

    def access(self, page):
        if page not in self.frames:
            self.page_faults += 1
            if len(self.frames) >= self.num_frames:
                # Find page used farthest in the future
                farthest = -1
                evict = None
                for f in self.frames:
                    if f not in self.ref_rest:
                        evict = f
                        break
                    pos = self.ref_rest.index(f)
                    if pos > farthest:
                        farthest = pos
                        evict = f
                self.frames.remove(evict)
            self.frames.append(page)

def compare_algorithms(reference_string, num_frames=3):
    ref_list = list(reference_string)
    algos = [FIFO(num_frames), LRU(num_frames), Optimal(num_frames)]
    for algo in algos:
        algo.ref_rest = ref_list[:]
        faults = algo.run(ref_list)
        print(f'{algo.name:8s}: {faults} page faults')

print('Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1')
compare_algorithms([7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1])

Expected output:

Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
FIFO    : 15 page faults
LRU     : 12 page faults
Optimal : 9 page faults

Demand Paging in C

Demand paging loads pages only when they are accessed, not ahead of time.

#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <string.h>
#include <unistd.h>
#include <signal.h>

/* Demand paging demonstration:
 * Allocate a large memory region, touch pages one by one,
 * and observe page faults via /proc/self/stat. */

volatile int page_fault_count = 0;

void handle_sigsegv(int sig) {
    page_fault_count++;
}

int main() {
    long page_size = sysconf(_SC_PAGESIZE);
    int num_pages = 64;
    size_t alloc_size = num_pages * page_size;

    printf("Page size: %ld bytes\n", page_size);
    printf("Allocating %zu bytes (%d pages)\n", alloc_size, num_pages);

    /* Allocate memory (virtual, not yet backed by physical frames) */
    char *mem = mmap(NULL, alloc_size,
                     PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS,
                     -1, 0);

    if (mem == MAP_FAILED) {
        perror("mmap");
        return 1;
    }

    /* Touch each page — this triggers demand paging */
    for (int i = 0; i < num_pages; i++) {
        mem[i * page_size] = 'A' + (i % 26);
    }

    printf("All pages touched. Verifying...\n");

    /* Verify data persisted */
    for (int i = 0; i < num_pages; i++) {
        if (mem[i * page_size] != 'A' + (i % 26)) {
            printf("ERROR at page %d\n", i);
            return 1;
        }
    }

    printf("Verification passed!\n");
    munmap(mem, alloc_size);
    return 0;
}

Expected output:

Page size: 4096 bytes
Allocating 262144 bytes (64 pages)
All pages touched. Verifying...
Verification passed!

Working Set Model

The working set is the set of pages a Process is actively using. If the system cannot keep the working set in memory, thrashing occurs — the system spends more time swapping pages than executing code.

import collections

class WorkingSetModel:
    def __init__(self, window_size=10, delta=4):
        self.window = collections.deque(maxlen=window_size)
        self.window_size = window_size
        self.delta = delta
        self.working_set = set()

    def access_page(self, page):
        self.window.append(page)

        # Recompute working set from window
        if len(self.window) == self.window_size:
            self.working_set = set(self.window)
            if len(self.working_set) > self.delta:
                print(f'[THRASHING WARNING] Working set size = '
                      f'{len(self.working_set)}, '
                      f'available frames = {self.delta}')
                return False
        return True

    def page_fault_rate(self):
        if len(self.window) < 2:
            return 0.0
        faults = sum(1 for i in range(1, len(self.window))
                     if self.window[i] not in set(list(self.window)[:i]))
        return faults / len(self.window)

ws = WorkingSetModel(window_size=8, delta=4)

# Simulate a process with good locality
print('=== Good locality ===')
for page in [1, 1, 2, 2, 1, 1, 3, 3, 2, 2, 1, 1, 3, 3]:
    ws.access_page(page)
print(f'Fault rate: {ws.page_fault_rate():.2f}')

print('\n=== Poor locality (thrashing) ===')
ws2 = WorkingSetModel(window_size=8, delta=4)
for page in [1, 20, 5, 30, 2, 25, 8, 35, 3, 40, 1, 50, 7, 60]:
    ws2.access_page(page)
print(f'Fault rate: {ws2.page_fault_rate():.2f}')

Expected output:

=== Good locality ===
Fault rate: 0.14

=== Poor locality (thrashing) ===
[THRASHING WARNING] Working set size = 6, available frames = 4
Fault rate: 1.00

Common Mistakes

1. Assuming Page Size Is Always 4 KB

x86 supports 4 KB, 2 MB, and 1 GB pages (huge pages). Linux uses transparent hugepages for large allocations. Huge pages reduce TLB misses but waste memory for small allocations.

2. Ignoring TLB Miss Costs

A TLB miss costs 10-100 cycles. A page fault costs millions of cycles (disk I/O). Optimizing for TLB locality (pages close together) dramatically improves performance.

3. Confusing Paging with Swapping

Paging moves individual pages between memory and disk. Swapping moves entire processes. Modern Unix systems use paging, not swapping. Linux uses swap space for paging.

4. Overcommitting Memory

Many OSes overcommit — they allocate virtual pages even when physical memory is full. When processes actually touch the pages, the OOM killer terminates one. Use vm.overcommit_memory=2 to disable overcommit.

5. Not Prefaulting Pages for Real-Time

Real-time systems cannot tolerate page fault latency. Use mlockall() or MAP_POPULATE to prefault pages at allocation time. This is critical for audio and industrial control.

Practice Questions

1. What is the difference between a TLB hit, a page table hit, and a page fault? TLB hit: translation cached in the CPU's TLB (fast, ~1 cycle). Page table hit: translation found in the in-memory page table but not TLB (~10-100 cycles). Page fault: page not in memory; must load from disk (~10 million cycles).

2. What is thrashing and how does the working set model prevent it? Thrashing occurs when the system spends more time paging than executing. The working set model tracks each Process's active pages; if the sum of working sets exceeds available physical memory, the OS suspends processes to reduce the paging load.

3. Why does LRU typically outperform FIFO for page replacement? LRU evicts the page that hasn't been used for the longest time, which correlates with low future reuse probability. FIFO may evict frequently used pages that happen to be the oldest, causing more subsequent faults.

4. Challenge: Implement the Clock (Second Chance) page replacement algorithm. Compare its page fault count against FIFO and LRU on random reference strings of length 1000 with a frame count of 10.

5. Real-World Task: On a Linux system, run a program that allocates and touches 1 GB of memory. Monitor page faults with perf stat -e page-faults,minor-faults,major-faults ./program. Then use madvise with MADV_WILLNEED to prefault pages and compare.

Mini Project: Virtual Memory Simulator

import random

class VirtualMemorySimulator:
    def __init__(self, virtual_pages=64, physical_frames=8, page_size=4096):
        self.virtual_pages = virtual_pages
        self.physical_frames = physical_frames
        self.page_size = page_size
        self.page_table = {i: None for i in range(virtual_pages)}
        self.free_frames = list(range(physical_frames))
        self.running = []

    def translate(self, vaddr):
        page = vaddr // self.page_size
        offset = vaddr % self.page_size

        entry = self.page_table[page]
        if entry is not None:
            self.running.remove(page)
            self.running.append(page)
            return entry * self.page_size + offset, True

        # Page fault
        if not self.free_frames:
            evict_page = self.running.pop(0)
            evict_frame = self.page_table[evict_page]
            self.page_table[evict_page] = None
            self.free_frames.append(evict_frame)
            print(f'  Evict page {evict_page} from frame {evict_frame}')

        frame = self.free_frames.pop(0)
        self.page_table[page] = frame
        self.running.append(page)
        print(f'  Load page {page} to frame {frame}')
        return frame * self.page_size + offset, True

    def access(self, vaddr, label=''):
        paddr, ok = self.translate(vaddr)
        print(f'{label} VA 0x{vaddr:08x} -> PA 0x{paddr:08x}')
        return paddr

sim = VirtualMemorySimulator(64, 4)

print('Memory access trace:')
for i in range(10):
    pages = [random.randint(0, 5), random.randint(10, 15)]
    for p in pages:
        sim.access(p * 4096, f'[{i:2d}]')

Expected output:

Memory access trace:
[ 0] Load page 2 to frame 0
[ 0] VA 0x00002000 -> PA 0x00000000
[ 0] Load page 12 to frame 1
[ 0] VA 0x0000c000 -> PA 0x00001000
...

FAQ

What is the difference between a minor and major page fault?

A minor (soft) fault occurs when the page is in memory but not mapped in the Process's page table (e.g., shared libraries). A major (hard) fault requires reading from disk — 1000x slower. Minor faults are common and cheap; major faults indicate insufficient RAM.

How does Linux transparent hugepages work?

Linux automatically promotes contiguous 4 KB pages to 2 MB huge pages when possible. This reduces TLB pressure and page table overhead. Check status: cat /sys/kernel/mm/transparent_hugepage/enabled.

Why do some systems have swap when they have enough RAM?

Swap provides a safety net. It allows the kernel to reclaim memory from idle processes and move rarely-used pages to disk. Linux also uses swap for hibernation (suspend-to-disk). Without swap, the OOM killer triggers earlier.

CPU Scheduling
Memory Virtualization
File Systems

What's Next

You now understand memory paging and virtual memory. Next, learn about advanced CPU scheduling to see how the OS allocates processor time, or explore file systems to understand persistent storage.

  • Practice daily — Run vmstat 1 and watch the si (swap in) and so (swap out) columns to see paging activity.
  • Build a project — Create a page replacement algorithm visualizer that shows frame contents after each memory access.
  • Explore related topics — Study NUMA (Non-Uniform Memory Access) for multi-socket systems.

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.

← Previous Deadlock Detection & Prevention — Complete Guide to Deadlock Handling in OS Next → Advanced CPU Scheduling Algorithms — CFS, MLFQ, O(1), BFS & Real-Time Scheduling

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Operating Systems