Virtualization
Referenced technical blog
OSTEP slides
Reference
Virtual Memory
Virtualization: each process believes it has its own address space, and different processes’ address spaces are isolated from each other.
In practice, when the CPU gets a virtual address, the MMU inside the CPU translates the virtual address into a physical address (an address in main memory). Each memory address refers to a single byte.
Segmentation
Each segment corresponds to a logical entity in the address space, for example the stack or data. Each segment can:
- Be placed independently somewhere in memory
- Have its own protection bits
- Grow and shrink independently
The MMU keeps a segment table for each process.
In a virtual address, the top bits represent the segment number, and the low bits represent the offset within that segment.
What is the physical address for virtual address 0x0240?
There are 4 segments here, so 2 bits are used for the segment number. The address in binary is 00000000001001000000; the first two bits 00 mean segment 0; the lower 12 bits are the offset.
Therefore, the physical address is 0x2000 + 0x240 = 0x2240.
Drawbacks of segmentation
Segmentation can cause external fragmentation. Because each segment must be contiguous in memory, if a segment is too large and memory only has multiple small free regions (fragments), none might be large enough to hold the segment.
External fragmentation is visible to the OS.
Paging
To address external fragmentation, paging divides each process’s address space into equal-sized pages and places them in memory. Each unit in memory that can hold a page is called a page frame.
Page Table
Each process has its own page table that records which page frame each of the process’s pages resides in.
How big is a page table?
In Linux, a page is 4 KB. Suppose the system is 32-bit and an address space is represented by 32 bits; since each address refers to one byte, a process’s address space is 2^32 = 4 GB.
4 GB / 4 KB = 2^20, i.e., a process can have 2^20 pages. Assuming each page table entry is 4 KB, then the page table size is 2^20 × 4 KB = 4 MB.
The page table is stored in memory, and the MMU performs the translation.
Paging translation
On a 32-bit system, a logical address consists of a 20-bit virtual page number (VPN) and a 12-bit page offset.
If a data section is smaller than a page, it still occupies an entire page, which means there can be internal fragmentation within a page.
Main memory as a cache for virtual memory
The CPU hands the MMU a virtual address; the MMU consults the page table using the VPN to find the base physical address of the corresponding physical page. If found, it adds the page offset to the base to obtain the final physical address.
If no corresponding physical address exists, that’s a cache miss — a page fault exception.
At this point, the kernel’s page fault handler first determines whether DRAM is full; if so, it will evict a page from DRAM. The OS then loads the needed page from disk into DRAM.
When DRAM is full, this is also called swap out and swap in: select a page that no other process is using in DRAM and write it to disk (swap out), then load the needed page from disk into DRAM (swap in).
When running a process, you don’t need to load all of its pages into DRAM; instead, load pages on demand as they are accessed.
A drawback of page tables is that they can be too large; for example, 100 processes may require 400 MB just for page tables.