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^{10} 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^{10} x B bytes
Now,
According to the above condition, we must have-
2^{10} x B bytes <= 4 KB
2^{10} x B <= 2^{12}
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^{32} B / 2^{17} B
= 2^{15} 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^{15} x B bytes
Now,
According to the above condition, we must have-
2^{15} x B bytes <= 128 KB
2^{15} x B <= 2^{17}
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^{47} B / 2^{25} B
= 2^{22} 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^{22} x B bytes
Now,
According to the above condition, we must have-
2^{22} x B bytes <= 32 MB
2^{22} x B <= 2^{25}
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^{28} / 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^{28} / B) x 4 bytes
= (2^{30} / B) bytes
Now,
According to the above condition, we must have-
(2^{30} / B) bytes <= B bytes
B^{2} >= 2^{30}
B >= 2^{15}
Thus, minimum page size possible = 2^{15} 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^{19} / 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^{19} / B) x 2 bytes
= (2^{20} / B) bytes
Now,
According to the above condition, we must have-
(2^{20} / B) bytes <= B bytes
B^{2} >= 2^{20}
B >= 2^{10}
Thus, minimum page size possible = 2^{10} 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^{34} / 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^{34} / B) x 4 bytes
= (2^{36} / B) bytes
Now,
According to the above condition, we must have-
(2^{36} / B) bytes <= B bytes
B^{2} >= 2^{36}
B >= 2^{18}
Thus, minimum page size possible = 2^{18} 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.