The Optimal Caching Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 1: Line 1:
=External=
=External=
* https://www.coursera.org/learn/algorithms-greedy/lecture/VMnNW/application-optimal-caching
* https://www.coursera.org/learn/algorithms-greedy/lecture/VMnNW/application-optimal-caching
* An anomaly in space-time characteristics of certain programs running in a paging machine by https://dl.acm.org/doi/10.1145/363011.363155
=Internal=
=Internal=
* [[Algorithms#Greedy_Algorithms|Algorithms]]
* [[Algorithms#Greedy_Algorithms|Algorithms]]

Revision as of 02:16, 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.

The Bélády Theorem