Search code examples
algorithmhardwarefifolru

LRU vs FIFO vs Random

When there is a page fault or a cache miss we can use either the Least Recently Used (LRU), First in Fist Out (FIFO) or Random replacement algorithms. I was wondering, which one provides the best performance aka the least possible future cache miss'/page faults?

Architecture: Coldfire processor

Solution

  • No perfect caching policy exists because it would require knowledge of the future (how a program will access memory).

    But, some are measurably better than others in the common memory access pattern cases. This is the case with LRU. LRU has historically given very good performance in overall use.

    But, for what you are trying to do, another policy may be better. There is always some memory access pattern that will cause a caching policy to perform poorly.

    You may find this thread helpful (and more elaborate!) Why is LRU better than FIFO?