Redirected
edited by
10,356 views
21 votes
21 votes

Consider the following two-dimensional array $\text{D}$ in the $\text{C}$ programming language, which is stored in row-major order:

int D[128][128];

Demand paging is used for allocating memory and each physical page frame holds $512$ elements of the array $\text{D}.$ The Least Recently Used $\text{(LRU)}$ page-replacement policy is used by the operating system. A total of $\text{30}$ physical page frames are allocated to a process which executes the following code snippet:

for (int i = 0; i < 128; i++)
    for (int j = 0; j < 128; j++)
        D[j][i] *= 10;

The number of page faults generated during the execution of this code snippet is _______________.

edited by

4 Answers

Best answer
25 votes
25 votes

We are given an array D[128][128] and it is stored in Row-Major order.

Number of physical frames available = 30.

Number of elements in 1 frames = 512.

Number of pages required to accommodate array D[128][128] = (Number of elements in Array D) / (Number of elements in 1 Page frame)

= (128 * 128) / 512 = 32.

If we have total 32 frames instead of 30 frames then there will be no problem at all but here we are only provided with 30 frames.

Now, coming to the loop : 

                           for (int i = 0; i < 128; i++)

                               for (int j = 0; j < 128; j++)

                                        D[j][i] *= 10;

 

i → 0 – 127 & j → 0 – 127.

With D[j][i] we are accessing the array matrix in Vertical Manner like shown in below Image :

Number of rows occupied in 1 frame will be : 512 / 128 = 4.


So, Page Frame 1 will contain data from row D[0]…. D[3].


Page Frame 2 will contain data from row D[4]…. D[7]…. and so on up to..


Page Frame 32 will contain data from row D[124]… D[127].

Now it is saying that for page-replacement we have to use LRU policy with 30 Page frames.

As the loop start executing it will move from Frame 1 to Frame 32 in vertical manner as shown in 1st image. But, we have only 30 page frames and since we are using LRU poilcy so at the end of 1st iteration we will have Page frame 3 to page frame 32. Page 1 & Page 2 will be moved out due to LRU replacement. During this 1st iteration all 32 pages will give us page fault.

So, number of page fault after 1 iteration = 32.


Similarly this loop iterate 128 times and each time it will give 32 page faults.

So, total number of page faults will be 32 * 128 = 4096.

 

edited by
4 votes
4 votes

According to the question , one frame can hold 512 elements.

The array D[128][128] is stored in row-major order. i.e the array is stored in memory in  the following manner:

                        

Each page frame can hold 512 elements. Now as elements in memory are stored in row-major order, number of rows stored in one page frame will be 

 

                    number of rows of array in one page frame = $\frac{512}{128} = 4$

therefore , elements in 1st page frame frame will look like the following                                                                                                 

  Now,

          for(i=0; i<128; i++){

              for(j = 0; j < 128; j++){

                      D[j][i] *= 10

                  }

          }

       According to the for loop, elements accessed in the sequence:

             D[0][0] , D[1][0] , D[2][0] , D[3][0] , …..  D[127][0]  --------------  for i = 0

             D[0][1] , D[1][1] , D[2][1] , D[3][1] , …..  D[127][1]  --------------  for i = 1

              .

              .

            D[0][127] , D[1][127] , D[2][127] , D[3][127] , …..  D[127][127]  --------------  for i = 127

 

  Now as one page frame can store only 4 rows, so for D[0][0] ….. D[3][127], there will be 1 page

  fault and that also only for D[0][0] ( when it tries to access D[0][0] , it will the fetch 512

  elements and store it in the page frame ) .

 

  D[4][0] …. D[7][127], will be stored in the 2nd page frame and there will be also 1 page fault

  and that also for D[4][0].

 

 Now, as we are only having 30 frames and each frame can store upto 4 rows, so the elements

 that will be present in page frame 30 will be

                                               

 

Now, we are having 30 frames, and each frame stores 4 rows, for 1 page frame we are having 1

page fault so for 30 page frame we will have 30 page faults.

 

we are still left with 8 rows, for D[120][0] …. D[123][127] , there will be one page fault, that also

only for D[120][0]. ( Remember that we will be using LRU replacement policy, so 1st page frame

will be replaced ) . 

 

and then for D[124][0] … D[127][127], we will have one page fault and that also only for D[124][0].

 

So, in total for one iteration of outer loop we are having 32 page faults. In total we have 128

iterations of outer loop , so we will have 

 

              $128 * 32 = 4096$  page faults

1 votes
1 votes
Total entries = 128*128
And all are different

No of entries per frame = 512

So total no. of frames required = (128*128)/512 = 32

So total frames = 32

And total available frame = 30
Therefore total page fault = 32
1 flag:
✌ Low quality (ShubhamAgarwal)
1 votes
1 votes
This is not too hard queston as it seem initially
Given That Matrix stored in Row Major Order ( D[i][j])
also Given  D[j][i] *= 10; i.e. Matrix access in Coloumn Major Order
so
In Row Major Order we got 32 Page fault (128*128/512)
When we access matrix 128x128
Then  page Fault = 32 page fault Per Coloumn
So Total Page Fault = 32*128 = 4096
Answer:

Related questions

2 votes
2 votes
1 answer
1
3 votes
3 votes
1 answer
3
Sona Barman asked Jan 18, 2018
458 views
Self doubt:What is the rule or keyb point we should keep in mind while solving problems on LRU page replacement algorithm? Please explain with examples.