Problem For Practice
Q. Consider a virtual memory system with physical memory of 8GB, a page size of 8KB, and a 46-bit virtual address. Assume every page table exactly fits into a single page. If page table entry size is 4B then how many levels of page tables would be required?
Explanation:
Page size = 8KB = 213 B
Virtual address space size = 246 B
PTE = 4B = 22 B
Number of pages or number of entries in page table,
= (virtual address space size) / (page size)
= 246B/213 B
= 233
Size of Page Table,
= (number of entries in page table)*(size of PTE)
= 233*22 B
= 235 B
To create one more level,
Size of Page Table > Page Size
Number of page tables in last level,
= 235 B / 213 B
= 222
The base address of these tables is stored in the page table [second last level].
Multi-Level Paging
Size of page table [second last level]
= 222*22B
= 224B
To create one more level,
Size of page table [second last level] > page size
Number of page tables in second last level
= 224B/213 B
= 211
The base address of these tables are stored in page table [third last level]
Size of page table [third last level]
= 211*22 B
= 213 B
= page size
∴ 3 levels are required.
Multilevel Paging in Operating System
Multilevel Paging is a paging scheme that consists of two or more levels of page tables in a hierarchical manner. It is also known as hierarchical paging. The entries of the level 1 page table are pointers to a level 2 page table and entries of the level 2 page tables are pointers to a level 3 page table and so on. The entries of the last level page table store actual frame information. Level 1 contains a single-page table and the address of that table is stored in PTBR (Page Table Base Register).