Structure of page table
The data structure that is used by the virtual memory system to store the mapping between the physical and logical addresses is known as Page Table.
The page table provides the corresponding page number where the page is supposed to be stored.
Characteristics of a Page Table:
The characteristics of a page table are as follows:
- Page table is stored in the main memory.
- The number of entries in the page table is equal to the number of pages the processes are divided into.
- Each process has its page table.
- Page Table Base Register or PTBR holds the base address for the page table.
Techniques used for structuring the page table:
Some of the techniques used for structuring the page table are as follows:
- Hierarchical paging
- Inverted page tables
- Hashed page tables
Hierarchical paging
Hierarchical paging or multilevel paging is a type of paging where the logical address space is broken up into multiple page tables.
It is one of the simplest techniques and for this, a two-level or three-level page table is used.
Inverted Page Tables
Inverted page table is a combination of a page table and a frame table.
There is one entry for virtual page number and real page of memory.
This method decreases the memory needed to store each page table.
But, it may also increase the amount of time needed to search the table for a page reference.
Hashed Page Tables
The hashed page table method is used to handle address spaces larger than 32 Bits.
In this table, there is a chain of elements hashed into the same elements.
The elements consist:
- Virtual page number
- A pointer next to the element in the list.
- The value of the mapped page frame.
Cluster tables are similar to hashed page tables but used for 64 Bits.