Virtual Memory

(1) Virtual and physical memory

Virtual address space is the maximum amount of address space available to an application, which depends on architecture, e.g. CPU register size. Virtual memory enables each process to have its own unique view of a computer's memory.

Physical memory is a storage hardware, made up of physical memory devices, which is organized as an array of M contiguous byte-sized cells. Each byte has a unique physical address (PA).

Physical memory addresses are unique in the system, virtual memory addresses are unique per-process.

Only the kernel uses physical memory addresses directly. Userspace programs exculsively use virtual addresses. Translation from virtual to physical address needs the combination of OS software, address translation hardware in MMU, and page table stored in physical memory or disk.

The Pulpit Rock
Fig.1 - A system that uses virtual addressing.

(2) Memory management unit

MMU is a hardware sitting in CPU to translate virtual address to physical address before passing it onto memory unit, i.e., memory controller (MC). Conceptually, the MMU contains a page table which is simply an array of entries indexed by page number.

(3) Page table and TLB

The page table is just a data structure to map VA (or really Virtual Page Number) to PA (Physical Frame Number). Each process has its own set of page tables.

The address translation hardware reads the page table each time it converts a virtual addr to a physical addr. The OS is responsible for maintaining the contents of the page table and transferring pages back and forth between disk and DRAM. Page table size for a process is roughly 4MB for 32-bit address space with 4-byte PTE, and can be as large as 400MB for 100 processes.

The Pulpit Rock
Fig.2 - Address translation with a page table.

To speed address translation, TLB, part of chip's MMU, is used to cache the popular virtual-to-physical address translations. Upon each virtual memory reference, the hardware first checks the TLB to see if the desired translation is held therein; if so, the translation is performed without having to consult the page table (which has all translations).

A typical TLB might have 32, 64, or 128 entries and be what is called fully associative. TLB contains v2p translations that are only valid for the currently running process; these translations are not meaningful for other processes. Thus, when switching from one process to another, the hardware or OS (or both) must perform a context switching.

Acccesses to virtual addresses not listed in TLB (a "TLB miss") trigger a page table lookup, which is performed either by hardware, or the page fault handler to update the TLB.

(4) Page fault and handler

DRAM is kind of cache of disk contents. DRAM caches are fully associative, that is, any virtual page can be placed in any physical page. A DRAM cache miss is known as a page fault, which is processed by a page fault exception handler in the kernel:

Suppose page fault happens on page p1,

References:
[1] paging
[2] memory faq
[3] virtual memory (redhat)
[4] virtual memory (OSTEP)
[5] virtual memory (CS-APP)