LRU Cache & Page Replacement lab report

1. Title and aim

Operating Systems Memory Hierarchy & Page Replacement: LRU, Clock (Second-Chance), FIFO, Belady's Anomaly, and Working Set Dynamics. To investigate operating system virtual memory hierarchies, analyze the mathematical mechanics of the Least Recently Used (LRU) page replacement policy, evaluate temporal and spatial locality under Denning's Working Set model, compare LRU against FIFO, Second-Chance Clock, and Belady's Optimal (MIN) algorithms, demonstrate Belady's Anomaly and Mattson's inclusion property in stack algorithms, verify the linear marginal hit scaling law H(C) = k_lru · C + H_0 = 6.0000 · C + 0.0000 hits across cache frame capacities C ∈ [4, 28], and calculate Effective Memory Access Time (EMAT).

2. Abstract

Seven benchmark trials were generated across physical cache frame capacities C = 4 to C = 28 frames (total in-memory cache hits H from 24 to 168 hits out of N = 200 memory references). An ordinary least-squares regression of cache hits against frame capacity yielded an empirical marginal hit rate of 6.0000 hits/cache-frame and an intercept of 0.0000 hits, demonstrating exact agreement with Denning's working set locality model H(C) = 6C (difference = 0.0000%). The empirical telemetry confirms that by maintaining strict temporal recency via a Doubly-Linked Hash Map, each additional physical frame captures an exact linear slice of recurring loop references, boosting hit ratios from 12.0% at C = 4 to 84.0% at C = 28.

3. Apparatus and fixed settings

• Doubly-Linked List Recency Chain: Maintains strict temporal access ordering of resident pages with O(1) node splicing, head MRU insertion, and tail LRU eviction.
• Hash Map Frame Pointer Index: Provides O(1) average lookup from page ID to doubly-linked list node pointers, eliminating linear cache search scans.
• Circular Buffer Second-Chance Clock Unit: Simulates hardware reference bits (R ∈ {0, 1}) and a sweeping clock hand pointer to execute low-overhead second-chance page replacement.
• Belady's Anomaly Verification Framework: Tracks FIFO page fault counts across expanding frame sizes to isolate anomalous fault spikes violating the inclusion property.
• Synthetic Memory Reference Generator: Generates reproducible address trace workloads modeling temporal loops and spatial locality under Denning's working set model.
• Memory Hierarchy Telemetry & EMAT Logger: Measures cache hits, page fault frequencies, calculates Effective Memory Access Time (EMAT), and validates linear regression against H(C) = 6C.
• Memory reference stream: N = 200 sequential page requests generated under Denning's working set model.
• LRU implementation: O(1) Hash Map index combined with a Doubly-Linked List (MRU head / LRU tail).
• Cache frame capacities tested: C ∈ [4, 8, 12, 16, 20, 24, 28] frames.
• Memory hierarchy latencies: DRAM hit latency = 100 ns; Page fault SSD servicing latency = 10,000 ns (10 µs).
• Comparative algorithms simulated: LRU (Exact), Second-Chance Clock (1 reference bit), FIFO (Circular Queue), OPT (Belady MIN).

4. Theory and graph choice

In computing systems, the massive latency disparity between primary DRAM (50–100 ns) and secondary flash SSDs or magnetic storage (10 µs to 10 ms) renders physical memory allocation a critical operating system performance bottleneck. Under virtual memory architectures, the kernel and hardware Memory Management Unit (MMU) partition memory into fixed-size pages (typically 4KB). When physical memory is saturated, loading a new page triggers a page fault requiring the eviction of an existing resident frame. The choice of which page to evict is dictated by page replacement algorithms. In 1966, Laszlo Belady proved that the theoretical optimal policy (OPT/MIN) evicts the page needed furthest in the future; however, because general-purpose operating systems cannot predict future memory references with clairvoyance, practical systems rely on statistical approximations of temporal locality. The preeminent online replacement policy is Least Recently Used (LRU), which evicts the page that has remained unaccessed for the longest duration. In software caching (database buffer pools, Web servers, Redis), LRU is implemented in strict O(1) time using a Hash Map paired with a Doubly-Linked List. Unlike FIFO—which suffers from Belady's Anomaly, where allocating more memory frames can paradoxically increase page faults—LRU belongs to the class of 'Stack Algorithms' satisfying Mattson's Inclusion Property (S(C) ⊆ S(C+1)), mathematically guaranteeing monotonic hit rate growth as cache capacity expands. In kernel-level virtual memory, true LRU is approximated via the Second-Chance Clock Algorithm, which sweeps a circular frame buffer checking a single hardware-maintained reference bit R. In this laboratory investigation, students benchmark LRU memory hit dynamics across cache capacities C ∈ [4, 28], verify the linear scaling law H(C) = 6.0000 · C + 0.0000 via ordinary least-squares regression, contrast LRU against FIFO, Clock, and Belady's OPT, analyze O(1) doubly-linked list pointer operations, evaluate Effective Memory Access Time (EMAT), and reproduce Belady's Anomaly on non-stack queues.

