Deep Dive: Memory, Virtual Memory, & Executable Loading

Module 1

Foundations of Memory Management

Understanding physical memory constraints, virtual memory abstraction, fixed-size chunks, and reference patterns.

Paging Mechanism

Paging provides a non-contiguous virtual address space abstraction. Physical RAM is divided into fixed-size physical frames, and a process's virtual memory is divided into virtual pages of identical size.

Eliminates external fragmentation entirely
Enables lazy loading and memory protection
Simplifies physical memory allocation

VPN, PFN & Offsets

A Virtual Address is split into two components: the Virtual Page Number (VPN) and the Offset. Page alignment ensures lower bits directly specify position within the page.

Offset Bits = log₂(Page Size)
VPN = Virtual Address >> Offset Bits
Offset = Virtual Address & (Page Size - 1)

Locality of Reference

Programs do not access memory uniformly. Memory access patterns display high predictability across time and spatial proximity.

Temporal Locality:

Recently referenced items are likely to be accessed again soon (e.g., loop variables, stack frame).

Spatial Locality:

Items with nearby addresses are likely to be accessed together (e.g., array traversals, sequential instructions).

Virtual Memory to Physical Frame Mapping Abstraction

When a program accesses memory address 0x3A4F with a 4KB page size (12-bit offset = 4096 bytes):

The lower 12 bits (0xA4F) represent the Offset within the page.
The remaining upper bits (0x3) form the Virtual Page Number (VPN).
The Memory Management Unit (MMU) translates VPN 0x3 into a physical frame number (e.g., PFN 0x12).
The final physical memory location is constructed by appending the offset: 0x12A4F.

32-Bit Address Breakdown (4KB Pages)

VPN (Bits 31–12) [20 Bits]

Offset (Bits 11–0) [12 Bits]

Translate via MMU / Page Table ↓ Direct Copy ↓

PFN (Physical Frame Number)

Offset (Unchanged)

Module 2

Address Translation & Page Tables

Page Table Entries (PTE), hierarchical multi-level tables, and MMU hardware caching with TLB.

Page Table Entries (PTE)

Each entry in a page table contains control bits that govern memory security, caching, and state:

P / Valid Bit 1 if frame is in physical RAM

R/W & U/S Bit Read/Write & User/Supervisor privilege

Dirty (D) Bit 1 if page was written to (needs swap sync)

Accessed (A) Bit 1 if page was read/written (for LRU)

Multilevel Page Tables

A flat 64-bit page table would require terabytes of memory just to store metadata. Multi-level tables solve this by creating a tree structure where empty virtual memory regions do not allocate child tables.

4-Level x86-64 Paging:

PML4 → PDPT → Page Directory → Page Table

Saves massive memory for sparse address spaces!

Translation Lookaside Buffer

The TLB is a high-speed associative hardware cache in the MMU. It stores recently translated VPN → PFN mappings to bypass memory lookups.

EAT = Hit_Rate × (TLB_latency + Memory_latency) + (1 - Hit_Rate) × (TLB_latency + 2 × Memory_latency)

Typical TLB hit rate: 99%+ in modern workloads.

Full Hardware Address Translation Pipeline

1. CPU Virtual Address

[VPN] | [Offset]

2. Check TLB

Hit: Return PFN (1-2 cycles)

Miss: Traverses Page Directory

3. Walk Page Table

Fetch PTE from Physical RAM

4. Physical RAM Access

[PFN] + [Offset]

Module 3

Demand Paging & Page Fault Management

Lazy memory loading, step-by-step hardware/kernel page fault execution lifecycle, and secondary swap space.

Demand Paging Strategy

Pages are brought into physical RAM only when executed or accessed by the running program ("lazy loading"). This reduces program startup times and memory footprint.

Key Benefit: Allows system to execute programs larger than total physical RAM size!

