Timedora

Vm

A guided explanation of how operating systems map, protect, share, and efficiently manage virtual memory.

Virtual Addresses and Page Translation

Separate address spaces

Virtual memory gives each process its own space. A program issues loads and stores using virtual addresses; it does not need to know where the corresponding data sits in physical memory. The OS sets up page tables, and the hardware’s memory management unit () uses them to translate addresses during memory accesses.

This separation gives processes isolated views of memory. For example, the 0xCAFED00D in process A can refer to different data from that same in process B. The same therefore does not have to identify the same physical location across processes.

Translate by page, preserve the offset

Rather than keeping a separate mapping for every byte, a maps whole virtual pages to physical pages. A common page size is 4 kB, or 4,096 bytes. Because 4,096 is 2122^{12}, an address for this page size can be divided into a page number and a 12-bit offset within the page. In the described 64-bit-address example, the remaining 52 bits form the page number.

The page number is called the virtual page number (VPN) for a , and the physical page number (PPN) for a . Translation follows three steps: split the into its VPN and offset; look up the VPN to find its PPN; then combine that PPN with the original offset. The offset stays the same because it identifies a position within the page, while the changes which physical page is used.

Hypothetical translation example. Suppose a 4 kB-page mapping sends VPN 0x12345 to PPN 0xABCDE, and a has offset 0x678. The virtual page is replaced by the mapped physical page, while the offset remains 0x678. The resulting is 0xABCDE678. This example illustrates the procedure; the particular mapping is hypothetical.

Selecting the active

Each process has its own , stored by the OS in main memory. During a context switch, the OS sets a special register to the of the for the process it is switching to. The uses that register to locate the active table when translating addresses. In RISC-V, this register is called satp.

Address translation also applies to kernel accesses depending on the active translation mode and mappings; kernel privilege does not generally mean that memory accesses bypass translation.

Page Validity and Protection

Mapping is not the same as permission

A page-table entry can include a , which indicates whether the virtual page is mapped at all. Accessing an unmapped page is an error. A valid mapping can also carry specifying whether the page may be read (R), written (W), or executed (X). These permissions control what a process may do with the page; they are distinct from the translation that identifies its physical page.

For example, if a page’s W bit is 0, trying to store to an address in that page is an error—even if the page is mapped. Likewise, an access to an unmapped page fails because it has no valid mapping.

The restriction prevents execution from writable memory. Its purpose is to make it harder for bugs to lead to malicious instructions being run from a page that can also be written. It is a protection rule applied to page mappings, not a different method of translating addresses.

Page Faults, , and Mapped Files

A can have different causes

When a process accesses an invalid virtual page, a transfers control to the kernel. The fault signals that the access needs OS attention; it does not, by itself, tell you why the page is invalid.

The OS checks its internal data to determine what happened. The address might be unallocated—for example, the process never allocated that memory. In that case, there may be no page to load, and the access can result in a segmentation fault. Alternatively, the page may have backing data on disk. The OS can then read that page into physical memory and resume the process. Thus, a is not necessarily evidence that a page was swapped out.

Paging in and out

If the page is disk-backed, paging it in means reading it from disk into physical memory. There may not be room for it, so the OS might have to evict another page. A replacement policy guides that choice. The page-table entry marks a paged-out page as invalid; the OS uses its own data structures to determine whether the page is backed by disk.

Disk access is much slower than memory access, so the OS tries to keep frequently accessed data in memory. This uses temporal and spatial locality: recently accessed data, and data near it, may be accessed again. Frequent swapping can significantly hurt performance. While a disk request is outstanding, the scheduler may look for other work to run.

makes disk a level below main memory in the memory hierarchy. The source describes DRAM as somewhat like a cache for disk, with CPU caches above DRAM and registers above those caches. This analogy emphasizes that data nearer the processor is faster to access, while not all data must be kept at the fastest level.

Files loaded on demand

Unix systems can also use demand paging to make file contents accessible through a virtual memory region. The system call associates a region of virtual memory with a file. When the program accesses a page in that region, the OS can load the file-backed page rather than reading the whole file into memory in advance.

The source example opens .c read-only and maps 32 bytes with (NULL, 32, PROT_READ, MAP_PRIVATE, fd, 0). It then reads and prints the first four characters through the returned address, using addr[0] through addr[3]. To the program, the file contents are available through memory addresses; the OS loads the needed pages on demand.

Sharing and Efficient Translation

Sharing physical pages

Virtual-to-physical mappings do not have to be one-to-one. A virtual page in one process and a virtual page in another process can map to the same physical page. That lets processes use shared physical data without keeping a separate copy for each one.

If NN processes need the same BB bytes, sharing can use BB bytes of physical memory for that data rather than N×BN \times B bytes for separate copies. One use is read-only library code that several processes need. Another is inter-process communication: two processes can communicate by writing to a memory region they share.

Sparse virtual spaces and page-table size

A dense has an entry for every virtual page, including pages that are invalid. If the page size is 2s2^s bytes and the space spans 2V2^V bytes, the table needs 2V/2s2^V / 2^s entries. That can waste space when a process uses scattered islands of virtual addresses separated by large unused regions.

For the source’s example assumptions—4 kB pages and 8-byte page-table entries—a dense table for a 32-bit address space needs:

8×(232212)=8×220 bytes,8 \times \left(\frac{2^{32}}{2^{12}}\right) = 8 \times 2^{20}\text{ bytes},

or 8 MB. For a 64-bit address space, the same calculation gives 8×2528 \times 2^{52} bytes. The large cost motivates sparse representations that mainly pay for allocated pages. A VPN-to-entry hash table is one possibility, but the source describes it as too expensive to be practical; a tree-shaped is a cheaper alternative with many of the same sparsity benefits.

Caching translation information

Looking up an entry in a , especially a multi-level one, can require several memory accesses before the processor accesses the requested data. A processor’s on-chip is a special cache for page-table information that reduces this translation cost. Whether a program’s address-translation needs fit in the TLB can therefore strongly affect performance.