The Optimal Caching Problem

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/VMnNW/application-optimal-caching
• An anomaly in space-time characteristics of certain programs running in a paging machine by Bélády https://dl.acm.org/doi/10.1145/363011.363155

Internal

• Algorithms

Overview

The optimal caching problem can be solved with a greedy algorithm. A cache is a small fast memory.

The Problem

The problem consists in processing a sequence of "page requests". When a page that does not exist in cache is requested, the page must be brought from the big slow memory into the fast memory, and that constitutes a cache miss, or a "fault". As long as there is sufficient space left in cache, a fault triggers a simple page load. When the cache fills up, a fault causes an existing page to be evicted. The question is what page should be evicted from the cache to minimize the number of fault on the long term.