7.4 Compaction & Paging Architecture (Pages, Frames & Page Tables)

Back to Operating Systems Notes

📚Module 07: Main Memory ManagementTopic 7.4⏱️20 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Memory Systems

💡 Core Intuition

🍳 The Everyday Analogy: The Loose-Leaf Binder vs The Bound Journal

Imagine writing a comprehensive textbook across months of work:

Architecture Flow

The Textbook Binding Evolution Pipeline

From continuous bound pages to arbitrary loose-leaf distribution

💡 Hover or click any card for deep-dive operational details

📖Rigid Book

The Bound Leather Journal

Contiguous Allocation

You must reserve Chapter 3 as 50 consecutive printed pages.

→

Painful Alternative

📑Manual Shift

Tedious Page Shuffling

Compaction Overhead

Physically re-copying every chapter to unite all blank sheets at the back.

→

The Elegant Breakthrough

🗂️Indexed Sheets

Loose-Leaf Ring Binder & Index

Paging & Page Table

Every sheet of paper is an identical standardized size. Pages can be placed in any ring slot.

• Compaction: A desperate attempt to salvage contiguous allocation by physically shifting data in RAM, burning massive CPU cycles.
• Paging: The foundational breakthrough of modern operating systems. By separating the logical view of contiguous memory from the physical reality of scattered placement, external fragmentation is eliminated.

---

💻 Bridging to Computer Science

Contiguous memory allocation imposes an artificial and costly restriction: an entire program must occupy consecutive physical memory addresses. When free RAM becomes fragmented, the OS is faced with a dilemma:

---

📚 Core Deep-Dive & Concepts

1. The Anatomy of Paging: Pages vs Frames

Paging breaks physical and logical memory into standardized, uniform blocks:

---

2. The Paging Architecture & Mapping Engine

When the CPU executes instructions, it generates a Logical Address split into two components:

1. Page Number ($p$): Serves as an index into the process's page table.
2. Page Offset ($d$): The displacement within the page, identifying the specific byte.

Hardware MMU Paging Address Translation Blueprint

Decomposing logical addresses into page index and concatenating physical frame offsets

CPU Execution Core

Hardware MMU

Main Memory (RAM Page Table)

Physical DRAM Bus

1

CPU Execution Core→Hardware MMU

Issue Logical Address (p, d)

2

Hardware MMU→Main Memory (RAM Page Table)

Index Page Table via PTBR + (p × Entry Size)

3

Main Memory (RAM Page Table)→Hardware MMU

Return Physical Frame Number (f)

4

Hardware MMU→Physical DRAM Bus

Synthesize Physical Address (f, d) & Access DRAM

Step-by-Step Translation Mechanics

1. Address Decomposition: The CPU issues a logical address. The hardware splits the bitstring into high-order bits ($p$) and low-order bits ($d$).
2. Page Table Indexing: The hardware uses the Page Table Base Register (PTBR) to locate the process's page table in RAM. It computes $\text{PTBR} + (p \times \text{Entry Size})$ to read entry $p$.
3. Frame Resolution: From page table entry $p$, the MMU extracts the physical Frame Number ($f$).
4. Physical Address Synthesis: The frame number $f$ replaces $p$, while the offset $d$ is concatenated directly without modification: $\text{Physical Address} = (f \times \text{Frame Size}) + d$
5. DRAM Access: The memory controller reads/writes the physical DRAM cell at the computed address.

---

3. The Page Table: Operating System Data Structure

A fundamental principle: The Page Table is a data structure, NOT a piece of hardware.

• Location: Page tables are maintained in Main Memory (RAM) by the OS kernel.
• Per-Process Basis: Every process running in the system possesses its own dedicated page table.
• Kernel Management: During a context switch, the operating system reloads the Page Table Base Register (PTBR) with the physical address of the newly scheduled process's page table.

Anatomy of a Page Table Entry (PTE)

A Page Table Entry does not merely store the Frame Number; it contains vital hardware status bits:

Bitfield Component	Bit Width	Purpose & Operational Hardware Semantic
Valid / Invalid ($V$)	$1\text{ bit}$	1 = Resident in physical DRAM; 0 = Not in RAM (raises Page Fault trap).
Dirty / Modified ($M$)	$1\text{ bit}$	Hardware sets to 1 on write. If dirty, kernel must flush to disk on eviction.
Referenced ($R$)	$1\text{ bit}$	Hardware sets to 1 on read/write. Evaluated by Clock/LRU eviction heuristics.
Protection Bits	$3\text{ bits}$	Enforces Read, Write, and Execute (NX / DEP) access permissions.
Cache Disable / PWT	$1\text{ bit}$	Bypasses CPU L1/L2 caches for memory-mapped hardware I/O registers.
Frame Number ($f$)	$20\text{--}52\text{ bits}$	Base physical address of the DRAM frame backing this virtual page.

