Spread Knowledge

CS604 - Operating Systems - Lecture Handout 34

User Rating:  / 0

Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems


  • Protection under paging
  • Structure of the page table
    • Multi-level paging
    • Hashed page tables
    • Inverted page table

Protection under Paging

Memory protection in paging is achieved by associating protection bits with each page.
These bits are associated with each page table entry and specify protection on the corresponding page. The primary protection scheme guards against a process trying to access a page that does not belong to its address space. This is achieved by using a valid/invalid (v) bit. This bit indicates whether the page is in the process address space or not. If the bit is set to invalid, it indicates that the page is not in the process’s logical address space. Illegal addresses are trapped by using the valid-invalid bit and control is passed to the operating system for appropriate action. The following diagram shows the use of v bit in the page table. In this case, logical address space is six page and any access to pages 6 and 7 will be trapped because the v bits for these pages is set to invalid.

protection under paging

One bit can define the page table to be read and write or read only. Every reference to memory goes through the page table to find the correct frame number. At the same time that the physical address is being computed, the protection bits can be checked to verify that no writes are being made to a read only page. An attempt to write to a read-only page causes a hardware trap to the operating system (memory-protection violation).
This approach can be expanded to provide a finer level of protection. Read, write, and execute bits (r, w, x) can be used to allow a combination of these accesses, similar to the file protection scheme used in the UNIX operating system. Illegal attempts will be trapped to the operating system.

Structure of the Page Table

As logical address spaces become large (32-bit or 64-bit), depending on the page size, page table sizes can become larger than a page and it becomes necessary to page the page the page table. Additionally, large amount of memory space is used for page table. The following schemes allow efficient implementations of page tables.

  • Hierarchical / Multilevel Paging
  • Hashed Page Table
  • Inverted Page Table

Hierarchical/Multilevel Paging

Most modern computers support a large logical address space: Multilevel Paging. In such an environment, the page table itself becomes excessively large. Consider the following example:

  • Logical address = 32-bit
  • Page size = 4K bytes (212 bytes)
  • Page table entry = 4 bytes
  • Maximum pages in a process address space = 232 / 4K = 1M
  • Maximum pages in a process address space = 232 / 4K = 1M
  • Page table size = 4M bytes

This page table cannot fit in one page. One solution is to page the page table, resulting in a 2-level paging. A page table needed for keeping track of pages of the page table— called the outer page table or page directory. In the above example:

  • No. of pages in the page table is 4M / 4K = 1K
  • Size of the outer page table is 1K * 4 bytes = 4K bytes ⇒ outer page will fit in one page

In the 32-bit machine described above, we need to partition p into two parts, p1 and p2. p1 is used to index the outer page table and p2 to index the inner page table. Thus the logical address is divided into a page number consisting of 20 bits and a page offset of 12 bits. Since we page the page table, the page number is further divided into a 10-bit page number, and a 10-bit page offset. This is known as two-level paging. The following diagram shows division of the logical address in 2-level paging and hierarchical views of the page table.

Hierarchical-Multilevel Paging

Another Example: DEC VAX

Another Example  DEC VAX

  • Size of the outer page table (2K * 4 = 8 KB) is further paged, resulting in 3-level paging per section

outer page table

More Examples

  • 32-bit Sun SPARC supports 3-level paging
  • 32-bit Motorola 68030 supports 4-level paging
  • 64-bit Sun UltraSPARC supports 7-level paging – too many memory references needed for address translation

Hashed Page Table

This is a common approach to handle address spaces larger then 32 bits .Usually open hashing is used. Each entry in the linked list has three fields: page number, frame number for the page, and pointer to the next element—(p, f, next). The page number in the logical address (specified by p) is hashed to get index of an entry in the hash table. This index is used to search the linked list associated with this entry to locate the frame number corresponding to the given page number. The advantage of hashed page tables is smaller page tables.

Hashed Page Table

Inverted Page Table

Usually each process has a page table associated with it. The page table has one entry for each page in the address space of the process. For large address spaces (32-bit and above), 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 mapping of logical address spaces of processes onto the physical memory.
A solution is to use an inverted page table. An inverted page table has one entry for each real page (frame) of memory. Each entry consists of the virtual address of the page stored in the in that real memory location, with information about the process that own the page.

Page table size is limited by the number of frames (i.e., the physical memory) and not process address space. Each entry in the page table contains (pid, p). If a page ‘p’ for a process is loaded in frame ‘f’, its entry is stored at index ‘f’ in the page table. We effectively index the page table with frame number; hence the name inverted page table.
Examples of CPUs that support inverted pages tables are 64-bit UltraSPARC and PowerPC. The following diagram shows how logical addresses are translated into physical addresses.

Address translation with inverted page table