Cache Management

Before diving into policies, we first describe the problem we are trying to solve in more detail. Given that the main memory holds some subset of all the pages in the system, it can rightly be viewed as a cache for virtual memory pages in the system. Thus, our goal in picking a replacement policy for this cache is to minimize the number of cache misses, i.e., to minimize the number of times that we have to fetch a page from disk.

Alternately, one can view our goal as maximizing the number of cache hits, i.e., the number of times a page that is accessed is found in memory.

Average memory access time

Knowing the number of cache hits and misses let us calculate the average memory access time (AMAT) for a program ( a metric computer architects compute for hardware caches“Computer Architecture: A Quantitative Approach” by John Hennessy and David Patterson. Morgan-Kaufmann, 2006. A marvelous book about computer architecture. Read it!). Specifically, given these values, we can compute the AMAT of a program as follows:

$AMAT = T_M + (P_{Miss}\ \ .\ \ T_D)$ ...