Galvin Exercise Question 10.7| Memory Management | Page Replacement Algorithms|Operating System

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 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? Use LRU replacement, and assume that page frame 1 contains the process and the other two are initially empty.

Answer 1

There is space for 2 rows in one page frame, so If the architecture stores the array in row major order,

 The 'a' part code would require 50 page faults x 100 times = 5000 page faults.
Because in one complete iteration of the i loop, 100 different rows are accessed, since 2 rows are in one frame 50 times page fault will happen. And this happen for all the 100 column ( outer j loop). Thus 5000 faults.

But for 'b' code, 100 column are accessed of the same row, by the inner j loop, so no faults for column, only faults will be while trying to access different rows. again that will be only 50, since 2 rows are stored in a page, so always 2 adjacent rows will be available.

Also since we use LRU, the page for the instruction fetching will always stay in the memory, Because it is used in every instructions. Only the 2nd and 3rd pages be swapped for the matrix data storing.

Answer 2

Here page size=200 means 1 page requires 200 locations of array to be stored.
Means-
page 1= 0 to 199 + 200 to 299 (200 locations)
page 2=300 to 499
page 3=500 to 799
...... and so on.

Given that there are 3 page frames to be used
a) for each column all rows are iterated => page 1 is stored in 2 rows i=0 & i=1 for j=0
    so page fault that can occur is 1 time
   2 rows-> 1 page fault
   100 rows-> 100/2 page faults=50 page faults
    and here j will run from 0 to 99 columns so total page faults occuring here will be 50*100=5000 page faults

b) here for every row columns from 0 to 99 will run
    For i=0, j=0 to 99 columns & i=1 j=0 to 99 will contain 1 page only as page requires 200 locations to be stored
   so page fault will occur one time for two iterations of i
   2 rows -> 1 page faults
   100 rows-> 100/2=50 page faults
    but here column have no role in generating page faults as same page is stored across all columns of a row
   Total page faults from both loops= 5000+50=5050 page faults