Consider the following two-dimensional array: int X[64][64]; Suppose that a syst
ID: 3624623 • Letter: C
Question
Consider the following two-dimensional array: int X[64][64]; Suppose that a system has 4 page frames and one frame is 128 words (an integer occuppies one word). Programs that manipulate tin- X array fit into exactly one page and always occupy page 0. The data is swapped in and out of the other 3 frames. the X array is stored in row-major order (i.e.. x(0] [1) follows X[O] [O] in memory). Which of the two code fragments shown below will generate the lowest number of page faults? Explain and compute the total number of page faults.Explanation / Answer
Fragment A:
for (int j=0; j < 64; j++)
for (int i=0; i<64; i++)
X[i][j] = 0;
The array accesses are in the order X[0][0], X[1][0], X[2][0], X[3][0],
and so on. Because the array is laid out in row-major order in
memory, and there are 64 words in each row, each memory page can
hold two rows worth of data. This means that X[0][0] and X[1][0] are
in the same page, and then X[2][0] and X[3][0] are in the same page
(that is different from the page holding X[0][0]), and so on. In reading
a single column (the inner for loop), it is necessary to access 32
different memory pages, and there will be a page fault for each of
them. Thus the total number of page faults is 64*32=2048.
Fragment B:
for (int i=0; i < 64; i++)
for (int j=0; j<64; j++)
X[i][j] = 0;
The array accesses are in the order X[0][0], X[0][1],….. Because of
the layout of data in memory, two complete rows are present in the
same page, and there will be one page fault for accessing every two
rows. Since there are 64 rows in total, the total number of page faults
is 64/2 = 32.