[virtual memory] recap

Recap

Program address in linux/elf

Virtual Memory is used due to:

• RAM is not sufficient
• Holes in address space
• Programs writing over each other

Programs can access any byte in their 64-bit address space

Page Out

• While not enough memory, paging out(base on different algorithm) for free physical memory and flush data into next level storage system(usually disk)

    

Page Tables

• Page Table Entry(PTE) (usually 4kb page size (32bit) or 2mb (64bit))

Page faults (slow)

• Pages not in RAM
• CPU generates a page fault exception caught by OS
• OS flush out data from memory to give room for data on disk

Virtual Address <-> Page Table <-> Physical Address(PA)

Virtual Address layout: (2^32 or 2^64 physical memory wide)

20bit virtual page number (virtual page number, map to physical page number) + 12bit page offset (does not get translated into PA, the size 

depends on page size, e.g 4KB we need 2^12, 12 bits offset, i.e 2^12 = 4096 bytes = 4KB, remember, in memory, the basic unit is byte)

Physical Address layout: (2^N where N is the size of physical memory are installed on this box)

16bit physical page number + 12bit page offset (same as VA's page offset)

Page Table Size

Page table remains in the memory all the time, for lookup.

Page Table Lookup

Page Table Indirect

How to make virtual memory FAST?

List operations:

• Access the page table in RAM
• Translate the address
• Access the data in RAM

Cache for page table: Translation Lookaside Buffer(TLB)

    Virtual Address <-> TLB(small and fast) <-> PA

TLB should be small

• iTLB (for instructions)
• dTLB (for data)
• Second TLB
• 64 entries, 4 way (4kb pages)
• 32 entries, 4 way (2mb pages)

i.e If program runs in 4kb/2mb pages of data, there's no update needed for TLB.

Good: Page in RAM

• PTE (page table entry) in the TLB
• PTE not in the TLB

Bad: Page not in RAM

• PTE in the TLB(unlikely)
• PTE not in the TLB

TLB layout

tag + physical page number

• tag: physical memory index (virtual address(VA)'s virtual page number)
• physical page number: physical address

TLBs and CPU caches(L1/L2/L3)

• Physical Cache (slow, must do TLB lookup before accessing the cache)
• Virtual Cache (fast, TLB lookups only when having a cache miss)

VIPT (Virtually Indexed, Physically Tagged)

• Data in the cache in indexed by the virtual address
• But tagged by the physical address
• Only get a hit if the tag matches the physical address, but can start looking with the virtual address
  i.e TLB translation and Cache lookup at the same time(in parallel).

Reference:
David Black-Schaffer - virtual memory