The Gateway to Computer Science Excellence
0 votes
119 views

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 by (385 points)
edited by | 119 views
0
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

 
by Boss (23.5k points)
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

F'(o)=-K*e/$p^{2}$+1/2

F'(o)=0

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

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

Putting this value in eq (1)

Option (D) will satisfied.
by Active (2.8k points)

Related questions

0 votes
0 answers
4
asked Dec 3, 2017 in Operating System by student2018 Junior (947 points) | 89 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,312 answers
198,342 comments
105,035 users