The Gateway to Computer Science Excellence

+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)} = 2^{d}/2^{logP} = 2^{d}/P

Size of page table= (2^{d}/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= (2^{d}/P)*4 + P/2

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

dX/dP= (-4*2^{d})/P^{2} + 1/2

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

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

Option D

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,312 answers

198,342 comments

105,035 users