Operating Systems Practice Question 8: Array Traversal Locality
Operating Systems · Test 1 · question 8 of 10
A single-threaded C program sums a 4096 x 4096 array of 4-byte integers, stored row by row in memory (row-major). The whole array fits comfortably in RAM and is already resident. Summing it with the loop for row { for col } takes 0.1 s; swapping the loops to for col { for row } makes the same sum take several times longer.
What is the most likely cause?
Show answer and explanation
Answer:
Caches (the CPU caches and the TLB that caches virtual-to-physical translations) work because of locality. With spatial locality, once one address is used, nearby addresses are likely next. In a row-major array, the row-first loop walks memory sequentially: one cache line serves several elements, and one TLB entry serves every element on a 4 KB page, so almost every access hits. Each row here is 4096 x 4 bytes = 16 KB, so the column-first loop moves 16 KB, four pages, between consecutive accesses. Nearly every access touches a different cache line and a different page, so it misses in the caches and very often in the TLB. Same work, much worse memory behaviour.
Option A is wrong: the stem says the array is already resident in RAM. Page faults would need pages to be missing from memory; TLB misses are not page faults. They are resolved by walking the page table in memory.
Option B is wrong: reading an array element is an ordinary load instruction in user mode. Loop order does not introduce system calls.
Option D is wrong: the program is single-threaded and the stem mentions no lock, so there is no contention to change.
Reference: OSTEP - Paging: Faster Translations (TLBs)