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!!

Beanstalk

This is poorly worded problem. 1) No system would ever use pages of 200 bytes (small and not a power of 2. 2) Two frames are unrealistic in an VM system. 3) It presumes a C style of array layouts. This problem of accessing array elements non-contiguously is more relevant in the context of CPU caching. – Guarantee

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.

Garratt

I have a question for Grijesh, why do you divide 10,000 and 100 to 2? (10,000/2 and 100/2). Where did you get the 2? – Lothaire

because page fault happens in alternate frame change, notice number of page frame in system are two.-- to further understand it think what happens when there is only one page frame, then think what should happen when page frames are two.-- let me know if need explanation I will update answer. – Garratt

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.

Babel

Answer 3

So there's 50 pages total in the 2-d array stored either row by row, or column by column.

If you store pages row by row and you access them row by row, your going to access the same page over and over again until you get to the next page, so you switch pages (causing a page fault) only 50 times because there's 50 pages.

If you store pages row by row, and access them column by column (or vise-verse), your going to get an element from one page, switch pages, get one from another page, switch pages, etc. So your still going through 50 pages, but you switch 100 times for every page.

Imaging your reading a paper. If you read one page at a time, your gonna turn the page once for every page. If you read one line off every page, then start over and read the second line, third line etc. your going to have to flip through the whole paper over and over, for every line on a page (assuming all pages have the same number of lines like an array would)...each time you turn the page is a page fault.

Jammie

Answer 4

Let’s look at a contrived but informative example. Assume that pages are 128 words in size. Consider a C program whose function is to initialize to 0 each element of a 128-by-128 array. The following code is typical:

int i, j;
int[128][128] data;
for (j = 0; j < 128; j++)
  for (i = 0; i < 128; i++)
data[i][j] = 0;

Notice that the array is stored row major; that is, the array is stored data[0][0], data[0][1], ···, data[0][127], data[1][0], data[1][1], ···, data[127][127]. For pages of 128 words, each row takes one page. Thus, the preceding code zeros one word in each page, then another word in each page, and so on. If the operating system allocates fewer than 128 frames to the entire program, then its execution will result in 128 × 128 = 16,384 page faults.

In contrast, suppose we change the code to

int i, j;
int[128][128] data;
for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
data[i][j] = 0;

This code zeros all the words on one page before starting the next page, reducing the number of page faults to 128.

Coliseum

The concept was taken from "operating systems concepts essentials" book – Coliseum