fifo-replacement · research · also FIFO replacement

First-in first-out cache replacement

First-in first-out cache replacement evicts the resident entry that was inserted earliest, without refreshing its queue position on a hit.

Related Observatory article: First-in first-out cache replacement on hesela.com

This policy concerns eviction, not request scheduling or write durability. A larger FIFO cache can have more misses on the same reference string. [1]

Relations

related
belady-anomaly, cache-inclusion-property, lru-replacement, clock-replacement, sieve-eviction

Citations

  1. Peter Fornai and Antal Ivanyi. FIFO anomaly is unbounded. Acta Univ. Sapientiae, Informatica 2(1), 2010, pp. 80-89; sections 2-5, arXiv:1003.1336v2. (accessed 2026-10-17)
  2. Hesela: finite cache-capacity replay, with full traces and assumptions. (accessed 2026-10-17)
Sources & caveats

JSON: /data/terms/fifo-replacement.json