The Problem Paging Solves

Recall from Section 1 that contiguous memory allocation suffers from external fragmentation — after many allocations and deallocations, free memory is split into many small holes, none of which is large enough for new processes even though the total free memory might be sufficient.

The root cause is the requirement that a process must occupy a single, contiguous block of physical memory. Paging eliminates this requirement entirely.

---

The Core Idea: Pages and Frames

Paging divides both logical and physical memory into fixed-size blocks:

• Frame: A fixed-size block of physical memory (RAM). The OS tracks which frames are free and which are occupied.
• Page: A fixed-size block of a process's logical address space. Every page is the same size as a frame.

The crucial freedom: A process's pages can be placed in any available frames — they do not have to be adjacent in physical memory. Page 0 of a process might be in frame 5; page 1 might be in frame 1; page 2 might be in frame 14. They are scattered, but the process doesn't know or care.

Why external fragmentation is eliminated: Any free frame anywhere in RAM can hold any page of any process. There are no "holes" that are too small — as long as there are enough free frames in total, any process can be loaded.

---

Page Size: Why It's Always a Power of 2

Page size is defined by the hardware and is always a power of 2 (e.g., 512B, 4KB, 64KB). This is not arbitrary — it makes address splitting trivially fast using bit operations instead of division.

• Typical page size: 4KB (4,096 bytes) in modern systems (x86-64 Linux/Windows).
• Trend: Larger pages (2MB, 1GB "huge pages") are used for performance-critical applications to reduce TLB pressure.

---

The Logical Address Structure

Since page size is $2^n$ bytes, every logical address is mechanically split into two fields:

$\text{Logical Address} = \underbrace{p}_{\text{page number}} \| \underbrace{d}_{\text{page offset}}$

Where:

• $p$ (page number): The upper $(m - n)$ bits of the $m$-bit logical address. Used as an index into the page table.
• $d$ (page offset): The lower $n$ bits (where page size = $2^n$). The position within the page/frame. Preserved unchanged in the physical address.

Example with page size = $2^8$ = 256 bytes and a 10-bit logical address:

---

The Page Table

The page table is a data structure maintained by the OS (one per process) that maps each page number to the frame number where that page is currently stored in RAM.

Page Table for Process P:
┌───────────┬──────────────┐
│ Page No.  │ Frame No.    │
├───────────┼──────────────┤
│     0     │      5       │  ← Page 0 is in physical frame 5
│     1     │      1       │  ← Page 1 is in physical frame 1
│     2     │     14       │  ← Page 2 is in physical frame 14
│     3     │     17       │  ← Page 3 is in physical frame 17
└───────────┴──────────────┘

Physical address computation: $\text{Physical Address} = (\text{frame number} \times \text{page size}) + \text{offset}$

Or equivalently (using bit concatenation, which is how hardware does it): $\text{Physical Address} = \underbrace{f}_{\text{frame number from table}} \| \underbrace{d}_{\text{offset (unchanged)}}$

Worked example: Logical address 678, page size 256B, using the page table above:

1. $p = 678 \div 256 = 2$ (integer division) → page 2
2. $d = 678 \mod 256 = 166$ → offset 166
3. Page table lookup: page 2 → frame 14
4. Physical address = $14 \times 256 + 166 = 3,584 + 166 = \mathbf{3,750}$

---

Internal Fragmentation in Paging

Paging does not completely eliminate fragmentation — it trades external fragmentation for a small, bounded amount of internal fragmentation:

• If a process is not a perfect multiple of the page size, the last page will be partially full.
• The wasted space inside that last frame is internal fragmentation.
• Maximum waste: Page size − 1 bytes (e.g., with 4KB pages, max waste = 4,095 bytes ≈ 4KB per process).
• On average: Half a page per process — much smaller than external fragmentation losses.

Hardware Support: Making Paging Fast

The Naive Implementation: Page Table in RAM

