**Paging in OS-**

Before you go through this article, make sure that you have gone through the previous article on **Paging in OS**.

We have discussed-

- Paging is a non-contiguous memory allocation technique.
**Page Table**keeps track of the frames storing the pages of the process.

**Overhead in Paging-**

In paging scheme, there are mainly two overheads-

**1. Overhead of Page Tables-**

- Paging requires each process to maintain a page table.
- So, there is an overhead of maintaining a page table for each process.

**2. Overhead of Wasting Pages-**

- There is an overhead of wasting last page of each process if it is not completely filled.
- On an average, half page is wasted for each process.

Thus,

Total overhead for one process

= Size of its page table + (Page size / 2)

**Optimal Page Size-**

Optimal page size is the page size that minimizes the total overhead.

It is given as-

**Also Read-** **Important Formulas Of Paging**

**Proof-**

Total overhead due to one process

= Size of its page table + (Page size / 2)

= Number of entries x Page table entry size + (Page size / 2)

= Number of pages the process is divided x Page table entry size + (Page size / 2)

= (Process size / Page size) x Page table entry size + (Page size / 2)

Now,

For minimum overhead,

Keeping process size and page table entry size as constant, differentiating overhead with respect to page size, we get-

This page size minimizes the total overhead.

**PRACTICE PROBLEMS BASED ON OPTIMAL PAGE SIZE-**

**Problem-01:**

In a paging scheme, virtual address space is 4 KB and page table entry size is 8 bytes. What should be the optimal page size?

**Solution-**

Given-

- Virtual address space = Process size = 4 KB
- Page table entry size = 8 bytes

We know-

Optimal page size

= (2 x Process size x Page table entry size)^{1/2}

= (2 x 4 KB x 8 bytes)^{1/2}

= (2^{16} bytes x bytes)^{1/2}

= 2^{8} bytes

= 256 bytes

Thus, Optimal page size = 256 bytes.

**Problem-02:**

In a paging scheme, virtual address space is 16 MB and page table entry size is 2 bytes. What should be the optimal page size?

**Solution-**

Given-

- Virtual address space = Process size = 16 MB
- Page table entry size = 2 bytes

We know-

Optimal page size

= (2 x Process size x Page table entry size)^{1/2}

= (2 x 16 MB x 2 bytes)^{1/2}

= (2^{26} bytes x bytes)^{1/2}

= 2^{13} bytes

= 8 KB

Thus, Optimal page size = 8 KB.

**Problem-03:**

In a paging scheme, virtual address space is 256 GB and page table entry size is 32 bytes. What should be the optimal page size?

**Solution-**

Given-

- Virtual address space = Process size = 256 GB
- Page table entry size = 32 bytes

We know-

Optimal page size

= (2 x Process size x Page table entry size)^{1/2}

= (2 x 256 GB x 32 bytes)^{1/2}

= (2^{44} bytes x bytes)^{1/2}

= 2^{22} bytes

= 4 MB

Thus, Optimal page size = 4 MB.

**Next Article-** **Practice Problems On Paging in OS**

Get more notes and other study material of **Operating System**.

Watch video lectures by visiting our YouTube channel **LearnVidFun.**