[CS:APP-ch9] Virtual Memory

CS:APP ch-9 Virtual Memory

Virtual Memory

  • modern systems provide an abstraction of main memory

three important capabilities

  1. It uses main memory efficiently by treating it as a cache for an address space stored on disk, keeping only the active areas in main memory, and transferring data back and forth between disk and memory as needed.
  2. It simplifies memory management by providing each process with a uniform address space.
  3. It protects the address space of each process from corruption by other processes.

9.1 Physical and Virtual Addressing

Main memory organized as an array of M contiguous byte-size cells, each byte has a unique physical address.

Physical Addressing: use physical address ( PA ) to access memory

Virtual Addressing: use virtual address ( VA ) and translate to physical address

Addressing Translation: converting a virtual address to a physical one

9.2 Address Spaces

Virtual Address Space

  • CPU generates virtual addresses from an address space of $ N = 2^n $ addresses called the virtual address space {0 , 1, 2 ,…,N − 1}

Physical Address Space

  • A system also has a physical address space that corresponds to the M bytes of physical memory in the system {0 , 1, 2 ,…,M − 1}

9.3 VM as a Tool for Caching

A virtual memory is organized as an array of N contiguous byte-sized cells stored on disk. Each byte has a unique virtual address that serves as an index into the array.

VM systems partition the virtual memory into fixed-size blocks call Virtual Pages ( VP ) as transfer units between disk and main memory.

Three sets of VP: Unallocated, Cached, Uncached

DRAM cache organization

  1. large virtual pages ( cache block )( 4 KB to 2 MB )
  2. fully associative
  3. sophisticated replacement algorithms
  4. use write-back

Page Tables

A data structure stored in physical memory that maps virtual pages to physical pages.

Page Hit

Check valid bit, uses the physical memory address in the PTE (which points to the start of the cached page in PP 1) to construct the physical address of the word.

Page Faults

The page fault exception invokes a page fault exception handler in the kernel

  1. selects a victim page, in this case VP 4 stored in PP 3.
  2. modifies the page table entry for VP 4 to reflect the fact that VP 4 is no longer cached in main memory.
  3. copies VP 3 from disk to PP 3 in memory, updates PTE 3, and then returns.
  4. restarts the faulting instruction and page hit
  5. The strategy of waiting until the last moment to swap in a page, when a miss occurs, is known as demand paging

9.4 VM as a Tool for Memory Management

Operating systems provide a separate page table, and thus a separate virtual address space, for each process.

  1. Linking: Allow each process to use the same basic format for its memory image ( code segment always start at 0x400000 )

  2. Loading: (1) Allocate Virtual Pages (2) Mark as invalid ( not cached ) (3) Point table entries to the location of in object file (4) Data are paged in th first time referenced

  3. Sharing: Multiple processes share a single copy of some code

  4. Memory Allocation

9.5 VM as a Tool for Memory Protection

three permission bits to each PTE

  • SUP must run in kernel mode

9.6 Address Translation

a mapping between an N-element virtual address space and M-element physical address space

Steps that the CPU hardware performs when there is a page hit / fault

Speeding up Address Translation with a TLB

  • a small cache of PTEs in the MMU called a translation look aside buffer (TLB)

    Multi-Level Page Tables