Virtual Memory

Virtual memory is a fundamental memory management technique used in modern processors to allow programs to use more memory than physically available in the system. It creates an abstraction layer between the logical addresses used by programs and the physical addresses in RAM, enabling safe multitasking, process isolation, and efficient memory utilization.

Core Concept: What Virtual Memory Does

Every process in a modern OS believes it owns the entire address space from address 0 to 2^N - 1, where N is the address bit width. This is the illusion virtual memory creates. In reality, only parts of this space are backed by physical RAM at any moment, and the rest may reside on disk or be unmapped. The hardware component responsible for translating virtual addresses to physical addresses is the Memory Management Unit (MMU), which sits between the CPU and the memory bus.

The three main mechanisms implementing virtual memory are paging, segmentation, and their combination. Each has different tradeoffs in terms of fragmentation, flexibility, and hardware support. Most modern architectures, including x86-64, use paging as the primary mechanism.

Paging

In paging, the virtual address space is divided into fixed-size units called pages, and physical memory is divided into equal-sized units called frames. A page table maintained per process stores the mapping from virtual page numbers (VPN) to physical page numbers (PPN). The virtual address is split as: upper bits form the VPN, lower bits form the page offset. The offset is directly passed through to the physical address since page size equals frame size. The page table entry also contains a valid bit, dirty bit, reference bit, and protection bits.

When the MMU encounters a valid bit of 0 during translation, a page fault exception is raised. The OS page fault handler then loads the required page from swap space (disk) into a free frame, updates the page table, and restarts the faulting instruction. This mechanism enables programs larger than physical RAM to run correctly.

Segmentation and Segmentation with Paging

In segmentation, the address space is divided into variable-sized logical segments such as code, data, stack, and heap. A segment is identified by a segment number and an offset within it. The segment table stores the base address and limit of each segment. Segmentation matches the programmer's logical view of memory, but causes external fragmentation since segments vary in size.

To combine the benefits of both, segmentation with paging (used in older Intel x86 protected mode) adds a paging layer on top of segments. The virtual address is first translated via the segment table to a linear address, which is then further translated through page tables to a physical address. This eliminates external fragmentation while retaining segment-level protection. Modern 64-bit x86 processors largely bypass segmentation and use flat segment models, relying purely on paging.

Translation Lookaside Buffer

Page table walks are expensive because every memory access would require multiple additional memory reads to traverse the page table hierarchy. The Translation Lookaside Buffer (TLB) solves this by acting as a small, fast, fully associative cache inside the MMU that stores recently used VPN-to-PPN translations. On a TLB hit, address translation completes in one cycle. On a TLB miss, the MMU performs a page table walk (hardware or software managed), loads the entry into the TLB, and retries.

TLB reach is defined as the total memory addressable by the TLB entries at once. With 64 TLB entries and 4 KB pages, the TLB reach is 64 x 4 KB = 256 KB. Using larger pages (such as 2 MB huge pages) increases TLB reach significantly, which improves performance for large working sets. TLB shootdown is an important consideration in multiprocessor systems, where changing a page table entry requires invalidating the corresponding TLB entry on all processors.

Mathematical Expression

For a system with a virtual address of V bits and a page size of 2^p bytes, the virtual page number occupies (V - p) bits and the page offset occupies p bits. If the page table entry size is E bytes, the total page table size for one process is:

Page Table Size = (2^(V-p)) x E bytes. For example, with V=32, p=12 (4 KB pages), and E=4 bytes: size = 2^20 x 4 = 4 MB per process. This is why multi-level page tables and inverted page tables were introduced to reduce this overhead.

Effective Memory Access Time

The effective memory access time (EMAT) with TLB is calculated as follows. Let h be the TLB hit ratio, t_tlb be the TLB access time, t_mem be the main memory access time, and t_disk be the disk access time for page faults. Let p be the page fault rate. Then:

EMAT = h(t_tlb + t_mem) + (1-h)(t_tlb + 2t_mem) + page fault overhead. The factor of 2 appears because on a TLB miss we need one memory access for the page table and one for the actual data.

Given:
Virtual address size = 32 bits
Page size = 4 KB = 2^12 bytes
Page table entry size = 4 bytes
TLB hit ratio (h) = 0.95
TLB access time = 5 ns
Main memory access time = 100 ns
Page fault rate = 0 (assume negligible for this example)

Why this formula applies:
With TLB, hit accesses need TLB lookup + one memory access.
Miss accesses need TLB lookup + page table read from memory + data memory access.

Formula:
EMAT = h(t_tlb + t_mem) + (1-h)(t_tlb + 2t_mem)

Substitution:
EMAT = 0.95*(5 + 100) + 0.05*(5 + 200)

Calculation:
EMAT = 0.95105 + 0.05205
EMAT = 99.75 + 10.25

Final Answer: EMAT = 110 ns

Bonus - Page table size:
Entries = 2^(32-12) = 2^20 = 1,048,576
Page Table Size = 1,048,576 * 4 = 4 MB per process

Exam Tip: GATE frequently asks EMAT calculation with TLB. Remember the TLB miss path requires TWO memory accesses (one for page table entry, one for data), not one. Also, page table size formula 2^(V-p) * E is directly asked in multiple-choice questions.

Address Translation: Step by Step

• A virtual address is split into VPN (upper bits) and page offset (lower bits). The offset size equals log2(page size).
• TLB is checked first. A TLB hit directly provides the PPN, and physical address = PPN concatenated with page offset.
• On TLB miss, the MMU walks the page table in memory. For a 2-level page table, this requires 2 memory reads before the actual data access.
• If valid bit is 0, page fault exception is raised. OS finds a free frame, loads page from disk, updates page table entry, sets valid bit to 1, and retries.
• Page replacement algorithms (LRU, FIFO, Optimal) decide which frame to evict when no free frame is available. The dirty bit determines if evicted page must be written back to disk.
• TLB entries are tagged with ASID (Address Space Identifier) in some architectures to avoid full TLB flush on context switch, reducing TLB miss overhead during multitasking.

Quick Revision

• Virtual memory maps virtual addresses to physical addresses through the MMU using page tables, providing process isolation and memory abstraction.
• Key formula: Page Table Size = 2^(V-p) x E, where V = virtual address bits, p = page offset bits, E = page table entry size.
• EMAT with TLB = h(t_tlb + t_mem) + (1-h)(t_tlb + 2*t_mem). The factor of 2 on TLB miss is a common GATE trap.
• Page fault occurs when valid bit = 0. OS handles it by loading the page from disk, updating the page table, and restarting the instruction.
• Segmentation divides address space into variable-size logical segments. It causes external fragmentation. Segmentation with paging avoids external fragmentation by paging each segment.
• TLB reach = Number of TLB entries x Page size. Larger pages increase TLB reach and reduce miss rate for large working sets.
• GATE trap: Do not confuse page size with number of pages. Also note that inverted page tables have one entry per physical frame, not per virtual page.