7.5 Address Translation Mechanics: Logical Address to Physical Address

Back to Operating Systems Notes

📚Module 07: Main Memory ManagementTopic 7.5⏱️22 min read

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

💡 Core Intuition

🍳 The Everyday Analogy: The Postal Mail Forwarding Directory

Imagine living in a global university with students scattered across dozens of off-campus residence halls:

Architecture Flow

The Campus Mail Routing Pipeline

Translating student directory IDs into physical dormitory room numbers

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

✉️Student ID

Logical Campus Address

Logical Address (p, d)

A letter arrives addressed to: Student #42, Line 15.

→

Consult Central Directory

📒Master Registry

Housing Office Directory

The Page Table

The mail clerk looks up Row 42 in the housing ledger.

→

Assemble Delivery Slip

🚪Physical Dorm

Real Room Delivery

Physical Address (f, d)

The mail carrier walks directly to Dormitory Hall #7, Room 15.

• Logical Address: A coordinate generated by the CPU program counter: [Page Number p | Offset d].
• Page Table Lookup: Translates the abstract Page Number $p$ into a concrete Physical Frame Number $f$.
• Physical Address: Direct coordinates on the motherboard's DRAM bus: [Frame Number f | Offset d]. The offset $d$ is untouched.

---

💻 Bridging to Computer Science

Address translation is the hardware bridge connecting a process's illusion of a contiguous, private memory space to the fragmented physical reality of DRAM chips.

---

📚 Core Deep-Dive & Concepts

1. Fundamental Mathematical Formulations

To master address translation and solve numerical systems problems with 100% precision, we establish the canonical relationships between bit widths and storage capacities:

Address Space & Bit Width Relationship

For any byte-addressable memory of capacity $C$ bytes:

$\text{Capacity } C = 2^k \text{ bytes} \iff \text{Address Bit Width } k = \log_2(C)$

Where:

• $2^{10}\text{ B} = 1\text{ KB}$ ($10\text{ bits}$)
• $2^{20}\text{ B} = 1\text{ MB}$ ($20\text{ bits}$)
• $2^{30}\text{ B} = 1\text{ GB}$ ($30\text{ bits}$)
• $2^{40}\text{ B} = 1\text{ TB}$ ($40\text{ bits}$)

Core Paging Dimensions

$\text{Page Offset Bits } (d) = \log_2(\text{Page Size})$

$\text{Total Pages in Logical Space } = \frac{\text{Logical Address Space (LAS)}}{\text{Page Size}}$

$\text{Page Number Bits } (p) = \log_2(\text{Total Pages}) = \text{LAS Bits} - d$

$\text{Total Frames in Physical Space } = \frac{\text{Physical Address Space (PAS)}}{\text{Frame Size}}$

$\text{Frame Number Bits } (f) = \log_2(\text{Total Frames}) = \text{PAS Bits} - d$

$\text{Logical Address Length } = p + d$

$\text{Physical Address Length } = f + d$

$\text{Page Table Size (PTS)} = \text{Total Pages} \times \text{Page Table Entry (PTE) Size}$

---

2. Comprehensive System Configurations: Worked Reference Table

The following master reference table analyzes five fundamental systems architectures with varying Secondary Memory (Logical Address Space), Physical RAM (Physical Address Space), and Page Sizes:

System #	Logical Space (SM)	Physical RAM (MM)	Page Size (PS)	Addressability	LA Bits	PA Bits	Offset Bits ($d$)	Page Bits ($p$)	Frame Bits ($f$)
1	$32\text{ GB}$	$128\text{ MB}$	$1\text{ KB}$	1 Byte	$\mathbf{35}$	$\mathbf{27}$	$\mathbf{10}$	$\mathbf{25}$	$\mathbf{17}$
2	$4\text{ TB}$	$8\text{ GB}$	$2\text{ KB}$	1 Byte	$\mathbf{42}$	$\mathbf{33}$	$\mathbf{11}$	$\mathbf{31}$	$\mathbf{22}$
3	$512\text{ GB}$	$2\text{ GB}$	$512\text{ B}$	1 Byte	$\mathbf{39}$	$\mathbf{31}$	$\mathbf{9}$	$\mathbf{30}$	$\mathbf{22}$
4	$128\text{ GB}$	$32\text{ GB}$	$128\text{ B}$	1 Byte	$\mathbf{37}$	$\mathbf{35}$	$\mathbf{7}$	$\mathbf{30}$	$\mathbf{28}$
5	$1\text{ TB}$	$64\text{ MB}$	$4096\text{ B}$ ($4\text{ KB}$)	1 Byte	$\mathbf{40}$	$\mathbf{26}$	$\mathbf{12}$	$\mathbf{28}$	$\mathbf{14}$

---