The mathematical regression fits the linear model y = mx + b, where x = C represents cache frame capacity in frames, y = H represents total in-memory cache hits, m represents the marginal hit rate k_lru, and b represents the baseline hit offset (theoretically H_0 = 0.0000 hits). The gradient has physical units hits/cache-frame.

5. Method

1. Initialize the synthetic address reference stream of N = 200 page requests across benchmark cache capacities C ∈ [4, 8, 12, 16, 20, 24, 28] frames, modeling a localized program loop over 32 virtual pages.
2. Initialize the doubly-linked list with dummy head (MRU) and tail (LRU) sentinel nodes. Clear the hash map index and set maximum capacity to C frames. Reset hit, miss, and pointer update counters.
3. For each incoming page reference p in the stream, query the hash map index. If page p is present (Cache Hit), unlink node p from its current position and re-insert it directly after head (MRU promotion), incrementing the hit counter H by 1.
4. If page p is absent (Cache Miss / Page Fault), increment the miss counter M. If the cache is full (resident node count = C), evict the least recently used node at tail.prev, delete its key from the hash map, and insert a new node for p at the MRU head position.
5. Re-execute the identical reference stream across Second-Chance Clock, FIFO, and Belady's Optimal algorithms under identical capacity constraints, logging relative page fault frequencies and EMAT latencies.
6. Plot recorded cache hits H(C) against cache capacity C. Perform ordinary least-squares regression to verify the theoretical marginal hit slope k_lru = 6.0000 hits/frame, intercept H_0 = 0.0000, and correlation coefficient R² = 1.00000.

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 0.00000; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 4.7246e-08. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 8.4515e-07.

Propagating the fit parameters yields a fit standard error of 4.7246e-08 hits/cache-frame, with an ideal coefficient of determination R² = 1.000000.

In operating systems virtual memory analysis and caching theory, the cache hit count H(C) = k_lru · C + H_0 = 6.0000·C + 0.0000 hits across frame capacity C is an exact algorithmic invariant for our standardized localized reference stream. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal drift, or calibration variance in counting discrete cache hits or page fault exceptions. However, in physical computer architectures and operating system kernels, wall-clock memory access latency and system throughput are heavily modulated by hardware and software dynamics: (1) Hardware Memory Management Unit (MMU) TLB miss penalties: translating virtual page numbers to physical frame numbers relies on the Translation Lookaside Buffer (TLB); TLB misses require multi-level page table walks in DRAM, adding 20–50 ns of latency per reference; (2) Secondary storage I/O latency disparity: a cache hit accesses volatile DRAM in ~50–100 ns, whereas a page fault requiring an NVMe SSD flash read incurs 10–50 µs (~500× slower), and a mechanical hard disk seek incurs 5–10 ms (~100,000× slower); (3) Dirty page writeback overhead: evicting a modified (dirty) page requires flushing its contents synchronously or asynchronously to swap space on disk before the frame can be reallocated, doubling I/O bus traffic relative to clean page evictions; and (4) Multiprocessor lock contention on cache metadata: in concurrent multicore operating systems, updating doubly-linked list pointers or clock hands requires synchronizing across CPU cores, mitigated in production by segmented LRU (2Q) or lock-free clock buffers. Ordinary least-squares linear regression of observed cache hits against frame capacity C across instances from C = 4 to C = 28 frames yields an empirical marginal hit rate k_lru = 6.0000 hits/cache-frame and baseline intercept H_0 = 0.0000 hits with zero residual variance (R² = 1.00000), verifying the working set capacity scaling bound Θ(C) with mathematical certitude.

10. Result and discussion

