In virtual memory, a page replacement algorithm decides which page to evict when all physical page frames are full. This tool shows how each algorithm behaves in a table, one reference at a time. Switch between FIFO, LRU, OPT and Clock to compare page fault counts and hit rates. You can also use it to check your answers to the common exam question “how many page faults occur?”
Favorites and recently used calculators are stored only in this browser (localStorage).
Results
Page faults
–
Hits
–
Hit rate
–
Red marks a frame loaded on a page fault and green a frame that was hit. For Clock, the reference bit is shown at the top right of each page.
Page faults by number of frames
Page fault counts for the same reference string with 1 to 8 page frames. The current number of frames is underlined.
With FIFO, there are places (in red) where adding frames increases the number of page faults. This is Belady's anomaly.
All frames start empty, and while free frames remain they are used from the left (these loads also count as page faults). In OPT, when several pages will never be referenced again, or will next be referenced at the same time, the page in the leftmost frame is evicted.
See it as a graph
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
Page faults and page replacement
Virtual memory divides a program's address space into fixed-size pages and loads only the pages that are needed into page frames in physical memory. When a referenced page is not in memory, a page fault occurs and the OS loads the page from storage. If there is no free frame, some page must be evicted to make room. The page replacement algorithm decides which page to evict. Reading from storage is orders of magnitude slower than accessing memory, so reducing the number of page faults directly affects performance.
How FIFO, LRU and OPT differ
FIFO evicts the page that was loaded earliest. It is simple, but it evicts a page because it is old even if it is used often. LRU evicts the page that has not been referenced for the longest time. It exploits locality, the tendency for recently used pages to be used again, so it often performs better than FIFO. OPT (optimal) evicts the page that will not be referenced for the longest time in the future, which gives the theoretical minimum number of page faults; but because it requires knowing future references, it cannot be used in practice and serves as a benchmark for evaluating other algorithms. With the example 20-reference string and 3 frames, FIFO causes 15 page faults, LRU 12 and OPT 9.
Belady's anomaly
Normally, adding page frames reduces page faults, but with FIFO it can sometimes increase them. This is called Belady's anomaly. For the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO causes 9 page faults with 3 frames and 10 with 4. LRU and OPT have the property that the pages in memory with n frames are always also in memory with n+1 frames (they are stack algorithms), so the anomaly cannot occur with them. Look for the places in the comparison table where the FIFO row increases.
Clock, used in real operating systems
Implementing LRU exactly requires updating the order on every reference, which places a heavy burden on the hardware. Real operating systems therefore often use the Clock algorithm, which approximates LRU using a reference bit for each page (set to 1 by the hardware when the page is accessed). The page frames are arranged in a circle with a hand pointing at one; when a page must be evicted, if the page under the hand has its reference bit set to 1, the bit is cleared to 0 and the hand moves on (giving the page a second chance), and the first page found with a bit of 0 is evicted. Recently referenced pages are less likely to be evicted, so Clock achieves performance close to LRU at low cost.
Intuitively, more physical pages should mean fewer page faults, but with FIFO certain access sequences are known to fault more when the page count grows from three to four. This is Bélády's anomaly. It cannot occur with stack algorithms such as LRU, where the set of pages held with more frames always contains the set held with fewer. Thrashing is constant replacement from memory shortage, and copy-on-write copies pages on write.
Step by step: A (miss, [A]), B (miss, [A,B]), A (hit, A becomes most recent), C (miss, evicts least recent B, [A,C]), B (miss, evicts least recent A, [C,B]), A (miss, evicts least recent C, [B,A]), for 5 misses. Counting 4 comes from wrongly evicting A when C arrives; under LRU, the hit on A made it the most recent. 6 overlooks the hit on the third reference.
AIt is the most common replacement policy, widely used in real caches
BIt cannot be built but gives a lower bound on misses
CIt produces exactly the same number of misses as LRU for every access sequence
Show answer and explanation
Answer: B. It cannot be built but gives a lower bound on misses
Optimal replacement (Bélády's OPT) assumes the future access order is known and evicts the block whose next use is furthest away, giving the theoretical minimum number of misses. Real hardware cannot see the future, so it cannot be implemented; instead it is applied to recorded access traces to evaluate how close policies such as LRU come to optimal. It evicts different blocks than LRU, so miss counts generally differ.
AWhen data is not in the cache and is fetched from main memory
BWhen the accessed page is not mapped to physical memory
CWhen the TLB holds the translation and the physical address is found immediately
Show answer and explanation
Answer: B. When the accessed page is not mapped to physical memory
A page fault is an exception raised when the accessed page's page-table entry is invalid, meaning it is not mapped to physical memory (it was paged out or never loaded), or when the access is not permitted, such as writing a read-only page. The OS supplies the page and retries the instruction. A cache miss is handled entirely in hardware and is not an exception. If the TLB has the translation, it completes at once and no fault occurs.
FAQ
Do loads into empty frames at the start count as page faults?
This tool counts them. Initial loads (compulsory faults) are page faults too, since the page is not in memory. If an exam question says something like “do not count the initial loads”, subtract them.
What is the difference between LRU and OPT?
LRU looks at the past and evicts the page that has gone unused the longest. OPT looks at the future and evicts the page that will go unused the longest. OPT gives the fewest page faults, but it cannot be implemented without knowing future references.
Can this be used for cache replacement too?
Yes. For a fully associative cache, treat the lines as frames and the blocks as pages, and the same calculation gives the number of misses. For a set-associative cache, calculate each set separately.
How is this tested in exams?
IT certification exams such as Japan's Fundamental and Applied Information Technology Engineer Examinations often give a reference string and a number of page frames and ask how many page faults occur with FIFO or LRU, or which pages remain at the end. The answer is the number of × marks in the “Fault” row of the table.