Structure of a Page Table

• A Page Table is one type of data structure used by a virtual memory of the system to store the mapping between virtual or logical addresses and physical addresses.
• The structure of the page table represents how many ways a page table can be structured.
• The paging is a methodology in the memory management system where a large process is divided into pages and is placed into the physical memory which is also divided into frames.
• The size of the frame and page are the same.
• The OS uses a page table to map the logical or virtual address of the page generated by the CPU to its physical address in the main memory.

Some of the common techniques used for structuring the Page table are as follows:

• Hierarchical Paging

• Hashed Page Tables

• Inverted Page Tables

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:

• Here, P1 & P2 represent Page Numbers and d represents the Page Offset.
• In the above address, P1 is an index into the Outer Page table, and P2 indicates the displacement within the page of the Inner page Table.

Three Level Page Table

• A two-level paging table is not appropriate for the system with a 64-bit logical address space.
• Hence, for 64-bit logical address space, Three-Level Page Table is used.
• In this, divide the outer page table first, and then it will result in a Three-level page table as shown below.
• Example: 64-bit logical address space and a page size of 4 KB is divided.

2] Hashed Page Tables

• Hashed page tables are commonly used in address spaces greater than 32 bits.
• In a hashed page table, the virtual addresses are hashed into the hash table.
• Each element in the table comprises a linked list of elements to avoid collisions.
• For each element in the hash table, there are three fields available,
  • The virtual Page Number (hash value, all bits are not part of the page offset)
  • The value of the mapped page frame
  • A pointer to the next element in the linked list
• The virtual page number is matched against the first field (virtual address), and if a match is found, the corresponding mapped address in the second field is used to form the desired memory address.
• If a match is not found, the linked list is traversed using the next pointer until a match is found.

• The CPU generates a logical address for the page it needs.
• Then logical address needs to be mapped to the physical address. This logical address has two entries, page number (P3) and an offset.
• The page number from the logical address is directed to the hash function.
• The hash function produces a hash value corresponding to the page number.
• This hash value directs to an entry in the hash table.
• As each entry in the hash table has a link list. Here the page number is compared with the first element’s first entry if a match is found then the second entry is checked.
• In the example mentioned in the above image, the logical address includes page number P3 which does not match the first element of the link list as it includes page number P1.
• So it will move ahead and check the next element.
• Now, this element has a page number entry (P3) so further it will check the frame entry of the element which is fr5.
• To this frame number, it will append the offset provided in the logical address to reach the page’s physical address.
• This is how the hashed page table works to map the logical address to the physical address.

3] Inverted Page Tables

• The inverted page table consists of a one-page table entry for every frame of the main memory.
• The inverted page table combines a page table and a frame table into one data structure.
• So the number of page table entries in the Inverted Page Table reduces to the number of frames in physical memory.
• A single-page table represents the paging information of all the processes.
• One entry for each virtual page number and real page of memory.
• This provides the solution to the wastage of memory problem.
• The overhead of storing an individual page table for every process gets eliminated through the inverted page table.
• Only a fixed portion of memory is required to store the paging information of all the processes together.
• This technique is called inverted paging, as the indexing is done concerning the frame number instead of the logical page number.
• Each entry in the page table contains the fields such as
  • Page number
  • Process ID
  • Control bits
  • Chained Pointer.
• As inverted page tables decrease the need for storage for each table, but it increases the time needed to search the table when a page reference occurs.

• The CPU generates the logical address for the page it needs to access.
• This time the logical address consists of three entries process id, page number, and the offset.
• The process id identifies the process, of which the page has been demanded, the page number indicates which page of the process has been asked for and the offset value indicates the displacement required.
• The match of process id along with associated page number is searched in the page table and says if the search is found at the i^th entry of page table then i and offset together generates the physical address for the requested page.
• This is how the logical address is mapped to a physical address using the inverted page table.