As part of my operating systems homework, I was asked to compare the number of page faults produced by first-in-first-out and least-recently-used page-replacement strategies for a given sequence of page accesses. Perplexingly, it appears that FIFO produced fewer page faults than LRU. Is this possible, or have I made a mistake?
Yes, it's possible for FIFO to beat LRU. The smallest example I can think of,
Cache size: 2 pages.
Access pattern: A, B, A, C
After that, the LRU cache contains "A, C", whereas the FIFO cache contains "B, C". They have each missed 3 times so far. So if the next page access is "B", then FIFO beats LRU. If it's "A", LRU beats FIFO. If it's anything else, they remain tied.