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)$

where $T_M$ represents the cost of accessing memory, $T_D$ the cost of accessing the disk, and $P_{Miss}$ the probability of not finding the data in the cache (a miss); $P_{Miss}$ varies from 0.0 to 1.0, and sometimes we refer to a percent miss rate instead of a probability (e.g., a 10% miss rate means $P_{Miss}$ = 0.10). Note you always pay the cost of accessing the data in memory; when you miss, however, you must additionally pay the cost of fetching the data from disk.

For example, let us imagine a machine with a (tiny) address space: 4KB, with 256-byte pages. Thus, a virtual address has two components: a 4-bit VPN (the most-significant bits) and an 8-bit offset (the least-significant bits). Thus, a process in this example can access $2^4$ or 16 total virtual pages. In this example, the process generates the following memory references (i.e., virtual addresses): 0x000, 0x100, 0x200, 0x300, 0x400, 0x500, 0x600, 0x700, 0x800, 0x900. These virtual addresses refer to the first byte of each of the first ten pages of the address space (the page number being the first hex digit of each virtual address).

Let us further assume that every page except virtual page 3 is already in memory. Thus, our sequence of memory references will encounter the following behavior: hit, hit, hit, miss, hit, hit, hit, hit, hit, hit. We can compute the hit rate (the percent of references found in memory): 90%, as 9 out of 10 references are in memory. The miss rate is thus 10% ($P_{Miss} = 0.1$). In general, $P_{Hit} + P_{Miss} = 1.0$; hit rate plus miss rate sum to 100%.

To calculate AMAT, we need to know the cost of accessing memory and the cost of accessing disk. Assuming the cost of accessing memory ($T_M$) is around 100 nanoseconds, and the cost of accessing disk ($T_D$) is about 10 milliseconds, we have the following AMAT: $100ns + 0.1 · 10ms$, which is $100ns + 1ms$, or $1.0001 ms$, or about $$1 millisecond. If our hit rate had instead been 99.9% ($P_{Miss} = 0.001$), the result is quite different: AMAT is 10.1 microseconds, or roughly 100 times faster. As the hit rate approaches 100%, AMAT approaches 100 nanoseconds.