Page 171 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes of the latter’s validity). This table representation is a natural one, since processes reference pages
through the pages’ virtual addresses. The operating system t of millions of entries. These tables
may consume large amounts of physical memory, which is required just to keep track of how
the other physical memory is being used.
To solve this problem, we can use an inverted page table. An inverted page table has one entry
for each real page (or frame) of memory. Each entry consists of the virtual address of the page
stored in that real memory location, with information about the process that owns that page.
Thus, only one page table is in the system, and it has only one entry for each page of physical
memory. which depicts a standard page table in operation. Because only one page table is in the
system yet there are usually several different address spaces mapping physical memory, inverted
page tables often require an address-space identifier stored in each entry of the page table.

Figure 5.18: Inverted Page Table

Storing the address-space identifier ensures the mapping of a logical page for a particular process
to the corresponding physical page frame. Examples of systems using inverted page tables include
the 64-bit UltraSPARC and PowerPC. To illustrate this method, we describe a simplified version
of the implementation of the inverted page table used in the IBM RT. Each virtual address in the
system consists of a triple <process-id, page-number, offset>. Each inverted page-table entry is
a pair <process-id, page-number> where the process-id assumes the role of the address-space
identifier. When a memory reference occurs, part of the virtual address, consisting of <process-id,
page number>, is presented to the memory subsystem. The inverted page table is then searched
for a match. If a match is found-say, at entry i-then the physical address <i, offset> is generated.
If no match is found, then an illegal address access has been attempted.
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 sorted by a physical address, but lookups occur on virtual addresses,
the whole table might need to be searched for a match. This search would take far too long. Of
course, each access to the hash table adds a memory reference to the procedure, so one virtual-
memory reference requires at least two real-memory reads one for the hash-table entry and
one for the page table. To improve performance, recall that the TLB is searched first, before the
hash table is consulted.

164 LOVELY PROFESSIONAL UNIVERSITY