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.

Answer 2

The key here is to see how all the array accesses look when reading from linear memory addresses. Row-major (C) order also has to be assumed for the answer to make sense. The problem also left out units, which we'll assume are bytes (so A has to be held in 1-byte types).

char *B = &(A[0][0]); (memory address 200)

Accessing A[i][j] is now equivalent to B[i*100 + j] or *(200 + i*100+j) (row-major order). Two pages can fit in memory. One is taken by the program (bytes 0-199 - also the C convention). The other is for accessing A, which spans 100*100 bytes / (200 bytes / page) = 50 pages.

Since 0-199 is always in memory, the other page will address n*200 to (n+1)*200-1, where n is some integer -- corresponding to 2 rows of A at a time.

Finally, at a page fault, the least recently used (LRU) algorithm would have just read an instruction from page 0-199, so would always discard the page holding the old part of A to read the new part of A (when n changes, every 2 rows).

So you can easily see what's happening by reading down rows of a 100x100 matrix -- every 2 rows swaps a page, and this is repeated 100x in the outer loop (left-to-right across a row). This leads to 100x50 page-faults.

In the real world, you can track page faults with linux commands or getrusage.