A system using FIFO page replacement with 3 frames produces 10 page faults on a particular reference string. When frames are increased to 4, the same string produces 12 page faults. What does this demonstrate?
AThe reference string was adversarially constructed — this would not happen with real workloads
BBelady's Anomaly: FIFO can produce more page faults with more physical frames for certain reference strings
CThe system has a bug — more frames should always reduce or maintain page faults
DLRU would show the same behavior since it is also affected by the number of frames
This is a demonstration of Belady's Anomaly, which affects FIFO and certain other replacement algorithms. Intuitively, more frames should mean fewer evictions, but FIFO's eviction criterion — 'evict the page loaded longest ago' — is not aligned with which pages are actually useful. Adding a frame can change the eviction sequence in a way that, for some reference strings, triggers more total faults. LRU does not exhibit Belady's Anomaly because it is a 'stack algorithm' — with n+1 frames, the set of pages in memory always contains the set that would be in memory with n frames, so adding a frame can only help.
Question 2 Multiple Choice
Why is exact LRU not directly implemented in most real operating systems, despite being a strong approximation of the optimal algorithm?
ALRU requires future knowledge of access patterns, just like OPT
BTracking the exact recency order of all pages requires updating a timestamp or sorted structure on every memory access, which is prohibitively expensive in hardware
CLRU performs worse than FIFO on most real workloads
DLRU requires pages to be sorted by access frequency, not recency
LRU's logic is sound — evict the page unused longest — but implementing it exactly requires knowing the precise access order of all pages at all times. This means either recording a timestamp on every memory access and finding the minimum when eviction is needed, or maintaining a stack where the accessed page moves to the top on every reference. Both approaches require hardware support on every memory access, which happens billions of times per second — the overhead is enormous. Instead, hardware provides a single reference bit per page, which the Clock (Second-Chance) algorithm exploits to approximate LRU with minimal cost.
Question 3 True / False
The Optimal (OPT) page replacement algorithm cannot be implemented in a real operating system.
TTrue
FFalse
Answer: True
OPT evicts the page that will not be used for the longest time in the future, which requires knowing future memory access patterns — impossible during normal execution. The OS only knows which pages have been accessed in the past, not which will be needed next. OPT is therefore used only as a theoretical benchmark: you can apply it retrospectively to a recorded trace to measure how close a practical algorithm comes to the theoretical minimum number of page faults. It is not an implementable policy.
Question 4 True / False
LRU page replacement can also exhibit Belady's Anomaly — adding more frames can increase page faults — just like FIFO.
TTrue
FFalse
Answer: False
Belady's Anomaly does not affect LRU. LRU is a 'stack algorithm': with n frames, the set of pages in memory is always a subset of the set in memory with n+1 frames for any reference string. This means adding a frame can only keep the same pages or more — it can never cause a useful page to be evicted. FIFO lacks this property because its eviction criterion (age of loading) is not consistently aligned with usefulness; adding a frame can alter the eviction sequence in a way that introduces new faults on some strings. OPT is also a stack algorithm and similarly immune to Belady's Anomaly.
Question 5 Short Answer
Explain why the Clock (Second-Chance) algorithm uses a reference bit per page rather than tracking exact access times, and how it approximates LRU.
Think about your answer, then reveal below.
Model answer: Hardware sets the reference bit for a page automatically on every access with zero computational overhead. The Clock algorithm sweeps through pages in a circle: if a page's reference bit is 1, it clears the bit and moves on (giving a 'second chance'); if the bit is 0, the page has not been accessed since the last sweep and is evicted. This approximates LRU because a page with reference bit = 0 has gone at least one full clock cycle without being used — a proxy for 'least recently used.' Exact LRU would require a complete sorted ordering of all pages by last-access time, too expensive to maintain per-access.
The Clock algorithm trades precision for efficiency. Exact LRU knows the full ordering of recency; Clock only distinguishes recent vs. not-recent within each sweep cycle. In practice this approximation works well because actively used pages will have their reference bits set repeatedly, while cold pages will consistently show bit = 0 and be evicted promptly. The Clock algorithm is implemented in most Unix-derived operating systems — its simplicity (one bit per page and a circularly advancing pointer) makes it suitable for the OS kernel where per-access overhead must be minimal.