📄 Page Replacement — LRU, FIFO & Optimal

It takes the reference string you provide — a sequence of page numbers a process accesses over time — and replays it one reference at a time against a fixed number of memory frames, using whichever page-replacement policy you select. Each column in the frame table represents one reference, each row one physical frame, and every step is marked as either a hit (page already resident) or a fault (page had to be loaded, possibly evicting another).

FIFO evicts whichever page has been resident longest, tracked with a simple rotating pointer. LRU evicts the page least recently referenced, using a timestamp recorded on every hit. Clock approximates LRU cheaply with a circular reference-bit scan that gives recently touched pages a second chance before eviction. Optimal looks ahead in the reference string and evicts the page whose next use is furthest in the future — the provably best possible choice, though it needs knowledge no real system has.

Click the "Bélády's anomaly preset" button, which loads the reference string 1 2 3 4 1 2 5 1 2 3 4 5 and selects FIFO. Run it with the Frames slider at 3, note the fault count, then increase Frames to 4 and run again: FIFO produces 10 faults with 4 frames versus 9 with 3, even though it was given more memory. Switching the policy to LRU or Optimal on the same string shows faults only ever decrease or stay flat as frames increase.

LRU and Optimal are "stack algorithms": the set of pages they keep resident with n frames is always a subset of what they would keep with n+1 frames, which mathematically guarantees faults never increase when memory grows. FIFO and Clock do not have this stack property — the specific page a FIFO policy chooses to evict can change in ways that are not simply "keep everything from the smaller-frame case plus one more," which opens the door to anomalous behaviour.

Every reference in the string is classified as a hit (page already in a frame) or a fault (page absent, requiring a load and possibly an eviction). The hit ratio is simply hits divided by total references, and it is the standard way operating-systems textbooks compare replacement policies on the same workload: a higher hit ratio for a given amount of memory means fewer expensive disk fetches.