Paging

Question

Consider a computer system with single level paging architecture having logical address of 'd'-bit. The memory is byte addressable. If the page table entry size is '32'-bits. What must be the optimal page size P by minimizing the page table overhead and internal fragmentation in paging?

Comments

What is the answer of the question..Do Confirm??

---

your answer is correct.

---

@ Ashwani explain the solution in answer.

Answer 1

Two considerations while choosing the size of page

1. Larger Page Size : Smaller Page table but larger internal fragmentation

2. Smaller Page size : Larger Page table which may not be able to fit in one frame and less unused pages in memory

So ultimately we want an optimal size of  page so that both we can manage both the things together.

Let Page size is S, size of process is P and entry size is e.

Page Table Size = (P/S)* e

Average amount of internal fragmentation is S/2.

So in order to minimize this quantity differentiate it .

$\frac{\mathrm{d} }{\mathrm{d} S} ((P/S)*e + (S/2)) = 0$

-(1/S²) Pe + 1/2 = 0

S= $\sqrt{2Pe}$

Answer to the question

P= 2^d , e= 32bit= 4B

S= $\sqrt{2*2^d*4}$

Hence answer is S= 2$\sqrt{2^(d+1)}$

Comments

Why average overhead is $S/2$?

---

Average internal fragmentation is $\frac{page\space size}{2}$ because the last page would be half empty on an average.

Minimum internal fragmentation$=0$

Maximum internal fragmentation$=page \space size-1$

---

@Manoja Rajalakshmi A Please share a reference to study concepts related to average internal fragmentation.