74

What is Hashed Page Table in Operating System?

In this tutorial, we will study some of the most common techniques used for structuring the Page table. The data structure used by the virtual memory system in the operating system to store the mapping between physical and logical addresses is commonly known as Page Table.

The logical address 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. Some of the characteristics of the Page Table are as follows:

• It is stored in the main memory.
• The number of entries in the page table is equal to the Number of Pages in which the process is divided.
• Page table base register (PTBR) is basically used to hold the base address for the page table of the current process.
• Each process has its own independent page table.

Here are some of the common techniques that are used for structuring the Page table, such as:

1. Hierarchical Paging
2. Hashed Page Tables
3. Inverted Page Tables

What is Hierarchical Paging?

Another name for Hierarchical Paging is multilevel paging. When the CPU accesses a page of any process, it must be in the main memory. Along with the page, the page table of the same process must also be stored in the main memory. There might be a case where the page table is too big to fit in a contiguous space so that we may have a hierarchy with several levels.

In this type of paging, the logical address space is broken up into Multiple page tables. Hierarchical paging is one of the simplest techniques, and a two-level page table and a three-level page table can be used for this purpose. Let’s understand these levels with the help of an example.

1. Two Level Page Table: Two-level paging in which a page table itself is paged. So we will have two-page tables’ inner page table and outer page table. Consider a system having 32-bit logical address space and a page size of 1 KB. It is further divided into Page Number consisting of 20 bits and Page Offset consisting of 12 bits.

As we page the Page table, the page number is further divided into, Page Numbers consisting of 10 bits and Page Offset consisting of 12 bits.

Thus the Logical address is as follows:

In the above image, P1 is an index into the Outer Page table, and 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.

The above diagram shows the Address Translation scheme for a two-level page table.

2. Three-Level Page Table: A two-level paging scheme is not appropriate for a system with a 64-bit logical address space. Suppose that the page size is 4KB. If we use the two-page level scheme, then the addresses will look as follows:

Thus, to avoid such a large table, there is a solution to divide the outer page table, and then it will result in a Three-level page table as shown below.

What is Hashed Page Table?

Hashed page tables are a technique for structuring page tables in memory. 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. The hash value used is the virtual page number, i.e., all the bits that are not part of the page offset.

Each element in the hash table has the virtual page number, the value of the mapped page, and a pointer to the next element. Hashed page tables are common in address spaces greater than 32 bits. For each element in the hash table, there are three fields available,

1. The virtual Page Number (which is the hash value).
2. The value of the mapped page frame.
3. A pointer to the next element in the linked list.

The virtual page number is matched against the first field, i.e., the 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.

Though we can structure the large page table using the multilevel page table, it would consist of several levels that increase the page table’s complexity.

Working of Hashed Page Table

We would understand the working of the hashed page table with the help of an example. The CPU generates a logical address for the page it needs. Now, this logical address needs to be mapped to the physical address. This logical address has two entries, i.e., a page number (P₃) and an offset, as shown below.

• 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 we have studied earlier, 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 this example, the logical address includes page number P₃ which does not match the first element of the link list as it includes page number P₁. So we will move ahead and check the next element; now, this element has a page number entry, i.e., P3, so further, we will check the frame entry of the element, which is fr₅. We will append the offset provided in the logical address to this frame number to reach the page’s physical address. So, this is how the hashed page table works to map the logical address to the physical address.

Clustered page tables are also used to make this algorithm suitable for 64-bit address spaces.

What is Clustered Page Table?

The clustered page tables are similar to hashed page tables except that each entry in the hash table refers to many pages rather than one single page (as in a hashed page table). Hence, a single entry of a clustered page table can store the mappings for multiple physical page frames.

Clustered page tables are useful for sparse address spaces, where memory references are scattered throughout the address space (non-contiguous).

What is Inverted Page Table?

The concept of normal paging says that every process maintains its own page table, which includes the entries of all the pages belonging to the process. The large process may have a page table with millions of entries. Such a page table consumes a large amount of memory. Consider we have six processes in execution. So, six processes will have some or the other of their page in the main memory, which would compel their page tables also to be in the main memory consuming a lot of space. This is the drawback of the paging concept.

The inverted page table is the solution to this wastage of memory. The concept of an inverted page table consists of a one-page table entry for every frame of the main memory. 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.

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 with respect to the frame number instead of the logical page number. Each entry in the page table contains the following fields.

• Page number:It specifies the page number range of the logical address.
• Process id: An inverted page table contains the address space information of all the processes in execution. Since two different processes can have a similar set of virtual addresses, it becomes necessary to store each process’s process ID to identify its address space uniquely in the Inverted Page Table. This is done by using the combination of Pid and Page Number. So this Process Id acts as an address space identifier and ensures that a virtual page for a particular process is mapped correctly to the corresponding physical frame.
• Control bits: These bits are used to store extra paging-related information. These include the valid bit, dirty bit, reference bits, protection, and locking information bits.
• Chained pointer: It may be possible sometimes that two or more processes share a part of the main memory. In this case, two or more logical pages map to the same Page Table Entry then a chaining pointer is used to map the details of these logical pages to the root page table.

Working of Inverted Page Table

The CPU generates the logical address for the page it needs to access. The logical address consists of three entries process id, page number, and the offset, as shown below.

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 and 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 generate the physical address for the requested page. This is how the logical address is mapped to a physical address using the inverted page table.

Though the inverted page table reduces the wastage of memory but increases the search time, this is because the entries in an inverted page table are sorted based on physical address. In contrast, the lookup is performed using a logical address. It sometimes happens that the entire table is searched to find the match.

So these are the three techniques that can be used to structure a page table that helps the operating system map the logical address of the page required by the CPU to its physical address.

---