The page table is stored in main memory (RAM). The OS keeps a Page Table Base Register (PTBR) pointing to the start of the current process's page table in RAM.

The critical performance problem: Every single logical memory access now requires two physical memory accesses:

1. Access the page table in RAM to find the frame number.
2. Access the actual data in RAM at the computed physical address.

This doubles the memory access time — completely unacceptable for a general-purpose OS. The solution is a hardware cache specifically for page table entries.

---

The Translation Lookaside Buffer (TLB)

The TLB (Translation Lookaside Buffer) is a small, extremely fast associative cache built directly into the CPU (or MMU chip). It stores a small number of recently used (page number → frame number) mappings.

TLB Hit: Page number is found in the TLB → frame number retrieved immediately. → Cost: 1 TLB lookup + 1 RAM access (for data) = ~1 effective memory access

TLB Miss: Page number is not in the TLB → must access page table in RAM. → Cost: 1 TLB lookup + 1 RAM access (page table) + 1 RAM access (data) = ~2 effective memory accesses → After the miss, the mapping is loaded into the TLB for future use (replacing an old entry).

---

Effective Access Time (EAT): The Key Formula

Effective Access Time (EAT) measures the average time for a memory access, accounting for TLB hits and misses.

Definitions:

• $\alpha$ = TLB hit ratio (the fraction of accesses that find the page in the TLB)
• $\epsilon$ = TLB lookup time (associative lookup time, often 10–20 ns)
• $m$ = Memory access time (time to access RAM, e.g., 100 ns)

Formula: $\text{EAT} = \alpha \times (\epsilon + m) + (1 - \alpha) \times (\epsilon + 2m)$

Expanded: $\text{EAT} = (\epsilon + m) + (1 - \alpha) \times m$

• Hit path: TLB lookup + 1 RAM access (the data)
• Miss path: TLB lookup + 1 RAM access (page table) + 1 RAM access (the data)

Worked Example:

• $\alpha = 0.80$ (80% hit ratio), $\epsilon = 10$ ns, $m = 100$ ns

$\text{EAT} = 0.80 \times (10 + 100) + 0.20 \times (10 + 200)$ $= 0.80 \times 110 + 0.20 \times 210$ $= 88 + 42 = \mathbf{130 \text{ ns}}$

Without TLB (always 2 RAM accesses): $10 + 200 = 210$ ns. With TLB (80% hit rate): 130 ns — a 38% improvement.

Modern TLBs have hit ratios of 95–99% (because of locality of reference), making paging overhead negligible in practice.

---

Memory Protection: The Valid/Invalid Bit

Each entry in the page table contains more than just the frame number. A critical field is the valid/invalid bit:

• Valid (1): The page is part of the process's legal address space and is currently in memory.
• Invalid (0): The page is either not part of the process's address space, or it is currently swapped to disk.

If the CPU generates a logical address whose page table entry has the invalid bit set, the hardware triggers a page fault trap to the OS. The OS then either:

1. Terminates the process (if the address is illegal — like a null pointer dereference).
2. Loads the page from disk into a free frame and resumes the process (if the page was swapped — this is the mechanism behind virtual memory, covered in Section 3).

---

Shared Pages

Paging enables an elegant and important optimization: shared memory between processes without copying data.

Shared Code: If 10 users all run the same text editor, there's no need to have 10 copies of the editor's code in RAM. Each process's page table can map its code pages to the same physical frames containing the editor's code.

Requirement: Shared code must be reentrant (pure code) — it must not modify itself during execution. Only the data pages (stack, variables) need to be private to each process.

Process 1 Page Table:     Process 2 Page Table:
Page 0 → Frame 3 (code)   Page 0 → Frame 3 (code) ← SAME FRAME
Page 1 → Frame 8 (data)   Page 1 → Frame 9 (data) ← DIFFERENT FRAMES

This is the foundation of how modern OS memory mapping and shared libraries work.

---

Contiguous vs Paging: The Full Comparison