Page fault count within two arrays?

Question

Homework:

Consider the two-dimensional array A:

      int A[][] = new int[200][200];

where A[0][0] is at location 500 in a paged memory system with pages of size 500 (a little unrealistic -- not 512). A small process that manipulates the matrix resides in page 0 (locations 0 to 499). Thus, every instruction fetch will be from an instruction currently stored in page 0.

Assuming there are only five page frames, including page 0, how many page faults are generated by the following array-initialization loops, using LRU replacement and assuming that page frame 0 contains the process and the other four are initially empty?

A)for (int j = 0; j < 200; j++) for (int i = 0; i < 200; i++) A[i][j] = 0;

B)for (int i = 0; i < 200; i++) for (int j = 0; j < 200; j++) A[i][j] = 0;

Question:

Where do I begin to figure this out? I have went through my text but haven't found much of it to be useful. I threw some numbers around and I found:

40,000 = total number of array items

80 (40k/500) = total number of pages

A) 20,000 (80*250) because every other loop causes a page fault?

B) 80 (One for each page, 40,000/500 = 80)?

Am I on the right track? Any advice? Hints?

Answer 1

Think about the order that the initialization happens in loop A vs loop B, and how a multi-dimentional array is laid out in memory. One of them will access memory addresses in-order, the other will jump around. After 200 assignments, you'll be looking at A[199][0] in one case, and A[0][199] in the other. How many pages have you touched?