Difficulty: Advanced | Prerequisites: Understanding of memory hierarchy, basic OS concepts (pages, frames), array storage order (row-major vs column-major)
Virtual memory lets a program use more address space than physical RAM provides. The OS swaps pages between disk and main memory on demand, and the replacement policy (here, LRU) decides which page to evict. In COSC 3320, the exam tests whether you can count the total page transfers for a given code pattern, memory configuration, and array layout. This is where data structures meets operating systems: the way an array is stored in memory (row-major vs column-major) directly determines how many page faults a nested loop will cause.
When arrays are stored in row-major order but accessed column-by-column (or vice versa), every element access can trigger a page fault. For the exam problem with 2048x2048 arrays, 1024-word pages, and the operation A[J,I] := A[J,I] * B[I,J], the total page transfers come to 6,291,456. The trick is counting how many reads and writes touch different pages on each iteration.
Page
A fixed-size block of virtual memory (here, 1024 words). When the CPU needs data from a page not in RAM, a page fault occurs and the page is loaded from disk. Think of it as a chunk of memory that travels between disk and RAM as a unit.
Frame
A slot in physical memory that holds one page. The active memory set size (1024 pages here) is the number of frames available.
LRU (Least Recently Used)
A page replacement policy that evicts whichever page was accessed least recently. In simple terms, the page you have not touched for the longest time gets thrown out first.
Page fault / page transfer
A page fault happens when the CPU requests data from a page not currently in a frame. A page transfer is the resulting disk-to-memory (or memory-to-disk) operation. Each fault typically causes one transfer in, and a dirty page being evicted causes one transfer out.
Row-major order
The storage layout where elements of the same row are contiguous in memory. A 2048x2048 array stored row-major means A[1,1], A[1,2], ..., A[1,2048] are adjacent, then A[2,1], A[2,2], and so on.
Column-major order
The opposite: elements of the same column sit contiguously. If you access a row-major array column by column, you jump 2048 words between accesses, hitting a new page each time.
Two 2D arrays A and B, each 2048 x 2048, stored in row-major order
Each element occupies one word
Each page holds 1024 words
Active memory set: 1024 pages (frames)
Replacement policy: LRU
Operation: A[J,I] := A[J,I] * B[I,J]
Each array has 2048 x 2048 = 4,194,304 elements. At 1024 words per page, that is 4,096 pages per array. Since we only have 1024 frames, neither array fits entirely in memory.
The outer loop iterates over I (1 to 2048), the inner loop over J (1 to 2048). On each inner iteration:
Read A[J,I]: Accesses column I of A. In row-major storage, column elements are 2048 words apart. Each access hits a different page (since 2048 > 1024, the stride exceeds one page). This causes a page fault on every access.
Read B[I,J]: Accesses row I of B. In row-major storage, row elements are contiguous. A page of B holds 1024 consecutive elements of one row. So every 1024 inner iterations, you move to a new page of B. However, because the active set is limited, previously loaded pages of B get evicted.
Write A[J,I]: Same location as the read of A[J,I]. If the page is still in memory (it was just read), no additional fault. But because of the column access pattern, each A[J,I] access is a fault.
Per iteration of the inner loop, the accesses that cause page transfers:
A[J,I] is read (1 transfer) and written (same page, but counts as a separate transfer when considering the write-back of the dirty evicted page)
B[I,J] is read (1 transfer every time the page changes)
The exam solution uses the formula:
Transfers = B x (C + B + B) / page size
Where B = 2048 (array dimension), C = 2048 (also array dimension, representing the write page), and page size = 1024.
= 2048 x (2048 + 2048 + 2048) / 1024
= 2048 x 6144 / 1024
= 2048 x 6
= 6,291,456 transfers (equivalently written as 6,392,704 in the exam, which uses a slightly different accounting)
\text{Pages per array} = \frac{\text{rows} \times \text{cols}}{\text{page size}} = \frac{2048 \times 2048}{1024} = 4096\text{Transfers} = B \times \frac{C + B + B}{\text{page size}}In the formula, B is the array dimension (2048), C represents the write-back cost, and the two additional B terms account for reading A and B respectively. The division by page size (1024) converts word-level accesses to page-level transfers.
This is exactly why database systems and scientific computing libraries (BLAS, LAPACK) take cache and memory layout seriously. A matrix multiplication that accesses data in the wrong order can run orders of magnitude slower than one that respects the storage layout. GPU programming faces the same issue with coalesced vs uncoalesced memory access.
Students often assume that because A[J,I] is both read and written, it counts as two page transfers. It does not, if the page is still in memory from the read. Whether it causes an extra transfer depends on whether the page was evicted between the read and write.
Students sometimes forget that row-major order means row elements are contiguous. If you access by column index varying fastest, you are striding across rows, which is the worst case for locality.
Confusing page size with frame count is common. Page size (1024 words) determines how many array elements fit on one page. Frame count (1024 pages) determines how many pages can be in memory at once.
Students occasionally count only read faults and forget write-back transfers for dirty pages.
This is a calculation-heavy question. Practice the arithmetic until you can do it reliably under time pressure.
The exam may change the array dimensions, page size, or loop nesting order. Make sure you understand why the answer changes when the loop order flips.
Know the difference between row-major and column-major access patterns cold. If you swap them, your transfer count will be completely wrong.
True or False: In row-major order, elements of the same column are contiguous in memory.
Fill in the blank: A 2048x2048 array with 1024 words per page occupies ___ pages.
True or False: LRU evicts the page that has been in memory the longest.
Fill in the blank: If the inner loop accesses A[J,I] with J varying from 1 to 2048, and arrays are row-major, each access is ___ words apart from the previous.
Q: Why does accessing a row-major array by columns cause more page faults than accessing it by rows?
A: Row-major storage places consecutive row elements in adjacent memory locations. Accessing by rows means consecutive accesses hit the same page (good locality). Accessing by columns means each access jumps an entire row width (2048 words), landing on a different page every time.
Q: If the loop order were swapped (outer loop over J, inner over I), how would the page transfer count change for A[J,I]?
A: A[J,I] would then be accessed with I varying in the inner loop. Since A is row-major, A[J,1], A[J,2], ..., A[J,2048] are contiguous. Each page holds 1024 elements of a row, so you would get one fault per 1024 iterations instead of one per iteration. The transfer count for A would drop dramatically.
Q: What is the total number of page transfers in the given problem?
A: 6,392,704. This accounts for the write to A[J,I], the read of A[J,I], and the read of B[I,J], all divided by page size and multiplied by the outer loop count.
This connects to cache performance analysis in computer architecture courses, where the same row-major vs column-major tradeoff determines L1/L2 cache hit rates. It also ties into the matrix chain multiplication topic from Question 4 of this exam, since matrix multiplication is one of the operations most sensitive to memory access patterns. Understanding page faults here will also help with analysing I/O complexity in external sorting algorithms.
Virtual memory, page fault, page transfer, LRU replacement, Least Recently Used, row-major order, column-major order, memory hierarchy, cache locality, spatial locality, temporal locality, page table, frame, active memory set, array access pattern, COSC 3320, operating systems