The Optimal Caching Problem: Difference between revisions
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 | * An anomaly in space-time characteristics of certain programs running in a paging machine by Bélády https://dl.acm.org/doi/10.1145/363011.363155 | ||
=Internal= | =Internal= | ||
Revision as of 02:16, 20 October 2021
External
- 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 Bélády https://dl.acm.org/doi/10.1145/363011.363155
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.