Calculating number of page faults for 2-d array

Question

I am trying to study for an exam..and I found this example but can't understand how they got the answer. Can anyone explain it please?

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. A small process that manipulates the matrix resides in the page 0 (location 0 to 199). Thus every instruction fetch will be from page 0. For two page frames, how many page faults are generated by the following array-initialization loops, using LRU replacement and assuming that the first page frame contains the process and the other is 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;

The correct answer given is : a: 100 x 50 = 5000 b: 50

I somewhat understand the first part. There are total of 50 pages. (10000/200=50) and every time j changes, a page fault occurs..so a total of 100 page faults..but why is that multiplied by 50? and why is the second one 50?

Thanks!!

Answer 1

Suppose your systems allocated Two Frames for your process such that 200 * sizeof(int) of matrix can be keep in memory at a time. And allocation for matrix happens in Row Major Order.

In first loop A:

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

loop access memory cells for matrix column-wise like:

A[0][0], A[2][0], A[3][0], ...A[0][2], A[0][3], A[0][4], ......
  ^        ^        ^   
      row changes               

At each iteration Row changes and allocation is in row major and each row takes one page. so code A will causes page fault for each alternative A[i][j] access so total number of page faults are = 100 * 100 / 2) = 5000.

Where as second code B:

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

loop access memory cells for matrix row-wise on each iteration, like:

A[0][0], A[0][5], A[0][6],...,A[1][0], A[1][7], A[1][8],...,A[2][0], A[2][9],
     ^        ^        ^  
  column changes, row are same 

Access row wise (columns changes at read read row changes only after 100 read), One row loaded at time so page fault happens when row changes (for outer loop) and for each alternative row access a page fault happens so number of page faults = 100/2 = 50.

we can understand it another ways like:
In row major, Number of times row index changes we need new page to access because number of pages are small it page fault on each alternative index change in first A loop row index changes 100*100 times where as in B loop row index changes 100 times so page fault ration in both A/B = 100*100/100 = 100, and if number of page faults happens in A = 50,00 then in B number of page faults = 50,00/100 = 50.

Similarly you can calculate number of page-faults for Column-major order and because matrix has equal numbers of rows and cols result will be same.

The similar example is given in my book:
Download a pdf: operating system book Galvin Read chapter 9: Virtual Memory Section: 9.9.5 Program Structure.