Paging in OS | Practice Problems | Set-01

Paging in OS-

 

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

 

We have discussed-

• Paging is a non-contiguous memory allocation technique.
• Page Table is a table that maps a page number to the frame number containing that page.

 

Also Read- Important Formulas of Paging

 

In this article, we will discuss practice problems based on concepts of paging.

 

PRACTICE PROBLEMS BASED ON PAGING IN OS-

 

Problem-01:

 

Consider a single level paging scheme. The virtual address space is 4 MB and page size is 4 KB. What is the maximum page table entry size possible such that the entire page table fits well in one page?

 

Solution-

 

For page table, to fit well in one page, we must have-

Page table  size <= Page size

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 4 MB / 4 KB

= 2¹⁰ pages

 

Page Table Size-

 

Let page table entry size = B bytes

Now,

Page table size

= Number of entries in the page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= 2¹⁰ x B bytes

 

Now,

According to the above condition, we must have-

2¹⁰ x B bytes <= 4 KB

2¹⁰ x B <= 2¹²

B <= 4

Thus, maximum page table entry size possible = 4 bytes.

 

Problem-02:

 

Consider a single level paging scheme. The virtual address space is 4 GB and page size is 128 KB. What is the maximum page table entry size possible such that the entire page table fits well in one page?

 

Solution-

 

For page table, to fit well in one page, we must have-

Page table  size <= Page size

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 4 GB / 128 KB

= 2³² B / 2¹⁷ B

= 2¹⁵ pages

 

Page Table Size-

 

Let page table entry size = B bytes

Now,

Page table size

= Number of entries in the page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= 2¹⁵ x B bytes

 

Now,

According to the above condition, we must have-

2¹⁵ x B bytes <= 128 KB

2¹⁵ x B <= 2¹⁷

B <= 4

Thus, maximum page table entry size possible = 4 bytes.

 

Problem-03:

 

Consider a single level paging scheme. The virtual address space is 128 TB and page size is 32 MB. What is the maximum page table entry size possible such that the entire page table fits well in one page?

 

Solution-

 

For page table, to fit well in one page, we must have-

Page table  size <= Page size

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 128 TB / 32 MB

= 2⁴⁷ B / 2²⁵ B

= 2²² pages

 

Page Table Size-

 

Let page table entry size = B bytes

Now,

Page table size

= Number of entries in the page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= 2²² x B bytes

 

Now,

According to the above condition, we must have-

2²² x B bytes <= 32 MB

2²² x B <= 2²⁵

B <= 8

Thus, maximum page table entry size possible = 8 bytes.

 

Problem-04:

 

Consider a single level paging scheme. The virtual address space is 256 MB and page table entry size is 4 bytes. What is the minimum page size possible such that the entire page table fits well in one page?

 

Solution-

 

For page table, to fit well in one page, we must have-

Page table  size <= Page size

 

Let page size = B bytes.

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 256 MB / B bytes

= 2²⁸ / B

 

Page Table Size-

 

Page table size

= Number of entries in the page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= (2²⁸ / B) x 4 bytes

= (2³⁰ / B) bytes

 

Now,

According to the above condition, we must have-

(2³⁰ / B) bytes <= B bytes

B² >= 2³⁰

B >= 2¹⁵

Thus, minimum page size possible = 2¹⁵ bytes or 32 KB.

 

Problem-05:

 

Consider a single level paging scheme. The virtual address space is 512 KB and page table entry size is 2 bytes. What is the minimum page size possible such that the entire page table fits well in one page?

 

Solution-

 

For page table, to fit well in one page, we must have-

Page table  size <= Page size

 

Let page size = B bytes.

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 512 KB / B bytes

= 2¹⁹ / B

 

Page Table Size-

 

Page table size

= Number of entries in the page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= (2¹⁹ / B) x 2 bytes

= (2²⁰ / B) bytes

 

Now,

According to the above condition, we must have-

(2²⁰ / B) bytes <= B bytes

B² >= 2²⁰

B >= 2¹⁰

Thus, minimum page size possible = 2¹⁰ bytes or 1 KB.

 

Problem-06:

 

Consider a single level paging scheme. The virtual address space is 16 GB and page table entry size is 4 bytes. What is the minimum page size possible such that the entire page table fits well in one page?

 

Solution-

 

For page table, to fit well in one page, we must have-

Page table  size <= Page size

 

Let page size = B bytes.

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 16 GB / B bytes

= 2³⁴ / B

 

Page Table Size-

 

Page table size

= Number of entries in the page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= (2³⁴ / B) x 4 bytes

= (2³⁶ / B) bytes

 

Now,

According to the above condition, we must have-

(2³⁶ / B) bytes <= B bytes

B² >= 2³⁶

B >= 2¹⁸

Thus, minimum page size possible = 2¹⁸ bytes or 256 KB.

 

Next Article- Translation Lookaside Buffer | TLB

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.