LRU vs FIFO page fault performance

[ResidentBiscuit]

So after some testing I've noticed some interesting results. Using the LRU page replacement algorithm hasn't really been yielding better results. Often enough it faults just as much as FIFO, sometimes even a couple more. At the best, it's performing a small percentage better.

For example, given a 1000 digit reference string and 15 page frames...

Number of frames: 15
FIFO Faults: 848
LRU Faults: 850

Obviously, this can't be correct. I've ran through this probably ~20 times and I get similar results every time and never do I see the expected results of ~35% less page faults using LRU.

[firedraco]

Have you tried it on several reference strings instead of just one? I could easily make a reference string that causes LRU or FIFO to fault as many as possible.

[ResidentBiscuit]

Yea I have a randomly generated reference string.

[firedraco]

Try running it like 1000 times and compare it then.

[Script Coder]

I do not mean to be an expert (or troll or make like I know what I am talking about) but doesn't using randomly generated stings mean that they would more than likely perform evenly?

[ResidentBiscuit]

I would imagine not. They're both fed the same string each time, just each time the program runs it generates a new string.

Why would you think it'd make them perform equally?

[naraku9333]

@Script Coder
Maybe this will help explain http://www.d.umn.edu/~cprince/courses/cs5631spring12/lectures/Chapter8-partB.pdf

[Script Coder]

I now understand a little more. I thought you were using different strings for them at the same time (hope that made sense, if not I will re-explain myself). But still a normal program (IMHO) would access memory more sequentially, maybe you should try ensuring your randomization algorithm has a slight tendency to use on of say the previous 5 results it has made?

PS: Thank you naraku9333, the pdf helped a lot with the visualization.