Memory Management

Why every process gets its own address space

A computer runs dozens of processes at the same time, and all of them need memory. If they all shared one big range of addresses, every program would have to know which addresses the others use, and one buggy program could overwrite the memory of another, or of the operating system itself.

So the operating system gives each process its own address space: the range of memory addresses that process can use, which to the process looks like one large, private, continuous block. Two big advantages follow:

• Isolation. A process can only reach the addresses in its own address space. A bug or an attack in a web browser cannot read the memory of the password manager next to it. When a program touches an address it has no right to, the hardware stops it and the operating system ends that process: an "access violation" on Windows, a "segmentation fault" on Linux and macOS. The rest of the system keeps running.
• Simplicity. Programs and compilers do not have to care where in physical RAM they end up, or what else is running. The operating system can place the pieces wherever there is room, and even move them.

How a program divides its own address space into code, stack and heap is explained for programmers on Memory Management (Programming Concepts). This page is about the operating system's side: how all those private address spaces fit into one set of RAM chips.

Virtual and physical addresses

The addresses a program uses are virtual addresses. The addresses of real memory cells on the RAM modules are physical addresses. Between the two sits a translation, set up by the operating system and carried out by the hardware on every single memory access. This whole arrangement is virtual memory (see Hardware for the short definition).

Because of the translation, the same virtual address means different things in different processes. Address 0x7FF6A000 in Notepad and 0x7FF6A000 in Excel point to two different places in RAM, or perhaps to one shared place if both use the same system library. On 64-bit systems the virtual address space of a process is far larger than any amount of installed RAM (128 TiB for user programs on 64-bit Windows and Linux), so the space itself never runs out; the RAM and the disk space behind it do.

Pages and frames

Translating every byte separately would need an enormous table. So memory is managed in fixed-size blocks. Paging is the technique of dividing virtual memory into pages and physical memory into frames of the same size, so that any virtual page can be placed in any free frame. The usual size is 4 KiB (4,096 bytes) on x86-64 PCs and most ARM systems; Macs with Apple silicon use 16 KiB pages. Processors also support large pages (2 MiB, 1 GiB) that databases and virtual machines use to cut down on translation work.

Fixed-size blocks solve a problem that a scheme with variable-sized chunks has: after many programs start and stop, free memory falls apart into small gaps between used areas (external fragmentation). With paging, any free frame is as good as any other, so no RAM is wasted between programs. The price is a little waste inside the last page of each area, which is at most one page.

Page tables and the MMU

A page table is the data structure in which the operating system records, for one process, which virtual page is stored in which physical frame, together with flags such as "present in RAM", "writable", "may execute" and "accessible from user mode". The kernel builds and updates the page tables; the hardware reads them.

That hardware is the memory management unit (MMU), a part of the CPU that translates every virtual address the program uses into a physical address, using the current process's page table. When the operating system switches from one process to another, it points the MMU at the other process's page table: that one switch is what swaps the whole view of memory.

Looking up the page table in RAM for every access would make each memory access several times slower. So the MMU keeps recent translations in a small, very fast cache, the translation lookaside buffer (TLB). Because programs mostly use the same few pages for a while, almost all translations are found in the TLB.

Translating an address

With 4 KiB pages, the lowest 12 bits of an address (2¹² = 4,096) are the offset inside the page, and the remaining high bits are the page number. The MMU looks up the page number, replaces it with the frame number, and keeps the offset. In hexadecimal the split is easy to see: the last three hex digits are the offset. This simulation uses bit shifts, just like the hardware (see hexadecimal):

PAGE_SIZE = 4096           # 4 KiB pages
OFFSET_BITS = 12           # 2**12 = 4096, so the low 12 bits are the offset

# Page table of one process: virtual page number -> physical frame number
page_table = {0: 5, 1: 9, 2: 3, 4: 12}

def translate(virtual):
    page = virtual >> OFFSET_BITS          # high bits: which page
    offset = virtual & (PAGE_SIZE - 1)     # low 12 bits: where in the page
    if page not in page_table:
        return f"0x{virtual:05X} -> page {page}, offset 0x{offset:03X} -> page fault"
    frame = page_table[page]
    physical = (frame << OFFSET_BITS) | offset
    return f"0x{virtual:05X} -> page {page}, offset 0x{offset:03X} -> frame {frame} -> 0x{physical:05X}"

for address in [0x00A3C, 0x01A3C, 0x02010, 0x03FFF, 0x04000]:
    print(translate(address))

0x00A3C -> page 0, offset 0xA3C -> frame 5 -> 0x05A3C
0x01A3C -> page 1, offset 0xA3C -> frame 9 -> 0x09A3C
0x02010 -> page 2, offset 0x010 -> frame 3 -> 0x03010
0x03FFF -> page 3, offset 0xFFF -> page fault
0x04000 -> page 4, offset 0x000 -> frame 12 -> 0x0C000

Two addresses with the same offset (0xA3C) land in completely different frames, and neighboring virtual pages (0, 1, 2) do not have to be neighbors in RAM. Page 3 has no entry, so the MMU cannot translate it and hands control to the operating system: a page fault.

Page faults

A page fault is the exception the MMU raises when a program touches a virtual page that is not currently mapped to a frame in RAM. The name sounds like an error, but most page faults are completely normal: the kernel handles them, maps the page, and lets the program continue as if nothing happened. There are three outcomes:

• Minor (soft) fault: the page is already in RAM, just not mapped for this process. Examples: a system library another process has already loaded, or a page Windows had put on its standby list. The kernel only updates the page table, which takes microseconds.
• Major (hard) fault: the page must be read from disk, from the page file, swap space or the program file itself. That takes from tens of microseconds on a fast SSD to about ten milliseconds on a hard drive, while a RAM access takes about a hundred nanoseconds.
• Invalid access: the address does not belong to the process at all, or it tried to write to a read-only page. That is a real error; the process is stopped with an access violation or segmentation fault.

