Structure of Page Table in Operating Systems
In this tutorial, we will cover some of the most common techniques used for structuring the Page table.
The data structure that is used by the virtual memory system in the operating system of a computer in order to store the mapping between physical and logical addresses is commonly known as Page Table.
As we had already told you that the logical address that is generated by the CPU is translated into the physical address with the help of the page table.
- Thus page table mainly provides the corresponding frame number (base address of the frame) where that page is stored in the main memory.
The above diagram shows the paging model of Physical and logical memory.
Characteristics of the Page Table
Some of the characteristics of the Page Table are as follows:
-
It is stored in the main memory.
-
Generally; the Number of entries in the page table = the Number of Pages in which the process is divided.
-
PTBR means page table base register and it is basically used to hold the base address for the page table of the current process.
-
Each process has its own independent page table.
Techniques used for Structuring the Page Table
Some of the common techniques that are used for structuring the Page table are as follows:
-
Hierarchical Paging
-
Hashed Page Tables
-
Inverted Page Tables
Let us cover these techniques one by one;
Hierarchical Paging
Another name for Hierarchical Paging is multilevel paging.
-
There might be a case where the page table is too big to fit in a contiguous space, so we may have a hierarchy with several levels.
-
In this type of Paging the logical address space is broke up into Multiple page tables.
-
Hierarchical Paging is one of the simplest techniques and for this purpose, a two-level page table and three-level page table can be used.
Two Level Page Table
Consider a system having 32-bit logical address space and a page size of 1 KB and it is further divided into:
As we page the Page table, the page number is further divided into :
Thus the Logical address is as follows:
In the above diagram,
P1 is an index into the Outer Page table.
P2 indicates the displacement within the page of the Inner page Table.
As address translation works from outer page table inward so is known as forward-mapped Page Table.
Below given figure below shows the Address Translation scheme for a two-level page table
Three Level Page Table
For a system with 64-bit logical address space, a two-level paging scheme is not appropriate. Let us suppose that the page size, in this case, is 4KB.If in this case, we will use the two-page level scheme then the addresses will look like this:
Thus in order to avoid such a large table, there is a solution and that is to divide the outer page table, and then it will result in a Three-level page table:
Hashed Page Tables
This approach is used to handle address spaces that are larger than 32 bits.
-
In this virtual page, the number is hashed into a page table.
-
This Page table mainly contains a chain of elements hashing to the same elements.
Each element mainly consists of :
-
The virtual page number
-
The value of the mapped page frame.
-
A pointer to the next element in the linked list.
Given below figure shows the address translation scheme of the Hashed Page Table:
The above Figure shows Hashed Page Table
The Virtual Page numbers are compared in this chain searching for a match; if the match is found then the corresponding physical frame is extracted.
In this scheme, a variation for 64-bit address space commonly uses clustered page tables.
Clustered Page Tables
-
These are similar to hashed tables but here each entry refers to several pages (that is 16) rather than 1.
-
Mainly used for sparse address spaces where memory references are non-contiguous and scattered
Inverted Page Tables
The Inverted Page table basically combines A page table and A frame table into a single data structure.
-
There is one entry for each virtual page number and a real page of memory
-
And the entry mainly consists of the virtual address of the page stored in that real memory location along with the information about the process that owns the page.
-
Though this technique decreases the memory that is needed to store each page table; but it also increases the time that is needed to search the table whenever a page reference occurs.
Given below figure shows the address translation scheme of the Inverted Page Table:
In this, we need to keep the track of process id of each entry, because many processes may have the same logical addresses.
Also, many entries can map into the same index in the page table after going through the hash function. Thus chaining is used in order to handle this.