1. Valid/Invalid Bit ($V$):
   • 1 (Valid): The page is legally part of the process's address space and currently resides in physical RAM.
   • 0 (Invalid): The page is either unmapped or currently swapped out on disk. Referencing an invalid page triggers a Page Fault trap.
2. Dirty / Modified Bit ($M$):
   • Set to 1 by hardware whenever the CPU writes to any byte in that frame.
   • When the page is evicted, if $M = 1$, the kernel must write its contents back to disk; if $M = 0$, the frame can be silently overwritten without disk I/O.
3. Referenced / Access Bit ($R$):
   • Set to 1 by hardware whenever the page is read or written. Used by page replacement algorithms (such as Second-Chance and Clock) to approximate LRU.
4. Protection Bits:
   • Encodes access permissions: Read-Only, Read-Write, or Execute-Disable (NX / DEP). Prevents malicious execution of injected code on the stack.

---

4. Trade-Offs of Pure Paging

---

🏭 In The Real World: Production Case Study

Linux Page Allocation: Zero-Page Optimization & Shared Libraries

Modern operating systems leverage paging to achieve massive performance gains when launching programs:

1. Shared Read-Only Code (libc.so):
   • If 500 processes run on a server, each linking the standard C runtime (libc.so), the OS does not load 500 copies into RAM.
   • Paging maps the identical physical frame (Frame 500) into all 500 process page tables, saving gigabytes of physical DRAM.
2. The Zero-Page Optimization:
   • When a process allocates a large uninitialized memory buffer (calloc or anonymous mmap), the kernel points all newly created virtual pages to a single global read-only physical frame called the Zero Page.
   • Physical RAM is not consumed until the process writes to a specific page, at which point the MMU triggers a Copy-on-Write (COW) fault to allocate a fresh private frame.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Why is the page size in paging systems invariably chosen as a power of two ($2^k$ bytes)? Answer:

1. Zero-Latency Hardware Splitting: If the page size is a power of two ($2^k$ bytes), the lower $k$ bits of the CPU-generated logical address automatically represent the page offset ($d$), and the remaining higher bits represent the page number ($p$).
2. No Hardware Division or Modulo: If the page size were not a power of two (e.g. $3000$ bytes), the MMU hardware would have to perform integer division ($\lfloor \text{Address} / 3000 \rfloor$) to compute the page number and modulo ($\text{Address} \pmod{3000}$) to compute the offset. Division and modulo circuits are slow, bulky, and consume significant power.
3. With powers of two, address splitting is performed purely by bit-masking and wire routing at the hardware clock cycle level, taking effectively $0\text{ ns}$.

---

Question 2: If a process of size $72\text{ KB}$ is loaded into a paging system with page size $4\text{ KB}$, calculate:

1. The total number of pages allocated to the process.
2. The internal fragmentation generated.
3. What if the process size were $73\text{ KB}$?

Answer:

1. For $72\text{ KB}$ Process:
   • Number of pages $= \lceil 72\text{ KB} / 4\text{ KB} \rceil = 18$ pages.
   • Total allocated memory $= 18 \times 4\text{ KB} = 72\text{ KB}$.
   • Internal Fragmentation $= 72\text{ KB} - 72\text{ KB} = \mathbf{0\text{ bytes}}$ (Exact multiple).
2. For $73\text{ KB}$ Process:
   • Number of pages $= \lceil 73\text{ KB} / 4\text{ KB} \rceil = \lceil 18.25 \rceil = \mathbf{19\text{ pages}}$.
   • Total allocated memory $= 19 \times 4\text{ KB} = 76\text{ KB}$.
   • Internal Fragmentation $= 76\text{ KB} - 73\text{ KB} = \mathbf{3\text{ KB}} = 3072\text{ bytes}$.

Common Interview Traps

• The "Page Table is Inside the CPU" Fallacy: The page table is NOT a register inside the CPU! Page tables can contain millions of entries and reside in Main Memory (DRAM). The CPU contains only the Page Table Base Register (PTBR) pointing to the page table's starting address in RAM.
• Confusing Page Offset with Frame Offset: In paging, Page Offset is identically equal to Frame Offset ($d$). Because page size equals frame size, the relative byte offset within the page is identical to the relative byte offset within the physical frame.
• The "Two Memory Accesses" Trap: Never forget that pure paging doubles memory latency: for every single instruction or variable reference, the CPU must read the page table in RAM first, and then read the actual instruction/data in RAM second.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic7.3 Dynamic Storage Allocation AlgorithmsNext Topic →7.5 Address Translation Mechanics