Inverted Page table

Inverted Paging

Inverted paging was a concept that was introduced after the conventional Paging system, in order to remove the problems that the normal paging system was facing.

In the conventional paging system, we had stored them in the main memory.

A small depiction of the page table has been shown below.

As shown in the above diagram, we have a page table. The page table is referenced by a logical address. We will come back to the logical address a bit later.

First, we take a look at the total page table storage process.

Page table diagram

 Now, look at the above picture. Here on the left side, we find the process number and frame number distinction. This is actually the logical address. What happens is that virtual memory is created by the system, which stores all the process number against each page number.

Whenever a certain process in the page table is referred, then the logical table searches the whole table for the matching process number. Once the process number matches, it checks whether it belongs to the required page or not by comparing the page numbers. If the match found, retrieves that data from the main memory. If match not found then it needs to go to the main memory, search for it and copy the required page to the page table and compare. 

One might feel that fine what is the problem. I mean what was the need for this inverted page table. The answer is the searching time. and the process retrieval time.

To reduce this time inverted paging was proposed. But it had some grave disadvantages too.

Now first let us see what is this inverted paging.

In the inverted paging, everything was the same just the difference was that a process number is not mapped to a page number rather a page number was mapped to a process number.

I know it looks confusing but let's just look at the diagram to get a better insight. And definitely, I suggest one to compare the page table and the inverted page table diagram to understand better.

Inverted page table

Now here we can see there is only a small change, now the page number is the key against which the process number is mapped.

So, we can simply say that the physical address becomes the logical address and vice-versa.

One can also depict this as a mapping from physical address to logical address if we take our page table as the base of comparison.

Well now that you clearly see the comparison between the 2 diagrams, let's go ahead with the discussion.

Clearly, the inverted page table was invented for reducing the comparison time of the page table.

Clearly, this structure might have been suiting for uni-processing because in that case, we need to map against one process only but a disaster in case of multiprocessing systems where there are a large number of processes. In that case, finding which page is mapped against which process will again take linear time i.e. O(n) complexity as we need to compare each and every process. Thus, ruining the purpose of its presence. Hence this is not recently used.

In case of any doubt feel free to ask your doubts.