Cheat SheetsOperating SystemsMemory Management

Memory Management — Cheat Sheet

Operating Systems · 10 topics. Download the PDF or the Instagram carousel and share it.

Cheat Sheet · AiCanCode.org
Memory Management
Operating Systems10 topicsQuick revision reference
1

Memory Hierarchy

The memory hierarchy arranges storage from fastest and smallest (registers) to slowest and largest (network storage), exploiting the principle of locality to make programs run efficiently.

  • ✓Memory hierarchy: registers < L1 < L2 < L3 < RAM < SSD < HDD < network — speed decreases, size increases.
  • ✓Temporal locality: recently accessed data will likely be accessed again — exploited by caches.
  • ✓Spatial locality: nearby memory is likely accessed together — CPU fetches 64-byte cache lines.
  • ✓Array traversal is cache-friendly (sequential); linked list traversal causes cache misses (pointer chasing).
  • ✓Row-major access of 2D arrays in Java is faster than column-major due to spatial locality.
  • ✓L1 cache is ~100x faster than RAM; RAM is ~1000x faster than SSD — design data structures accordingly.
Java — array (cache-friendly) vs LinkedList (cache-unfriendly) benchmark
// Cache-friendly (array) vs cache-unfriendly (LinkedList) traversal
int SIZE = 10_000_000;

// Array: contiguous memory — excellent spatial locality
int[] array = new int[SIZE];
Arrays.fill(array, 1);

long start = System.nanoTime();
long sum = 0;
for (int x : array) sum += x;   // sequential access → CPU prefetcher works perfectly
long arrayTime = System.nanoTime() - start;

// LinkedList: each node is a separate heap object — random memory locations
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < SIZE; i++) list.add(1);

start = System.nanoTime();
sum = 0;
for (int x : list) sum += x;   // pointer-chasing → cache miss on every node!
long listTime = System.nanoTime() - start;

System.out.printf("Array traversal:      %d ms%n", arrayTime  / 1_000_000);
System.out.printf("LinkedList traversal: %d ms%n", listTime   / 1_000_000);
System.out.printf("Speedup:              %.1fx%n", (double) listTime / arrayTime);
// Typical result: array is 5x–20x faster than LinkedList for sequential traversal
2

Virtual Memory & Address Space

Virtual memory gives each process the illusion of a large, private address space by mapping virtual pages to physical frames, allowing processes larger than physical RAM to run.

  • ✓Each process has its own virtual address space — isolation prevents one process from corrupting another.
  • ✓Address space layout: text → data → BSS → heap (grows up) → gap → stack (grows down) → kernel.
  • ✓32-bit processes are limited to 4 GB address space; 64-bit processes have 128 TB virtual space.
  • ✓Java -Xmx controls max heap size — only the heap portion of the virtual address space.
  • ✓CompressedOops encodes 64-bit heap pointers in 32 bits; disabled automatically above 32 GB heap.
  • ✓Memory-mapped files use demand paging to load file contents — only accessed pages consume RAM.
Java — virtual address space layout and JVM memory flags
// Java: controlling heap portion of virtual address space
// java -Xms512m -Xmx2g -Xss256k -XX:MaxMetaspaceSize=256m MyApp
//
// Virtual address space breakdown for a typical JVM process:
// ┌─────────────────────────┐ high address
// │  Kernel space (1TB+)    │ — inaccessible from user code
// ├─────────────────────────┤
// │  Stack(s) — one per     │ — grows down; -Xss controls each thread stack
// │  thread (~256KB–2MB)    │
// ├─────────────────────────┤
// │  Memory-mapped files,   │
// │  JVM code cache (JIT)   │
// ├─────────────────────────┤
// │  Heap (Java objects)    │ — -Xms to -Xmx; GC operates here
// ├─────────────────────────┤
// │  Metaspace (class meta) │ — -XX:MaxMetaspaceSize
// ├─────────────────────────┤
// │  JVM + libc text/data   │ — read+exec
// └─────────────────────────┘ low address (0x0 — unmapped, catches null deref)

// Checking runtime memory from Java
Runtime rt = Runtime.getRuntime();
long heapUsed = rt.totalMemory() - rt.freeMemory();
long heapMax  = rt.maxMemory();
System.out.printf("Heap: %d MB used / %d MB max%n",
    heapUsed / 1_048_576, heapMax / 1_048_576);

// OutOfMemoryError = heap portion exhausted (not all virtual memory)
// StackOverflowError = thread stack portion exhausted
3

