Difficulty: Intermediate | Prerequisites: Understanding of arrays, basic knowledge of how computer memory works.
Modern computers use virtual memory to let programs work with more data than fits in physical RAM. The operating system divides memory into fixed-size pages, loading them in and out of main memory as needed. When the exam gives you a loop that accesses large arrays, the question is: how many times does the system need to swap pages between disk and memory? This depends on the page size, the total memory capacity, the size of the data, and the replacement strategy. These concepts sit at the boundary between programming and computer architecture.
Memory is divided into pages of fixed size. When a program accesses data not currently in memory, a page fault triggers a transfer from disk. LRU (Least Recently Used) evicts the page that has gone longest without being accessed. The exam asks you to calculate total page transfers for loops that access multiple large arrays, given specific page sizes and memory capacities.
Page
A fixed-size block of memory. Both main memory (RAM) and virtual memory on disk are divided into pages of equal size. Think of it as a "slot" that holds a chunk of your data.
Page size
The number of words (or bytes) that fit in one page. In the COE 301 exam scenario, each page holds 1,024 words.
Page fault
An event that occurs when the program tries to access data on a page that is not currently in main memory. The system must load (transfer) that page from disk before the program can continue.
Page transfer
The act of moving a page between disk and main memory. Each page fault causes at least one transfer in. If memory is full, the replaced page may also need to be written back.
Active memory set (main memory capacity)
The total number of pages that can reside in main memory at the same time. In the exam scenario, this is 1,024 pages, which means main memory holds 1,024 × 1,024 = 1,048,576 words.
LRU (Least Recently Used)
A page-replacement strategy that, when memory is full and a new page must be loaded, evicts the page whose most recent access was the longest ago. In simple terms, it kicks out whatever has not been touched for the longest time.
Row-major order
The standard way arrays are laid out in memory in languages like Java and C. Elements of the same row are stored in consecutive memory locations. For a 2D array A[1:2048, 1:2048], the entire first row (A[1][1] through A[1][2048]) comes first in memory, then the entire second row, and so on.
Thrashing
A situation where the system spends most of its time swapping pages in and out of memory rather than doing useful work. This happens when the working set of pages exceeds the memory capacity.
Sequential access
Accessing array elements in the order they are stored in memory (row by row for row-major). This is cache- and page-friendly because consecutive accesses tend to hit the same page.
The recurring setup in COE 301 memory questions uses these parameters:
Page size: 1,024 words
Main memory capacity: 1,024 pages (so 1,048,576 words total)
Replacement strategy: LRU
Three 2D arrays (A, B, C), each of size [1:2048, 1:2048]
Each array element occupies one word
Arrays are mapped into memory in order (A first, then B, then C)
The loop under examination:
for (int i = 1; i <= 2048; i++)
for (int j = 1; j <= 2048; j++)
A[i][j] = B[i][j] + C[i][j];Each array has 2048 × 2048 = 4,194,304 elements (words). With a page size of 1,024 words, each array occupies 4,194,304 / 1,024 = 4,096 pages.
All three arrays together require 3 × 4,096 = 12,288 pages. Main memory can hold only 1,024 pages, so the arrays do not fit in memory simultaneously.
Each row of an array has 2,048 elements, which spans 2,048 / 1,024 = 2 pages.
For each iteration of the outer loop (one value of i), the inner loop sweeps through all 2,048 columns. In each inner-loop iteration, the code accesses three arrays: B[i][j], C[i][j], and A[i][j].
Because the arrays are stored in row-major order, elements within the same row are contiguous in memory. When j = 1, the page containing A[i][1] through A[i][1024] is loaded. That page serves all accesses for j = 1 through j = 1024 without another fault. When j = 1025, a new page is needed.
So each row of each array causes 2 page faults (one per 1,024-element half of the row). Three arrays, each with 2,048 rows, each row causing 2 faults:
Per row: 2 pages × 3 arrays = 6 page transfers
Total: 2,048 rows × 6 = 12,288 page transfers (if no eviction forces re-loading)
Whether this stays at 12,288 or climbs higher depends on whether the pages from one array's row get evicted before the inner loop finishes. With 1,024 pages of memory and only 6 pages active at a time per row iteration (2 pages each for A, B, C of that row), the pages fit comfortably and are not evicted. So the clean total is 12,288 page transfers.
The model answer also mentions a worst-case thrashing figure of 8,392,704 transfers if column-major access or pathological mapping forced every single element access to fault. The exam may ask you to justify which scenario applies.
Three factors determine the number of transfers:
Page size: larger pages mean fewer faults per row
Array size: more data means more pages to bring in
Replacement strategy (LRU): determines which pages get evicted when memory is full
CPU clock speed does not affect the number of page transfers. It affects how fast each transfer completes, but not how many occur.
Students often think CPU speed affects the number of page transfers. It does not. Speed determines how long each transfer takes, but the count is determined by data size, page size, and replacement policy.
Students sometimes assume that accessing B[i][j] and C[i][j] in the same iteration always faults twice. If B and C pages from the same row are already in memory (loaded earlier in the same inner-loop sweep), they do not fault again.
Students confuse "number of pages an array spans" with "number of page transfers." An array may span 4,096 pages, but if memory is large enough, those pages stay resident after their first load.
⚠️ The exam repeatedly uses the same memory scenario (1,024-word pages, 1,024-page memory, 2048×2048 arrays). Know the setup cold.
⚠️ You will be asked to calculate how many pages a 1D or 2D array spans. A 1D array of 2,048 elements spans 2,048 / 1,024 = 2 pages.
⚠️ LRU is the only replacement strategy tested. Know its definition: the page not accessed for the longest time is removed.
⚠️ The exam may ask which factors influence page transfers. The correct set is page size, array size, and replacement strategy. CPU clock speed is the distractor.
Fill in the blank: A 1D array of 2,048 elements stored in 1,024-word pages spans ____ pages. (2)
True or false: LRU removes the first page that was loaded. (False. LRU removes the page not accessed for the longest time, which is different from FIFO.)
True or false: CPU clock speed affects the number of page faults. (False.)
Fill in the blank: Each row of a 2048-column array occupies ____ pages when the page size is 1,024 words. (2)
Q: If an array B has 2,048 elements and is stored in memory with 1,024-word pages, how many pages does B span?
A: 2,048 / 1,024 = 2 pages.
Q: Which LRU behaviour occurs when the active memory set is full?
A: The page not accessed for the longest time is removed.
Q: Identify the factors that influence the number of page transfers in the memory access problem.
A: Page size, array size, and replacement strategy (LRU). CPU clock speed does not affect the count.
Q: In the loop A[i][j] = B[i][j] + C[i][j], why is row-major access pattern important for page faults?
A: Row-major order means consecutive j values within the same row hit the same page. This minimises faults because one page load serves 1,024 consecutive element accesses.
Page replacement connects to operating systems concepts you may see in later courses. The idea of locality of reference (why sequential access is fast) also explains why cache-friendly code runs faster, a theme in computer architecture. Understanding how arrays map to memory pages helps you write more efficient loops in any language.
virtual memory, paging, page fault, page transfer, page replacement, LRU, least recently used, FIFO, active memory set, main memory, RAM, disk, page size, row-major order, column-major order, 2D array, array mapping, thrashing, sequential access, cache, locality of reference, COE 301, memory access, University of Texas