Dr. Soumadip Biswas
Computer Science & Engineering | Student | Researcher | Educator

The Illusion of Contiguous Memory: Arrays to Page Faults

📅 Aug 30, 2026 ★★★★☆ 📚 Operating Systems, Computer Architecture
#Memory Management #Virtual Memory #Page Faults #TLB #Cache

Scenario: The 2D Array Matrix Traversal

A junior engineer is writing a C program for image processing. They allocate a massive 2D array of integers to represent pixel data and write a nested loop to process the matrix column-by-column rather than row-by-row.

Q:The engineer notices the language guarantees $O(1)$ access time for arrays. Does this mean the 1GB array they just allocated is occupying a single, contiguous block of physical RAM on the motherboard? Reveal â–¾
No. From the process’s perspective, the memory appears perfectly contiguous. However, this is an illusion created by the OS called Virtual Memory. In reality, the physical RAM is broken up into small blocks called “frames” (typically 4KB). The contiguous virtual memory pages are mapped to scattered, fragmented physical frames across the actual RAM chips.
Q:If the physical memory is scattered, how does the CPU actually find the correct physical frame when the program requests `array[x][y]`? Reveal â–¾
Every time the CPU requests a memory address, the Memory Management Unit (MMU)—a hardware component—intercepts it. The MMU looks up the virtual address in a data structure maintained by the Operating System called the Page Table, which contains the exact mapping from the virtual page to the physical frame.
Q:The Page Table is stored in RAM. Doesn't that mean every single array access requires two memory reads—one to check the Page Table, and one to read the actual data? Wouldn't that cut execution speed in half? Reveal ▾
Theoretically, yes. To prevent this massive performance penalty, the CPU utilizes a specialized, ultra-fast hardware cache located directly inside the MMU called the Translation Lookaside Buffer (TLB). The TLB caches the most recently used virtual-to-physical address translations. If the mapping is in the TLB (a TLB hit), the CPU skips reading the Page Table entirely.
Q:Back to the engineer's code: they are processing the 2D array column-by-column. The program's execution time is suddenly 100x slower than processing it row-by-row. Why? Reveal â–¾

In C, 2D arrays are stored in row-major order in memory. When iterating row-by-row, the CPU accesses memory sequentially, taking advantage of spatial locality. The TLB and the L1/L2 data caches efficiently pre-fetch the next elements.

By iterating column-by-column, the engineer forces the CPU to jump across massive memory strides (skipping entire rows). This continuously requests data outside the currently cached pages, causing constant Cache misses and TLB misses. The CPU spends more time fetching page table entries and loading cache lines than it does doing actual math. This is known as TLB thrashing.

Q:What happens if the system is low on RAM, and the column-by-column traversal asks for a page that the OS has temporarily swapped out to the hard drive? Reveal â–¾
The MMU fails to find the physical mapping and triggers a hardware interrupt called a Page Fault. The CPU traps into the OS kernel. The OS must then freeze the program, select an existing page in RAM to evict, write it to the disk (if modified), read the required page from the hard drive into RAM, update the Page Table, and finally resume the program. Because disk I/O is magnitudes slower than RAM access, frequent page faults lead to system-wide lockups, a state called Thrashing.

Variations & Real-World Impact

  • Database Engineering: Modern databases (like PostgreSQL) allow administrators to configure “Huge Pages” (e.g., 2MB or 1GB pages instead of 4KB). This drastically reduces the size of the Page Table and practically eliminates TLB misses for massive, memory-intensive data operations.
  • Security (Rowhammer): The physical layout of RAM frames led to a vulnerability where rapidly accessing the same memory rows over and over (similar to a malicious cache-miss loop) can cause electrical charge to leak into adjacent physical memory cells, flipping bits in memory belonging to the kernel or other users.

Further Exploration

Discussion & Comments