Paging

Paging divides virtual memory into fixed-size pages and physical memory into frames, using a page table to translate virtual addresses to physical addresses, eliminating external fragmentation.

  • ✓Paging divides virtual memory into fixed-size pages (4 KB typical) and physical RAM into same-size frames.
  • ✓Page table maps virtual page number → physical frame number; maintained per process by the OS.
  • ✓Physical address = frame_number × page_size + page_offset (bottom 12 bits for 4 KB pages).
  • ✓Page table entry bits: valid (in memory?), dirty (written?), reference (accessed recently?).
  • ✓Multi-level page tables (4-level on x86-64) avoid storing page table entries for unused virtual regions.
  • ✓Paging eliminates external fragmentation — any free frame can satisfy any page request.
Java — virtual-to-physical address translation simulation
// Address translation formula
// Virtual Address = [Page Number | Page Offset]
// Physical Address = frame_number × page_size + offset

// Example: page size = 4 KB = 4096 bytes
int PAGE_SIZE = 4096;
int virtualAddress = 0x5A3F;  // example virtual address

int pageNumber = virtualAddress / PAGE_SIZE;   // top bits
int offset     = virtualAddress % PAGE_SIZE;   // bottom 12 bits

System.out.printf("Virtual address: 0x%X%n", virtualAddress);
System.out.printf("Page number:     %d%n", pageNumber);
System.out.printf("Offset:          %d (0x%X)%n", offset, offset);

// Simulated page table: page# → frame#
int[] pageTable = {3, 7, 2, 5, 1};  // page 0 → frame 3, page 1 → frame 7, etc.

if (pageNumber < pageTable.length) {
    int frameNumber   = pageTable[pageNumber];
    int physicalAddr  = frameNumber * PAGE_SIZE + offset;
    System.out.printf("Frame number:    %d%n", frameNumber);
    System.out.printf("Physical addr:   0x%X%n", physicalAddr);
} else {
    System.out.println("Page fault! Page not in table.");
}
// Standard 4KB page: 12-bit offset, remainder = page number
4

Segmentation

Segmentation divides a process's address space into variable-size logical segments (code, data, heap, stack), each with independent base, limit, and protection attributes.

  • ✓Segmentation divides address space into variable-size logical segments, each with base + limit + permissions.
  • ✓Physical address = segment base + offset; OS raises segfault if offset exceeds limit.
  • ✓Each segment has independent protection: code = rx, data/heap/stack = rw.
  • ✓External fragmentation: variable-size segments leave unusable holes in physical memory.
  • ✓Compaction solves external fragmentation but is expensive (stop, copy, update pointers).
  • ✓Modern x86-64 OS use flat segmentation (all bases = 0) combined with paging for all practical isolation.
Java — segment table simulation with bounds check and protection
// Segmentation: logical address = [segment number, offset]
// Physical address = segment_base + offset  (if offset < segment_limit)

// Simulated segment table
record Segment(int base, int limit, String permission) {}

Segment[] segmentTable = {
    new Segment(0x1000, 0x0FFF, "rx"),   // seg 0: code (read+exec)
    new Segment(0x5000, 0x1FFF, "rw"),   // seg 1: data (read+write)
    new Segment(0x8000, 0x3FFF, "rw"),   // seg 2: heap (read+write)
    new Segment(0xF000, 0x1FFF, "rw"),   // seg 3: stack (read+write)
};

// Translate logical address [segment=1, offset=0x100]
int segNum = 1;
int offset = 0x100;
Segment seg = segmentTable[segNum];

if (offset > seg.limit()) {
    System.out.println("Segmentation fault: offset exceeds limit!");
} else {
    int physicalAddr = seg.base() + offset;
    System.out.printf("Logical [%d:0x%X] → Physical 0x%X  (perm: %s)%n",
        segNum, offset, physicalAddr, seg.permission());
}

// Attempt to write to code segment → protection violation
segNum = 0; offset = 0x10;
System.out.println("Code segment permission: " + segmentTable[segNum].permission());
// A write attempt to seg 0 (rx) would fault — OS enforces this via segment permissions
5

Page Faults & Demand Paging

