Inverted Page Table
Need of Inverted Page table
Most of the Operating Systems use a separate page table for each process as in normal paging. In normal paging if there are 100 process then 100 will be the page tables in main memory. Sometimes when a process size is very large then its page table size also increases considerably. Through inverted page table, the overhead of storing an individual page table for each process is removed. A global page table is used which is utilized by all processes.
Example: If A process size is 2 GB with Page size = 512 Bytes and page table entry size is 4 Bytes, then
- Number of pages in the process = 2 GB / 512 B = 222
- Page Table Size = 222 * 22 = 224 bytes
If multiple processes running simultaneously in an OS with large sizes, then a considerable amount of memory is occupied by page tables only.
Various efforts are made to utilize the memory efficiently and to maintain a good balance in the level of multi-programming and efficient CPU utilization.
In inverted page table indexing is done with frame numbers instead of the logical page number. Each entry in the page table contains the following fields.
- Frame No: It specifies the Frame where the page no is actually present in main memory
- Page number:It specifies the page number which is required.
- Process id: An inverted page table contains pages of all the processes in execution. So page No may be same of different process but Process Id of each process is unique. Through Process ID we get the desired page of that process.
- Control bits –These bits are used to store paging table entry information. These include the valid/invalid bit, protection, dirty bit, reference bits, and other information bit.
- Chained pointer:It is possible when two or more processes share some part of main memory. In simple words, when two or more logical pages need to map to same Page Table Entry then a chaining pointer is used.
No of frames in main memory = No of entries in Inverted page table
We have to linear search as we want to find page 2 of process 3 then
The logical address generated by the CPU contains Process ID, Page No, and Page Offset.
Through searching in Inverted Page Table, Process ID and Page No of logical address are compared with Process ID and Page No.
If match found then its corresponding frame number is obtained from page table entry otherwise page fault is occur and Demand paging comes into picture.
Note: No. of Entries in Inverted page table = No. of frames in Physical address Space
Advantages and Disadvantages:
- Reduced memory space
- Longer Search time
If It Is Useful Then Help Other’s By Sharing…