Log In
0 votes

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)1/2                   b) (4*d)2

C) (8*2(2d))1/2        d) (2(d+3))1/2

in Operating System
edited by
it will be D...

2 Answers

2 votes

Let X=page table size overhead + internal fragmentation overhead

We need to minimize X.

If we take very large P i.e. large page size then chances of internal fragmentation will be high.

If we take very small P then no. of pages required for a process will be high which means no. of page table entry will increase which in turn means the page table size will increase.

We need to manage both.

If P is the page size then log(P) is the page offset bits. Since logical address bits is "d" so no. of bits for pages= (d-logP). 

So no. of pages= 2(d-logP) = 2d/2logP = 2d/P

Size of page table= (2d/P)*4 B

internal fragmentation in page table:

Min internal frag=0 i.e. when the page table is full

Max internal frag=P-4 i.e. when only one entry(i.e. of size 4B) is present in page table (it can be approximated to P)

So average internal frag=0+P/2=P/2.

X= (2d/P)*4 + P/2

To minimize X(i.e. overall overhead) we need to find dX/dP

dX/dP= (-4*2d)/P2 + 1/2

dX/dP=0 then P= (2(d+3))1/2

Since d2X/dP2 > 0 at P =(2(d+3))1/2 so we know that X is minimum of that value of P.

Option D

0 votes
Overhead=page table size+p/2

F(o)=(V.A/P)*e +P/2

where V.A=virtual address

P=page size

e=page table entry

Differentiating with respect to P



P=$(2*k*e)^{1/2}$         (1)

Where K=virtual address=$(2)^{d}$

Putting this value in eq (1)

Option (D) will satisfied.

Related questions

0 votes
0 answers
I studied from book william stalling ,it was written there if we increase the size of page then pagefault first increases and then when pagesize become size of process then pagefault decreases. Can someone explain with an example why this happens?
asked Dec 8, 2018 in Operating System garvit_vijai 182 views
1 vote
0 answers
I have watched two video lectures on OS memory management (PK Biswas and IISc Mathew Jacob). In both lectures they say that the compiler assumes (while compiling and generating the logical addresses to instructions) that for each process, all of the virtual address space is ... the page table of each process consists of same number of entries..? Is it the real reason to use valid/invalid bit ?
asked Aug 12, 2018 in Operating System Harsh Kumar 288 views
0 votes
0 answers
Consider a system with byte-addressable memory, 32 bit logical addresses, 4 kilobyte page size and page table entries of 4 bytes each. The size of the page table in the system in bytes is __________________
asked Jul 26, 2018 in Operating System srestha 242 views
0 votes
0 answers