3.5 Virtual Memory & Paging

Virtual Memory translates logical program addresses into physical memory frame locations. Managed by the Memory Management Unit (MMU) hardware, virtual memory isolates process execution spaces and extends primary memory capacity onto disk. This chapter explores paging formats, translation pipelines, Translation Lookaside Buffers, and page fault handling.

Learning Objectives

Define paging parameters: Virtual Address, Physical Address, Page Table, TLB, Page Fault, and MMU.
Explain how the Memory Management Unit (MMU) translates logical page numbers to physical frame numbers using page tables and TLBs.
Compute physical addresses from virtual addresses given page sizes and active page table mappings.
Contrast TLB lookups with standard page table traversals in terms of memory cycles and latencies.
Evaluate page replacement policies (FIFO, LRU) and page table scaling structures (Multi-level page tables).

Prerequisites

Before studying this chapter, you should review Chapter 3.4: Cache Writing Policies to understand memory write caches and dirty bits.

1. Concept of Virtual Memory

**Virtual Memory** is a hardware and software memory management scheme that abstracts the physical address space, presenting program code with a large, contiguous **Virtual Address Space**. This permits programs larger than the physical DRAM capacity to execute by keeping only active portions in main memory, swapping inactive segments to disk.

2. Paging Mechanics & Address Partitioning

Both virtual and physical address spaces are partitioned into fixed-size blocks: - **Pages**: Fixed-size blocks of virtual address space. - **Frames**: Identical-sized blocks of physical memory.

The CPU virtual address is partitioned into two fields: - **Page Number ($p$)**: High-order bits used as an index into the **Page Table**. - **Page Offset ($d$)**: Low-order bits used to specify the byte offset within the page. $$d = \log_2(\text{Page Size in Bytes})$$

The translated physical address consists of a **Frame Number ($f$)** combined directly with the unmodified **Page Offset ($d$)**.

3. MMU Hardware and Translation Lookaside Buffer (TLB)

The **Memory Management Unit (MMU)** is the hardware block within the CPU that performs address translation. Because page tables reside in main memory (RAM), translating an address requires a memory read to query the table, followed by a second read to access the target byte.

To eliminate this 2x latency penalty, the MMU features a small, highly associative hardware cache called the **Translation Lookaside Buffer (TLB)**. The TLB caches recently translated virtual page-to-frame mappings.

[Figure 3.5.1: Address Translation Pipeline Flowchart]

  CPU Virtual Address (p, d)
  ├── p ──► [ Query TLB ] ──(Hit)──► [ Retrieve Frame f ] ──► Physical Address (f, d)
  │            │
  │          (Miss)
  │            ▼
  └───────► [ Read Page Table in RAM ] ──(PTE Present=1)──► [ Load TLB & Frame f ]
               │
          (Present=0)
               ▼
        [ PAGE FAULT INTERRUPT ] ──► Load page from disk to RAM

Figure 3.5.1: Flowchart of the MMU address translation pipeline showing TLB and Page Table lookup paths.

4. Page Faults & Replacement

A **Page Fault** is a hardware interrupt triggered when the Page Table Entry (PTE) Present bit is 0, indicating the page does not reside in RAM. The OS halts the process, reads the page from disk into a free memory frame, updates the Page Table and TLB, and restarts the instruction.

5. Worked Examples & Traces

Execution Trace

Worked Example 3.5.1: Virtual Address Translation Trace

**Problem**: Trace how the MMU translates the 16-bit Virtual Address `0x1E5C` in a system with $4\text{ KB}$ pages, given the Page Table entries: - Page `0` maps to Frame `0x0F` - Page `1` maps to Frame `0x2C` - Page `2` maps to Frame `0x1B`

**Step-by-Step Translation Trace**:

**Calculate Offset Bits**: $$\text{Page Size} = 4\text{ KB} = 4096\text{ Bytes} \Rightarrow d = \log_2(4096) = 12 \text{ Offset Bits}$$
**Partition the 16-bit Virtual Address**: - In `0x1E5C`, the low-order 12 bits constitute the Offset, and the remaining high-order 4 bits represent the Page Number. $$\text{Virtual Address } \text{0x1E5C} = 0001\ 1110\ 0101\ 1100_2$$ $$\text{Page Number } (p) = 0001_2 = 1$$ $$\text{Page Offset } (d) = 1110\ 0101\ 1100_2 = \text{0xE5C}$$
**Lookup Page Table**: The MMU queries Page Table entry index $p=1$. - The entry shows Page 1 is mapped to **Frame `0x2C`**.
**Assemble Physical Address**: Combine Frame Number (`0x2C`) with the unmodified Page Offset (`0xE5C`): $$\text{Physical Address} = \text{Frame } \text{0x2C} \text{ and Offset } \text{0xE5C}$$ $$\text{Hex Physical Address} = \text{0x2CE5C}$$

Numerical Example

Worked Example 3.5.2: Address Space Bit Partitioning

**Problem**: A virtual memory system features a 32-bit virtual address space, $4\text{ KB}$ pages, and $256\text{ MB}$ of physical RAM. Calculate the number of bits in the Page Number and Frame Number fields.

**Solution**:

Offset bits: $\log_2(4096) = 12$ bits.
Page Number bits: $32 - 12 = 20$ bits.
Physical address size: $\log_2(256\text{ MB}) = \log_2(276,480,000) = 28$ bits.
Frame Number bits: $28 - 12 = 16$ bits.

Common Mistakes to Avoid

Warning: Common Student Pitfalls

**Modifying the Offset**: Attempting to decode or alter the page offset bits ($d$) during translation. Offset remains identical in both logical and physical addresses.
**Confusing TLB Misses and Page Faults**: A TLB miss means the mapping is in memory, requiring a page table lookup. A page fault means the page is on disk, requiring I/O swapping.

Revision Summary & Takeaways

Virtual memory maps logical pages to physical frames via page tables.
The TLB hardware caches virtual-to-physical address mappings.
Page faults interrupt the CPU to fetch missing pages from disk.

How this chapter connects to the next

We have analyzed how the MMU manages internal CPU-to-memory address translations. In Chapter 3.6: I/O Interface, we move outside memory access logic to explore physical Input/Output interfaces, analyzing how the CPU routes commands and data to external peripheral devices.

Check Your Understanding

1. Which hardware unit in the CPU translates logical page addresses to physical frame addresses?

References

**ref-notes-syed-arsalaan**: Handwritten Lecture Notes, Page 92 (Paging Hardware). [Local Verified]
**ref-notes-class**: Class COA Lecture Notes, Page 44 (Virtual Address Map). [Local Verified]
**ref-book-stallings**: William Stallings, *Computer Organization and Architecture*, Chapter 8. [Pending Verification]
**ref-lecture-sanchez-15**: Prof. Daniel Sanchez, MIT 6.004, Lecture 15 (Virtual Memory). [Pending Verification]