Least Recently Used (LRU) paging algorithm always more efficient than FIFO?

Question

I am doing a project simulating page replacement for my operating systems course. I have a simulator than runs all three algorithms on 1200 references. I am getting page fault rates, however, where the LRU algorithm is getting an equal to or lower score than FIFO only most of the time. Occasionally an input will run that LRU will have a slightly higher page fault rate than FIFO. Is this incorrect?

I am using counters for each page number that are incremented each round to implement LRU. The page being used has its counter reset to 0. When I swap a frame, I use my frame that has the maximum counter value. I feel my implementation should be correct.

Answer 1

It can certainly happen that LRU is not optimal, and FIFO might even work out better.

Consider, for example, an application which repeatedly sequentially scans a large array (too large to fit in memory) always starting at the beginning, usually getting far enough to force page replacement, but often not getting to the end.

An optimal strategy would, I think, keep early pages in the array, which will be used on every scan, in preference to recently accessed pages, which might not be needed again for some time. This strategy would be more similar to FIFO than LRU.