Suppose a 32 K×8 K matrix A with 1-byte element...

Suppose a 32 K×8 K matrix A with 1-byte elements is stored in row major order in virtual memory. Assume only the program in question occupies space in physical memory.
Program 1 
for (i = 0; i < 32768; i++) 
   for (j = 0; j < 8192; j++) 
       A[i][j] = A[i][j] * A[i][j];

Program 2
for (j = 0; j < 8192; j++) 
 for (i = 0; i < 32768; i++) 
      A[i][j] = A[i][j] * A[i][j];

If Program 1 yields 8 K page faults and  Program 2 experiences the same number of page faults as Program 1 does. How many page faults would Program 2 experience if the physical memory can store 1 page?

(A) 8M
(B) 16M
(C) 32M
(D) 64M

A

B

C

D

2Comments
Sumit Verma @sumitverma 10 Jan 2018 10:05 pm

We can break the question as follow:
If Program 1 yields 8 K page faults, what is the size of a page in this architecture?
 A_SIZE = 32K × 8K × 1B = 256MB
A_SIZE / PAGE SIZE = PAGE FAULTS
PAGE SIZE = A_SIZE/PAGE FAULTS = 256MB/8K = 32KB

Consider Program 2. How many pages should the physical memory be able to store to ensure that Program 2 experiences the same number of page faults as Program 1 does?

8K page faults is possible only if each page is brought into physical memory exactly once – i.e., there shouldn’t be any swapping. Therefore, the physical memory must be large enough to retain all the pages. PAGE COUNT = A_SIZE/PAGE SIZE = 256MB/32K = 8K

Consider Program 2. How many page faults would Program 2 experience if the physical memory can store 1 page?

32K × 8K / 4 = 64M. The inner loop touches a page four times before moving on to a different page.

reena @reenakandari 11 Jan 2018 06:20 pm

everything is perfect but I am not getting last sentence.If there is only one page of size 32kB then there should be as many page fault as number of element i.e 32K*8K?