Virtual Memory — Computer Organization & Architecture

Introduction

What if you could give every program the illusion of having its own vast, private memory — even if physical RAM is limited? That's exactly what virtual memory does. It creates an abstraction layer between the addresses a program uses (virtual addresses) and the actual physical memory locations (physical addresses). This enables multiple programs to share RAM safely, allows programs larger than physical memory to run, and provides memory protection. Virtual memory is one of the most elegant solutions in computer architecture.

The Problems Virtual Memory Solves

1. Limited physical memory: Programs can use more address space than physical RAM available
2. Memory protection: Programs can't access each other's memory (security and stability)
3. Memory sharing: Common libraries loaded once in physical memory, shared by all programs
4. Simplified programming: Each program gets a clean, contiguous address space starting at 0
5. Process isolation: A bug in one program can't corrupt another program's memory

Basic Concept

Every program uses virtual addresses (e.g., 0x00000000 to 0xFFFFFFFF for 32-bit). The hardware translates these to physical addresses in actual RAM. Different programs can use the same virtual address (e.g., both start at 0x00400000) but map to different physical locations.

Paging

Virtual memory divides both virtual and physical address spaces into fixed-size blocks:

• Pages: Fixed-size blocks of virtual memory (typically 4 KB)
• Frames: Fixed-size blocks of physical memory (same size as pages)

Address Translation

The page offset passes through unchanged (same position within the page/frame). Only the page number is translated to a frame number.

Page Table

Each process has a page table mapping its virtual pages to physical frames:

• Valid bit = 1: Page is in physical memory (frame number valid)
• Valid bit = 0: Page is on disk (accessing it triggers a page fault)

TLB (Translation Lookaside Buffer)

The page table is in memory — but accessing it for every memory reference would double memory access time! The TLB is a small, fast cache that stores recent page translations.

TLB characteristics:

• Fully associative (32-512 entries)
• Hit rate: 99%+ (excellent due to spatial locality within pages)
• Miss penalty: page table walk (10-100 cycles)

Page Faults

When a program accesses a page not in physical memory (valid bit = 0):

1. CPU detects page fault → transfers control to OS
2. OS finds the page on disk (swap space)
3. OS selects a victim frame (using replacement algorithm: LRU, clock)
4. If victim is dirty (modified), write it to disk first
5. Load the requested page from disk into the free frame
6. Update the page table (set valid, record frame number)
7. Restart the instruction that caused the fault

Page fault penalty is enormous: Disk access takes ~5-10 milliseconds = millions of CPU cycles! This is why minimizing page faults is critical.

Page Replacement Algorithms

When physical memory is full, which page to evict?

• LRU (Least Recently Used): Best theoretical performance but expensive to track perfectly
• Clock (Second Chance): Approximation of LRU using reference bits — practical and effective
• FIFO: Simple but can have anomalies (Belady's anomaly)
• Optimal (OPT): Replace the page needed farthest in the future — theoretical ideal, impossible in practice

Key Takeaways

1. Virtual memory creates an abstraction layer: programs use virtual addresses, hardware translates to physical
2. Paging divides memory into fixed pages (virtual) and frames (physical)
3. The page table (per process) maps virtual page numbers to physical frame numbers
4. The TLB caches recent translations for fast address translation (~99% hit rate)
5. A page fault occurs when accessing a page not in RAM — requires expensive disk access
6. Virtual memory enables protection, sharing, and programs larger than physical RAM
7. Page replacement algorithms (LRU, clock) decide which pages to evict when RAM is full