Consider the two-dimensional array A: int A[][] = new int[100][100]; where A[0][

Question

Consider the two-dimensional array A:

int A[][] = new int[100][100];

where A[0][0] is at location 200 in a paged memory system with pages of size 200. In addition,

in this system arrays are stored in memory in the following order:

A[0][0], A[1][0], ...

A small process that manipulates the matrix resides in page 0 (locations 0 to 199). Thus, every instruction fetch will be from page 0.

For three page frames, how many page faults are generated by the following array-initialization loops, using LRU replacement and assuming that page frame 1 contains the process and the other two are initially empty?

A) for(int j=0; j<100; j++)

for(int i=0; i<100; i++)

A[i][j]=0;

B) for(int i=0; i<100; i++)

for(int j=0; j<100; j++)

A[i][j]=0;

Explanation / Answer

An integer (int) is of 2 bytes and each page has length 200 bytes. So each row of array A (100 int) fits exactly in a page.

(a) For the first array-initialization loop, one column is processed at a time, so it generates a page fault at every inner loop iteration, with a total of 100*100=10,000 page faults.

(b)  For the second array-initialization loop, one row is processed at a time, and so it generates a page fault at every outer loop iteration, with a total of 100 page faults.

Hence second  array-initialization loop,has better spatial locality.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.