Paging Design & Thrashing

Start with the picture that every OS course draws and every engineer eventually lives through. Imagine slowly raising the number of processes running at once — the degree of multiprogramming. At first, more processes is strictly good: while one waits on I/O, another uses the CPU, so utilization climbs. It keeps climbing, then flattens as the CPU nears fully busy. Everything so far says "add more load, get more work". And then, past one particular point, the curve does not flatten further or dip politely. It plunges. CPU utilization collapses toward zero exactly when you are asking the machine to do the most. That collapse is thrashing.

Here is the mechanism, and it is a vicious circle. Each process needs a certain set of pages resident to make progress. Pack in enough processes and the sum of everything they actively need exceeds physical RAM. Now every process is short of frames, so it faults constantly. To service a fault the kernel must evict some other page — but that page belonged to another process that was about to use it, so that process immediately faults too, evicting a page a third process needed. Every page brought in kicks out a page that is about to be wanted. The processes spend their time blocked on the disk, waiting for pages, so the CPU goes idle. And a low-CPU signal is exactly what tempts a naive scheduler to admit even more processes — tightening the noose.

The number that makes this real is the speed gap between RAM and disk. A memory access takes tens of nanoseconds; servicing a major page fault from a spinning disk takes milliseconds — roughly a hundred thousand times slower, and even a fast SSD is thousands of times slower than RAM. So it takes only a tiny fraction of your accesses missing to disk to swamp everything. If even one access in ten thousand becomes a page fault, your effective memory speed is dominated entirely by the faults, not by RAM. Thrashing is that arithmetic playing out at full scale: the machine is technically running, but its effective speed has fallen to disk speed.

Thrashing

A state where the system spends more time paging (moving pages between RAM and disk) than executing useful work, so throughput collapses.

Degree of multiprogramming

How many processes are resident and competing for memory and CPU at once. Raising it helps — until working sets no longer fit.

The cliff

The point on the CPU-utilization curve where adding one more process tips the system from productive into thrashing, and utilization falls off a cliff.

Vicious circle

Faults evict pages that are about to be needed, causing more faults; low CPU tempts more admission, which makes it worse.

To fix thrashing you first need a way to reason about "how much memory does a process actually need right now" — and the classic answer is the working-set model. Over any recent window of time, a process touches some set of distinct pages; that set is its working set. The insight is that a process runs happily if its working set is resident, and thrashes the moment it is not. So the whole system stays healthy precisely when the sum of every running process’s working set fits in physical memory. Thrashing is the name for the sum overflowing RAM. This gives the kernel a policy: measure each process’s working set, and admit only as many processes as their working sets will collectively fit.

A more directly measurable cousin is page-fault-frequency (PFF) control. Instead of tracking which pages are in the working set, just watch each process’s page-fault rate against two thresholds. If a process is faulting faster than the upper threshold, it clearly does not have enough frames — give it more. If it faults slower than the lower threshold, it has more frames than it needs — reclaim some for others. And if the fault rate is high but there are no free frames to hand out to anyone, that is the signal to reduce the load: suspend or swap out an entire process so the survivors get enough frames to stop thrashing. PFF turns the working-set idea into a simple feedback loop the kernel can run continuously.

On a real Linux box you diagnose this in seconds, and the tool of choice is vmstat. Watch the si and so columns — swap-in and swap-out, in kilobytes per second. On a healthy machine they sit at zero. When they are large and sustained, memory is being paged to and from disk continuously: that is the fingerprint of thrashing. Notice below how CPU is not busy doing work (low us/sy) but is dominated by wa — time waiting on I/O — the exact signature from the cliff graph: idle CPU, saturated disk.

$ vmstat 1
procs -----------memory---------- ---swap-- -----io---- --system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 1  6  20480  10240   512   2048    0    0     0     0   50   80  3  1 96  0  0   <- healthy: si/so = 0
 2  9 512000   4096   128    900 8192 9600 12040 10200 4200 9100  4  6  2 88  0   <- thrashing: si/so huge, wa 88%
 3  8 640000   3800   120    850 9100 9400 11800  9900 4400 9500  3  7  1 89  0

