The Optimal Caching Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 6: | Line 6: | ||
The optimal caching problem can be solved with a [[Algorithms#Greedy_Algorithms|greedy algorithm]]. A [[Cache|cache]] is a small fast memory. | The optimal caching problem can be solved with a [[Algorithms#Greedy_Algorithms|greedy algorithm]]. A [[Cache|cache]] is a small fast memory. | ||
=The Problem= | =The Problem= | ||
The problem consists in processing a sequence of "page requests". | 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. | ||
Revision as of 02:13, 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.