What is inverted page table how does it compare to two level page table?
Answers
Answered by
0
Before we explain how inverted page table works, let us first mention why is it called inverted. Normal page tables map virtual pages into physical memory frames. In an inverted page table, for each occupied physical memory frame there is an associated virtual page. It is inverted in the sense that we look at mapping starting from a physical memory frame back to a virtual page though the actual address translation starts with a virtual page all the way to a physical memory frame just like a normal page table. I know, sometimes terminology is confusing. Anyway, what is an inverted page table ?
The idea behind inverted page tables is to have a single page table on the operating system level that is not tied to any specific process. It is based on the observation that the CPU only references entries in those pages that are already present in memory. The number of pages that are present in physical memory frames are far less than the total number of virtual pages that are on disk. Having a single table that maps occupied memory frames to virtual pages consumes far less space than having a page table for each process that is big enough to fit all virtual pages.
Inverted page table address translation
Given a process ID and a virtual page number, we need to search the inverted page table for a match. Linear lookup takes time so using an efficient data structure like a hash table is appealing. Here is how the translation takes place:
Hashed inverted page table
Hash the (process ID and virtual page number).The inverted page table hash function gives us an index to the hash table.Use that index to get the physical frame number if the stored process ID and virtual page number at that index location match the input process ID and virtual page number.If they do not match (different process ID or different virtual page number) then that is a collision.In this case, follow the pointer to the next link in the chain until you get a match.If all entries in the chain are checked without a match. This means a miss or a page fault.In practice, the number of entries in the hash table should be larger than the number of physical pages in order to reduce hash table collisions.
The idea behind inverted page tables is to have a single page table on the operating system level that is not tied to any specific process. It is based on the observation that the CPU only references entries in those pages that are already present in memory. The number of pages that are present in physical memory frames are far less than the total number of virtual pages that are on disk. Having a single table that maps occupied memory frames to virtual pages consumes far less space than having a page table for each process that is big enough to fit all virtual pages.
Inverted page table address translation
Given a process ID and a virtual page number, we need to search the inverted page table for a match. Linear lookup takes time so using an efficient data structure like a hash table is appealing. Here is how the translation takes place:
Hashed inverted page table
Hash the (process ID and virtual page number).The inverted page table hash function gives us an index to the hash table.Use that index to get the physical frame number if the stored process ID and virtual page number at that index location match the input process ID and virtual page number.If they do not match (different process ID or different virtual page number) then that is a collision.In this case, follow the pointer to the next link in the chain until you get a match.If all entries in the chain are checked without a match. This means a miss or a page fault.In practice, the number of entries in the hash table should be larger than the number of physical pages in order to reduce hash table collisions.
Similar questions