The Optimal Caching Problem

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/VMnNW/application-optimal-caching

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". As long as there is sufficient space left in cache, the pages are brought from big slow memory into the fast memory. When the cache fills up, a new request for a page that does not exist in cache triggers a "fault" (or a cache miss) and an existing page must be evicted. The question is what page should be evicted from the cache to minimize the number of fault on the long term.