2.4k views
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. 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;

First of all I am assuming some of the facts because the question does not state them.

I assume array is stored in row major order and i is used for accessing row and j is used for accessing column. As page size is specified in number I am assuming it is going to hold 200 elements of the array.

Now it is saying memory has 3 frames and as said earlier 1 frame will be always occupied by the process so we have left with 2 frames.

Lets analyse second loop first as it will be easy:

(b)

Total number of elements will be =100*100=10000.
So 10000 contiguous memory will be allocated to array in the form R1, R2... where R stand for row. As the page size is 200,  at the start of loop 0-199 elements will come to main memory in one page after an initial page fault. After that when we reach 200 the second page fault occurs. Thus for every 200 element 1 page fault is occurring. So 10000/200 = 50 page faults

(a)

For 1st loop, I am drawing the image diagram.

You may guess that now blue element will be needed for which another page fault will occur and we will be accessing only 2 element per page fault. So number of page faults =10000/2=5000.

This concept can be extended if page size is given in kB and array element size is taken as 4B- just count number of array elements in one page. I think now you have understood the concept.

selected
+1
You got it perfect..
0
I didnt get it for the first loop...where is the diagram u mentioned? Please explain the first loop.
+2

i have posted a image i think u didn't get it .