The companion snapshot is free -h, which shows the standing state of memory rather than the flow. When free memory is near zero, the page cache (buff/cache) has already been squeezed down, and the "Swap used" line is large and climbing, the machine has run out of room and is leaning on disk to fake more. Read free and vmstat together: free tells you memory is gone, vmstat tells you the machine is actively paying for it in swap traffic right now.

$ free -h
               total        used        free      shared  buff/cache   available
Mem:            15Gi        14Gi       180Mi        40Mi       900Mi       210Mi
Swap:          4.0Gi       3.6Gi       400Mi

• ▸Reduce the load: run fewer processes, or have the kernel suspend/swap out whole processes so the rest get enough frames — this breaks the vicious circle at its root.
• ▸Add RAM: the honest fix when working sets legitimately exceed memory; more frames mean the working sets fit again and faults drop to near zero.
• ▸Admission control: at the scheduler/system level, refuse to admit new work when memory is already tight, instead of letting low CPU trick you into piling on more.
• ▸Right-size the app: cut a program’s own footprint (smaller caches, streaming instead of loading everything) so its working set shrinks to fit.

Suppose the kernel has a fixed number of physical frames and several processes wanting them. How many frames should each process get? The simplest answer is equal allocation: if there are 100 frames and 5 processes, each gets 20. It is fair in the crudest sense, but wasteful — a tiny helper process does not need 20 frames while a large database process is starved with only 20. So real systems lean toward proportional allocation: give each process frames in proportion to its size (or its measured working set), so the big process that actually touches many pages gets the large share it needs, and the small one gets a small share.

Cutting across that choice is a second, sharper one we first met when studying page replacement: when a process faults and a frame must be freed, whose frame may be taken? Under local replacement, a process may only evict its own frames — its allocation is a fixed budget it manages internally. Under global replacement, a faulting process may take a frame from any process in the system, whoever happens to hold the best victim page. Global is the more common default because it adapts automatically: a process that suddenly needs more memory can grow at the expense of idle ones, and the whole machine uses its frames efficiently.

But global replacement is exactly where thrashing becomes contagious, and this is the tension that ties the section back to the headline. Under local replacement a thrashing process mostly hurts itself — its fault rate soars but it cannot steal frames from its neighbours, so the damage is contained. Under global replacement there is no such firewall: a single memory-hungry process, faulting hard, will keep stealing frames from everyone else, pushing them below their working sets until the entire system thrashes together. Global replacement gives you efficiency in the good case and a system-wide meltdown in the bad case — which is precisely why the kernel needs the working-set and PFF controls from the previous section to keep any one process from dragging the rest off the cliff.

Equal allocation

Split frames evenly across processes regardless of their size — simple but often wasteful.

Proportional allocation

Give each process frames in proportion to its size or working set, matching supply to demand.

Local replacement

A faulting process may only evict its own frames; thrashing stays contained to that process.

Global replacement

A faulting process may evict any frame in the system; efficient, but lets one process spread thrashing to all.

We have taken the 4 KB page as a given, but page size is a design choice with real consequences, and it pulls in two opposite directions. Small pages waste very little memory to internal fragmentation — the leftover space in the last, partly-used page of an allocation is at most a few kilobytes. But small pages mean a huge number of pages to describe a large region, so page tables grow large, and worse, each TLB entry maps only 4 KB, so covering a big working set needs many TLB entries. When the TLB cannot hold enough of them, you take TLB misses, and every miss costs a page-table walk. A program striding over gigabytes of data can spend a shocking fraction of its time just translating addresses.

Large pages — "huge pages" on Linux, typically 2 MB, and even 1 GB "gigantic" pages — flip every one of those trade-offs. One huge-page TLB entry covers 2 MB instead of 4 KB, so a single entry maps 512 times as much memory; a handful of entries can cover a working set that would have needed thousands of 4 KB entries. TLB misses plummet, page tables shrink, and translation gets cheap. The cost is the mirror image: internal fragmentation grows, because now the wasted tail of a partly-used region can be up to 2 MB, and the kernel needs 2 MB of physically contiguous free memory to form each huge page — which is hard to find on a machine that has been running a while and whose free memory is fragmented.