The empirical benchmark observations provide rigorous quantitative verification of Virtual Memory Architecture, Caching Theory, and Denning's Principle of Locality. In modern computer systems, the immense access latency gap between volatile DRAM (50–100 ns) and secondary NVMe SSD storage (10–50 µs) creates an astronomical performance penalty whenever a requested virtual page is not resident in physical memory. Evaluating Effective Memory Access Time (EMAT = h·t_hit + (1-h)·t_fault) demonstrates that even a 5% page fault rate degrades system performance by over 500%, explaining why optimizing page replacement policies is vital to operating system stability. The investigation evaluated the four foundational page replacement algorithms: Laszlo Belady's Optimal Algorithm (OPT / MIN, 1966) establishes the theoretical lower bound on page faults by evicting the page needed furthest in the future; however, because general-purpose operating systems cannot predict future memory references with clairvoyance, OPT serves solely as an offline gold standard. First-In, First-Out (FIFO) evicts the oldest resident frame; however, FIFO ignores access recency and is susceptible to Belady's Anomaly, where allocating more physical frames paradoxically increases page faults! Least Recently Used (LRU) exploits temporal locality by evicting the frame that has remained unreferenced for the longest time. Crucially, LRU belongs to the class of 'Stack Algorithms' satisfying Mattson's Inclusion Property (S(C) ⊆ S(C+1)), mathematically guaranteeing monotonic hit rate growth as cache capacity expands. In our software benchmark, LRU is implemented in strict O(1) time using a Hash Map paired with a Doubly-Linked List: hash lookup identifies target nodes in O(1) time, and 4 pointer updates splice nodes to the MRU head or evict the LRU tail. Across all benchmark trials from C = 4 to C = 28 frames, the empirical regression slope m = 6.0000 hits/frame and baseline intercept b = 0.0000 confirm the linear working set expansion model with zero residual variance (R² = 1.00000). Finally, operating system architectural analysis highlighted the Second-Chance Clock Algorithm: because tracking true LRU timestamps on every memory instruction introduces prohibitive hardware overhead, production kernels (Linux, FreeBSD, Windows NT) implement Clock approximation, sweeping a circular frame buffer with a single MMU-maintained hardware reference bit R to achieve near-LRU efficiency with zero runtime overhead.

11. Precautions and limitations

• In multithreaded LRU cache implementations, ensure that doubly-linked list node splicing and hash map updates are wrapped in fine-grained mutex locks or read-write locks to prevent pointer corruption.
• When benchmarking page replacement algorithms, ensure the reference string represents realistic program locality rather than uniform random noise, which exhibits zero temporal correlation.
• In the Second-Chance Clock algorithm, verify that the clock hand terminates search within at most two full rotations to avoid infinite loops when all reference bits are initially set to 1.
• Ensure sentinel head and tail nodes in the doubly-linked list are properly initialized to reference each other to eliminate edge-case null pointer dereferences during node insertions.

The simulated benchmark environment models idealized memory access streams where physical cache capacities C ∈ [4, 28] frames execute deterministically (H(C) = 6C hits). In physical computer systems, real-world cache throughput is heavily modulated by CPU hardware TLB miss latencies, multi-core false sharing on cache lines, kernel page fault interrupt servicing overhead (context switches, disk controller interrupts), dirty page writeback delays (swapping out dirty pages requires disk writes vs. clean pages which can be overwritten), and memory bus bandwidth saturation. In the LRU cache replacement benchmark across physical frame capacities C in [4, 28] frames (processing a standardized cyclic reference sequence of N = 200 memory page requests generated under Denning's working set model with locality parameter L = 32), each additional physical frame allocated to the cache captures an exact linear slice of the process working set. In our standardized benchmark environment, each frame added to the cache preserves exactly 6 recurring loop page references across the execution epoch. Across all benchmark capacities C ∈ [4, 8, 12, 16, 20, 24, 28], the cumulative cache hit count is strictly governed by the exact deterministic linear invariant H(C) = 6.0000 · C + 0.0000 hits (yielding hit ratios h = H/200 ranging from 12.0% at C = 4 to 84.0% at C = 28). Plotting cache hits against capacity C yields an ordinary least-squares regression slope k_lru = 6.0000 hits/cache-frame and baseline intercept H_0 = 0.0000 hits with an ideal coefficient of determination R² = 1.000000.

12. Conclusion

This laboratory investigation quantitatively verified the memory hierarchy dynamics, O(1) doubly-linked list mechanics, and working set scaling of the LRU Page Replacement Algorithm. Through systematic benchmarking across frame capacities from C = 4 to 28 frames, we verified the empirical marginal hit rate k_lru = 6.0000 hits/cache-frame and baseline intercept H_0 = 0.0000 hits with an ideal R² = 1.00000. The investigation established the microarchitectural efficiency and theoretical necessity of stack algorithms, temporal locality caching, and second-chance clock approximations, proving why LRU and its architectural descendants form the foundational core of modern virtual memory management, database buffer pools, and high-performance computing systems.