The caching problem arises from the limitation of finite space. Lets assume our cache C
has k
pages. Now we want to process a sequence of m
item requests which must have been placed in the cache before they are processed.Of course if m<=k
then we just put all elements in the cache and it will work, but usually is m>>k
.
We say a request is a cache hit, when the item is already in cache, otherwise its called a cache miss. In that case we must bring the requested item into cache and evict another, assuming the cache is full. The Goal is a eviction schedule that minimizes the number of evictions.
There are numerous greedy strategies for this problem, lets look at some:
Attention: For the following examples we evict the page with the smallest index, if more than one page could be evicted.
Let the cache size be k=3
the initial cache a,b,c
and the request a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c
:
|Request | a | a | d | e | b | b | a | c | f | d | e | a | f | b | e | c | |:––––:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |cache 1
| a | a | d | d | d | d | a | a | a | d | d | d | f | f | f | c | |cache 2
| b | b | b | e | e | e | e | c | c | c | e | e | e | b | b | b | |cache 3
| c | c | c | c | b | b | b | b | f | f | f | a | a | a | e | e | |cache miss| | | x | x | x | | x | x | x | x | x | x | x | x | x | x |
Thirteen cache misses by sixteen requests does not sound very optimal, lets try the same example with another strategy:
Let the cache size be k=3
the initial cache a,b,c
and the request a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c
:
|Request | a | a | d | e | b | b | a | c | f | d | e | a | f | b | e | c | |:––––:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |cache 1
| a | a | d | e | e | e | e | e | e | e | e | e | e | e | e | c | |cache 2
| b | b | b | b | b | b | a | a | a | a | a | a | f | f | f | f | |cache 3
| c | c | c | c | c | c | c | c | f | d | d | d | d | b | b | b | |cache miss| | | x | x | | | x | | x | x | | | x | x | | x |
Eight cache misses is a lot better.
Selftest: Do the example for LIFO, LFU, RFU and look what happend.
The following example programm (written in C++) consists of two parts:
The skeleton is a application, which solves the problem dependent on the chosen greedy strategy: