The Optimal Caching Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 7: | Line 7: | ||
=The Problem= | =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. | 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. | ||
=The Bélády Theorem= | |||
Revision as of 02:15, 20 October 2021
External
Internal
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.