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

= 210 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

= 210 x B bytes

 

Now,

According to the above condition, we must have-

210 x B bytes <= 4 KB

210 x B <= 212

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

= 232 B / 217 B

= 215 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

= 215 x B bytes

 

Now,

According to the above condition, we must have-

215 x B bytes <= 128 KB

215 x B <= 217

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

= 247 B / 225 B

= 222 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

= 222 x B bytes

 

Now,

According to the above condition, we must have-

222 x B bytes <= 32 MB

222 x B <= 225

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

= 228 / 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

= (228 / B) x 4 bytes

= (230 / B) bytes

 

Now,

According to the above condition, we must have-

(230 / B) bytes <= B bytes

B2 >= 230

B >= 215

Thus, minimum page size possible = 215 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

= 219 / 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

= (219 / B) x 2 bytes

= (220 / B) bytes

 

Now,

According to the above condition, we must have-

(220 / B) bytes <= B bytes

B2 >= 220

B >= 210

Thus, minimum page size possible = 210 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

= 234 / 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

= (234 / B) x 4 bytes

= (236 / B) bytes

 

Now,

According to the above condition, we must have-

(236 / B) bytes <= B bytes

B2 >= 236

B >= 218

Thus, minimum page size possible = 218 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.

Summary
Paging in OS | Practice Problems | Set-01
Article Name
Paging in OS | Practice Problems | Set-01
Description
Practice Problems based on Paging in OS. Paging in OS is a non-contiguous memory allocation technique. In paging scheme, page table performs the mapping of page number to the frame number.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-