Least frequently used
Least Frequently Used (LFU) is an algorithm that uses a fixed-size cache to select the entry that is evicted from the cache when the cache is full. The entry from the cache that has so far been used the least often is always displaced. For this purpose, the algorithm notes for each entry in a counter how often this entry has already been accessed.
If the situation arises that the algorithm has to choose between two entries with the same counter, the FIFO algorithm can be used, for example .
implementation
With LFU, a counter is kept for each entry in the cache, which indicates how often the entry was accessed. Each access increases the counter. If an entry has to be replaced because the cache is full, the entry with the fewest accesses is replaced.
example
| A: 2 | A: 2 | Q: 1 | ||
| B: 3 | –B → | B: 4 | –F → | B: 4 |
| C: 8 | C: 8 | C: 8 | ||
| Cache hit | Cache miss |
|---|
Time-dependent variant
A problem with this algorithm is that an entry that was used frequently at the beginning (for example when loading or initializing) has a high count. Even if the entry is no longer accessed, the counter status of the entry remains high and the entry is not initially displaced. This means that a space in the cache remains practically unused.
A solution to this problem can be, for example, to halve the counter readings at regular time intervals, which leads to an exponential decrease. This prevents an entry that has been used a lot for some time, but which is then hardly accessed at all, from being kept in the cache forever.
rating
Advantages :
- Relatively easy to implement
- Observes the age of an entry (if the meter readings are regularly halved)
- Observes the access frequency of an entry
Cons :
- An entry that is used frequently is only replaced after many misses and thus blocks the cache
See also
literature
- Andrew S. Tanenbaum: Modern Operating Systems . 3. Edition. Pearson Studium, 2009, ISBN 3-8273-7342-5 (comprehensive explanations on memory management, translation from English)