Virtual Memory
One of the most fundamental abstractions of multiprocessing is the concept of virtual memory. While the kernel can see physical system resources directly, processes access memory indirectly through a process called address translation. When a processor instruction accesses a particular virtual memory address, a component of the processor called the memory management unit (MMU) invisibly translates the address into a physical address, using a page table. This allows every process to see its own memory as a continuous sequence of addresses starting from 0, when in reality its data is scattered throughout physical memory.
A page is a block of memory, usually 4kB, and both the virtual and physical address spaces are broken up into enumerated pages:
Page Number |
Address Range (4kB pages) |
|
|---|---|---|
0 |
[0, 4096) |
|
1 |
[4096, 8912) |
|
2 |
[8912, 12288) |
|
… and so on … |
||
A memory address can be broken into a page number and page offset. With 4096 kB pages, the lower 12 (because 
) bits of an address make up the page offset, and the remaining bits make up the page number. For example, the address for byte 78586 is 0x12B2A in hexadecimal; the three rightmost hexadecimal digits (0xB2A), are the page offset and the remaining digits (0x12) are the page number.
The page table maps virtual pages to physical pages; following from our example above, virtual page 0x12 (18 in decimal) might map to physical page 0x31 (49 in decimal). The MMU will read this from the page table, and convert the virtual address 0x12B2A to the physical address 0x31B2A, which will be used to access the appropriate location in physical memory, without the process being aware of the address translation. The kernel is responsible for populating and managing a process’s page table–when a process attempts to access an unmapped page, this triggers a processor interrupt called a page fault. The page fault causes a jump into kernel code that handles page faults. There are basically three types of page faults that can occur,
- Minor
Minor faults occur when the requested page is loaded into memory, but not mapped in the page table; the kernel simply updates the process’s page table to point to the page.
- Major
Major faults occur when the required page is not currently loaded into memory. The requested page must be allocated and initialized or loaded with the appropriate contents before it can be mapped. Major faults are expensive operations, because they involve copying large amounts of data, usually from a slow disk, into memory. A great deal of effort goes into avoiding major faults within the critical execution path of a program, both from the system programmer and kernel developer side.
- Invalid
Invalid faults occur when an address is requested that is not part of the virtual address space; this will generally result in the kernel sending a SIGSEGV (segmentation fault) signal to the process.
Since most processes request much more virtual memory than they actually need, there are three common techniques that are used to increase the apparent size of system memory resources: swapping, overcommit, and shared memory.
Swapping
Swapping is a technique where the kernel uses storage on a hard drive to store copies of unused pages, allowing those pages in memory to be reused by other processes without losing the data they held. When a process later tries to access a swapped page, this generates a page fault, and the kernel copies the swapped page back into memory and updates page tables to reflect the change. This allows processes on a system to use much more memory than is actually physically available by extending it with additional swap space, at the cost of performance and disk space.
Lazy Allocation and Over-Commit
Processes can allocate much more memory than the system is able to support, even with its swap space. The kernel performs lazy-allocation, which means that uninitialized pages are simply never actually allocated until the process attempts to access that page. The active memory mappings of a process are stored in a structure called a memory map, which simply tracks the regions of memory that the process has asked the kernel to allocate memory for, so that the kernel knows what to do when that memory is actually later touched and needs to be allocated on-the-fly.
This works very well since most processes never use all of the memory they allocate, and it greatly simplifies the kernel’s memory management, but with a cost – the kernel can overcommit. When processes attempt to access unmapped pages that aren’t backed by remaining swap space, a very grim process occurs: the kernel just starts killing processes until balance is restored to the system. This is called the OOM (Out Of Memory) killer, and it tries to select less important processes to kill, but it can result in data corruption or system instability in the worst case.