Memory Management

Question

Given that the logical address is "d" bits.Page table entry size is 4 Bytes, what must be the optimal page size P by minimizing the page table size overhead and internal fragmentation in paging?

a) √4d

b) (4d)²

c) √8.2^2d

^d) √2^d+3 

Comments

Plz check my answer @srestha..

Answer 1

Given logical address size = d bits

Therefore , logical address space = 2^d bytes( assuming that it is byte addressable memory meaning word size = 1 Byte)

Let the page size   =   p

So , no of pages    =   Logical address space / Page size 

                            =   2^d / p

Now we know that ,

No of page table entries  =   No of pages in single level paging

                                    =    2^d / p

Therefore the memory required for page table which is considered as the overhead

in the question :             =   No of page table entries  *  Page table entry size

                                    =   (2^d / p)  *  4 B

                                    =    2^d+2 / p

We know that internal fragmentation in the paging if exists can occur only in the last page and hence internal fragmentation varies from  0  to  p , where p is the page size .

So as an average , internal fragmentation   =  (0 + p) / 2             

                                                              =   p / 2

Hence the total overhead    =    Overhead due to page table + Internal fragmentation

                                        =     2^d+2 / p   +  p / 2      =    f(p) say

Now as a function to minimise this ,

d (f(p)) / dp   =    0

⇒  -2^d+2 / p²  +  1/2    = 0

⇒  p²  =   2^d+3

⇒  p   =    √ 2^d+3

Further , for minimum ,

d² (f(p)) / dp²   > 0 which can be verified easily by applying this on f(p).

So  optimal page size which is required  =  √ 2^d+3  B    

Hence D is the correct option.