The Optimal Caching Problem: Difference between revisions

From NovaOrdis Knowledge Base
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.