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.
Computer Science / LRU Cache & Page Replacement
FREE TO EXPLORELABORATORY 22 · COMPUTER SCIENCE
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). Explore interactive search algorithms, compare operation counts and analyse complexity scaling.
COMPUTE · BENCHMARK · ANALYSE
Your virtual algorithm laboratory.
CACHE HITS H(C)—
EXECUTION STATUS
Ready to execute C benchmark.
Adjust C n, then execute benchmark.
Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.
Algorithmic assumptions and limits
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.
Computational tools & environment.
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.
FOLLOW THE METHOD
A reason behind every step.
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). Suggested independent settings: 4, 8, 12, 16, 20, 24, 28 frames.
01
Working Set & Reference Stream Generation
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.
02
Cache Structure & Sentinel Node Initialization
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.
03
Sequential Address Query & Hash Lookup
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.
04
Page Fault Handling & Tail Node Eviction
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.
05
Comparative Execution: Clock, FIFO & Belady OPT
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.
06
Linear Regression & Model Verification
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.
YOUR NOTEBOOK · 0 OBSERVATIONS
Turn measurements into asymptotic insight.
Points are your recorded benchmark observations. The regression line validates LRU Cache & Page Replacement complexity scaling.
LINEAR ASYMPTOTIC FIT · y = mx + b
H(C) = k_lru · C + H_0 = 6.0000 · C + 0.0000 hits
| # | Cache Frame Capacity C (frames) | Cache Hits H(C) (hits) | Cache frame capacity C (frames) | Cache hits H(C) = 6.0000 · C + 0.0000 (hits) | Remove |
|---|
No readings yet. Execute a C benchmark and record it.
Calculate it yourself.
CHECK YOUR UNDERSTANDING