Memory

The two fragmentations — get these the right way round

The relationship is the insight: paging trades external fragmentation for internal fragmentation, and that's a good trade because internal waste is bounded (at most one page per allocation, on average half a page) while external waste is unbounded and unpredictable.

Placement strategies

The counter-intuitive result worth stating: first fit generally beats best fit on both speed and fragmentation. "Best" refers to the tightness of the fit, not the outcome.

Real allocators

The mechanism

Split the virtual address space into pages and physical memory into frames of the same size (4 KB typically). A page table maps page → frame. The MMU does the translation in hardware on every single memory access.

Address translation, worked

Given:  32-bit virtual addresses, 4 KB pages, single-level table
        4 KB = 2¹² → offset is the low 12 bits
                   → page number is the high 20 bits
                   → 2²⁰ = 1,048,576 entries per process

Virtual address 0x00004A3F
  = 0000 0000 0000 0000 0100 1010 0011 1111
    └──────── page 0x00004 ───────┘└─ offset 0xA3F ─┘
  page number = 0x4 = 4
  offset      = 0xA3F = 2623

  Page table[4] = frame 0x11 (17), present, rw
  Physical address = (17 × 4096) + 2623 = 69,632 + 2,623 = 72,255
                   = 0x00011A3F        // note the offset is unchanged

Quick facts to derive rather than memorise:
  page size 2ⁿ           → offset = n bits
  virtual address v bits → page number = v − n bits
  entries per table      = 2^(v−n)
  a 4-byte entry, 20-bit page number → 4 MB of page table PER PROCESS
  100 processes → 400 MB of page tables for mostly-empty address spaces.
  That waste is exactly what multi-level tables fix.

Multi-level page tables

Rather than one giant flat array, use a tree. Only the branches you actually use get allocated — and a typical process uses a tiny, sparse fraction of its address space, so nearly all branches are absent.

x86-64, 4-level, 4 KB pages: 48 bits of virtual address in use
  9 bits  → PML4 index      (512 entries)
  9 bits  → PDPT index
  9 bits  → PD index
  9 bits  → PT index
 12 bits  → offset
 = 48 bits → 256 TB of address space

A process touching 8 MB needs a handful of tables, not 512 GB of them.
Cost: 4 memory accesses per translation on a TLB miss — hence the TLB,
and hence huge pages.

Huge pages (2 MB or 1 GB): fewer entries cover far more memory.
  TLB REACH = entries × page size
    1536 entries × 4 KB  = 6 MB   ← a 1 GB working set thrashes the TLB
    1536 entries × 2 MB  = 3 GB   ← now it fits
  Used by databases and JVMs deliberately. Cost: more internal
  fragmentation, and allocation can fail once memory is fragmented.

Page table entry contents

The flags are asked about because each one enables a feature:

Handling a page fault

1. The MMU finds the present bit clear and raises a page fault — a trap into the kernel. The faulting instruction is suspended, not aborted.
2. The kernel checks whether the address is legal for this process. If not: SIGSEGV, process dies. This is what a segfault is.
3. It finds a free frame. If none is free, it evicts a victim — writing it to disk first if it's dirty, which is why the dirty bit matters.
4. It reads the page in from disk (or the swap file, or zeroes it for a fresh anonymous page).
5. It updates the page table and the TLB, then re-executes the faulting instruction, which now succeeds.

Replacement algorithms

Traced side by side

Reference string:  7 0 1 2 0 3 0 4 2 3 0 3 2   ·   3 frames

FIFO
 7 | 7    0 | 7 0    1 | 7 0 1    2 | 2 0 1  ← evict 7 (oldest)
 0 | hit        3 | 2 3 1   ← evict 0     0 | 2 3 0  ← evict 1
 4 | 4 3 0      2 | 4 2 0      3 | 4 2 3      0 | 0 2 3
 3 | 0 3 ... → 15 faults

LRU
 same start, but at the 4:  frames hold 2 0 3, least recently USED is 2
 → evict 2, not 0 → 12 faults

OPT
 at each eviction, look forward and drop the page needed latest
 → 9 faults   ← the floor. LRU's 12 is respectable; FIFO's 15 is not.

Frame allocation and the second policy

Replacement is only half the decision; how many frames each process gets is the other half.

• Local replacement: a faulting process evicts only its own pages. Predictable per-process performance, but a process can thrash inside its own allocation while frames sit idle elsewhere.
• Global replacement: evict from anyone. Better overall utilisation, but one greedy process degrades everyone and performance becomes non-reproducible. Most real systems are global with limits.
• Proportional allocation gives frames by process size rather than equally, which stops a tiny process from hoarding.

The working set model

The practical control is page fault frequency: measure each process's fault rate, give more frames to processes above the upper bound, take frames from processes below the lower bound, and if no process can be satisfied, suspend one entirely to let the rest run. Counter-intuitive but correct — running fewer processes well beats running all of them badly.

Swap

Some swap is healthy: it lets the kernel evict genuinely cold anonymous pages and use the RAM for page cache instead. Zero swap doesn't prevent memory pressure; it just removes an option and makes the OOM killer fire sooner.

Copy-on-write

fork() must give the child a copy of a possibly-gigabyte address space.
Copying it eagerly would be absurd — and usually wasted, because the
child typically calls exec() immediately and discards all of it.

Instead: map the SAME frames into both, marked read-only.
  · Reads are free and shared.
  · The first WRITE traps → kernel copies just that one page, marks
    both writable, resumes.
  → cost is proportional to pages actually MODIFIED, not pages owned.

Same trick appears everywhere once you recognise it: mmap of a file,
shared libraries (one physical copy of libc for the whole system),
container image layers, database snapshots, and Redis's BGSAVE — which
forks and lets COW give it a consistent point-in-time view.

The gotcha: a write-heavy child after fork can double memory usage as
COW faults copy page after page. Redis is famous for this — a background
save during heavy writes can spike RSS toward 2×.

Diagnosing memory in production

$ free -h
              total  used  free  shared  buff/cache  available
Mem:            31G   28G   0.4G   0.1G        2.6G       1.1G
Swap:          2.0G  1.9G   0.1G
// swap almost full + available tiny = pressure. Not proof of thrash.

$ vmstat 1
 r  b   swpd   free  si   so    cs
 2  9  1.9G   400M  4200 3800  42000
// si/so = pages swapped IN/OUT per second. Sustained non-zero
// si+so is THE signature of thrashing. b=9 blocked, cs very high.

$ ps -eo pid,comm,rss,maj_flt --sort=-rss | head -3
  PID COMMAND          RSS  MAJFL
 4211 java        24500000  182004   // major faults = disk hits

$ dmesg -T | grep -i "killed process"
// the answer to "why did my service disappear at 3am"