---

1. Linear Page Table

Most of the page table is unused, full of invalid entries.

---

2. Segment Tables

Base and bounds registers for each segment

Example: 32-bit virtual address space, 4KB pages, three segments: code, heap, stack

2-bit segment selector: 00 unused, 01 code, 10 heap, 11 stack

TLB miss handling:

  SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT

  VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT

  AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

specify SEG_MASK, SN_SHIFT, VPN_MASK, VPN_SHIFT: ________________

---

3. Two-level Page Tables

page directory: PDE = page directory entry, PFN = page frame number

---

4. 16KB Example

Address space size 16KB with 64-byte pages: 14-bit virtual address = 8 bits VPN + 6 bits offset

Linear page table would have 2⁸=256 entries

Example with virtual pages 0 and 1 used for code, 4 and 5 for the heap, 254 and 255 for the stack:

---

5. 16KB Example with Page Directory

256 page table entries * 4 bytes each = 1 KB = 16 * 64-byte pages with 16 PTEs per page

4 bits to index one of the 16 entries in the page directory:

  PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))

4 bits to index one of the 16 PTEs:

  PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))

---

6. Page Directory Example

PDIndex 0, 15 valid; PFN 100 PTIndex 0, 1, 4, 5 valid; PFN 101 PTIndex 14, 15 valid

VA = 0x3f80 = 1111 1110 000000 = PDIndex + PTIndex + offset

PDIndex = 15 --> PFN 101; PTIndex = 14 --> 55 (00110111); PhysAddr = 00110111 000000 = 3520

---

7. Multi-level Page Tables

30-bit virtual address space, 512 byte page = 21-bit virtual page number + 9-bit offset

PTE size 4 bytes --> 128 PTEs per page --> 7-bit PTIndex --> 14-bit PDIndex

2¹⁴ 4-byte page directory entries --> 128 pages

---

Split page directory into two levels:

2⁷ 4-byte page directory entries --> 1 page

---

8. Opteron Page Tables

The Opteron uses 48-bit virtual addresses and 40-bit physical addresses.

The upper 16 bits of the virtual address are just the sign extension of the lower 48 bits.

(from Hennessy & Patterson)

---

9. Exercises

Exercises from the book using paging-multilevel-translate.py:

1. With a linear page table, you need a single register to locate the page table, assuming that hardware does the lookup upon a TLB miss. How many registers do you need to locate a two-level page table? A three-level table?

2. Use the simulator to perform translations given random seeds 0, 1, and 2, and check your answers using the -c flag. How many memory references are needed to perform each lookup?

3. Given your understanding of how cache memory works, how do you think memory references to the page table will behave in the cache? Will they lead to lots of cache hits (and thus fast accesses?) Or lots of misses (and thus slow accesses)?