A page fault occurs when a process accesses a virtual page not currently in physical RAM, triggering the OS to load it from disk — demand paging loads pages only when first accessed.

  • ✓Demand paging loads pages only when first accessed — program starts instantly without loading everything.
  • ✓Minor page fault: page is in memory but PTE not set — handled without disk I/O.
  • ✓Major page fault: page must be loaded from disk — costs ~1–10 ms (millions of CPU cycles).
  • ✓The page fault handler validates the address, allocates a frame, loads from disk, updates PTE, and restarts.
  • ✓Java OutOfMemoryError means heap limit reached — not a page fault (that would be transparent to Java).
  • ✓Memory-mapped files use demand paging — only accessed pages consume RAM, ideal for large datasets.
Pseudocode — OS page fault handler with minor vs major fault distinction
// Page fault handler (OS pseudocode)
void handlePageFault(Process p, long virtualAddress) {
    // 1. Validate: is this address in the process's valid VMA (virtual memory area)?
    if (!p.isValidAddress(virtualAddress)) {
        sendSignal(p, SIGSEGV);  // → Java NullPointerException / OOBE
        return;
    }
    // 2. Check if minor fault (page in memory, PTE not set)
    if (isPageInMemory(virtualAddress)) {
        updatePageTableEntry(p, virtualAddress);  // no disk I/O
        return;  // minor fault handled
    }
    // 3. Major fault: find a free frame (or evict a page)
    int frame = findFreeFrame();
    if (frame == -1) frame = evictPage();   // page replacement algorithm
    // 4. Load page from disk (swap or file)
    loadPageFromDisk(p, virtualAddress, frame);  // ~5ms disk I/O
    // 5. Update PTE: mark valid, set frame number
    p.pageTable[getPageNumber(virtualAddress)] = frame | VALID_BIT;
    // 6. Restart the faulting instruction
}

// Java: triggering page faults deliberately (warm-up vs cold start)
// Cold start: JVM reads class files → major page faults on each new class loaded
// After warm-up: all hot pages in RAM → no page faults → fast execution
6

Translation Lookaside Buffer (TLB)

The TLB is a small hardware cache of recent virtual-to-physical page translations that makes address translation nearly instantaneous on a hit, avoiding expensive page table walks.

  • ✓TLB is a hardware cache of recent page table entries — a hit translates addresses in ~1 CPU cycle.
  • ✓TLB miss triggers a hardware page table walk — ~20-100 cycles; 4 memory reads on x86-64.
  • ✓TLB reach = entries × page size; 64 entries × 4 KB = 256 KB — small for multi-GB heaps.
  • ✓Context switch without ASIDs requires full TLB flush — causes TLB cold-start miss surge.
  • ✓Huge pages (2 MB) increase TLB reach 512x — critical for GC performance on large Java heaps.
  • ✓EAT = hit_rate × (tlb_time + mem_time) + miss_rate × (tlb_time + page_walk + mem_time).
Java — Effective Access Time with TLB hit/miss calculation
// Effective Access Time calculation
// Assumptions: TLB access = 1 ns, Memory access = 100 ns
// TLB hit rate = 99% (h = 0.99)

double tlbAccessTime  = 1.0;    // nanoseconds
double memAccessTime  = 100.0;  // nanoseconds
double hitRate        = 0.99;

// TLB hit path:  TLB lookup (1ns) + memory access (100ns) = 101 ns
// TLB miss path: TLB lookup (1ns) + page table walk (4×100ns) + memory access (100ns) = 502 ns
double hitCost  = tlbAccessTime + memAccessTime;          // 101 ns
double missCost = tlbAccessTime + 4 * memAccessTime + memAccessTime;  // 502 ns (4-level PT)

double eat = hitRate * hitCost + (1 - hitRate) * missCost;
System.out.printf("EAT = %.1f ns  (ideal no-TLB cost: %.0f ns)%n",
    eat, 4 * memAccessTime + memAccessTime);
// EAT ≈ 106 ns vs 500 ns without TLB → ~5x speedup at 99% hit rate

// TLB reach = TLB entries × page size
int tlbEntries = 64;
int pageSize   = 4096; // 4 KB
System.out.printf("TLB reach: %d KB%n", tlbEntries * pageSize / 1024);
// 256 KB — only covers 256 KB of working set with 4KB pages
// With 2MB huge pages: 64 × 2MB = 128 MB TLB reach!
7

Page Replacement Algorithms