Linux offers two ways to get huge pages. Explicit hugetlb pages are reserved up front and requested deliberately by an application — predictable, but you must plan for them. Transparent Huge Pages (THP) is the kernel trying to do it for you automatically: it silently promotes eligible 4 KB regions into 2 MB pages in the background, no application changes required. THP is a genuine win for workloads that scan large contiguous regions and want fewer TLB misses. The setting is a single file you can read and toggle.

# See the current mode; the value in [brackets] is active
$ cat /sys/kernel/mm/transparent_hugepage/enabled
[always] madvise never

# Databases often set "madvise" (only where asked) or "never"
$ echo madvise | sudo tee /sys/kernel/mm/transparent_hugepage/enabled

# Confirm how much memory is currently backed by THP
$ grep AnonHugePages /proc/meminfo
AnonHugePages:   1048576 kB

Here is the gotcha that trips up real teams, and it is why so many database vendors tell you to turn THP off. Because THP works in the background, the kernel sometimes has to do expensive work at the worst possible moment: to promote a region it may need to compact memory to find 2 MB of contiguous space, and that compaction can stall the process — introducing sudden latency spikes and jitter in a workload that cared more about predictable tail latency than about TLB efficiency. Databases like MongoDB, Oracle, and Redis have historically recommended disabling THP (or setting it to madvise) for exactly this reason: their access patterns do not benefit much, but the unpredictable compaction stalls hurt their latency badly.

You call malloc (or new, which sits on top of it) constantly, but it is a user-space library function, not a system call — and understanding what it does underneath explains a whole category of confusing production behaviour. malloc manages a pool of memory inside your process. When it needs more raw memory from the kernel, it has two syscalls to choose from. For small requests it grows the heap with brk/sbrk, which simply moves the "top of heap" pointer upward to annex more of the contiguous heap region. For large requests (glibc’s default threshold is around 128 KB) it instead calls mmap to get a fresh, independent region of pages mapped straight from the kernel.

The reason for two paths is fragmentation and return-ability. The heap is one contiguous region grown from one end, so it is cheap for many small objects but awkward to shrink — you can only lower the top-of-heap line if the very top is free. A big mmap region, by contrast, stands alone and can be handed straight back to the kernel with munmap when freed. That is why large allocations use mmap: the memory can actually be returned. To keep multithreaded programs from all contending on one heap, modern allocators also split the pool into several arenas — independent sub-heaps that different threads use in parallel to reduce lock contention.

Now the fact that surprises almost everyone: when you free() memory, it usually does not go back to the operating system. free returns the block to malloc’s own free list so your next malloc can reuse it — but the pages typically stay mapped in your process, because releasing them to the kernel only to ask for them again moments later would be wasteful, and the heap can only shrink from its top anyway. This is not a leak; the memory is reusable by you. But it explains why a process that briefly allocated a lot of memory keeps showing a large size in ps or top long after it "freed" everything. The memory is idle, owned by your allocator, waiting to be reused.

This leads directly to two numbers every engineer must be able to tell apart. VSZ (virtual size) is the total size of everything mapped into the process’s address space — heap, mmap regions, libraries, stacks — whether or not any of it is currently in RAM. RSS (resident set size) is the portion of that which is actually resident in physical memory right now. VSZ can be huge and largely meaningless; RSS is the number that reflects real memory pressure. A process can mmap a 10 GB file (VSZ jumps by 10 GB) while touching only a few pages of it (RSS barely moves).

#include <stdlib.h>

int main(void) {
    /* small: served from the heap, grown via brk/sbrk,
       reused from malloc’s free list after free() */
    char *small = malloc(64);

    /* large (> ~128 KB): glibc calls mmap for its own region,
       which munmap can hand straight back to the kernel */
    char *big = malloc(4 * 1024 * 1024);

    free(small);   /* returns to the free list, NOT to the OS */
    free(big);     /* large mmap block CAN be munmap’d back */
    return 0;
}

Linux does something that sounds reckless and is actually clever: it hands out more memory than it has. This is overcommit. When your program asks for memory, the kernel usually says yes and maps the pages lazily — it only finds real physical frames when you actually touch a page (remember demand paging). Because most programs ask for far more than they ever simultaneously use — think of a process that malloc’s a big buffer and fills only part of it — overcommit lets the machine run many more programs than a strict accounting would allow. The gamble is that not everyone will cash in their promises at once.

