The most common techniques for structuring the page table

• Hierarchical Paging

  Most modern computer systems support a large logical-address space. In such an environment, the page table itself becomes excessively large. The one page table already isn’t enough for so large space.

  One simple solution to this problem is to divide the page table into smaller pieces. There are several ways to accomplish this division.

  One way is to use a two-level paging algorithm, in which the page table itself is also paged.

  • forward-mapped page table

    A page is divided into two page. Using a page to find other page. The address translation works from the outer page table inward.

    The Pentium-II uses this architecture.

  • section

    The VAX architecture also support a variation of two-level paging. The VAX is 32-bit machine with page size of 512 bytes.

    The logical-address of a process is divided into four equal sections, each of which consists of 2³⁰ bytes.

    Each section represents a different part of the logical-address space of a process. The first 2 high-order bits of the logical address designate the appropriate section.

    By partitioning the page table in this manner, the operating system can leave partitions unused until a process needs them.

  Disadvantage

  For 64-bit : For a system with a 64-bit logical-address space, a two-level paging scheme is no longer appropriate. The outer page will become large. The obvious method to avoid such a larger table is to divide the outer page table into smaller pieces. This approach is also used on some 32-bit processors for added flexibility and efficiency.

  However, for 64-bit architectures, hierarchical page tables are generally considered inappropriate.

A common approach for handling address spaces larger than 32 bits is to use a hased page table, with the hash value being the virtual-page number. Each entry in the hash table contains a linked list of elements that hash to the same location (to handle collisions).

Each element consists of three fields:

1. the virtual page number
2. the value of the mapped page frame
3. a pointer to the next element in the linked list.

Algorithm

The virtual page number in the virtual address is hased into the hash table.

The virtual page number is compared to field(1) [the virtual page number] in the first element in the linked list.

If there is a match, the corresponding page frame( field(2) [the value of the mapped page frame] ) is used to form the desired physical address.

If there is no match, subsequent entries in the linked list are searched for a matching virtual page number.

Clustered page tables

A variation to this scheme that is favorable for 64-bit address spaces has been proposed.

Clustered page tables are similar to hased page tables except that each entry in the hash table refers to several pages (such as 16) rather than a single page. Therefore, a signle page-table entry can store the mappings for multiple physical-page frame.

Clustered page tables are particularly useful for sparse address spaces where memory reference are nocontiguous and scattered throughout the address space.

• Face the problem

  The table is sorted by virtual address, the operating system is able to calculate where in the table the associated physical-address entry is, and to use that value directly.

  One of the drawbacks of this method is that each page table may consist 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.

• Inverted Page Table

  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.

  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. Storing the address-space identifier ensures the mapping of a logical page for a particular process to the corresponding physical page frame.

  The system used inverted page tables include the 64-bit UltraSPARC and PowerPC

  • Simple virtual memory address
    <process-id, page-page, 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 as been attempted.

  • The problem

    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 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.

  • The improvement for this problem

    To alleviate this problem, we use a hash table to limit the search to one – or at most a few – page-table entries.

    Of course, each access to the hash table adds a memory reference to the procedure, so one virtual-memory reference require at least two real-memory reads:
    one for the hash-table entry
    one for the page table

    To improve performance, recall that the TLB is search first, before the hash table is consulted.

The sharing common code is particularly important in a time-sharing environment.

If the code is reentrant code, it can be shared. Reentrant code (or pure code) is non-self-modifying code. If the code is reentrant, then it never changes during execution. Thus, two or more processes can execute the same code at the same time. Each process, has own copy of registers and data storage to hold the data for the process’ execution. The data for two different processes will, of course, vary for each process.

Other heavily used programs can also be shared – compilers, window system, run-time libraries, database system, and so on.

To be sharable, the code must be reentrant. The read-only nature of shared code should not be left to the correctness of the code; operating system should enforce this property.

This sharing of memory among processes on a system is similar to the sharing of the address space of a task by threads.

Some operating systems implement shared memory using shared pages.

Systems that use inverted page tables have difficulty implementing shared memory. 
Shared memory is usually implemented as multiple virtual addresses (one for each process sharing the memory) that are mapped to one physical address.
This standard method cannot be used, however, as there is only one virtual page entry for every physical page, so one physical page cannot have two (or more) shared virtual addresses.

Organizing memory according to pages provides numerous other benefits in addition to allowing several processes to share the same physical pages.