3. Step-by-Step Derivations of Classic Configurations

Let us rigorously derive the exact values for each case from first principles:

Derivation for System 1

• Given:
  • Secondary Memory / Logical Space $= 32\text{ GB} = 2^5 \times 2^{30}\text{ B} = 2^{35}\text{ Bytes}$.
  • Main Memory / Physical Space $= 128\text{ MB} = 2^7 \times 2^{20}\text{ B} = 2^{27}\text{ Bytes}$.
  • Page Size $= 1\text{ KB} = 2^{10}\text{ Bytes}$.
  • Word Size $= 1\text{ Byte}$ (Byte-addressable).
• Step 1: Compute Offset Bits ($d$): $d = \log_2(\text{Page Size}) = \log_2(2^{10}) = \mathbf{10\text{ bits}}$
• Step 2: Compute Logical Address Bits ($\text{LA}$): $\text{LA} = \log_2(\text{Logical Address Space}) = \log_2(2^{35}) = \mathbf{35\text{ bits}}$ $p = \text{LA} - d = 35 - 10 = \mathbf{25\text{ bits}}$
• Step 3: Compute Physical Address Bits ($\text{PA}$): $\text{PA} = \log_2(\text{Physical Address Space}) = \log_2(2^{27}) = \mathbf{27\text{ bits}}$ $f = \text{PA} - d = 27 - 10 = \mathbf{17\text{ bits}}$
• Verification:
  • Total Pages $= 2^{25} = 33,554,432$ pages.
  • Total Frames $= 2^{17} = 131,072$ frames.

---

Derivation for System 2

• Given:
  • $\text{LAS} = 4\text{ TB} = 2^2 \times 2^{40}\text{ B} = 2^{42}\text{ Bytes} \implies \mathbf{\text{LA} = 42\text{ bits}}$.
  • $\text{PAS} = 8\text{ GB} = 2^3 \times 2^{30}\text{ B} = 2^{33}\text{ Bytes} \implies \mathbf{\text{PA} = 33\text{ bits}}$.
  • $\text{Page Size} = 2\text{ KB} = 2^1 \times 2^{10}\text{ B} = 2^{11}\text{ Bytes} \implies \mathbf{d = 11\text{ bits}}$.
• Address Breakdown: $p = \text{LA} - d = 42 - 11 = \mathbf{31\text{ bits}}$ $f = \text{PA} - d = 33 - 11 = \mathbf{22\text{ bits}}$

---

4. Page Table Entry (PTE) Sizing & Memory Footprint

A common source of confusion in computer systems is the distinction between Frame Number Bits and Page Table Entry Size:

Minimum Page Table Entry (PTE) Sizing Rule

A Page Table Entry must store the Frame Number ($f\text{ bits}$) plus any hardware status bits. Because memory is byte-addressable, data structures cannot allocate fractional bytes:

$\mathbf{\text{PTE Size (minimum)} = \left\lceil \frac{f + \text{Status Bits}}{8} \right\rceil \text{ Bytes}}$

If status bits are not explicitly specified in problem statements, assume $\text{PTE Size} = \lceil f / 8 \rceil\text{ Bytes}$.

Detailed Example: Sizing the Page Table

• Given:
  • Virtual Address Space $= 16\text{ GB} = 2^{34}\text{ Bytes} \implies \text{LA} = 34\text{ bits}$.
  • Physical RAM $= 64\text{ MB} = 2^{26}\text{ Bytes} \implies \text{PA} = 26\text{ bits}$.
  • Page Size $= 1\text{ KB} = 2^{10}\text{ Bytes} \implies d = 10\text{ bits}$.
• Calculate Bits:
  • Page number bits $p = 34 - 10 = 24\text{ bits}$.
  • Total Pages $= 2^{24} = 16\text{ Million pages}$.
  • Frame number bits $f = 26 - 10 = 16\text{ bits}$.
• Minimum PTE Size:
  • To store $16$ bits of frame number, we require: $\text{PTE Size} = \frac{16\text{ bits}}{8\text{ bits/byte}} = \mathbf{2\text{ Bytes}}$
• Total Page Table Size: $\text{Page Table Size} = \text{Total Pages} \times \text{PTE Size} = 2^{24} \times 2\text{ Bytes} = 2^{25}\text{ Bytes} = \mathbf{32\text{ MB}}$
• Architectural Insight:
  • Notice that the physical memory is only $64\text{ MB}$!
  • Storing a single process's page table consumes $32\text{ MB}$, which is $50\%$ of the entire physical RAM!
  • This demonstrates why naive single-level paging collapses on large virtual address spaces and necessitates Multi-Level Paging.

---

🏭 In The Real World: Production Case Study

x86-64 4-Level Paging (Paging-48 & Paging-57)

