CS537 10/5

Brief

Virtual Memory

• Goal: each process with illusion (own large private memory)
• Three techniques
  • Base/Bounds & Segmentation
    • Variable-sized allocation
    • External Fragmentation
  • Paging
    • Fixed-sized units (pages)
    • No external fragmentation
    • Too slow
    • Too big

Structure of Page Table:

Linear (Arrays)

• One entry in Page table per virtual page
• V: valid bit (set by OS)
• Protection: R/W/X

Problem: Large Virtual Address Space (32bit, 64bit)

• 32 Bit, 4KB Page => ~1 Million ($2^{20}$) Virtual Pages
• Size: $2^{20}; \times$ PTE size (4 Byte) = 4MB
• 300 Processes = 300 $\times$ 4 MB = ~1.2GB of memory

Analyze

• 32-bit VA space, 4 KB pages
• Most system set page 0 as invalid because want to catch NULL pointer access

How to Make Smaller Tables?

Technique #1 Hybrid

• Paging and Segmentation
  • 
  • 1 page table per segment (per process)
  • per segment: base/bounds
    • Base: page table for this segment resides
    • Bounds: Size of page table (of that segment)
  • Page Table for segment 0:
    • |v|proct|----PFN----|
    • base: point to the start
    • bounds: 1
  • Problems
    • Reintroduce external fragmentation (Just for pieces of page table)

Technique #2 Multi-level Page Table (~Tree)