Least frequently used
Least frequently used ( LFU) ( " dislike most used " ) is an algorithm, which describes the procedure for replacing a page in the page table. Is understood as a page a block of memory of the computer memory of fixed size. The page table is a table that will help you (or vice versa ) can convert a logical memory address to a physical memory address (paging).
The algorithm says that the person Page entry is replaced in the page table, which was previously used the least.
One problem with this algorithm is that a page that was used to start a lot, has a high counter (the counter indicates how many times the Page entry was used in the page table ). This situation is quite possible during charging. Although the Page entry is then no longer queried, this entry remains in the page table, since the count is high enough. Thus you lose a place in the page table. A solution to this problem may be, for example, the counts per unit of time by one bit to the right to shift, resulting in an exponential decay of the counter. This will prevent that an entry which has been used for some time much, but then almost no longer accessed can keep forever in the page table.
If the situation should arise that the algorithm between two Page entries must select with the same level meter, can be applied, for example, the FIFO algorithm.
Advantages:
- Relatively easy to implement
- Notice the age of a page
- Note the reference frequency of side
Cons:
- Once a frequently referenced page is replaced after several misses and thus blocks the cache
Implementation
LFU at a reference counter is passed to each page in the cache that indicates how often the page has been accessed. Each page view increases the reference count. Must be a side to be replaced because the cache is full, the side with the fewest references is replaced.