/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- 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.
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: 
. 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.
Another Example: DEC VAX
- Size of the outer page table (2K * 4 = 8 KB) is further paged, resulting in 3-level paging per section
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.
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.
Google +