Lecture 21 (contd)

The crux

How to make page tables smaller

Why does size matter?

• 32-bit address space, 4KB pages \(\Rightarrow\) 20-bit VPN and 12-bit offset
• 20-bit VPN \(\Rightarrow 2^{20}\) translations
• 4 bytes/page table entry (PTE) \(\Rightarrow 4MB\) of memory needed for each page table!
• \(100\) processes would need 400MB of memory just for all those address translations!

Simple solution: Bigger pages

Example

• 32-bit address space but 16KB pages \(\Rightarrow\) 18-bit VPN and 14-bit offset
• 4 bytes/page table entry (PTE) \(\Rightarrow 1MB\) of memory needed for each page table

 

Problem with bigger pages?

• internal fragmentation

What a waste!

A 16KB Address Space With 1KB Pages	Page Table For 16KB Address Space

Hybrid Approach: Paging and Segments

• In order to reduce the memory overhead of page tables
  • Using base not to point to the segment itself but rather to hold the physical address of the page table of that segment
  • The bounds register is used to indicate the end of the page table

Example: Hybrid approach

32-bit address space with 4KB pages

Seg value	Content
00	unused segment
01	code
10	heap
11	stack

Three base/bounds pairs per process

• Base: physical address of a linear page table for that segment
• Bounds: indicated end of PT
• What happens on a TLB miss?

TLB miss on Hybrid Approach

• HW uses the segment bits to determine which base and bounds pair to use.
• HW then takes the PA and combines it with VPN to form the address of PTE

SN           = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN          = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

Hybrid approach: pros and cons

Advantage over linear page table

Disadvantages

Lecture 22

Multi-level PT

• Chop up the PT into page-sized units
• If an entire page of PTEs is invalid, don’t allocate that page of the PT

Data structure

Page directory: To track whether a page of the PT is valid

Linear vs. multi-level PTs

Page directory entry (PDE)

• PD contains one entry per page of the page table
  • It consists of a number of PDEs
• PDE has a valid bit and PFN

Poll: Advantages and disadvantages of multi-level PTs

Multi-level PT

Advantages

• Only allocates PT space in proportion to the amount of address space used
• Each portion of PT fits can be made to fit within a page, making it easier to manage memory

Disadvantages

• TLB miss is costlier
• Complexity

Detailed example

16-KB address space with 64-byte pages

Detailed example (contd)

• 14-bit address space, 64-byte pages \(\Rightarrow\) 8-bit VPN and 6-bit offset
• Linear PT \(\Rightarrow 2^{8}\) entries in PT
• 4 bytes/PTE \(\Rightarrow 1KB\) of memory needed for each PT
• 64 bytes page \(\Rightarrow\) PT divided into 16 pages
• Number of entries in the page directory is
• 16

Detailed example (contd)

• Top \(4\) bits are the page directory index (PDindex)
• \(PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))\)
• If PDE is not valid, raise an exception, let OS handle it
• Else, see the fig below

• Page Table Index(PTindex) used to index into the page table itself.
• fetch the PTE from the page of the PT pointed to by this PDE
• to fetch this PTE, use the remaining bits of VPN: \(PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))\)

Lecture 23

A Page Directory, And Pieces Of Page Table

• Page containting first 16 VPN mappings of the PT
• Valid VPNS: 0,1 of code and 4,5 of heap, so PFN 100 has useful information
• PFN 101 has useful information related to the last 16 VPNs (valid mappings from stack)
• **Savings:*
• Linear PT: \(16\) pages allocated for \(256\) entry PT
• Two-level PT: \(3\) pages: one for page directory, two valid pages for heap and stack

Address translation in the detailed example

• Address: 0x3F80, or 11 1111 1000 0000 in binary
  • 8-bit VPN \(\Rightarrow\) VA refers to the 0th byte of VPN 254
• 1111 will choose the last (15th, if you start at the 0th) entry of the page directory
• This maps to PFN 101
• Next 4 bits 1110 is the VPN
• PTE says PFN is 55 for this VPN
• \(PhysAddr = (PTE.PFN << SHIFT) + offset = 00 1101 1100 0000 = 0x0DC0\)

Two-level Page Table Control Flow

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)   // TLB Hit
  if (CanAccess(TlbEntry.ProtectBits) == True) 
    Offset = VirtualAddress & OFFSET_MASK 
    PhysAddr = (TlbEntry.PFN << SHIFT) | Offset 
    Register = AccessMemory(PhysAddr)
  else
      RaiseException(PROTECTION_FAULT)
else // TLB Miss
  // first, get page directory entry
PDIndex
PDEAddr
PDE
if (PDE.Valid == False)
= (VPN & PD_MASK) >> PD_SHIFT
= PDBR + (PDIndex * sizeof(PDE)) = AccessMemory(PDEAddr)
    RaiseException(SEGMENTATION_FAULT)
else
  // PDE is valid: now fetch PTE from page table
  PTIndex = (VPN & PT_MASK) >> PT_SHIFT
  PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE)) 
  PTE = AccessMemory(PTEAddr)
  if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
  else if (CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT)
  else
      TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits) 
      RetryInstruction()

Other things

• One can extend multi-level PT to more than two levels leading to a deeper tree
  • flip side?
• Inverted page tables:
  • Instead of having one PT per proc, keep a single PT that has an entry for each physical page of the system.
  • Map PFN to VPN along with ASID
  • speed up using hashing