A page table is maintained by the operating system on a per process basis. Every process has its own page table, and that is why we do not need to store any process identifier(s) in the page table. Page table maps a given logical/virtual page number to actual physical frame/page address.
The logical address for a memory reference is of the form:
Logical Address: <virtual page number (p), offset (d)>
Page-number (virtual page number) is used to perform look up into the page table and get the base address of the physical frame it is mapped to. The frame’s base address (f) is then combined with offset into the page (d) to get the physical memory frame address as:
f = page-table[p]
Physical Address: <physical frame address (f), offset (d)>
Now, consider a system with:
1. logical address space: 32-bit
2. page size: 4KB (2^12)
3. page table entry size: 4 bytes
4. physical memory: 2GB
Please note that 4 bytes of a page table entry effectively stores multiple types of information apart from the base address of physical frame. This information can be for memory protection(valid/invalid bit), type of access(read/write), bookkeeping etc. So, when I refer to physical frame address (f), I actually refer to this particular part of the 4 byte entry.
Let’s calculate the size of a page table:
Size of the page table = (No. of entries * size of each entry).
Given the above parameters, a 32-bit logical address will be partitioned into:
<(2^32)/(2^12) bits for page number, 12 bits for offset into page> or
<20 bits for page number, 12 bits for offset into page>.
We can now calculate that number of entries in the page table (total virtual page numbers) can be as large as 2^20. Hence, the size of page table would be :
(2^20) * 4bytes = 4MB of space (per process).
This much of space would be required in physical memory for the page table of every process. Don’t forget we have only 2GB of main memory, and having 4MB of that space for page table of every process may not be a good idea. Also, many of the virtual addresses might not have any physical page address mapped to them. But, still the page table size will be large. Even if the “valid” bit is not set for a virtual page number, a slot for it will have to exist in the page table.
In case of shared memory, having a page table per process will require an entry of the same physical page in the page table of every process that is having a shared access to that page. Thus the system will end up keeping multiple entries for the same physical frame address. Not a very good utilization of physical memory.
We can also understand that a page table for every process will contain one entry per virtual address. The size of the table is thus proportional to the size of logical/virtual address space which can actually turn out to be enormous.
Our goal is reduce/optimize the amount of physical memory required to store the page tables. Inverted page table is one such solution.
Inverted page table is a global page table maintained by the operating system for all the processes. There is just one page table in the entire system, implying that additional information needs to be stored in the page table to identify page table entries corresponding to each process.
It stores one entry per physical frame, and is a linear array where the contents at each location is <pid (process id), virtual page number> and the index of each location is the physical frame address. The formula will change now:
<pid (id), virtual page number (p)> = page-table[f]
This straightaway implies that look-ups can no more happen on the virtual page number. The entire table has to be searched entry-by-entry to find a matching entry having the pid equal to “id” and virtual page number equal to “p”. The index location corresponding to the match is the physical frame address (f), which then combined with the offset(d) gives the physical address.
We can easily infer that look-up time in an inverted page table may be significantly higher when compared to a simple page table.
However, because the table stores one entry per physical frame address and there is a single page table in the entire system, the amount of memory used by the inverted page table has reduced considerably. How ?
Consider the same parameters again:
1. logical address space: 32-bit
2. page size: 4KB (2^12)
3. page table entry size: 4 bytes.
4. physical memory: 2GB (2 ^31)
Number of entries in the page table = Number of physical pages =
(2^31)/(2^12) = 2^19 physical pages or frames.
Let’s say we use 1 byte process identifiers. Size of each page table entry would be:
8 bits (PID)+20bits (virtual page number)+4bits (access information) = 32 bits = 4 bytes.
Size of the page table = (2^19) *4 = 2MB for the entire system.
Performance of inverted page tables is usually addressed through hashed page tables. But, there is one more disadvantage of using inverted page tables apart from performance. It is shared memory.
Because there is one and only one entry in the page table per physical frame, and that contains exactly one virtual page number, we no longer can map the same physical frame to multiple virtual page numbers in different processes. There are ways around this, but I am not very sure of the details.
Source — Operating System Concepts ( Silberschatz et al).
Loonytek - Delving into Tech 
Leave a Reply