But sometimes they do. When physical RAM and swap are both genuinely exhausted and a process touches one more page that must be backed by a real frame, the kernel is cornered: it made promises it cannot keep, and there is nothing left to reclaim. Rather than freeze the whole machine, it invokes the OOM (out-of-memory) killer. The OOM killer scores every process with an oom_score that roughly reflects how much memory it uses (with adjustments for priority and the tunable oom_score_adj), picks the highest scorer — typically the biggest memory hog — and terminates it with SIGKILL, the signal that cannot be caught or ignored. It sacrifices one process to save the system.

For anyone running containers, this is not abstract trivia — it is the single most common way pods die. A container runs inside a cgroup with a memory limit, and that limit is enforced independently of how much RAM the host has. When a process exceeds its cgroup memory limit, the kernel OOM-kills it even if the host has plenty of free memory — the limit, not the hardware, is the ceiling. In Kubernetes and Docker this shows up as the infamous exit code 137, which is simply 128 + 9 (128 plus the signal number for SIGKILL). If you have ever seen a pod restart with "OOMKilled" and code 137, this is exactly what happened: your process asked for more than its cgroup allowed, and the kernel killed it.

# The kernel log records who it killed and why
$ dmesg | grep -i "killed process"
Out of memory: Killed process 8123 (java) total-vm:6291456kB, anon-rss:2097152kB

# In Kubernetes/Docker, an OOM-killed container exits with 137 (= 128 + SIGKILL(9))
$ kubectl get pod api-7c9 -o jsonpath='{.status.containerStatuses[0].lastState.terminated}'
{"exitCode":137,"reason":"OOMKilled","startedAt":"..."}

# A process’s own OOM score and adjustment knob
$ cat /proc/8123/oom_score
742

Let us gather everything into the mental model a working engineer actually carries. When you monitor a service, RSS is the number that matters — it is the real physical memory your process holds, the thing that fills RAM and triggers the OOM killer. VSZ, the virtual size, is mostly noise: a process can map tens of gigabytes it never touches. So set your alerts and your container limits against RSS and its growth over time. And watch swap like a hawk: on a latency-sensitive service, any sustained swapping is a five-alarm fire, because a request that used to hit RAM in nanoseconds now waits milliseconds on the disk. The saying in the trade is blunt and correct — for a low-latency database, swap is death.

Databases are where every idea in Part D collides with reality, and they respond by fighting the OS for control of memory. A database keeps its own buffer pool — a large, carefully managed cache of data pages it thinks it knows better how to manage than the kernel does. But the kernel also keeps a page cache of the same file data, so a naive setup caches everything twice, wasting RAM. This is why serious databases reach for O_DIRECT, an I/O mode that bypasses the kernel page cache entirely so reads and writes go straight between the database’s buffer pool and the disk — no double caching, and the database in full control of what stays resident. It also explains why databases so often disable Transparent Huge Pages: they want predictable tail latency, not background compaction stalls, and they manage their own memory layout deliberately.

RSS vs VSZ (in monitoring)

Alert on RSS — real resident memory. VSZ is virtual and usually meaningless for pressure.

Page cache vs buffer pool

The kernel caches file data (page cache); a DB caches the same data in its own buffer pool. O_DIRECT skips the page cache to avoid double caching.

THP off for DBs

Databases often disable Transparent Huge Pages to avoid unpredictable compaction latency spikes.

“Swap is death for latency”

On a latency-sensitive service, sustained swapping turns nanosecond memory access into millisecond disk waits — treat any swap as an incident.

Step back and see the arc of Part D. We started with a single program owning all of RAM and the crude tricks — fixed partitions, base-and-limit, swapping whole processes — that let a few share it. We built the great illusion of virtual memory: private address spaces, pages, and the MMU translating them onto scattered frames. We made it efficient with demand paging, understood the page fault as the event that drives it all, and studied the replacement algorithms that decide what to evict. This chapter closed the loop by showing the limit — when working sets outgrow RAM the illusion collapses into thrashing — and by tying frame allocation, page size, malloc, and the OOM killer back to the systems you run in production. Memory management is no longer a black box; it is a set of levers you can reason about and measure.