Programs even rely on page faults on purpose. When a program starts, Windows and Linux load almost nothing: pages of the program file are brought in only when first used (demand paging). That is why a program starts faster the second time: its pages are still in RAM, so the faults are minor.

Swapping and paging to disk

When RAM is full and a process needs another frame, the operating system takes one away from somewhere else. Pages that are a copy of a file (program code, for example) can simply be dropped and read again later. Pages with data that exists nowhere else, such as a document being edited, must first be written to disk. Where they go depends on the operating system:

• Swap space is the disk area Linux (and other Unix-like systems) use to hold memory pages that were moved out of RAM: a dedicated swap partition or a swap file. Many distributions also use zram, a compressed swap area inside RAM itself. macOS keeps its swap files in /private/var/vm and first tries to compress memory before swapping.
• The page file is the hidden system file C:\pagefile.sys that Windows uses to hold memory pages moved out of RAM, and whose size also raises the commit limit (see below). By default Windows manages its size automatically. Windows also compresses memory before paging out; Task Manager shows it as "Compressed".

Older systems moved whole processes out to disk at once, which is where the word swapping comes from; today they move single pages, but the words swap and paging are used for the same thing.

Thrashing and page replacement

A little paging is harmless: pages that nobody has used for an hour might as well be on disk. The trouble starts when the programs that are actively running need more memory together than there is RAM. Then every page brought in pushes out another page that is needed again a moment later. Thrashing is that state: the system spends most of its time moving pages between RAM and disk instead of doing useful work.

Symptoms a technician recognizes:

• Everything is slow, the mouse stutters, switching between windows takes seconds.
• The disk shows constant activity (Task Manager: disk at or near 100%) while the CPU is mostly idle, waiting.
• Memory is close to 100% in use, and Resource Monitor (resmon) shows many "Hard Faults/sec". On Linux, vmstat 1 shows nonzero si and so (swap in, swap out) columns second after second.

A bigger page file does not help: it only allows even more memory to be paged out. The fixes are to close programs, find the process that uses too much memory (sort Task Manager's Processes tab by Memory), or add RAM. An SSD makes thrashing less painful than a hard drive, but it is still far slower than RAM.

Which page goes out: FIFO and LRU

When a frame has to be freed, the operating system chooses a victim page. A good choice evicts a page that will not be needed for a long time. Two classic policies:

• FIFO (first in, first out): evict the page that was loaded earliest. Simple, but it happily throws out a page that is used all the time just because it was loaded long ago.
• LRU (least recently used): evict the page that has gone unused the longest. It follows the idea that the recent past predicts the near future.

The simulation below counts page faults for the same sequence of page references with three frames of RAM:

def fifo(references, frame_count):
    frames, faults = [], 0
    for page in references:
        if page not in frames:
            faults += 1
            if len(frames) == frame_count:
                frames.pop(0)              # evict the page loaded first
            frames.append(page)
    return faults

def lru(references, frame_count):
    frames, faults = [], 0
    for page in references:
        if page in frames:
            frames.remove(page)            # hit: move to "most recent" end
        else:
            faults += 1
            if len(frames) == frame_count:
                frames.pop(0)              # evict the least recently used
        frames.append(page)
    return faults

references = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
print(f"{len(references)} references, 3 frames")
print(f"FIFO: {fifo(references, 3)} page faults")
print(f"LRU:  {lru(references, 3)} page faults")

20 references, 3 frames
FIFO: 15 page faults
LRU:  12 page faults

LRU causes fewer faults here because it keeps page 0, which is used again and again, while FIFO keeps throwing it out. Real operating systems do not track the exact order of every access (that would be too slow); they approximate LRU with an "accessed" bit that the MMU sets in the page table, and scan those bits now and then (the clock algorithm and its variants).

When memory runs out

On Windows, what can run out is not RAM but commit: the total memory that programs have been promised. The commit limit is roughly the size of RAM plus the page file. When the committed memory approaches the limit, Windows first tries to grow a system-managed page file; when that is not possible, it shows the warning "Your computer is low on memory" and asks the user to close programs. The Resource-Exhaustion-Detector logs this in Event Viewer (System log), usually naming the processes that used the most memory. Programs that then ask for more memory get an error and may crash.

Linux normally promises more memory than it has (overcommit), because most programs never touch everything they reserve. When RAM and swap are truly exhausted, the kernel's OOM killer (out-of-memory killer) picks a process, usually the one using the most memory, and ends it to save the rest of the system. The only trace is a line in the kernel log (illustrative):

sudo journalctl -k | grep -i "killed process"

Oct 01 10:42:17 web01 kernel: Out of memory: Killed process 2314 (java) total-vm:8123456kB, anon-rss:6012344kB, file-rss:0kB, shmem-rss:0kB, UID:1001 pgtables:12500kB oom_score_adj:0

A service that "just disappears" on a Linux server, with nothing in its own log, is a classic OOM-killer case: check the kernel log first.

Reading memory use in practice

In Windows, open Task Manager (Ctrl+Shift+Esc), tab Performance, then Memory. The fields below come from a machine with 16 GB installed (illustrative values):

On Linux, free -h gives the same overview. This illustrative machine is under pressure: little is available and swap is in use.

free -h

               total        used        free      shared  buff/cache   available
Mem:           7.6Gi       6.7Gi       142Mi       188Mi       720Mi       410Mi
Swap:          2.0Gi       1.6Gi       412Mi

Look at available, not free: Linux uses spare RAM as disk cache, so a low free value on its own is normal. Here available is only 410 MiB and 1.6 GiB of swap is used; if the machine also feels slow, it is short of RAM.