2

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?

Evan Kroske
  • 4,506
  • 12
  • 40
  • 59
  • 2
    Of course it's possible. There's no single algorithm that's the best in page-replacement. LRU outperforms FIFO in real world usage, but it's certainly possible to build a case in which the opposite is true. – user703016 Mar 05 '12 at 16:03
  • 3
    Suggested extension for your own edification: Given _any_ two page replacement strategies X and Y, prove that there exists a sequence of accesses such that X has fewer page faults than Y. – Nemo Mar 05 '12 at 16:11

2 Answers2

5

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.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • This has to be the smallest possible example: certainly no cachesize=1 example is possible, since LRU=FIFO when cachesize=1. And no cachesize=2, totalnumaccesses=4 example is possible, since such an example must involve an eviction on the 3rd access, but LRU and FIFO always evict the same item (if any) on the 3rd access so no differentiation happens here. – Don Hatch Apr 06 '16 at 02:30
3

It's kind of difficult to give you a hint without giving you the answer. Why don't you try setting the question for yourself ? Put yourself in the mind of your teacher, a twisted dark place, and try setting the question in such a way as will make your (fellow) students think deeply about this.

High Performance Mark
  • 77,191
  • 7
  • 105
  • 161
  • Theoretically it will obviously depend upon the given sequence. And +1 for the "twisted dark place", a very good suggestion come to think of it :D – Gargi Srinivas Mar 05 '12 at 16:11