Introduction
- Paging is a memory management strategy that avoids the necessity for contiguous physical memory allocation. This approach allows a process's physical address space to be non-contiguous.
- Page tables are data structures that map the page number to the frame number.
- The process of Paging is when we divide the entire procedure into equal-sized pages. In addition, each page has a set quantity of words (if it is word addressable).
- When the size of the page table is greater than the frame size, then the page table cannot be stored in a single frame in the main memory in such a case. In such cases, we need the Multilevel paging technique.
(Also, see Need for Paging)
MultiLevel Paging
Multilevel paging is a hierarchical technique consisting of two or more layers of page tables. Level 1 page table entries are pointers to a level 2 page table, while level 2 page table entries are pointers to a level 3 page table, and so on. The actual frame information is stored in the entries of the final level page table. Level 1 has a single-page table whose address is contained in PTBR (Page Table Base Register).
Virtual Address
Working
- The page table that is larger than the frame size is divided into several parts.
- Except for the last component, the size of each part is the same as the size of the frame.
- The page table pages are then stored in various frames of main memory.
- Another page table is maintained to keep track of the frames that store the pages of the divided page table.
- As a consequence, the page table hierarchy is created.
- Multilevel paging is carried out until the level is reached, where the complete page table can be stored in a single frame.
In multilevel paging, regardless of the levels of paging, all page tables are kept in the main memory.
As a result, obtaining the physical address of a page frame necessitates more than one memory access.
Each level requires one access.
Except for the last level page table item, each page table entry provides the base address of the subsequent level page table.
The following is a reference to the actual page frame:
PTE reference in level 1 page table = PTBR value + Level 1 offset in virtual address
PTE reference in level 2 page table = base address (present in Level 1 PTE) + level 2 offset (present in VA).
PTE reference in level 3 page table = base address (present in Level 2 PTE) + level 3 offset (present in VA).
PTE is the actual page frame address (present in level 3).
The page table will usually be the same size as the page itself.
Click here to know about Process Control Block in OS
Illustration of Multilevel Paging
Let us consider a system that employs a paging technique in which :
- Physical Address Space = 16 TB
- Physical Address Space = 16 TB
- 4 KB page size
Let us now determine how many levels of page tables will be needed.
The number of bits in a physical address:
Main memory size = Physical Address Space = 16 TB = 244 B
As a result, the physical address contains 44 bits.
The number of frames in the main memory:
Frames in main memory = main memory size / frame size = 16 TB / 4 KB = 232 frames
As a result, the number of bits in a frame number equals 32 bits.
The number of bits in the page offset:
We have a page size of = 4 KB = 212 B.
As a result, the number of bits in page offset equals 12 bits.
Alternatively,
The number of bits in the page offset
= The number of bits in the physical address − the number of bits in the frame number
= 44 bits - 32 bits =12 bits
Thus, the physical address is :
Number of Pages of Process:
The Number of pages in which the process is divided
= Process size / Page size = 4 GB / 4 KB
= 220 pages
Inner Page Table Dimensions:
The inner page table maintains track of the frames that hold the process pages.
Inner Page table size = The number of entries in the inner page table X the size of the page table entry
= Number of pages in which the process is divided x Number of bits in frame number
= 220 x 32 bits = 220 x 4 bytes = 4 MB
We can now observe:
The inner page table is larger than the frame size (4 KB).
As a result, the inner page table cannot be stored in a single frame.
As a result, the inner page table must be divided into pages.
The number of pages of the inner page table
The number of pages in which the inner page table is divided
= Inner page table size / Page size
= 4 MB / 4 KB = 210 pages
These 210 pages of the inner page table are now stored in various frames of th main memory.
Number of Page Table Entries on One Inner Page Table Page:
The number of page table entries on a single page of an inner page table
= Size of a page / Size of a page table entry
= Page size / the number of bits in the frame number
= 4 KB / 32 bits = 4 KB / 4 B = 210
Number of bits required to search an entry in one Page of an Inner Page Table
There are 210 entries on one page of the inner page table.
Thus, The number of bits needed to search for a specific entry in one page of an inner page table = 10 bits.
Outer Page Table Size
The outer page table is needed to maintain track of the frames that store the pages of the inner page table.
Size of outer page table
= number of entries in outer page table X Page table entry size
= number of pages in which the inner page table is divided X number of bits in frame number
= 210 x 32 bits = 210 x 4 bytes = 4 KB
Now we can see that
- The size of the outer page table is the same as the size of the frame (4 KB).
- As a result, the outer page table may be stored in a single frame.
- As a result, we will have two levels of page tables for the specified system.
- The base address of the outer page table will be stored in the Page Table Base Register (PTBR).
The number of bits required to search for an entry in an outer page table
The outer page table has 210 entries.
Thus, the number of bits necessary to search for a certain entry in the outer page table is equal to 10 bits.
As demonstrated below, the paging system will look like this:
Disadvantage
Programs can be slowed by a factor of two or more when there are extra memory references to access address translation tables. We may speed up the address translation by saving page table entries in a translation lookaside buffer (TLB).
You can also read about the interleave memory.
Must Read Evolution of Operating System