Modern Intel and AMD server processors do not utilize 64 full bits of virtual address space because managing $2^{64}$ bytes would require astronomically large page tables:

Address Bitfield	Bit Range	Width	Purpose in Multi-Level Paging Hierarchy
Sign Extension	Bits $63\dots48$	$16\text{ bits}$	Canonical form check (Must be all 0s for user space or all 1s for kernel)
PML4 Index	Bits $47\dots39$	$9\text{ bits}$	Level 4: Page Map Level 4 Table ($512$ entries)
PDPT Index	Bits $38\dots30$	$9\text{ bits}$	Level 3: Page Directory Pointer Table ($512$ entries)
PD Index	Bits $29\dots21$	$9\text{ bits}$	Level 2: Page Directory ($512$ entries)
PT Index	Bits $20\dots12$	$9\text{ bits}$	Level 1: Page Table ($512$ entries)
Page Offset	Bits $11\dots0$	$12\text{ bits}$	Byte displacement within target $4\text{ KB}$ physical frame

1. Canonical 48-Bit Virtual Addressing:
   • Bits $0$ to $11$ ($12$ bits) specify the offset inside a standard $4\text{ KB}$ page ($2^{12} = 4096\text{ bytes}$).
   • The remaining $36$ bits are divided into four 9-bit chunks ($9 + 9 + 9 + 9 = 36$).
   • Why 9 bits? Because each level's table has $2^9 = 512$ entries. With an 8-byte (64-bit) PTE, $512 \times 8\text{ B} = 4096\text{ bytes} = 4\text{ KB}$—meaning every page table fits inside a physical frame!
2. 5-Level Paging (PML5):
   • Modern Linux kernels powering AI clusters support 57-bit virtual addressing by adding a 5th level (PML5) to address up to $128\text{ PB}$ (petabytes) of virtual memory and $4\text{ PB}$ of physical DRAM.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: In a computer system, the logical address is $32$ bits and the physical address is $24$ bits. The page size is $4\text{ KB}$.

1. Find the number of pages in the logical address space.
2. Find the number of frames in physical memory.
3. If each page table entry takes $4$ bytes, calculate the total size of the page table for a process.

Answer:

1. Number of pages:
   • $\text{Page Size} = 4\text{ KB} = 2^{12}\text{ bytes} \implies d = 12\text{ bits}$.
   • Logical address length $= 32\text{ bits} \implies p = 32 - 12 = 20\text{ bits}$.
   • Number of pages $= 2^{20} = \mathbf{1,048,576\text{ pages}}$ ($1\text{ Million pages}$).
2. Number of frames:
   • Physical address length $= 24\text{ bits} \implies f = 24 - 12 = 12\text{ bits}$.
   • Number of frames $= 2^{12} = \mathbf{4096\text{ frames}}$.
3. Total size of Page Table:
   • $\text{Size} = \text{Number of pages} \times \text{PTE Size} = 2^{20} \times 4\text{ bytes} = 4 \times 2^{20}\text{ bytes} = \mathbf{4\text{ MB}}$.

---

Question 2: A byte-addressable system has a physical address space of $512\text{ MB}$ and a page size of $8\text{ KB}$. What is the minimum number of bits required to store the physical frame number in each page table entry? Answer:

1. $\text{Physical Address Space} = 512\text{ MB} = 2^9 \times 2^{20}\text{ bytes} = 2^{29}\text{ bytes} \implies \text{PA} = 29\text{ bits}$.
2. $\text{Page Size} = 8\text{ KB} = 2^3 \times 2^{10}\text{ bytes} = 2^{13}\text{ bytes} \implies d = 13\text{ bits}$.
3. $\text{Frame Number Bits } f = \text{PA} - d = 29 - 13 = \mathbf{16\text{ bits}}$.
4. Conclusion: At minimum, $16$ bits must be dedicated strictly to hold the frame number.

Common Interview Traps

• The Word-Addressable Trap: Always verify whether the problem specifies byte-addressable or word-addressable memory. If a system is 2-byte word addressable, $4\text{ KB}$ represents $2\text{ K words}$, meaning $d = 11$ bits instead of $12$ bits!
• The Frame Number vs Physical Address Confusion: Students often mistake $f$ (frame number) for the full physical address. Remember: $\text{Physical Address} = [f \mid d]$. The frame number is only the higher-order component.
• Rounding Up PTE Sizes: In theoretical questions, if $f = 17$ bits, the minimal byte-aligned storage is $\lceil 17/8 \rceil = 3$ bytes. In real systems, hardware alignments favor power-of-two bytes ($4$ bytes or $8$ bytes). Always state your alignment assumption clearly.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic7.4 Compaction & Paging ArchitectureNext Topic →7.6 TLB & Effective Access Time