Virtual Memory

• Every user program is using virtual memory --> it is fake physical memory
  • Isolation from the physical memory
  • Security reason
• Translation from virtual address to physical address --> help determine CPU which process is running
• Different process using different translation (parameters to that translation function is different based on the process) --> CPU only translate current process --> proccess is isolated.

Physical Memory

• If physical addresses are P bits, then the maximum amount of addressable physical memory is $2^{p}$ bytes.
• OS manage the memory
• Most compiler only do 32 bits --> only 4GB RAM has been used --> if want to use 8GB --> switch to 64bits compile

Virtual Memory

• Kernel provides a separate, private virtual memory for each process
• The virtual memory of a process holds the code, data, and stack for the program that is running in that process.
• It is possible to use more bits virtual than physical
  • store the address on disk
  • load part of the address when we need it
• If virtual memory are V bits, the maximum size of a virtual memory is $2^v$ bytes
• Running applications see only virtual address.
• Everything in user program are using virtual memory. --> never ever see physical address
• Each process is isolated in its virtual memory and cannot access other process' virtual memories
• Why VM?
  • isolate processes from each other
  • potential to support VM larger than physical memory
  • more process running

Address Translation

• Each virtual memory is mapped to a different part of physical memory
• At least one translation required for every assembly instruction (i.e. program counter)
• Virtual address is translated to its corresponding physcial address
• Address translation is performed in HARDWARE. (MMU -> Memory Management Unit) provided by the kernel.

Virtual Memory implementation

• Goals:
  • 1. Transparency: user program believes the address is real
  • 2. Protection: offer isolation from different processes and kernel
  • 3. Efficiency: need to be done for every single instruction
• Dynamic Relocation:
  • For each process we need to store 2 integers --> offset and size
  • if size < limit, just add the offset
  • if not --> raise exception and terminate the program
  • Although efficient, suffer fragmentation --> external waste space
  • Memory waste problem --> 1KB used (stack start from the middle) --> 2KB needed --> internal waste space
• Segmentation:
  • Instead of allocating a continue chunk of memory, we only allocate the exact memory that going to use --> allocate 3 times (data, code, stack) instead of once.
  • Then we do dynamic allocation on the segment
  • The kernel maintains an offset and limit for each segment --> hardware tells OS # of segment to support
  • K bits for the segment ID, we have up to $2^k$ segments with $2^{v-k}$ bytes per segment
  • address: seg# | offset --> hex
  • MMU has a relocation register and limit register for each segment
    • split the VM into segment number and address within segment
    • if offset (i.e. the second part of VM separated from seg#) $\ge$ limit --> raise exception
    • else p = offset + relocation offset
    • Efficient on space and time --> two value stored for segment
  • Disadvantage:
    • Fragmentation problem
    • MMU is large(multiple registers)--> take physical space (too many MMU footprint) --> take too much CPU space
• Paging
  • Logically divide physical memory equal size $\rightarrow$ physical page / frame; normally we have 4KB.
  • To get fragmentation: let any page of virtual memory map to any frame of physical memory.
  • We never allocate the chunk of memory, instead we only allocate several individual memory for one frame --> no more external fragmentation
  • But still have internal fragmentation --> since the smallest page is 4KB, so might lose a little bit $\rightarrow$ dont care!
  • Any page --> Any frame --> Any memory location (more process running than the RAM support)
• Page Tables
  • It has frame number and valid bit
  • Valid bit --> track whether the page is in use --> through exception if not
  • Number of PTEs(Page Table Entry) = Maximum Virtual Memory Size / Page Size
    • e.g. 32-bit virtual address --> $2^32$ Memory Size
    • page size of $2^12$ bytes --> we have $2^20$ PTEs
  • Determine the page number and offset --> PG# | offset
  • Number of Bits for PG# = $\log$(Number of PTEs)
  • Number of Bits for Offset = $\log$(Page size)