Page 168 - DCAP103_Principle of operating system

Unit 5: Memory Management

Notes
5.5.4 Hierarchical Paging
Most modern computer systems support a large logical-address space (Z3 to 2@). In such an
environment, the page table itself becomes excessively large. For example, consider a system
with a 32-bit logical-address space. If the page size in such a system is 4 KB (212), then a page
table may consist of up to 1 million entries (232/212). Assuming that each entry consists of 4
bytes, each process may need up to 4 MB of physical-address space for the page table alone.
Clearly, we would not want to allocate the page table contiguously in main memory. One simple
solution to this problem is to divide the page table into smaller pieces. There are several ways
to accomplish this division.

Figure 5.11: A Two-level Page-table Scheme

Remember our example to our 32-bit machine with a page size of 4 KB. A logical address is divided
into a page number consisting of 20 bits, and a page offset consisting of 12 bits. Because we page the
page table, the page number is further divided into a 10-bit page number and a 10-bit page offset.
Thus, a logical address is as follows—where p1 is an index into the outer page table and p2 is the

Figure 5.12: Logical Address

Page number Page offset

p1 p2 d

10 10 12

displacement within the page of the outer page table. The address-translation method for this
architecture is shown in Figure 5.14. Because address translation works from the outer page table
inwards, this scheme is also known as a forward-mapped page table. The Pentium-I1 uses this
architecture. The VAX architecture also supports a variation of two-level paging. The VAX is

LOVELY PROFESSIONAL UNIVERSITY 161