Virtual memory at work

Why this matters

A program allocates 8 GiB on a machine with four, and it works. A 40 GiB file opens through mmap instantly. A fork of a process that occupies 2 GiB takes microseconds.

All three cases rest on one mechanism: a page can be in the address space without being in memory. The valid-invalid bit in a page table entry (module 11) turns any access into an event that the kernel handles as it sees fit.

Prerequisites. The page table and the valid-invalid bit (module 11), interrupts and exceptions (module 2).

Demand paging

There is no need to load the whole program into memory before starting it, and it is almost always wasteful: a large part of the code never runs during the whole session.

Demand paging means that a page is brought into memory at the moment of the first access to it, and not earlier. The kernel clears the valid-invalid bit in the entries of all pages not yet loaded, and the hardware itself reports when one of them is needed.

The most important step is the seventh: the instruction is executed again, and this time translation succeeds. The process has no way to notice that anything happened.

A page fault, despite the name, is a routine message from the hardware: there is no mapping, deal with it. It becomes an error only when the address really does not belong to the process, and then the kernel sends SIGSEGV.

Most faults never reach the disk at all:

• a minor fault happens when the page is already in physical memory and it is enough to add an entry to the table. This is the case with a shared library that another process has already loaded;
• a major fault requires reading from disk.

The orders of magnitude are these: a minor fault costs a few microseconds (on a virtual machine, first touching anonymous memory comes to about 2.3 µs per page), a major fault costs hundreds of microseconds on an SSD and a few milliseconds on a spinning disk. That is a difference of two to three orders of magnitude, and it decides whether the system responds or stalls.

Copy-on-write

By design, fork should have copied the entire address space. Instead, the kernel marks the pages of both processes read-only and leaves them shared.

The very first write to such a page causes a page fault. The kernel sees that the page is shared and marked for copying, copies only that page, gives the process write permission, and repeats the instruction.

The consequences are visible every day. A fork of a large process costs almost as much as that of a small one. A hundred processes of the same program share a single copy of the code. And memory just allocated with malloc does not physically exist until something is written to it.

Page replacement

When there are no free frames and a page has to be loaded, something has to be evicted. The only question is what.

Algorithm	Rule	Problem
Optimal	the page that will be accessed furthest in the future	requires knowing the future; used as a benchmark
FIFO	the one loaded earliest	how long ago a page was loaded says nothing about how useful it is
LRU	the one used least recently	an exact implementation requires updating a timestamp on every access
Clock	an approximation of LRU using the accessed bit	it works, which is why it is used in reality

The optimal algorithm cannot be implemented, but it is needed: without it there is nothing to compare the others against.

LRU looks like the ideal approximation, yet in its pure form it is almost never used, because updating a timestamp on every memory access is impossible in either hardware or software.

What actually works is the clock algorithm. The pages form a ring, and a hand moves around it. If the accessed bit is set, the hand clears it and moves on, so the page gets another chance. If it is clear, that page is evicted. The hardware sets the bit for free, and the kernel reads it occasionally. Linux uses a variant with two lists, active and inactive.

Belady's anomaly

Common sense says that more memory means fewer faults. For FIFO this is not true. There are access sequences on which increasing the number of frames increases the number of faults.

Algorithms free of this anomaly are called stack algorithms; LRU and optimal belong to them, FIFO does not. The practical conclusion is simple: better not to use FIFO even where it seems good enough.

Working set and thrashing

A process’s working set is the set of pages it accesses during the current interval of time. As long as the working sets of all active processes fit into physical memory, the system works normally.

As soon as they stop fitting, thrashing begins. One process evicts a page that another will need immediately, that one evicts it back, and between faults nobody gets anything useful done.

The symptom is recognizable at once: CPU utilization drops almost to zero, the disk is at one hundred percent, the system does not respond. Worst of all, thrashing reinforces itself: the scheduler sees an idle CPU and adds processes, and each one brings its own working set.

What is done about it:

• limit the number of simultaneously active processes;
• allocate frames in proportion to the working set, not equally;
• stop or kill some of the processes, which is the OOM killer’s job;
• in Linux, read the pressure indicator (/proc/pressure/memory), which shows the problem before the system stalls.

What this gives you in practice

mmap maps a file into the address space, so reading turns into memory access, and loading becomes the job of the demand paging mechanism. A forty-gigabyte file opens instantly, because nothing is read until you access it.

The page cache is the same mechanism seen from the other side: pages read from disk stay in memory. That is why reading a file a second time is instant, and why all free memory in Linux is taken up by cache (module 13).

Swap is space on disk for evicted anonymous pages, that is, those with no file behind them: the heap and the stack. By itself it neither speeds the system up nor slows it down; it gives the kernel the ability to evict what is not being used instead of keeping it in memory in place of useful cache. zram does the same, but instead of a disk it uses a compressed area in memory itself: two to three times more data at the cost of CPU time.

