Chapter 9: Swapping, Reclaim, and Page Replacement Policies
Chapter 9: Swapping, Reclaim, and Page Replacement Policies
No matter how many gigabytes or terabytes of physical DRAM are provisioned on a server, memory consumption will eventually approach capacity. When available memory falls below kernel watermark thresholds, the operating system faces a critical architectural decision: Which physical pages should be evicted or swapped, and when?
A flawed eviction policy evicts hot pages, throwing the system into severe disk thrashing where the CPU spends 99% of its cycles waiting for swapped-out memory to reload. A robust policy smoothly balances file cache shrinking with anonymous page swapping, maintaining high system throughput.
This chapter details the Linux reclaim architecture: dual active/inactive LRU lists, page replacement heuristics, swap space mechanics, compressed in-RAM caching (zswap), thrashing prevention, and practical tuning of vm.swappiness.
When RAM Runs Out: The Reclaim Problem
Physical memory pages belong to two distinct categories:
- File-Backed Pages (Page Cache): Pages backed by files on disk (executables, shared libraries, data files).
- Clean Page: Can be discarded instantly with zero I/O; if needed later, the kernel re-reads the data from the backing file.
- Dirty Page: Must be flushed to disk before the physical page frame can be reclaimed.
- Anonymous Pages: Pages that have no backing file on disk (heap memory, stack variables, BSS segments, anonymous
mmapallocations).- Cannot be discarded! The data must either be preserved in physical RAM or written to dedicated secondary backing storage: the Swap Space.
Active and Inactive Page Lists
To determine which pages are cold candidates for eviction, Linux maintains dual linked lists per memory zone:
┌────────────────────────────────────────────────────────────────────────┐
│ DUAL LRU LIST ARCHITECTURE │
│ │
│ New Allocation ──► Enters INACTIVE List (Head) │
│ │ │
│ ▼ Accessed again? (Hardware Referenced Bit)│
│ ┌──────┴──────┐ │
│ ▼ YES ▼ NO (Remains unreferenced) │
│ Promote to ACTIVE List Migrate toward Inactive List Tail │
│ (Hot working set pages) (Cold pages targeted for reclaim) │
│ │ │ │
│ ▼ Aging pass ▼ │
│ Demote cold pages back ──────────► Reclaim / Swap Out │
│ to Inactive List │
└────────────────────────────────────────────────────────────────────────┘The kernel tracks four distinct lists per NUMA node: - anon_inactive: Cold anonymous pages eligible for swapping. - anon_active: Hot anonymous pages actively accessed by processes. - file_inactive: Cold file cache pages eligible for clean dropping. - file_active: Hot file cache pages actively referenced.
The Clock-Pro / Pseudo-LRU Heuristic
Linux does not maintain a perfect Least Recently Used (LRU) list because moving a page to the front of a linked list on every single memory access would cause severe lock contention across CPU cores.
Instead, Linux uses a Two-Hand Clock Heuristic: - When the hardware MMU translates an address, it sets the page’s hardware Accessed Bit (A = 1). - The kernel’s reclaim scanner periodically clears the bit (A = 0). - If the bit remains 0 on the subsequent scanner pass, the page has not been touched and is demoted to the inactive list for eviction.
Swap Spaces, Swap Devices, and File-Based Swapping
Swap storage can be provisioned as a dedicated raw block partition (/dev/nvme0n1p3) or as a dynamic swap file on an existing filesystem (/swapfile):
# Create and activate a 4 GiB swap file
sudo fallocate -l 4G /swapfile
sudo chmod 0600 /swapfile
sudo mkswap /swapfile
sudo swapon /swapfileThe Swap Map and Swap Slots
Inside the kernel, swap space is divided into \(4\text{ KiB}\) Swap Slots. When an anonymous page is selected for swapping: 1. A free swap slot is allocated from the swap device. 2. The page data is written to the swap slot via Block I/O. 3. The process’s Page Table Entry (PTE) is updated: the Present bit is cleared (P = 0), and the physical frame address is replaced with a Swap Identifier (device index + slot offset). 4. The physical DRAM page frame is freed back to the Buddy Allocator.
When the process subsequently attempts to read the swapped-out address, the MMU triggers a page fault. The kernel reads the swap slot identifier from the PTE, reads the data block back from disk into a fresh DRAM frame (Swap-In), sets P = 1, and frees the swap slot.
zswap, z3fold, and Compressed Caching
Writing anonymous pages to persistent NVMe or SATA storage incurs high I/O latency. To eliminate this bottleneck, Linux includes zswap: a compressed, in-RAM write-behind cache for swap pages.
┌────────────────────────────────────────────────────────────────────────┐
│ ZSWAP COMPRESSION PIPELINE │
│ │
│ Page Eviction selected for Swap-Out │
│ │ │
│ ▼ Intercepted by zswap │
│ Compress 4 KiB Page using LZ4 / ZSTD (Latency: ~2 microseconds) │
│ │ │
│ ▼ Achieved 3:1 Compression Ratio? │
│ ┌──────┴───────────────────────────────────────────────────────┐ │
│ │ YES: Store compressed 1.3 KiB payload in zpool (z3fold/zsmalloc)│ │
│ │ Avoids physical disk I/O completely! (100x faster swap-in) │ │
│ ├──────────────────────────────────────────────────────────────┤ │
│ │ NO: Pass uncompressed page through to physical swap disk │ │
│ └──────────────────────────────────────────────────────────────┘ │
└────────────────────────────────────────────────────────────────────────┘- Compression Algorithms: Typically configured to use LZ4 (fastest) or Zstandard (ZSTD) (highest compression ratio).
- Memory Pool Allocators (
zsmalloc/z3fold): Packs multiple compressed page fragments into single physical page frames, eliminating internal fragmentation.
# Verify zswap status and compression ratio
grep -r . /sys/kernel/debug/zswap/Thrashing Detection and Prevention
When active process memory significantly exceeds physical RAM, the kernel enters Thrashing: pages swapped out are immediately referenced and swapped back in, while file cache is completely purged.
Pressure Stall Information (PSI)
Modern Linux kernels monitor memory health via PSI (Pressure Stall Information) in /proc/pressure/memory:
cat /proc/pressure/memory
# some avg10=2.40 avg60=1.10 avg300=0.45 total=1240189
# full avg10=0.80 avg60=0.30 avg300=0.10 total=482101some: Percentage of time that at least one CPU task was stalled waiting for memory reclaim or swap I/O.full: Percentage of time that all non-idle tasks were completely blocked waiting for memory (catastrophic thrashing). Production orchestrators (systemd-oomd, Kubernetes) monitor PSI to shed load before complete system lockups.
Practical Experiment: Tuning vm.swappiness and Observing Behavior
The kernel parameter vm.swappiness (ranging from 0 to 200, default 60) controls the relative ratio of reclaiming anonymous memory vs reclaiming file-backed page cache:
\[\text{Swap Tendency} = \frac{\text{swappiness} \times \text{Anon Inactive Ratio}}{100}\]
# Query current swappiness
sysctl vm.swappiness
# Server Tuning: Reduce swapping aggressiveness to prioritize keeping anon memory in RAM
sudo sysctl -w vm.swappiness=10
# Desktop / Container Host Tuning: Aggressive swapping to preserve large file caches
sudo sysctl -w vm.swappiness=100swappiness = 0: The kernel will never initiate swap until available memory falls below the absolute emergency zone watermarks.swappiness = 100: The kernel treats anonymous memory and file page cache with equal eviction weight.swappiness = 200: The kernel aggressively swaps out idle anonymous memory to preserve maximum file cache capacity.