Abstract
Current caching algorithms are based on heuristics or in exible statistical mod-
els. In this thesis, I present the mixture model caching (MMC) algorithm. This
algorithm uses a exible mixture of statistical models to describe the current usage
of a computer's memory. MMC uses the expectation-maximization (EM) algorithm
to estimate all model parameters in the mixture before it evicts the page with the
smallest expected value. I present two mixture models { one that looks at the recency
and frequency of page references, and one that additionally looks at whether the last
reference to a page was for a read or for a write.
I use traces from real systems to demonstrate that MMC makes reasonable page
eviction decisions. I use published traces to compare both versions of MMC to the
least recently used (LRU) algorithm and the adaptive replacement cache (ARC) al-
gorithm. MMC outperformed LRU and compared favorably with ARC.