FOR FREE MATERIALS

Inverted Page Table with examples

Usually, each process has at least one-page table. The page table has one entry (Frame number and other important information) for each page that the process is using.

One disadvantage of this method is that each page table may consist of millions of entries that are right now present at the memory, not contain all entries. These tables may consume large amount of physical memory just to keep track of how another physical memory is being used.

To save the page table size, we use an inverted page table. In this case, only one-page table will be maintained for all the processes.

This page contains page numbers of all process which resides at the memory and here index is frame number unlike traditional page table and it is basically identified that which frame number contain which page. 

Now because of only one-page table for all processes to identify separately here process id attached page number.

Because of inverted page table indexed by frame number so, the size of the inverted page table depends on the number of frames in main memory or physical memory.

Disadvantage:

Although this scheme decreases the amount of memory needed to store each page table, it increases the amount of time needed to search the table when a page reference occurs. 

Because the inverted page table is store by physical memory (main memory), and it stores the page numbers of all processes, the whole table might need to be searched before a match find. 

Example 1

Consider a system with the logical address is 22 bit and physical address is 36 bit and the page size is 2KB. The memory is byte-addressable and the page table entry is 4 bytes. 

(1) What is the conventional page table size?

(2) What is the inverted page table size?

Solution:

Logical Address (LA) = 22 bit, so Logical Address Space (LAS) = ${\mathbf{2}}^{\mathbf{22}}$

Physical Address (PA) = 36 bit, so, Physical Address Space (PAS) = ${\mathbf{2}}^{\mathbf{36}}$

Page size = 2KB = ${\mathbf{2}}^{\mathbf{11}}$ and Page Table Entry (PTE) size = 4 bytes = ${\mathbf{2}}^{\mathbf{2}}$

(1) Conventional Page Table Size (PTS):

As we know Page Table Size (PTS) = Number of pages  ×  Page table entry

(2) Inverted Page Table Size (PTS):

Because of inverted page table indexed by frame number so, the size of the inverted page table depends on the number of frames in main memory or physical memory.

So, Inverted Page Table Size = Number of frames × page table entry