A page table is a data structure used by virtual memory system in a computer operating system to store the mapping between the virtual addresses and physical addresses. Multilevel page tables are split into two or more levels.The multi-level page tables are tree-like structures to hold page table.
The entries of the level-0 page table are pointers to a level-1 page table.
The entries of the level-1 page table are pointers to a level-2 page table.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
The entries of the last level page table are stores actual page frame information.
In multilevel paging when paging is applied on page table.
The first level page entry will have the base address of second level page table and second level page entry will have base address of third level page table and third level page entry will have the base address of fourth level page table and so on. The last level page entry will have frame number of the actual page table.
In multi-level paging whatever may be the levels of paging all the page tables (pages of page table) will be stored in the main memory and all the page table entries contain frame number only. All page tables are stored in memory. So, it requires more than one memory access to get the physical address of page frame.
Advantage:
It helps to reduce the size of page table needed to implement the virtual address space of a process.
Disadvantage:
Extra memory references to access address translation tables can slow programs down by a factor of two or more.
Formula to calculate EMAT:
Formula to calculate Effective Memory Access Time in multi-level paging is-
EMAT = [ (H) X (TLB access time + Memory access time)
+
(1 - H) X (TLB access time + (K X PT access time) + Memory access time)]
Where H = TLB Hit rate
K = Number of page table
Question-1:
Suppose you have a 32-bit virtual address with a page size of 4KB and that page table entry takes 4 bytes. How many levels of page tables would be required to map the virtual address space if every page table is required to fit into a single page?
(A) 2 levels
(B) 3 levels
(C) 4 levels
(D) 5 levels
Answer: (A) 2 levels
Explanation:
Page size = 4 KB = 22 X 210 = 212 bytes
So, in First level, one page table contains 210 PTEs ( 22 X 210 = 212 bytes )
Pointing to 210 pages (addressing a total of 210 X 212 = 222 bytes)
Adding a second level yields another 210 pages of page table, addressing 210 X 210 X 212 = 232 bytes.
So, we need 2 levels.
Question-2:
Suppose you have a 48-bit virtual address with page size 16KB and that page table entry takes 4 bytes. Then what is PT! size, PT2 size, PT3 size and how are you going to split the virtual address?
Explanation:
Virtual address = 48 bits
So, virtual address space = 248 bytes Page size = 16KB = 24 X 210 = 214 bytes
So, number of pages = Virtul address space/Page size = 248/214 = 234
Therefore, PT1 contains 234 entries and size of each entries is 4 bytes = 22 bytes.
So, size of PT1 is = 234 X 22 = 236 bytes.
But this is not fit in page table, because page table size is 214 bytes.
Therefore, again PT1 divided into many pages.
Therefore, PT2 contains 236/214 = 222 entries and size of each entries is 22 bytes.
So, size of PT2 is = 222 X 22 = 224 bytes.
This is also not fit in page table.Therefore, PT2 divided into many pages.
Therefore, PT3 contains 224/214 = 210 entries and size of each entries is 22 bytes
So, size of PT3 is = 210 X 22 = 212 bytes.
Finally this one is fit in page table.
Now we know that in multi-level paging CPU contain the base address of the outer most page table.
In this case PT3 is the outer most page table and in this page table total, 210 entries are present.
Therefore, from the virtual address first 10 bits are going to act as the index of outer most page table PT3.
But PT1 and PT2 both are completely full and both are contain 214/22 = 212 entries.
Therefore, from the virtual address second 12 bits and third 12 bits are going to act as the index of PT2 and PT1 and remaining 14 bits will be the page offset.