Self doubt

Question

How to understand that no. of entries in inverted page table is equal to no of frames in physical address space?

Answer 1

Inverted page table :- in normal paging PageTable size is dependent on number of pages because in normal paging every page table entry will correspond to one page and in that way number of entries in page table will just equal to number of pages in virtual address space.But we know that not all pages will be allocated to physical memory and only limited will be stored in frames. We know Page tables are stored in main memory , and when size of page table increases , it would be an unnecessary burden to main memory , if page table size is large enough then it may happen that we may have to use the same virtual memory concept will page table to , mean to put only currently useful entries in main memory and as per need fetch remaining from swap space.

so just to reduce page table size and save memory wastage , what we do eventually is 'Inverted paging scheme' , here we indexing of page table corresponds to number of frames rather than number of pages. so as there would be only few frames compare to pages , only currently useful entries would be present in page table.

in normal paging page table entry will store frame number and some protection bits and they are indexed on the bases of page numbers but in Inverted paging , page table entry will store page number and they are indexed on the bases of frame numbers. in normal paging you can directly go to required page number (O(1) time)  in page table to get the corresponding frame , but in inverted paging , as they are indexed on the bases of frames , you have to search each and every entry to know the required page for which you want to access frame , and in that way you have to access every entry and so complexity would be O(n) that is drawback of inverted paging...

to know more prefer those sites

https://en.wikipedia.org/wiki/Page_table

http://www.cs.cornell.edu/courses/cs4410/2017su/lectures/lec12-ipt.html

http://people.duke.edu/~tkb13/courses/ece250/resources/umass-trekp-csc262-lecture8-virtualmemory.pdf

https://web.eecs.umich.edu/~akamil/teaching/sp04/040104.pdf

Answer 2

I try to simplify these question so that you get the better idea.

In paging, the index of the page table is a page number and every process has its own page table.

While in Inverted Paging, the frame number is used as an index of the page table that why the number of an entry in the page table is equal to the number of the frame in main memory. There is single inverted page table for all process in main memory, not indivual for the different process.