The Optimal Caching Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 5: | Line 5: | ||
=Overview= | =Overview= | ||
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 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. | |||
Revision as of 02:09, 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". 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.