CS537 9/28

Brief

• Virtual Address technique
  • Base/Bounds
  • Segmentation
  • Paging

Problems with Segmentation:

• external fragmentation:
  • free space becomes full of small used spots and free spots intermixed
• not fully flexible
  • Internal fragmentation
    • e.g. “sparse” heap
    • (data in top and bottom of heap, even though middle part is unused must keep in memory)

New Approach: Paging

• divide virtual address space into small(4KB), fixed-sized units call pages
• similarly, divide physical memory into 4Kb page frames
• 
• Free space management: easy (e.g. free list of phys pages)

Address Translation: Virtual Addr => Phys. Addr

• e.g. virtual address space: 32-bit, page size: 4kb, how many pages? $2^{20}$ pages
• virtual address: |---virtual page number (20bits)---|--offset (12bits)--|

Problem: A Lot of Pages!

• e.g. $2^{20}$ (Per Process) (a lot of information)
• Where to store? Main Memory (Manage by OS) “Page Table”

Page Table

• e.g. 1kb page size, 8192 bytes virtual address, 8 frames

• Virtual Page Number	Physical Frame Number	Valid
  0	10	1
  1	21	1
  2		0
  3		0
  4		0
  5		0
  6		0
  7		0
  8	100	1

• naturally supports “sparse” addr. space

First Page Table: Linear Page Table

• Virtual Page Number is the index
• virtual address: |--VPN--|--offset--|

Translation

• Base address of page table: $B$
• Page Table Entry: $B+(VPN\times sizeof(page;table;entry))$
• Load full PTE from memory extract PFN (Problem: 2x mem access)
• Form full phys. addr: |--PFN--|--offset--|
• SLOW