Operating SystemsPaging Address Translation

Paging Address Translation Mechanisms

LevelIntermediate

Duration90 mins

TopicPaging Address Translation

4 / 5

Physical Address Formation

The Final Assembly

We've extracted the page number, looked up the frame number, and preserved the offset. Now comes the final step: assembling these components into a physical address that can be placed on the memory bus to access real, physical RAM.

This step is deceptively simple—just concatenation of bits. But its simplicity is precisely what makes paging efficient. No arithmetic beyond placing bits in the right positions. No computation that adds latency. Just reassembly: the frame number takes the place of the page number, and the offset remains unchanged.

What You Will Learn

By the end of this page, you will understand exactly how the physical address is constructed from frame number and offset, the bit-level mechanics of address formation, how different address sizes and page sizes affect the process, and how hardware implements this with zero computational overhead. This completes your understanding of the fundamental address translation mechanism.

The Formation Formula

Physical address formation is expressed by a simple formula:

Physical Address = (Frame Number × Page Size) + Offset

Or equivalently, using bit operations:

Physical Address = (Frame Number << offset_bits) | Offset

Both formulations produce identical results because:

The page size is always a power of 2 (Page Size = 2^offset_bits)
Multiplying by a power of 2 is equivalent to left-shifting
The offset is guaranteed to be less than the page size, so OR and addition produce the same result

Converting Mermaid diagram...

Worked Example (4KB Pages, 32-bit Physical Address):

Given:

Virtual Address: 0x00012345
Page Number: 0x12 (18)
Offset: 0x345 (837)
Frame Number (from page table): 0x5A2 (1442)

Formation:

Physical Address = 0x5A2 << 12 | 0x345
                 = 0x5A2000 | 0x345
                 = 0x5A2345

The resulting physical address 0x005A2345 points to byte 837 within frame 1442.

Physical Address Formation Examples
Virtual Addr	Page #	Frame #	Offset	Physical Addr	Calculation
0x00000500	0	0x100	0x500	0x00100500	(0x100 << 12) \| 0x500
0x00001234	1	0x055	0x234	0x00055234	(0x055 << 12) \| 0x234
0x00012345	18	0x5A2	0x345	0x005A2345	(0x5A2 << 12) \| 0x345
0x0002AFFF	42	0x999	0xFFF	0x00999FFF	(0x999 << 12) \| 0xFFF
0xFFFFFFFF	0xFFFFF	0xABCDE	0xFFF	0xABCDEFFF	(0xABCDE << 12) \| 0xFFF

No Overlap, No Gaps

Because the offset is strictly less than the page size, and the frame number is shifted left by exactly the number of offset bits, there's never any overlap or gap between them. The offset fills the low bits; the frame number fills the high bits. They join seamlessly to form the complete address.

Bit-Level Mechanics

Let's examine exactly how the bits fit together to form the physical address. Understanding this at the bit level reveals why the operation is so efficient.

physical_address_formation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>
#include <stdint.h>
 
/*
 * Physical Address Formation - Bit-Level Demonstration
 * 
 * This program shows exactly how frame number and offset
 * combine to form a physical address through bit operations.
 */
 
#define PAGE_SIZE       4096
#define OFFSET_BITS     12
#define OFFSET_MASK     0xFFF
 
void print_binary(uint64_t value, int total_bits, int split_point) {
    for (int i = total_bits - 1; i >= 0; i--) {
        printf("%d", (int)((value >> i) & 1));
        if (i == split_point) printf(" | ");
        else if (i > 0 && i % 4 == 0 && i != split_point) printf(" ");
    }
}
 