The OOM killer kicks in when there is no memory left and nothing left to evict. It picks a victim by the oom_score estimate, roughly speaking the largest consumer, and kills it. You can see its work in the kernel log.

Why malloc almost never returns NULL

By default Linux allows overcommit: malloc hands out addresses without checking whether that much physical memory exists, because most programs do not use everything they ask for. Physical pages appear on the first write.

So a shortage of memory shows up not as a malloc error but as the process being unexpectedly killed by the OOM killer, and this behavior is regularly mistaken for a bug in the program itself.

How it actually works in Linux

ps -o min_flt,maj_flt,rss,vsz,comm -p $$

min_flt counts minor faults, maj_flt major ones, which read from disk. A healthy process has thousands of the former and a handful of the latter.

/usr/bin/time -v ls / 2>&1 | grep -E 'page faults|Maximum resident'

The same for a single run, together with peak RSS.

grep -E 'pgfault|pgmajfault|pswpin|pswpout' /proc/vmstat

Counters since boot. Two measurements with a pause in between show the current rate; this is how thrashing is told apart from ordinary load.

cat /proc/pressure/memory

The memory pressure indicator (PSI): the share of time tasks spent waiting for memory. It shows the problem long before the system stalls.

free -h; swapon --show; cat /sys/block/zram0/comp_algorithm 2>/dev/null

Memory, cache and swap. Look at available, not at free.

journalctl -k --grep 'Out of memory|oom_reaper' | tail -5

The history of OOM killer activations: who was chosen as the victim and how much memory it was using.

python3 -c "
import mmap, os
f = os.open('/usr/bin/python3', os.O_RDONLY)
m = mmap.mmap(f, 0, prot=mmap.PROT_READ)
print('mapped', len(m), 'bytes, read from disk: 0')
print('first byte:', m[0:4])
"

The mapping happens instantly regardless of file size: the data arrives in pages as it is accessed.

Common misconceptions

“A page fault is an error.” It is a routine mechanism. Thousands of faults per second mean normal operation; the only problem is major faults, which go to disk.

“If I turn off swap, the system will get faster.” Without swap the kernel cannot evict a single anonymous page, so rarely used data pushes useful page cache out of memory. The result is often the opposite of what was expected, and instead of slowing down gradually the system runs straight into the OOM killer.

“malloc returned an address, so the memory is allocated.” Addresses are allocated. Physical pages will appear on the first write, and that is when it may turn out that there are none.

“The process was killed, so the program has a bug.” First check journalctl -k for the OOM killer. The process may have been perfectly correct and simply turned out to be the largest one at the moment memory ran out.

“Operating systems use LRU.” They use approximations of it. Exact LRU would require updating a timestamp on every memory access, which no system does.

“Thrashing is when there isn’t enough memory.” Thrashing sets in when working sets do not fit. There may still be free memory, just not where it is needed, and the system spends all its time moving pages around.

Check yourself

1. What does the kernel do as the last step of handling a page fault?

Sends the process a signalRepeats the same instruction that caused the faultMoves on to the next instructionRestarts the process

2. Why does a fork of a 2 GiB process take microseconds?

The kernel copies the memory in the backgroundThe pages stay shared and are marked read-only; only what gets written to is copiedThe process memory is stored on diskfork copies only the stack

3. How does a minor page fault differ from a major one?

A minor fault is handled faster because the hardware handles itA minor fault needs no disk read: the page is already in physical memory, only the table entry is missingA minor fault does not interrupt the processThe difference is only in terminology

4. Why is exact LRU not used in operating systems?

It gives worse results than FIFOIt would require updating a timestamp on every memory accessIt is subject to Belady’s anomalyIt does not work with multi-level tables

5. CPU utilization is close to zero, the disk is at 100%, the system does not respond. What is this?

DeadlockThrashing: the working sets do not fit into memory, and processes evict each other’s pagesA memory leak in the kernelA scheduler bug

6. malloc(8 GiB) returned a valid pointer on a machine with 4 GiB of memory. Why?

The memory was taken from swapLinux allows overcommit: addresses were handed out, and physical pages will appear on writemalloc made a mistake and the program will crash right awayThe kernel compressed memory

Lab

A5 — page replacement simulator. FIFO, LRU, clock and optimal on a real access trace. The mandatory part is to reproduce Belady’s anomaly with FIFO and confirm that it does not reproduce with LRU.

B3 — cgroups and OOM. Limit a process’s memory with cgroups v2, push it to the limit, and trace in the log how the OOM killer kicks in.

Sources

• OSTEP: Beyond Physical Memory: Mechanisms, Policies
• Silberschatz, Operating System Concepts, chapter 10
• man 2 mmap, man 5 proc, man 8 zramctl
• Documentation/admin-guide/mm/concepts.rst
• Pressure Stall Information — how to see a memory shortage in advance