When physical memory is full and a page fault occurs, the OS uses a page replacement algorithm to evict a victim page — FIFO, Optimal, LRU, and the Clock algorithm offer different trade-offs.

  • ✓FIFO evicts the oldest-loaded page — simple but susceptible to Belady's anomaly.
  • ✓Optimal (OPT) evicts the page used furthest in the future — minimum faults but requires future knowledge.
  • ✓LRU evicts the least recently used page — excellent in practice, approximated by the Clock algorithm.
  • ✓Belady's anomaly: more frames can cause more page faults with FIFO — does not occur with LRU or OPT.
  • ✓Clock algorithm: circular list of frames; clears reference bit first, evicts on second encounter.
  • ✓Java LinkedHashMap with access-order=true is a ready-made LRU structure for application-level caches.
Java — FIFO vs LRU page replacement simulation on reference string
// Reference string: 1,2,3,4,1,2,5,1,2,3,4,5  — 3 frames
int[] refs   = {1,2,3,4,1,2,5,1,2,3,4,5};
int   frames = 3;

// ── FIFO ──────────────────────────────────────────────────────
Queue<Integer> fifo   = new LinkedList<>();
Set<Integer>   inMem  = new HashSet<>();
int fifoPF = 0;
for (int page : refs) {
    if (!inMem.contains(page)) {
        fifoPF++;
        if (fifo.size() == frames) {
            int evict = fifo.poll();   // remove oldest
            inMem.remove(evict);
        }
        fifo.add(page);
        inMem.add(page);
    }
}
System.out.println("FIFO page faults: " + fifoPF);   // 9

// ── LRU ───────────────────────────────────────────────────────
LinkedHashMap<Integer,Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
int lruPF = 0;
for (int page : refs) {
    if (!lru.containsKey(page)) {
        lruPF++;
        if (lru.size() == frames) {
            // Remove least recently used (first entry in access-order map)
            lru.remove(lru.keySet().iterator().next());
        }
        lru.put(page, 1);
    } else {
        lru.get(page);  // access-order map: moves page to tail
    }
}
System.out.println("LRU  page faults: " + lruPF);   // 8

// Optimal = 6 faults (requires future knowledge — theoretical minimum)
System.out.println("OPT  page faults: 6  (theoretical minimum)");
8

Thrashing

Thrashing occurs when a process spends more time paging than executing, caused by insufficient physical frames to hold the active working set, collapsing CPU utilisation.

  • ✓Thrashing: processes spend more time swapping pages than executing — CPU utilisation collapses.
  • ✓Caused by sum of all working sets exceeding available physical frames.
  • ✓Working set model: keep all pages referenced in the last Δ time units in memory.
  • ✓PFF algorithm: give more frames when fault rate is high, reclaim when low.
  • ✓Solution: reduce degree of multiprogramming — suspend a process to free frames for remaining ones.
  • ✓Java equivalent: GC thrashing when heap is too small — JVM spends >98% in GC, triggers OOM.
Java — working set window simulation and CPU load monitoring
// Working Set Model — conceptual simulation
// Working set W(t, Δ) = distinct pages referenced in last Δ time units

int[] accessHistory = {1,2,3,1,4,2,5,3,1,2,3,4,1,2}; // page reference string
int delta = 5;  // working set window size

for (int t = delta; t <= accessHistory.length; t++) {
    // Working set at time t = unique pages in [t-delta, t)
    Set<Integer> workingSet = new HashSet<>();
    for (int i = t - delta; i < t; i++) {
        workingSet.add(accessHistory[i]);
    }
    System.out.printf("t=%2d  Working set size: %d  pages: %s%n",
        t, workingSet.size(), workingSet);
}

// Total working set demand = sum of all process working set sizes
// If total demand > physical frames → THRASHING inevitable
// OS response: suspend (swap out) a process to reduce demand

// Detecting thrashing in production (Java metrics)
OperatingSystemMXBean osBean =
    (OperatingSystemMXBean) ManagementFactory.getOperatingSystemMXBean();
double cpuLoad = osBean.getProcessCpuLoad();
// If cpuLoad ≈ 1.0 AND throughput is near zero → likely thrashing
System.out.printf("Process CPU load: %.1f%%%n", cpuLoad * 100);
9

Internal vs External Fragmentation

Internal fragmentation is wasted space inside an allocated block; external fragmentation is free memory that exists but is too scattered to satisfy large allocation requests.

  • ✓Internal fragmentation: wasted space inside an allocated block — paging causes this (page larger than request).
  • ✓External fragmentation: total free memory sufficient but no single contiguous block large enough.
  • ✓Paging eliminates external fragmentation; segmentation suffers from it.
  • ✓Compaction solves external fragmentation by relocating objects — expensive (stop-the-world or concurrent).
  • ✓G1GC and ZGC compact the Java heap to avoid promotion failures from old-gen fragmentation.
  • ✓Buddy system: power-of-2 allocations enable O(1) coalescing — used in Linux kernel page allocator.
