virtual memory 4486
old post discussing how hardware address translation worked on trout 1.5 (3090), including email from...
Brian Inglis
FIFO, like all these algorithms, tries to predict future behaviour from the past. LRU guesses that pages that have not been used for a while have moved out of the working set, LFU prefers pages that have not been used very often, and FIFO thinks that the working set typically moves through the page set, so old pages are more likely to have moved out of it.
The standard objection to FIFO is that it has the undesirable property of being able to perform worse given more real memory. LRU and friends have the property that if you repeat a run with more real memory, then, at any time t, the set of pages in memory will be a superset of the pages in memory at time t in the previous run, i.e the most important pages are in memory, and adding more memory will not cause any of them to be not in memory at the same point of the run.
FIFO cannot guarantee such good behaviour. It is quite easy to set up an end trace that demonstrates this.
--brian
-- Wellington, New Zealand
actually LRU replacement strategy has the property that it can degenerate to FIFO replacement strategy ... i.e. program behavior that cycles through memory location. An example is the apl-360 memory management within...
"What's life? Life's easy. A quirk of matter. Nature's way of keeping meat fresh."
Alt Folklore Computers from Newsgroups