MMC: The Development of the Mixture Model Caching Algorithm

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.Thesis (M.S., Computer Science)--University of Idaho, June 201