Java — internal fragmentation (paging) and external fragmentation example
// Internal fragmentation: paging rounds up to page size
int PAGE_SIZE = 4096;  // 4 KB

int actualRequest = 4097;  // bytes needed
int pagesNeeded   = (int) Math.ceil((double) actualRequest / PAGE_SIZE);  // 2 pages
int allocated     = pagesNeeded * PAGE_SIZE;     // 8192 bytes allocated
int wasted        = allocated - actualRequest;   // 4095 bytes wasted inside!

System.out.printf("Requested:  %d bytes%n", actualRequest);
System.out.printf("Allocated:  %d bytes (%d pages)%n", allocated, pagesNeeded);
System.out.printf("Internal fragmentation: %d bytes (%.1f%% waste)%n",
    wasted, 100.0 * wasted / allocated);

// External fragmentation: free memory exists but not contiguous
// Memory map (block sizes in KB): [FREE:4][USED:8][FREE:2][USED:16][FREE:6][USED:4][FREE:3]
int[] freeBlocks = {4, 2, 6, 3};  // KB
int totalFree = Arrays.stream(freeBlocks).sum();  // 15 KB total free
int needed = 8;  // 8 KB request
boolean canSatisfy = Arrays.stream(freeBlocks).anyMatch(b -> b >= needed);
System.out.printf("%nTotal free: %d KB, largest block: %d KB%n",
    totalFree, Arrays.stream(freeBlocks).max().getAsInt());
System.out.printf("Can satisfy %d KB request: %b  (external fragmentation = %b)%n",
    needed, canSatisfy, !canSatisfy);
10

Contiguous Memory Allocation Strategies

First Fit, Best Fit, and Worst Fit are strategies for allocating contiguous memory from a free list; each trades allocation speed for fragmentation outcomes, while the buddy system and slab allocator address specific use cases.

  • ✓First Fit: fast O(n); allocates first sufficient hole — good average performance.
  • ✓Best Fit: smallest sufficient hole — minimal per-allocation waste but creates many tiny unusable holes.
  • ✓Worst Fit: largest hole — large leftovers but poor overall fragmentation outcomes.
  • ✓Buddy system: power-of-2 blocks with O(log n) split/merge — used in Linux kernel page allocator.
  • ✓Slab allocator: fixed-size object caches with per-CPU free lists — O(1) kernel object allocation.
  • ✓In practice, First Fit and Best Fit outperform Worst Fit; First Fit is simplest and widely used.
Java — First Fit, Best Fit, Worst Fit allocation from free-hole list
// Free holes: [100, 500, 200, 300, 600] KB
// Allocation request: 212 KB

int[] holes   = {100, 500, 200, 300, 600};  // free hole sizes in KB
int   request = 212;

// First Fit: first hole >= request
for (int i = 0; i < holes.length; i++) {
    if (holes[i] >= request) {
        System.out.printf("First Fit: hole[%d]=%d KB → leftover=%d KB%n",
            i, holes[i], holes[i] - request);
        break;  // hole[1]=500 KB, leftover=288 KB
    }
}

// Best Fit: smallest hole >= request
int bestIdx = -1;
for (int i = 0; i < holes.length; i++) {
    if (holes[i] >= request) {
        if (bestIdx == -1 || holes[i] < holes[bestIdx]) bestIdx = i;
    }
}
System.out.printf("Best Fit:  hole[%d]=%d KB → leftover=%d KB%n",
    bestIdx, holes[bestIdx], holes[bestIdx] - request);
// hole[2]=300 KB, leftover=88 KB (smaller leftover, but 88KB may be too small to use)

// Worst Fit: largest hole >= request
int worstIdx = -1;
for (int i = 0; i < holes.length; i++) {
    if (holes[i] >= request) {
        if (worstIdx == -1 || holes[i] > holes[worstIdx]) worstIdx = i;
    }
}
System.out.printf("Worst Fit: hole[%d]=%d KB → leftover=%d KB%n",
    worstIdx, holes[worstIdx], holes[worstIdx] - request);
// hole[4]=600 KB, leftover=388 KB (largest leftover for future allocations)
Learn this free with Aria, your AI tutor → AiCanCode.org/learn/operating-systems