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:

1. First in, first out (FIFO): The oldest page gets evicted
2. Last in, first out (LIFO): The newest page gets evicted
3. Last recent out (LRU): Evict page whose most recent access was earliest
4. Least frequently requested(LFU): Evict page that was least frequently requested
5. Longest forward distance (LFD): Evict page in the cache that is not requested until farthest in the future.

Attention: For the following examples we evict the page with the smallest index, if more than one page could be evicted.

Example (FIFO)

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:

Example (LFD)

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: