Structure of the Page Table

Structure of the Page Table

AU May-17, 19, 22

Multilevel or Hierarchical Page Table

• Page tables can consume a significant amount of memory.

• For example: A 32-bit virtual address space using 4 kB pages.

Page size = 2¹² bytes

Space for page numbers = 2³² - 2¹²

= 2²⁰ bytes

• So page table may consists of upto 1 million entries, one for each page, for a total address capacity of about four billion bytes.

• Hierarchical page table is also called as forward mapped page table. This approach is so effective that many modern operating systems employ it.

• In this method, each level containing a table that stores pointers to tables in the level below. Each table in the hierarchy is the size of one page. It enables the operating system to transfer page tables between main memory and secondary storage device easily.

For two levels of page table

Virtual address contains page number and displacement into that page.

Virtual address (v) = (p, t, d)

Where           (p, t)=Page number

d = Displacement

• Here p is an index into the outer page table.

• Fig. 4.6.1 shows hierarchical page table.

• Intel IA - 32 architecture support two levels of page

Advantages

1. It is compact and support sparse address space.

2. It easily manage the memory.

3. It reduce table fragmentation.

Disadvantages

1. Overhead due to one more page table.

2. On TLB miss, two loads from memory will be required to get the right address translation information from the page table.

Hashed Page Tables

• Hashed page table support address space of 32 bits and more. Hash value is used as virtual page number.

• Hash table contains a link list of elements. Each elements consists of following fields :

1. Virtual page number

2. Mapped page frame value.

3. Pointer to the next element. Hash table improves search speed.

Fig. 4.6.2 shows block diagram of hashed

Working

1. Virtual page number is taken from virtual address.

2. Virtual page number is hashed into the hash table.

3. Virtual page number is compared with the first element of linked list.

4. Both the value is matched, that value is (i.e. page frame) used for calculating physical address.

5. If the both value is not matched, the entire linked list is searched for a matching.

• Clustered page table is same as hashed page table but only difference is that each entry in the hash table refers to several pages.

Inverted Page Table

• It uses a page table that contains an entry for each physical frame. This ensure that the page table occupies a fixed fraction of memory. The size is proportional to the physical memory.

• Page table overhead increases with address space size. Page table get too big to fit in memory.

• Inverted page table has one entry for each real page of memory. Lookup time is increased because it requires a search on the inverted table.

• Logical address is as follows

• Inverted page table is used by Itanium, Power PC and Ultra SPARC.

University Questions

1. Discuss the given Memory Management techniques with diagrams: Paging and Translation Look-aside Buffer. AU May-17, Marks 6

2. i) Consider a computer system with 16 bit logical address and 4 KB page size. The system supports upto 1 MB of physical memory. Assume that the actual process size is only 33 KB, page table base register contains 1000 and free frame list contains 13,11,9,7,5,3,1,2,4,6,8.

Construct the physical and logical memory structures, page table of the corresponding process. Find the physical address of 13,256 and another logical address with page number 2 and offset of 128. Discuss about the possible valid-invalid bit and possible protection bits in page table. AU May-19, Marks 8

3. Consider a paging system with page table stored in stored in memory.

1) If a memory reference with takes 50 ns, how long does a paged memory reference take?

2) If we add TLB and 75 % of all page table references are found in TLB, what is the effective memory reference time? (Assume that find a page entry in TLB takes 2 ns, if entry is present). AU May-19, Marks 8

4. Explain briefly about the hardware implementation of page table. AU May-19, Marks 5 AU May-22, Marks 13