Andrew S. Tanenbaum (OS) Edition 4 Exercise 3 Question 38 (Page No. 258)

Question

Consider the following two-dimensional array:

int X[64][64];

Suppose that a system has four page frames and each frame is $128$ words (an integer occupies one word). Programs that manipulate the $X$ array fit into exactly one page and always occupy page $0.$ The data are swapped in and out of the other three frames. The $X$ array is stored in row-major order $(i.e., X[0][1]$ follows $X[0][0]$ in memory$).$ Which of the two code fragments shown below will generate the lowest number of page faults? Explain and compute the total number of page faults.
 

Fragment A
for (int j = 0; j < 64; j++) 
     for (int i = 0; i < 64; i++) X[i][j] = 0;

Fragment B 
for (int i = 0; i < 64; i++) 
     for (int j = 0; j < 64; j++) X[i][j] = 0;

Answer 1

(B) If you are accessing  through ROW major order then for every 128 entries there is only 1 page fault 

EX: in frame 2:

X[0][0],X[0][1]..........X[0][64], X[1][0],X[1][1]..........X[1][64].

only  X[0][0] is page fault 

and total references are 64*64 

so total page faults are  (64*64)/128=32

OR you can say that The inner loop causes only one page fault for every other iteration of the outer loop. Hence, 32 page faults occur.

 

 

 

(A)  If you are accessing  through COLUMN major order then for every 2 entries there is only 1 page fault 

EX: in frame 2:

X[0][0]X[0][1]..........X[0][64], X[1][0],X[1][1]..........X[1][64].

only  X[1][0] is hit

and total reference are 64*64 

so total page faults are  (64*64)/2=2048

 OR you can say that The inner loop causes 32 page faults for every iteration of the outer loop. Hence, 2048 page faults occur. 

 

Comments

Please can you explain how using column major for every two entries there is one page fault??

---

Like in row ordering you go row wise and , so you get 128 words every time a page fault occurs like

………………………..  

………………………..      

so you assume this to lines to be two 64 element row . so there are 32 such

     pair. So every page fault will bring 128 words each row as 64 so every time two rows will be finished so 32 fault for 64 rows one fault for each  pair.

In colum ordering you fill 128 but vertically so every time your page faults you will get 128 words and keep them vertically  like this

 1   64     

2   65         

 3   66         

 4    67        
….. ….

 see there you will get 1 and 64 so for every miss you get 128 words and it will provide you    
  with one more word in advance because rest are filled vertical you cannot access them
  so for every 2 pages you read there is one fault you can say. there are 2048 elements
  2048/2 = 1024.