1] Hierarchical Paging
- It is also called Multilevel Paging and it is a very simple methodology.
- When the page table is too big to fit in a contiguous space then this hierarchical paging system is used with several levels.
- In this, the logical address space is broken up into Multiple page tables.
- Hierarchical paging uses the following two types of page tables:
- Two-Level Page Table
- Three-Level Page Table
Two Level Page Table:
- On this page table, itself is paged. Therefore, here two-page tables' inner page table and outer page table are present.
- Example: 32-bit logical address space and a page size of 4 KB is divided into A Page Number consisting of 20 bits and A Page Offset consisting of 12 bits.
- Since the Page table itself paged, the page number is further divided into, A 10-bit page number and A 10-bit page offset.
Therefore Logical Address looks as follows:
P1 |
P2 |
d |
10 |
10 |
12 |
Outer Page Table |
Inner Page Table |
Offset |
Suppose the question asked
P1 |
P2 |
d |
8 |
? |
12 |
Outer Page Table |
Inner Page Table |
Offset |
Note that p1 is the first level index which is the outer level Here with terminology you can find difficulty but take time to understand it
Now the the Outer Level is pointer to the inner table ; note that each of the of page
0 , 1, 2 ,3 ,4 …. 2^8-1 is mapping to the each page table
For example
Outer page table of
0th page is pointing to the inner page table which we will have 2^12 entries of page table
1th page is pointing to the inner page table which we will have 2^12 entries of page table
2th page is pointing to the inner page table which we will have 2^12 entries of page table
so on
2^8 -1 th page is pointing to the inner page table which we will have 2^12 entries of page table
Now the Inner table of 0th page which have entries of 2^12 each entries is pointing to the page table of 2^12 in the virtual memory
the Inner table of 1th page which have entries of 2^12 each entries is pointing to the page table of 2^12 in the virtual memory
so on
the Inner table of 2^8- 1 th page which have entries of 2^12 each entries is pointing to the page table of 2^12 in the virtual memory
This is the idea of Two level paging Hope You understand.