Structure of Page Table

Structure of page table simply defines, in how many ways a page table can be structured. Well, the paging is a memory management technique where a large process is divided into pages and is placed in physical memory which is also divided into frames. Frame and page size is equivalent. The operating system uses a page table to map the logical address of the page generated by CPU to its physical address in the main memory.

In this section, we will discuss three common methods that we use to structure a page table.

Structure of Page Table

1. Hierarchical Page Table
2. Hashed Page Table
3. Inverted Page Table

Hierarchical Page Table

As we knew when the CPU access a page of any process it has to be in the main memory. Along with the page, the page table of the same process must also be stored in the main memory. Now, what if the size of the page table is larger than the frame size of the main memory.

In that case, we have to breakdown the page table at multiple levels in order to fit in the frame of the main memory. Let us understand this with the help of an example.

Consider that the size of main memory (physical memory) is 512 MB = 2²⁹ (i.e. physical memory can be represented with 29 bits)

This physical memory is divided into a number of frames where each frame size = 4 KB = 2¹² (i.e. frame size can be represented with 12 bits)

Physical memory in bits = 29

Frame size in bits = 12

Number of bits used to represent frame number= 29 – 12 = 17.

We represent physical memory as:

Total number of frames would be 2¹⁷ = 1, 31,072

Now we have a physical memory of 512 MB which is divided into 131072 frames where each frame size is 4 KB.

Today modern system supports logical address space up to 2³² to 2⁶⁴ bytes.

Consider we have a process whose size is 4 GB = 2³²

The process is now divided into a number of pages and we know that page size is equal to frame size = 4 KB = 2¹²

Now the logical address is represented as:

 

Logical address in bits = 32

Page size in bits = 12

Number of bits used to represent page number= 32 – 12 = 20.

So the total number of the pages of the process would be = 2²⁰ i.e. up to 1 million.

Now we have a process of size 4 GB which is divided into 1 million pages each of size 4KB.

Next, we have to implement a page table to store the information of pages of process i.e. which page is stored in which frame of the memory. As we have 1 million pages of the process there will be 1 million entries in the page table.

Now in page table the page number provided by CPU in logical address act as an index which leads you to the frame number where this page is stored in main memory. This means each entry of the page table has the frame number.

As we have seen above the frame number is represented by 17 bits so the size of each entry will be of 17 bits i.e. approx. 2 bytes.

Size of page table = number of entries * size of each entry

= 2²⁰ * 2

= 2²¹

=2 MB

So can you store the page table of size 2 MB in a frame of the main memory where frame size is 4 KB? It is impossible.

So we need to divide the page table this division of page table can be accomplished in several ways. You can perform two-level division, three-level division on page table and so on.

Let us discuss 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. We have a logical address with page number 20 and page offset 12. As we are paging a page table the page number will further get split to 10-bit page number and 10 bit offset as you can see in the image below.

 

Here P₁ would act as an index and P₂ would act as an offset for the outer page table. Further, the P₂ would act as an index and d would act as an offset to inner page table to map the logical address of the page to the physical memory.

Hashed Page Table

When the logical address space is beyond 32 bits in such case the page table is structured using hashed page table. Though we can structure the large page table using the multilevel page table it would consist of a number of levels increases the complexity of the page table.

The hashed page table is a convenient way to structure the page table where logical address space is beyond 32 bits. The hash table has several entries where each entry has a link list. Each link list has a set of linked elements where each element hash to the same location. Each element has three entries page number, frame number and pointer to the next element.  We would understand the working of this page table better 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₃ in our case) 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 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 our 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. P₃ so further we will check the frame entry of the element which is fr₅. To this frame number, we will append the offset provided in the logical address 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.

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 involves the existence of single-page table which has entries of all the pages (may they belong to different processes) in main memory along with the information of the process to which they are associated. To get a better understanding consider the figure below of inverted page table.

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, 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 say 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.

Though the inverted page table reduces the wastage of memory but it increases the search time. This is because the entries in an inverted page table are sorted on the basis of physical address whereas the lookup is performed using logical address. It happens sometimes 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 in mapping the logical address of the page required by CPU to its physical address.