Page Fault Exception (#PF)

Occurs when the CPU attempts to access a virtual address whose PTE has the Present Bit = 0. This triggers a hardware interrupt trap to the OS kernel.

Invalid Access vs Valid Fault: Segmentation fault (SIGSEGV) occurs if access permissions (VMA) are violated.

Swap Space Mechanics

Swap space is a designated block device on SSD/HDD used as backing store for evicted anonymous pages (heap, stack, data).

File-Backed vs Anonymous: Text sections are backed by binary files on disk; Heap/Stack pages use Swap Space.

Step-by-Step Kernel Page Fault Handling Pipeline

Step 1

MMU Trap

CPU references virtual page with Present=0. Control traps to kernel page fault handler.

Step 2

VMA Verification

Kernel checks Virtual Memory Area struct. If illegal address/permissions, throw SIGSEGV.

Step 3

Frame Allocation

Kernel allocates free physical frame. If RAM is full, invokes eviction algorithm (LRU/Clock) to swap out a victim page.

Step 4

Swap Read & Resume

Kernel reads missing page from disk into frame, updates PTE (Present=1), flushes TLB, and restarts trapped instruction.

Module 4

Memory Eviction & Working Set Dynamics

Least Recently Used (LRU) eviction strategies, Clock algorithm approximation, and Working Set model thrashing prevention.

LRU & Clock Replacement Algorithm

Pure Least Recently Used (LRU) requires hardware timestamps or linked-list updates on every memory access, which is prohibitively expensive.

Clock (Second-Chance) Algorithm:

Uses a 1-bit reference flag in hardware. A circular pointer sweeps frames: if reference bit is 1, set it to 0 and skip (second chance); if bit is 0, evict frame.

Working Set Model & Thrashing

The Working Set W(t, Δ) is the set of pages referenced by a process in the most recent time window Δ.

Thrashing Condition:

If ∑ |W_i| > Total Physical Memory RAM

When total working set exceeds RAM, the OS spends 100% of CPU time paging to/from disk rather than executing real work.

Module 5

Memory Sharing & Optimizations

Copy-On-Write (COW), `mmap()` syscall, inter-process shared memory, and shared read-only code sections.

Copy-On-Write (COW)

Optimizes fork() system calls. Instead of duplicating physical memory, the child process shares parent page frames marked Read-Only.

Upon a write attempt, a write-fault traps to OS kernel, which allocates a new frame, copies the 4KB page, and marks it Read-Write for the writer.

mmap() System Call

Maps files or block device objects directly into a process's virtual memory space.

Bypasses user-space buffer copying (`read`/`write` overhead). Also used for shared memory Inter-Process Communication (IPC) and Memory-Mapped I/O (MMIO).

Shared Code Sections

Read-only executable text sections (.text) of shared libraries (e.g. libc.so) are mapped to the same physical frames across all running processes.

Saves gigabytes of system RAM when hundreds of processes run simultaneously.

Module 6

Linking, Loading & Executable Mechanics

Program lifecycle from source binary, relocation, symbol resolution, Position Independent Code (PIC), GOT, PLT, and relative jumps.

Core Linking & Loading Pipeline

(a) Loading

Kernel loader (execve) reads ELF binary headers, allocates Virtual Memory Areas (`.text`, `.data`, `.bss`), and maps initial pages.

(b) Relocation

Modifying symbol references inside code/data sections to match their actual assigned runtime virtual addresses.

(c) Symbol Resolution

Associating each global symbol reference (e.g. printf) with its precise definition in object files or dynamic shared objects (.so).

Position Independent Code (PIC)

PIC allows shared library code to be loaded at any arbitrary memory address without requiring text relocation (which would break page sharing across processes).

GOT (Global Offset Table): Contains absolute physical/virtual addresses of global variables and functions. Placed in writable .got section.

PLT (Procedure Linkage Table): Code stubs that look up addresses in the GOT on function calls. Enables Lazy Dynamic Binding.

PC-Relative Jumps & Addressing

In x86-64, PC-relative addressing (RIP-relative) encodes target instruction operands as relative offsets from the current Instruction Pointer (RIP).

// Absolute jump (requires relocation if moved):

JMP 0x7FFF0040

// RIP-Relative jump (works anywhere in VM space):

JMP RIP + 0x28

Interactive Architecture Lab

Interactive Systems Simulators

Live hands-on simulators for address translation, LRU eviction, COW fork execution, and executable loading.

Simulator 1: Address Translation & TLB Lookup

16-Bit Memory Model

Virtual Address (Hex 0x0000 - 0xFFFF)

Page Size

VPN

0x3

Offset

0xA4F

TLB Status

HIT

Physical Address

0x12A4F

Simulator 2: Page Replacement Visualizer (LRU vs Clock)

Algorithm:

Reference String (Comma-separated)

Physical Frame Slots

Step: 0 / 12

Page Faults: 0

Hit Rate: 0%

Press "Step" to advance page reference stream execution.

Simulator 3: Copy-On-Write (COW) Fork Simulation

Kernel Virtual Memory Handler

Trigger Process Actions:

Parent Process (PID 1001) Active

Page 0: Frame 1 R/W

Page 1: Frame 2 R/W

Child Process (PID 1002) Not Created

Page 0: Unallocated -

Page 1: Unallocated -

Ready. Click "Execute fork()" to start Copy-On-Write simulation.

Simulator 4: Executable Linking & Loading Pipeline

ELF Binary Lifecycle