void form_physical_address(uint32_t page_number, uint32_t frame_number, 
                           uint32_t offset) {
    printf("\n╔══════════════════════════════════════════════════════════════════╗\n");
    printf("║              PHYSICAL ADDRESS FORMATION                           ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    // Original virtual address reconstruction
    uint64_t virtual_addr = ((uint64_t)page_number << OFFSET_BITS) | offset;
    printf("║ Virtual Address:  0x%08llX                                      ║\n",
           (unsigned long long)virtual_addr);
    printf("║ Binary: ");
    print_binary(virtual_addr, 32, 12);
    printf("  ║\n");
    printf("║         |--Page Number--| |---Offset---|                          ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    printf("║ Extracted Components:                                             ║\n");
    printf("║   Page Number: 0x%05X (decimal: %u)                              ║\n",
           page_number, page_number);
    printf("║   Offset:      0x%03X (decimal: %u)                               ║\n",
           offset, offset);
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    printf("║ After Page Table Lookup:                                          ║\n");
    printf("║   Frame Number: 0x%05X (decimal: %u)                             ║\n",
           frame_number, frame_number);
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    printf("║ Formation Steps:                                                  ║\n");
    printf("║                                                                   ║\n");
    
    // Step 1: Frame number before shift
    printf("║ 1. Frame Number (0x%05X):                                        ║\n",
           frame_number);
    printf("║    Binary: ");
    print_binary(frame_number, 20, -1);
    printf("                ║\n");
    printf("║                                                                   ║\n");
    
    // Step 2: Frame number shifted left
    uint64_t shifted_frame = (uint64_t)frame_number << OFFSET_BITS;
    printf("║ 2. Frame << 12 (0x%08llX):                                      ║\n",
           (unsigned long long)shifted_frame);
    printf("║    Binary: ");
    print_binary(shifted_frame, 32, 12);
    printf("  ║\n");
    printf("║            |--Frame Number-| |-Zeros for Offset-|                 ║\n");
    printf("║                                                                   ║\n");
    
    // Step 3: Offset
    printf("║ 3. Offset (0x%03X):                                               ║\n",
           offset);
    printf("║    Binary: ");
    print_binary(offset, 32, 12);
    printf("  ║\n");
    printf("║            |-All Zeros----| |---Offset Bits----|                  ║\n");
    printf("║                                                                   ║\n");
    
    // Step 4: OR them together
    uint64_t physical_addr = shifted_frame | offset;
    printf("║ 4. Physical = (Frame << 12) | Offset:                             ║\n");
    printf("║    Binary: ");
    print_binary(physical_addr, 32, 12);
    printf("  ║\n");
    printf("║            |--Frame Number-| |----Offset----|                     ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    printf("║ RESULT:                                                           ║\n");
    printf("║   Physical Address: 0x%08llX                                    ║\n",
           (unsigned long long)physical_addr);
    printf("║                                                                   ║\n");
    printf("║   Virtual 0x%08llX → Physical 0x%08llX                       ║\n",
           (unsigned long long)virtual_addr, (unsigned long long)physical_addr);
    printf("╚══════════════════════════════════════════════════════════════════╝\n");
}
 
void demonstrate_formation_equivalence() {
    printf("\n═══════════════════════════════════════════════════════════════\n");
    printf("     FORMATION METHOD EQUIVALENCE                                \n");
    printf("═══════════════════════════════════════════════════════════════\n\n");
    
    uint32_t frame = 0x5A2;
    uint32_t offset = 0x345;
    
    // Method 1: Shift and OR
    uint64_t method1 = ((uint64_t)frame << 12) | offset;
    
    // Method 2: Multiply and ADD
    uint64_t method2 = ((uint64_t)frame * PAGE_SIZE) + offset;
    
    // Method 3: Concatenation view
    // In hardware, this is just wiring - no operation
    
    printf("Frame Number: 0x%X (%u)\n", frame, frame);
    printf("Offset:       0x%X (%u)\n", offset, offset);
    printf("\n");
    printf("Method 1 (Shift + OR):      (0x%X << 12) | 0x%X = 0x%08llX\n",
           frame, offset, (unsigned long long)method1);
    printf("Method 2 (Multiply + Add):  (0x%X × 4096) + 0x%X = 0x%08llX\n",
           frame, offset, (unsigned long long)method2);
    printf("Method 3 (Concatenation):   0x%X || 0x%03X = 0x%08llX\n",
           frame, offset, (unsigned long long)method1);
    printf("\n");
    printf("All methods produce: 0x%08llX\n", (unsigned long long)method1);
    printf("Equivalence: %s\n", method1 == method2 ? "✓ Confirmed" : "✗ Error!");
    printf("\n");
    printf("Hardware uses Method 3: just wire the frame bits to high positions,\n");
    printf("wire the offset bits to low positions. Zero computation.\n");
}
 
int main() {
    printf("╔══════════════════════════════════════════════════════════════╗\n");
    printf("║      PHYSICAL ADDRESS FORMATION DEMONSTRATION                 ║\n");
    printf("╚══════════════════════════════════════════════════════════════╝\n");
    
    // Demonstrate several translations
    form_physical_address(0x12, 0x5A2, 0x345);   // Page 18 -> Frame 0x5A2
    form_physical_address(0x0, 0x100, 0x500);    // Page 0 -> Frame 0x100
    form_physical_address(0x1, 0x055, 0xFFF);    // Page 1, max offset
    
    demonstrate_formation_equivalence();
    
    return 0;
}

The Beauty of Bit Alignment

The reason we can use simple OR (|) instead of addition (+) is that the two operands never have overlapping 1-bits. The shifted frame number has all zeros in the offset positions; the offset has all zeros in the frame positions. This guarantee comes from using power-of-two page sizes.

Hardware Implementation

In actual hardware, physical address formation is not a computation—it's a wiring arrangement. The frame number bits are routed to the upper bit positions of the physical address bus; the offset bits are routed to the lower positions. There are no gates, no ALU operations, no latency introduced.

Converting Mermaid diagram...

The Zero-Latency Property:

Because address formation is just wire routing:

Parallel with TLB Lookup: The offset bits are positioned on the physical address bus while the TLB lookup is in progress. The moment the frame number is available, formation is complete.
No Pipeline Stall: Unlike arithmetic operations that consume ALU cycles, wiring introduces only propagation delay—nanoseconds at most, far faster than a clock cycle.
Fixed Latency: Every address formation takes exactly the same time (essentially zero), regardless of the specific values involved.

What Hardware Does

•Routes frame number to high address lines
•Routes offset to low address lines
•Uses multiplexer to select frame source (TLB vs memory)
•Drives physical address bus with combined result

What Hardware Doesn't Do

•No arithmetic unit involvement
•No multiplication circuit
•No addition/OR circuit
•No clock cycles consumed for formation

The Address Formation Timing:

Clock Cycle  |  TLB Path           |  Offset Path
─────────────┼─────────────────────┼──────────────────
    1        |  TLB CAM compare    |  Offset positioned
    2        |  Frame # available  |  (waiting)
    2+       |  → Combined with offset → Physical address ready

The offset is ready from the moment the virtual address is presented. The formation completes in the same cycle that the frame number becomes available—no additional cycles needed.

Multiplexer Role

A multiplexer selects the frame number source: from the TLB on a hit, or from the page table walk logic on a miss. Once selected, the frame bits flow directly to the physical address bus. The multiplexer is the only 'logic' in this path, and it's trivial.

Variable Address and Page Sizes

The physical address formation process adapts to different address widths and page sizes. Modern systems support 32-bit, 48-bit, even 52-bit or 57-bit physical addresses, and multiple page sizes (4KB, 2MB, 1GB).

Address Formation Parameters by Configuration
Configuration	Page Size	Offset Bits	Frame Bits	Physical Address
32-bit, 4KB	4 KB	12	20	32 bits total
32-bit, 4MB (PAE)	4 MB	22	10	32 bits total
x86-64, 4KB	4 KB	12	40	52 bits total
x86-64, 2MB	2 MB	21	31	52 bits total
x86-64, 1GB	1 GB	30	22	52 bits total

variable_page_sizes.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>
#include <stdint.h>
 
/*
 * Physical Address Formation with Variable Page Sizes
 * 
 * Shows how the formation process adapts to 4KB, 2MB, and 1GB
 * pages on x86-64 systems.
 */
 
typedef struct {
    const char* name;
    int offset_bits;
    uint64_t size;
    uint64_t offset_mask;
} PageConfig;
 
PageConfig page_configs[] = {
    {"4 KB", 12, 4096ULL, 0xFFFULL},
    {"2 MB", 21, 2097152ULL, 0x1FFFFFULL},
    {"1 GB", 30, 1073741824ULL, 0x3FFFFFFFULL},
};
 
void form_address_for_size(uint64_t virtual_addr, uint64_t frame_number, 
                            PageConfig* config) {
    uint64_t offset = virtual_addr & config->offset_mask;
    uint64_t physical_addr = (frame_number << config->offset_bits) | offset;
    
    printf("\n┌─ %s Pages ──────────────────────────────────────────────────┐\n",
           config->name);
    printf("│ Virtual Address:  0x%016llX                      │\n",
           (unsigned long long)virtual_addr);
    printf("│ Offset bits: %d, Frame bits: %d                              │\n",
           config->offset_bits, 52 - config->offset_bits);
    printf("├────────────────────────────────────────────────────────────────┤\n");
    printf("│ Extraction:                                                    │\n");
    printf("│   Offset = VA & 0x%llX = 0x%llX                      │\n",
           (unsigned long long)config->offset_mask, (unsigned long long)offset);
    printf("├────────────────────────────────────────────────────────────────┤\n");
    printf("│ Formation:                                                     │\n");
    printf("│   Frame Number: 0x%llX                                        │\n",
           (unsigned long long)frame_number);
    printf("│   Frame << %d: 0x%llX                              │\n",
           config->offset_bits, 
           (unsigned long long)(frame_number << config->offset_bits));
    printf("│   | Offset:    0x%llX                                         │\n",
           (unsigned long long)offset);
    printf("│   = Physical:  0x%016llX                      │\n",
           (unsigned long long)physical_addr);
    printf("├────────────────────────────────────────────────────────────────┤\n");
    printf("│ Frame covers: 0x%012llX - 0x%012llX              │\n",
           (unsigned long long)(frame_number << config->offset_bits),
           (unsigned long long)((frame_number << config->offset_bits) + 
                                 config->size - 1));
    printf("└────────────────────────────────────────────────────────────────┘\n");
}
 
void compare_page_sizes() {
    printf("\n═══════════════════════════════════════════════════════════════\n");
    printf("     PAGE SIZE COMPARISON: SAME VIRTUAL ADDRESS                  \n");
    printf("═══════════════════════════════════════════════════════════════\n");
    
    uint64_t vaddr = 0x00007FFFF7DD5000ULL;  // Typical library address
    
    // For 4KB pages
    uint64_t page_4kb = vaddr >> 12;
    uint64_t offset_4kb = vaddr & 0xFFF;
    
    // For 2MB pages  
    uint64_t page_2mb = vaddr >> 21;
    uint64_t offset_2mb = vaddr & 0x1FFFFF;
    
    // For 1GB pages
    uint64_t page_1gb = vaddr >> 30;
    uint64_t offset_1gb = vaddr & 0x3FFFFFFF;
    
    printf("\nVirtual Address: 0x%016llX\n\n", (unsigned long long)vaddr);
    
    printf("%-10s | %-15s | %-15s | %-15s\n",
           "Page Size", "Page Number", "Offset", "Entries Needed");
    printf("%-10s-+-%-15s-+-%-15s-+-%-15s\n",
           "----------", "---------------", "---------------", "---------------");
    
    printf("%-10s | 0x%-13llX | 0x%-13llX | many           \n",
           "4 KB", (unsigned long long)page_4kb, (unsigned long long)offset_4kb);
    printf("%-10s | 0x%-13llX | 0x%-13llX | fewer          \n",
           "2 MB", (unsigned long long)page_2mb, (unsigned long long)offset_2mb);
    printf("%-10s | 0x%-13llX | 0x%-13llX | very few       \n",
           "1 GB", (unsigned long long)page_1gb, (unsigned long long)offset_1gb);
    
    printf("\nObservation: Larger pages mean smaller page numbers,\n");
    printf("fewer page table entries, but also more potential\n");
    printf("internal fragmentation.\n");
}
 
int main() {
    printf("╔══════════════════════════════════════════════════════════════╗\n");
    printf("║     PHYSICAL ADDRESS FORMATION: VARIABLE PAGE SIZES           ║\n");
    printf("╚══════════════════════════════════════════════════════════════╝\n");
    
    uint64_t vaddr = 0x00000000012345678ULL;
    
    // Same address with different page sizes and frame mappings
    form_address_for_size(vaddr, 0x12345, &page_configs[0]);  // 4KB
    form_address_for_size(vaddr, 0x91A, &page_configs[1]);     // 2MB  
    form_address_for_size(vaddr, 0x2, &page_configs[2]);       // 1GB
    
    compare_page_sizes();
    
    return 0;
}

Huge Page Benefits

With 1GB pages, the frame number is only 22 bits (for 52-bit physical), and each TLB entry covers an enormous range. Databases and VMs use huge pages specifically because TLB misses become rare—the working set fits in fewer pages, and each page table entry covers gigabytes of contiguous memory.

Physical Address Space Considerations

The formed physical address must fit within the system's physical address space. Unlike virtual address spaces (which are per-process and can overlap), the physical address space is global and shared by all processes, the kernel, and hardware devices.

Physical Address Space Characteristics
Architecture	Physical Address Bits	Max Physical Memory	Notes
x86 (original)	24	16 MB	8086, 286
x86 (386+)	32	4 GB	Standard 32-bit
x86 PAE	36	64 GB	Physical Address Extension
x86-64 (early)	40	1 TB	First 64-bit AMD/Intel
x86-64 (current)	46-52	4-64 PB	Server/workstation chips
ARM64	48-52	256 TB - 4 PB	ARMv8 and later

Physical vs Virtual Address Width:

The physical address width is independent of the virtual address width:

Virtual: Typically 48-57 bits on x86-64 (256 TB - 128 PB per process)
Physical: Typically 40-52 bits system-wide (1 TB - 4 PB total hardware)

The page table entry stores enough bits for the physical frame number. The MMU forms physical addresses using whatever width the hardware supports.

Memory Holes and Reserved Regions:

Not all of the physical address space contains usable RAM:

•Legacy I/O Region (0-1MB): BIOS, VGA buffer, legacy device memory
•PCI MMIO: Memory-mapped I/O for devices (typically 4GB-8GB region)
•Reserved: ACPI tables, firmware, hardware-specific regions
•DRAM Gaps: Between RAMM sticks if not contiguous
•High Memory: Physical RAM above certain boundaries may need special handling

The OS maintains a physical memory map (obtained from firmware via ACPI/UEFI) describing which physical address ranges contain usable RAM. Only frames within usable regions appear in page table entries.

Physical Address ≠ RAM

A valid physical address might point to hardware device registers (MMIO), not RAM. The page table can map virtual addresses to device memory for memory-mapped I/O. The translation is the same; the physical target is different. This is how drivers access hardware without port I/O instructions.

Complete Translation Example

Let's trace a complete address translation from start to finish, showing every step from virtual address to physical address.

complete_translation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
 
/*
 * Complete Address Translation Walkthrough
 * 
 * This program traces every step of translating a virtual
 * address to a physical address, culminating in address formation.
 */
 
#define PAGE_SIZE   4096
#define OFFSET_BITS 12
 
// Simulated page table entry
typedef struct {
    uint32_t frame;
    bool present;
    bool writable;
    bool user;
    bool accessed;
    bool dirty;
} PTE;
 
// Simulated TLB entry
typedef struct {
    uint32_t page;
    uint32_t frame;
    bool valid;
} TLBEntry;
 
// Simple simulation state
PTE page_table[256];  // Simplified small table
TLBEntry tlb[8];      // Small TLB
 
void init_simulation() {
    // Set up a mapping: Page 18 -> Frame 0x5A2
    page_table[18].present = true;
    page_table[18].frame = 0x5A2;
    page_table[18].writable = true;
    page_table[18].user = true;
    page_table[18].accessed = false;
    page_table[18].dirty = false;
    
    // TLB starts empty
    for (int i = 0; i < 8; i++) {
        tlb[i].valid = false;
    }
}
 
void complete_translation(uint64_t virtual_addr) {
    printf("\n");
    printf("╔══════════════════════════════════════════════════════════════════╗\n");
    printf("║           COMPLETE ADDRESS TRANSLATION WALKTHROUGH               ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    printf("║ VIRTUAL ADDRESS: 0x%08llX                                      ║\n",
           (unsigned long long)virtual_addr);
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    // ═══════════════════════════════════════════════════════════════════════
    // STEP 1: DECOMPOSE VIRTUAL ADDRESS
    // ═══════════════════════════════════════════════════════════════════════
    
    uint32_t page_number = virtual_addr >> OFFSET_BITS;
    uint32_t offset = virtual_addr & (PAGE_SIZE - 1);
    
    printf("║                                                                  ║\n");
    printf("║ ┌──────────────────────────────────────────────────────────────┐ ║\n");
    printf("║ │ STEP 1: DECOMPOSE VIRTUAL ADDRESS                           │ ║\n");
    printf("║ └──────────────────────────────────────────────────────────────┘ ║\n");
    printf("║                                                                  ║\n");
    printf("║   Virtual Address: 0x%08llX                                    ║\n",
           (unsigned long long)virtual_addr);
    printf("║                                                                  ║\n");
    printf("║   Split at bit 12 (for 4KB pages):                               ║\n");
    printf("║     ┌─────────────────────┬────────────────┐                     ║\n");
    printf("║     │ Bits 31-12 (high)   │ Bits 11-0 (low)│                     ║\n");
    printf("║     │ Page Number         │ Offset         │                     ║\n");
    printf("║     │ 0x%05X (%u)       │ 0x%03X (%u)    │                     ║\n",
           page_number, page_number, offset, offset);
    printf("║     └─────────────────────┴────────────────┘                     ║\n");
    printf("║                                                                  ║\n");
    printf("║   Extraction:                                                    ║\n");
    printf("║     Page Number = 0x%08llX >> 12 = 0x%05X                      ║\n",
           (unsigned long long)virtual_addr, page_number);
    printf("║     Offset      = 0x%08llX & 0xFFF = 0x%03X                     ║\n",
           (unsigned long long)virtual_addr, offset);
    printf("║                                                                  ║\n");
    
    // ═══════════════════════════════════════════════════════════════════════
    // STEP 2: TLB LOOKUP
    // ═══════════════════════════════════════════════════════════════════════
    
    printf("║ ┌──────────────────────────────────────────────────────────────┐ ║\n");
    printf("║ │ STEP 2: TLB LOOKUP                                          │ ║\n");
    printf("║ └──────────────────────────────────────────────────────────────┘ ║\n");
    printf("║                                                                  ║\n");
    printf("║   Searching TLB for Page Number %u...                            ║\n",
           page_number);
    
    bool tlb_hit = false;
    uint32_t frame_number = 0;
    
    for (int i = 0; i < 8; i++) {
        if (tlb[i].valid && tlb[i].page == page_number) {
            tlb_hit = true;
            frame_number = tlb[i].frame;
            break;
        }
    }
    
    if (tlb_hit) {
        printf("║   TLB HIT! Frame = 0x%X                                        ║\n",
               frame_number);
    } else {
        printf("║   TLB MISS - Proceeding to page table walk                     ║\n");
        printf("║                                                                  ║\n");
        
        // ═══════════════════════════════════════════════════════════════════
        // STEP 3: PAGE TABLE WALK
        // ═══════════════════════════════════════════════════════════════════
        
        printf("║ ┌──────────────────────────────────────────────────────────────┐ ║\n");
        printf("║ │ STEP 3: PAGE TABLE WALK                                     │ ║\n");
        printf("║ └──────────────────────────────────────────────────────────────┘ ║\n");
        printf("║                                                                  ║\n");
        printf("║   Page Table Base Register (PTBR): 0xPTABE_BASE                  ║\n");
        printf("║   PTE Address = PTBR + (Page# × 4)                               ║\n");
        printf("║   PTE Address = PTBR + (%u × 4) = PTBR + %u                      ║\n",
               page_number, page_number * 4);
        printf("║                                                                  ║\n");
        printf("║   Reading PTE from memory...                                     ║\n");
        
        if (page_number < 256 && page_table[page_number].present) {
            frame_number = page_table[page_number].frame;
            printf("║   PTE found:                                                     ║\n");
            printf("║     Frame Number: 0x%X                                          ║\n",
                   frame_number);
            printf("║     Present: Yes                                                 ║\n");
            printf("║     Writable: %s                                                ║\n",
                   page_table[page_number].writable ? "Yes" : "No");
            printf("║     User: %s                                                    ║\n",
                   page_table[page_number].user ? "Yes" : "No");
            printf("║                                                                  ║\n");
            printf("║   Setting ACCESSED bit in PTE...                                 ║\n");
            page_table[page_number].accessed = true;
            printf("║   Inserting into TLB for future accesses...                      ║\n");
            
            // Insert into TLB
            tlb[0].valid = true;
            tlb[0].page = page_number;
            tlb[0].frame = frame_number;
        } else {
            printf("║   PAGE FAULT! Page not present in memory.                        ║\n");
            printf("║   OS would handle: load from disk, update PTE, retry.            ║\n");
            printf("╚══════════════════════════════════════════════════════════════════╝\n");
            return;
        }
    }
    
    printf("║                                                                  ║\n");
    
    // ═══════════════════════════════════════════════════════════════════════
    // STEP 4: FORM PHYSICAL ADDRESS
    // ═══════════════════════════════════════════════════════════════════════
    
    uint64_t physical_addr = ((uint64_t)frame_number << OFFSET_BITS) | offset;
    
    printf("║ ┌──────────────────────────────────────────────────────────────┐ ║\n");
    printf("║ │ STEP 4: FORM PHYSICAL ADDRESS                               │ ║\n");
    printf("║ └──────────────────────────────────────────────────────────────┘ ║\n");
    printf("║                                                                  ║\n");
    printf("║   Components:                                                    ║\n");
    printf("║     Frame Number: 0x%X                                          ║\n",
           frame_number);
    printf("║     Offset:       0x%03X                                         ║\n",
           offset);
    printf("║                                                                  ║\n");
    printf("║   Formation:                                                     ║\n");
    printf("║     Physical = (Frame << 12) | Offset                            ║\n");
    printf("║              = (0x%X << 12) | 0x%03X                            ║\n",
           frame_number, offset);
    printf("║              = 0x%X000 | 0x%03X                                 ║\n",
           frame_number, offset);
    printf("║              = 0x%08llX                                        ║\n",
           (unsigned long long)physical_addr);
    printf("║                                                                  ║\n");
    printf("║     ┌─────────────────────┬────────────────┐                     ║\n");
    printf("║     │ Frame Number        │ Offset         │                     ║\n");
    printf("║     │ 0x%05X             │ 0x%03X          │                     ║\n",
           frame_number, offset);
    printf("║     └─────────────────────┴────────────────┘                     ║\n");
    printf("║                                                                  ║\n");
    
    // ═══════════════════════════════════════════════════════════════════════
    // SUMMARY
    // ═══════════════════════════════════════════════════════════════════════
    
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    printf("║                         TRANSLATION COMPLETE                     ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    printf("║                                                                  ║\n");
    printf("║   Virtual Address:  0x%08llX                                   ║\n",
           (unsigned long long)virtual_addr);
    printf("║                         ↓                                        ║\n");
    printf("║   Physical Address: 0x%08llX                                   ║\n",
           (unsigned long long)physical_addr);
    printf("║                                                                  ║\n");
    printf("║   The memory controller now accesses physical RAM at 0x%08llX  ║\n",
           (unsigned long long)physical_addr);
    printf("║                                                                  ║\n");
    printf("╚══════════════════════════════════════════════════════════════════╝\n");
}
 
int main() {
    init_simulation();
    
    // First access - TLB miss, page table walk
    printf("\n═══════════════════════════════════════════════════════════════\n");
    printf("     FIRST ACCESS (TLB MISS - FULL TRANSLATION)                  \n");
    printf("═══════════════════════════════════════════════════════════════\n");
    complete_translation(0x00012345);
    
    // Second access to same page - TLB hit
    printf("\n═══════════════════════════════════════════════════════════════\n");
    printf("     SECOND ACCESS (TLB HIT - FAST PATH)                         \n");
    printf("═══════════════════════════════════════════════════════════════\n");
    complete_translation(0x00012500);  // Same page, different offset
    
    return 0;
}

The Complete Picture

This example shows the entire translation pipeline: decomposition → TLB check → page table walk (if needed) → physical address formation. On the first access, all steps execute. On subsequent accesses to the same page, the TLB hit bypasses the page table walk entirely—formation happens immediately.

Summary: Physical Address Formation

Physical address formation is the final, simplest step in address translation—but its simplicity is key to paging's efficiency. The formed address directly accesses physical RAM or device memory.

Key Takeaways

•Formation Formula: Physical = (Frame << offset_bits) | Offset, or equivalently (Frame × PageSize) + Offset.
•Zero Computation: In hardware, formation is wiring—frame bits go to high positions, offset bits to low positions.
•Parallel with TLB: The offset is ready while TLB lookup proceeds; formation completes instantly when frame is available.
•Variable Sizes: The same process applies to all page sizes; only the split point (offset bit count) changes.
•Physical Address Space: The formed address must fall within valid physical memory or MMIO regions.
•Overall Pipeline: Decompose → TLB/Walk → Validate → Form Physical → Access Memory.

What's Next:

Having understood the complete translation mechanism—page number extraction, offset extraction, frame lookup, and physical address formation—we'll conclude with a comprehensive translation example that ties everything together, walking through realistic scenarios with actual numbers and timing considerations.

Page Complete

You now understand physical address formation—the final step where frame number and offset combine into a complete physical memory reference. This simple concatenation, implemented as wiring in hardware, is what makes billions of translations per second possible.

4 / 5

Loading learning content...

Operating SystemsPaging Address Translation

Paging Address Translation Mechanisms

LevelIntermediate

Duration90 mins

TopicPaging Address Translation

4 / 5

Physical Address Formation

The Final Assembly

What You Will Learn

The Formation Formula

Physical address formation is expressed by a simple formula:

Physical Address = (Frame Number × Page Size) + Offset

Or equivalently, using bit operations:

Physical Address = (Frame Number << offset_bits) | Offset

Both formulations produce identical results because:

The page size is always a power of 2 (Page Size = 2^offset_bits)
Multiplying by a power of 2 is equivalent to left-shifting
The offset is guaranteed to be less than the page size, so OR and addition produce the same result

Converting Mermaid diagram...

Worked Example (4KB Pages, 32-bit Physical Address):

Given:

Virtual Address: 0x00012345
Page Number: 0x12 (18)
Offset: 0x345 (837)
Frame Number (from page table): 0x5A2 (1442)

Formation:

Physical Address = 0x5A2 << 12 | 0x345
                 = 0x5A2000 | 0x345
                 = 0x5A2345

The resulting physical address 0x005A2345 points to byte 837 within frame 1442.

Physical Address Formation Examples
Virtual Addr	Page #	Frame #	Offset	Physical Addr	Calculation
0x00000500	0	0x100	0x500	0x00100500	(0x100 << 12) \| 0x500
0x00001234	1	0x055	0x234	0x00055234	(0x055 << 12) \| 0x234
0x00012345	18	0x5A2	0x345	0x005A2345	(0x5A2 << 12) \| 0x345
0x0002AFFF	42	0x999	0xFFF	0x00999FFF	(0x999 << 12) \| 0xFFF
0xFFFFFFFF	0xFFFFF	0xABCDE	0xFFF	0xABCDEFFF	(0xABCDE << 12) \| 0xFFF

No Overlap, No Gaps

Bit-Level Mechanics

Let's examine exactly how the bits fit together to form the physical address. Understanding this at the bit level reveals why the operation is so efficient.

physical_address_formation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>
#include <stdint.h>
 
/*
 * Physical Address Formation - Bit-Level Demonstration
 * 
 * This program shows exactly how frame number and offset
 * combine to form a physical address through bit operations.
 */
 
#define PAGE_SIZE       4096
#define OFFSET_BITS     12
#define OFFSET_MASK     0xFFF
 
void print_binary(uint64_t value, int total_bits, int split_point) {
    for (int i = total_bits - 1; i >= 0; i--) {
        printf("%d", (int)((value >> i) & 1));
        if (i == split_point) printf(" | ");
        else if (i > 0 && i % 4 == 0 && i != split_point) printf(" ");
    }
}
 
void form_physical_address(uint32_t page_number, uint32_t frame_number, 
                           uint32_t offset) {
    printf("\n╔══════════════════════════════════════════════════════════════════╗\n");
    printf("║              PHYSICAL ADDRESS FORMATION                           ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    // Original virtual address reconstruction
    uint64_t virtual_addr = ((uint64_t)page_number << OFFSET_BITS) | offset;
    printf("║ Virtual Address:  0x%08llX                                      ║\n",
           (unsigned long long)virtual_addr);
    printf("║ Binary: ");
    print_binary(virtual_addr, 32, 12);
    printf("  ║\n");
    printf("║         |--Page Number--| |---Offset---|                          ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    printf("║ Extracted Components:                                             ║\n");
    printf("║   Page Number: 0x%05X (decimal: %u)                              ║\n",
           page_number, page_number);
    printf("║   Offset:      0x%03X (decimal: %u)                               ║\n",
           offset, offset);
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    printf("║ After Page Table Lookup:                                          ║\n");
    printf("║   Frame Number: 0x%05X (decimal: %u)                             ║\n",
           frame_number, frame_number);
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    printf("║ Formation Steps:                                                  ║\n");
    printf("║                                                                   ║\n");
    
    // Step 1: Frame number before shift
    printf("║ 1. Frame Number (0x%05X):                                        ║\n",
           frame_number);
    printf("║    Binary: ");
    print_binary(frame_number, 20, -1);
    printf("                ║\n");
    printf("║                                                                   ║\n");
    
    // Step 2: Frame number shifted left
    uint64_t shifted_frame = (uint64_t)frame_number << OFFSET_BITS;
    printf("║ 2. Frame << 12 (0x%08llX):                                      ║\n",
           (unsigned long long)shifted_frame);
    printf("║    Binary: ");
    print_binary(shifted_frame, 32, 12);
    printf("  ║\n");
    printf("║            |--Frame Number-| |-Zeros for Offset-|                 ║\n");
    printf("║                                                                   ║\n");
    
    // Step 3: Offset
    printf("║ 3. Offset (0x%03X):                                               ║\n",
           offset);
    printf("║    Binary: ");
    print_binary(offset, 32, 12);
    printf("  ║\n");
    printf("║            |-All Zeros----| |---Offset Bits----|                  ║\n");
    printf("║                                                                   ║\n");
    
    // Step 4: OR them together
    uint64_t physical_addr = shifted_frame | offset;
    printf("║ 4. Physical = (Frame << 12) | Offset:                             ║\n");
    printf("║    Binary: ");
    print_binary(physical_addr, 32, 12);
    printf("  ║\n");
    printf("║            |--Frame Number-| |----Offset----|                     ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    printf("║ RESULT:                                                           ║\n");
    printf("║   Physical Address: 0x%08llX                                    ║\n",
           (unsigned long long)physical_addr);
    printf("║                                                                   ║\n");
    printf("║   Virtual 0x%08llX → Physical 0x%08llX                       ║\n",
           (unsigned long long)virtual_addr, (unsigned long long)physical_addr);
    printf("╚══════════════════════════════════════════════════════════════════╝\n");
}
 
void demonstrate_formation_equivalence() {
    printf("\n═══════════════════════════════════════════════════════════════\n");
    printf("     FORMATION METHOD EQUIVALENCE                                \n");
    printf("═══════════════════════════════════════════════════════════════\n\n");
    
    uint32_t frame = 0x5A2;
    uint32_t offset = 0x345;
    
    // Method 1: Shift and OR
    uint64_t method1 = ((uint64_t)frame << 12) | offset;
    
    // Method 2: Multiply and ADD
    uint64_t method2 = ((uint64_t)frame * PAGE_SIZE) + offset;
    
    // Method 3: Concatenation view
    // In hardware, this is just wiring - no operation
    
    printf("Frame Number: 0x%X (%u)\n", frame, frame);
    printf("Offset:       0x%X (%u)\n", offset, offset);
    printf("\n");
    printf("Method 1 (Shift + OR):      (0x%X << 12) | 0x%X = 0x%08llX\n",
           frame, offset, (unsigned long long)method1);
    printf("Method 2 (Multiply + Add):  (0x%X × 4096) + 0x%X = 0x%08llX\n",
           frame, offset, (unsigned long long)method2);
    printf("Method 3 (Concatenation):   0x%X || 0x%03X = 0x%08llX\n",
           frame, offset, (unsigned long long)method1);
    printf("\n");
    printf("All methods produce: 0x%08llX\n", (unsigned long long)method1);
    printf("Equivalence: %s\n", method1 == method2 ? "✓ Confirmed" : "✗ Error!");
    printf("\n");
    printf("Hardware uses Method 3: just wire the frame bits to high positions,\n");
    printf("wire the offset bits to low positions. Zero computation.\n");
}
 
int main() {
    printf("╔══════════════════════════════════════════════════════════════╗\n");
    printf("║      PHYSICAL ADDRESS FORMATION DEMONSTRATION                 ║\n");
    printf("╚══════════════════════════════════════════════════════════════╝\n");
    
    // Demonstrate several translations
    form_physical_address(0x12, 0x5A2, 0x345);   // Page 18 -> Frame 0x5A2
    form_physical_address(0x0, 0x100, 0x500);    // Page 0 -> Frame 0x100
    form_physical_address(0x1, 0x055, 0xFFF);    // Page 1, max offset
    
    demonstrate_formation_equivalence();
    
    return 0;
}

The Beauty of Bit Alignment

Hardware Implementation

Converting Mermaid diagram...

The Zero-Latency Property:

Because address formation is just wire routing:

Parallel with TLB Lookup: The offset bits are positioned on the physical address bus while the TLB lookup is in progress. The moment the frame number is available, formation is complete.
No Pipeline Stall: Unlike arithmetic operations that consume ALU cycles, wiring introduces only propagation delay—nanoseconds at most, far faster than a clock cycle.
Fixed Latency: Every address formation takes exactly the same time (essentially zero), regardless of the specific values involved.

What Hardware Does

•Routes frame number to high address lines
•Routes offset to low address lines
•Uses multiplexer to select frame source (TLB vs memory)
•Drives physical address bus with combined result

What Hardware Doesn't Do

•No arithmetic unit involvement
•No multiplication circuit
•No addition/OR circuit
•No clock cycles consumed for formation

The Address Formation Timing:

Clock Cycle  |  TLB Path           |  Offset Path
─────────────┼─────────────────────┼──────────────────
    1        |  TLB CAM compare    |  Offset positioned
    2        |  Frame # available  |  (waiting)
    2+       |  → Combined with offset → Physical address ready

The offset is ready from the moment the virtual address is presented. The formation completes in the same cycle that the frame number becomes available—no additional cycles needed.

Multiplexer Role

Variable Address and Page Sizes

Address Formation Parameters by Configuration
Configuration	Page Size	Offset Bits	Frame Bits	Physical Address
32-bit, 4KB	4 KB	12	20	32 bits total
32-bit, 4MB (PAE)	4 MB	22	10	32 bits total
x86-64, 4KB	4 KB	12	40	52 bits total
x86-64, 2MB	2 MB	21	31	52 bits total
x86-64, 1GB	1 GB	30	22	52 bits total

variable_page_sizes.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>
#include <stdint.h>
 
/*
 * Physical Address Formation with Variable Page Sizes
 * 
 * Shows how the formation process adapts to 4KB, 2MB, and 1GB
 * pages on x86-64 systems.
 */
 
typedef struct {
    const char* name;
    int offset_bits;
    uint64_t size;
    uint64_t offset_mask;
} PageConfig;
 
PageConfig page_configs[] = {
    {"4 KB", 12, 4096ULL, 0xFFFULL},
    {"2 MB", 21, 2097152ULL, 0x1FFFFFULL},
    {"1 GB", 30, 1073741824ULL, 0x3FFFFFFFULL},
};
 
void form_address_for_size(uint64_t virtual_addr, uint64_t frame_number, 
                            PageConfig* config) {
    uint64_t offset = virtual_addr & config->offset_mask;
    uint64_t physical_addr = (frame_number << config->offset_bits) | offset;
    
    printf("\n┌─ %s Pages ──────────────────────────────────────────────────┐\n",
           config->name);
    printf("│ Virtual Address:  0x%016llX                      │\n",
           (unsigned long long)virtual_addr);
    printf("│ Offset bits: %d, Frame bits: %d                              │\n",
           config->offset_bits, 52 - config->offset_bits);
    printf("├────────────────────────────────────────────────────────────────┤\n");
    printf("│ Extraction:                                                    │\n");
    printf("│   Offset = VA & 0x%llX = 0x%llX                      │\n",
           (unsigned long long)config->offset_mask, (unsigned long long)offset);
    printf("├────────────────────────────────────────────────────────────────┤\n");
    printf("│ Formation:                                                     │\n");
    printf("│   Frame Number: 0x%llX                                        │\n",
           (unsigned long long)frame_number);
    printf("│   Frame << %d: 0x%llX                              │\n",
           config->offset_bits, 
           (unsigned long long)(frame_number << config->offset_bits));
    printf("│   | Offset:    0x%llX                                         │\n",
           (unsigned long long)offset);
    printf("│   = Physical:  0x%016llX                      │\n",
           (unsigned long long)physical_addr);
    printf("├────────────────────────────────────────────────────────────────┤\n");
    printf("│ Frame covers: 0x%012llX - 0x%012llX              │\n",
           (unsigned long long)(frame_number << config->offset_bits),
           (unsigned long long)((frame_number << config->offset_bits) + 
                                 config->size - 1));
    printf("└────────────────────────────────────────────────────────────────┘\n");
}
 
void compare_page_sizes() {
    printf("\n═══════════════════════════════════════════════════════════════\n");
    printf("     PAGE SIZE COMPARISON: SAME VIRTUAL ADDRESS                  \n");
    printf("═══════════════════════════════════════════════════════════════\n");
    
    uint64_t vaddr = 0x00007FFFF7DD5000ULL;  // Typical library address
    
    // For 4KB pages
    uint64_t page_4kb = vaddr >> 12;
    uint64_t offset_4kb = vaddr & 0xFFF;
    
    // For 2MB pages  
    uint64_t page_2mb = vaddr >> 21;
    uint64_t offset_2mb = vaddr & 0x1FFFFF;
    
    // For 1GB pages
    uint64_t page_1gb = vaddr >> 30;
    uint64_t offset_1gb = vaddr & 0x3FFFFFFF;
    
    printf("\nVirtual Address: 0x%016llX\n\n", (unsigned long long)vaddr);
    
    printf("%-10s | %-15s | %-15s | %-15s\n",
           "Page Size", "Page Number", "Offset", "Entries Needed");
    printf("%-10s-+-%-15s-+-%-15s-+-%-15s\n",
           "----------", "---------------", "---------------", "---------------");
    
    printf("%-10s | 0x%-13llX | 0x%-13llX | many           \n",
           "4 KB", (unsigned long long)page_4kb, (unsigned long long)offset_4kb);
    printf("%-10s | 0x%-13llX | 0x%-13llX | fewer          \n",
           "2 MB", (unsigned long long)page_2mb, (unsigned long long)offset_2mb);
    printf("%-10s | 0x%-13llX | 0x%-13llX | very few       \n",
           "1 GB", (unsigned long long)page_1gb, (unsigned long long)offset_1gb);
    
    printf("\nObservation: Larger pages mean smaller page numbers,\n");
    printf("fewer page table entries, but also more potential\n");
    printf("internal fragmentation.\n");
}
 
int main() {
    printf("╔══════════════════════════════════════════════════════════════╗\n");
    printf("║     PHYSICAL ADDRESS FORMATION: VARIABLE PAGE SIZES           ║\n");
    printf("╚══════════════════════════════════════════════════════════════╝\n");
    
    uint64_t vaddr = 0x00000000012345678ULL;
    
    // Same address with different page sizes and frame mappings
    form_address_for_size(vaddr, 0x12345, &page_configs[0]);  // 4KB
    form_address_for_size(vaddr, 0x91A, &page_configs[1]);     // 2MB  
    form_address_for_size(vaddr, 0x2, &page_configs[2]);       // 1GB
    
    compare_page_sizes();
    
    return 0;
}

Huge Page Benefits

Physical Address Space Considerations

Physical Address Space Characteristics
Architecture	Physical Address Bits	Max Physical Memory	Notes
x86 (original)	24	16 MB	8086, 286
x86 (386+)	32	4 GB	Standard 32-bit
x86 PAE	36	64 GB	Physical Address Extension
x86-64 (early)	40	1 TB	First 64-bit AMD/Intel
x86-64 (current)	46-52	4-64 PB	Server/workstation chips
ARM64	48-52	256 TB - 4 PB	ARMv8 and later

Physical vs Virtual Address Width:

The physical address width is independent of the virtual address width:

Virtual: Typically 48-57 bits on x86-64 (256 TB - 128 PB per process)
Physical: Typically 40-52 bits system-wide (1 TB - 4 PB total hardware)

The page table entry stores enough bits for the physical frame number. The MMU forms physical addresses using whatever width the hardware supports.

Memory Holes and Reserved Regions:

Not all of the physical address space contains usable RAM:

•Legacy I/O Region (0-1MB): BIOS, VGA buffer, legacy device memory
•PCI MMIO: Memory-mapped I/O for devices (typically 4GB-8GB region)
•Reserved: ACPI tables, firmware, hardware-specific regions
•DRAM Gaps: Between RAMM sticks if not contiguous
•High Memory: Physical RAM above certain boundaries may need special handling

Physical Address ≠ RAM

Complete Translation Example

Let's trace a complete address translation from start to finish, showing every step from virtual address to physical address.

complete_translation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
 
/*
 * Complete Address Translation Walkthrough
 * 
 * This program traces every step of translating a virtual
 * address to a physical address, culminating in address formation.
 */
 
#define PAGE_SIZE   4096
#define OFFSET_BITS 12
 
// Simulated page table entry
typedef struct {
    uint32_t frame;
    bool present;
    bool writable;
    bool user;
    bool accessed;
    bool dirty;
} PTE;
 
// Simulated TLB entry
typedef struct {
    uint32_t page;
    uint32_t frame;
    bool valid;
} TLBEntry;
 
// Simple simulation state
PTE page_table[256];  // Simplified small table
TLBEntry tlb[8];      // Small TLB
 
void init_simulation() {
    // Set up a mapping: Page 18 -> Frame 0x5A2
    page_table[18].present = true;
    page_table[18].frame = 0x5A2;
    page_table[18].writable = true;
    page_table[18].user = true;
    page_table[18].accessed = false;
    page_table[18].dirty = false;
    
    // TLB starts empty
    for (int i = 0; i < 8; i++) {
        tlb[i].valid = false;
    }
}
 
void complete_translation(uint64_t virtual_addr) {
    printf("\n");
    printf("╔══════════════════════════════════════════════════════════════════╗\n");
    printf("║           COMPLETE ADDRESS TRANSLATION WALKTHROUGH               ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    printf("║ VIRTUAL ADDRESS: 0x%08llX                                      ║\n",
           (unsigned long long)virtual_addr);
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    
    // ═══════════════════════════════════════════════════════════════════════
    // STEP 1: DECOMPOSE VIRTUAL ADDRESS
    // ═══════════════════════════════════════════════════════════════════════
    
    uint32_t page_number = virtual_addr >> OFFSET_BITS;
    uint32_t offset = virtual_addr & (PAGE_SIZE - 1);
    
    printf("║                                                                  ║\n");
    printf("║ ┌──────────────────────────────────────────────────────────────┐ ║\n");
    printf("║ │ STEP 1: DECOMPOSE VIRTUAL ADDRESS                           │ ║\n");
    printf("║ └──────────────────────────────────────────────────────────────┘ ║\n");
    printf("║                                                                  ║\n");
    printf("║   Virtual Address: 0x%08llX                                    ║\n",
           (unsigned long long)virtual_addr);
    printf("║                                                                  ║\n");
    printf("║   Split at bit 12 (for 4KB pages):                               ║\n");
    printf("║     ┌─────────────────────┬────────────────┐                     ║\n");
    printf("║     │ Bits 31-12 (high)   │ Bits 11-0 (low)│                     ║\n");
    printf("║     │ Page Number         │ Offset         │                     ║\n");
    printf("║     │ 0x%05X (%u)       │ 0x%03X (%u)    │                     ║\n",
           page_number, page_number, offset, offset);
    printf("║     └─────────────────────┴────────────────┘                     ║\n");
    printf("║                                                                  ║\n");
    printf("║   Extraction:                                                    ║\n");
    printf("║     Page Number = 0x%08llX >> 12 = 0x%05X                      ║\n",
           (unsigned long long)virtual_addr, page_number);
    printf("║     Offset      = 0x%08llX & 0xFFF = 0x%03X                     ║\n",
           (unsigned long long)virtual_addr, offset);
    printf("║                                                                  ║\n");
    
    // ═══════════════════════════════════════════════════════════════════════
    // STEP 2: TLB LOOKUP
    // ═══════════════════════════════════════════════════════════════════════
    
    printf("║ ┌──────────────────────────────────────────────────────────────┐ ║\n");
    printf("║ │ STEP 2: TLB LOOKUP                                          │ ║\n");
    printf("║ └──────────────────────────────────────────────────────────────┘ ║\n");
    printf("║                                                                  ║\n");
    printf("║   Searching TLB for Page Number %u...                            ║\n",
           page_number);
    
    bool tlb_hit = false;
    uint32_t frame_number = 0;
    
    for (int i = 0; i < 8; i++) {
        if (tlb[i].valid && tlb[i].page == page_number) {
            tlb_hit = true;
            frame_number = tlb[i].frame;
            break;
        }
    }
    
    if (tlb_hit) {
        printf("║   TLB HIT! Frame = 0x%X                                        ║\n",
               frame_number);
    } else {
        printf("║   TLB MISS - Proceeding to page table walk                     ║\n");
        printf("║                                                                  ║\n");
        
        // ═══════════════════════════════════════════════════════════════════
        // STEP 3: PAGE TABLE WALK
        // ═══════════════════════════════════════════════════════════════════
        
        printf("║ ┌──────────────────────────────────────────────────────────────┐ ║\n");
        printf("║ │ STEP 3: PAGE TABLE WALK                                     │ ║\n");
        printf("║ └──────────────────────────────────────────────────────────────┘ ║\n");
        printf("║                                                                  ║\n");
        printf("║   Page Table Base Register (PTBR): 0xPTABE_BASE                  ║\n");
        printf("║   PTE Address = PTBR + (Page# × 4)                               ║\n");
        printf("║   PTE Address = PTBR + (%u × 4) = PTBR + %u                      ║\n",
               page_number, page_number * 4);
        printf("║                                                                  ║\n");
        printf("║   Reading PTE from memory...                                     ║\n");
        
        if (page_number < 256 && page_table[page_number].present) {
            frame_number = page_table[page_number].frame;
            printf("║   PTE found:                                                     ║\n");
            printf("║     Frame Number: 0x%X                                          ║\n",
                   frame_number);
            printf("║     Present: Yes                                                 ║\n");
            printf("║     Writable: %s                                                ║\n",
                   page_table[page_number].writable ? "Yes" : "No");
            printf("║     User: %s                                                    ║\n",
                   page_table[page_number].user ? "Yes" : "No");
            printf("║                                                                  ║\n");
            printf("║   Setting ACCESSED bit in PTE...                                 ║\n");
            page_table[page_number].accessed = true;
            printf("║   Inserting into TLB for future accesses...                      ║\n");
            
            // Insert into TLB
            tlb[0].valid = true;
            tlb[0].page = page_number;
            tlb[0].frame = frame_number;
        } else {
            printf("║   PAGE FAULT! Page not present in memory.                        ║\n");
            printf("║   OS would handle: load from disk, update PTE, retry.            ║\n");
            printf("╚══════════════════════════════════════════════════════════════════╝\n");
            return;
        }
    }
    
    printf("║                                                                  ║\n");
    
    // ═══════════════════════════════════════════════════════════════════════
    // STEP 4: FORM PHYSICAL ADDRESS
    // ═══════════════════════════════════════════════════════════════════════
    
    uint64_t physical_addr = ((uint64_t)frame_number << OFFSET_BITS) | offset;
    
    printf("║ ┌──────────────────────────────────────────────────────────────┐ ║\n");
    printf("║ │ STEP 4: FORM PHYSICAL ADDRESS                               │ ║\n");
    printf("║ └──────────────────────────────────────────────────────────────┘ ║\n");
    printf("║                                                                  ║\n");
    printf("║   Components:                                                    ║\n");
    printf("║     Frame Number: 0x%X                                          ║\n",
           frame_number);
    printf("║     Offset:       0x%03X                                         ║\n",
           offset);
    printf("║                                                                  ║\n");
    printf("║   Formation:                                                     ║\n");
    printf("║     Physical = (Frame << 12) | Offset                            ║\n");
    printf("║              = (0x%X << 12) | 0x%03X                            ║\n",
           frame_number, offset);
    printf("║              = 0x%X000 | 0x%03X                                 ║\n",
           frame_number, offset);
    printf("║              = 0x%08llX                                        ║\n",
           (unsigned long long)physical_addr);
    printf("║                                                                  ║\n");
    printf("║     ┌─────────────────────┬────────────────┐                     ║\n");
    printf("║     │ Frame Number        │ Offset         │                     ║\n");
    printf("║     │ 0x%05X             │ 0x%03X          │                     ║\n",
           frame_number, offset);
    printf("║     └─────────────────────┴────────────────┘                     ║\n");
    printf("║                                                                  ║\n");
    
    // ═══════════════════════════════════════════════════════════════════════
    // SUMMARY
    // ═══════════════════════════════════════════════════════════════════════
    
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    printf("║                         TRANSLATION COMPLETE                     ║\n");
    printf("╠══════════════════════════════════════════════════════════════════╣\n");
    printf("║                                                                  ║\n");
    printf("║   Virtual Address:  0x%08llX                                   ║\n",
           (unsigned long long)virtual_addr);
    printf("║                         ↓                                        ║\n");
    printf("║   Physical Address: 0x%08llX                                   ║\n",
           (unsigned long long)physical_addr);
    printf("║                                                                  ║\n");
    printf("║   The memory controller now accesses physical RAM at 0x%08llX  ║\n",
           (unsigned long long)physical_addr);
    printf("║                                                                  ║\n");
    printf("╚══════════════════════════════════════════════════════════════════╝\n");
}
 
int main() {
    init_simulation();
    
    // First access - TLB miss, page table walk
    printf("\n═══════════════════════════════════════════════════════════════\n");
    printf("     FIRST ACCESS (TLB MISS - FULL TRANSLATION)                  \n");
    printf("═══════════════════════════════════════════════════════════════\n");
    complete_translation(0x00012345);
    
    // Second access to same page - TLB hit
    printf("\n═══════════════════════════════════════════════════════════════\n");
    printf("     SECOND ACCESS (TLB HIT - FAST PATH)                         \n");
    printf("═══════════════════════════════════════════════════════════════\n");
    complete_translation(0x00012500);  // Same page, different offset
    
    return 0;
}

The Complete Picture

Summary: Physical Address Formation

Physical address formation is the final, simplest step in address translation—but its simplicity is key to paging's efficiency. The formed address directly accesses physical RAM or device memory.

Key Takeaways

•Formation Formula: Physical = (Frame << offset_bits) | Offset, or equivalently (Frame × PageSize) + Offset.
•Zero Computation: In hardware, formation is wiring—frame bits go to high positions, offset bits to low positions.
•Parallel with TLB: The offset is ready while TLB lookup proceeds; formation completes instantly when frame is available.
•Variable Sizes: The same process applies to all page sizes; only the split point (offset bit count) changes.
•Physical Address Space: The formed address must fall within valid physical memory or MMIO regions.
•Overall Pipeline: Decompose → TLB/Walk → Validate → Form Physical → Access Memory.

What's Next:

Page Complete

4 / 5