Re:Linux Kernel: The multi-generational LRU
by jonstewart on Monday April 19, 2021 @07:35AM
(#26861556)
The description of the current system as being composed of two LRU queues sound a lot like the 2Queues cache replacement algorithm. However, I was under the impression that Linux used CLOCK-Pro?
[ Parent
| on HN ]
They decided against it, I believe because ClockPro was too complicated (but maybe NIH?). Instead they devised their own algorithm, DClock, borrowing ideas but is also different [1]. They use an ad hoc sizing rule (50%-99%) [2] which can dramatically impact its performance, neither extreme being universally better. When reimplementing their algorithm for analysis, the hit rates skewed towards being okay but not great [3]. You can compare ClockPro [4] and DClock [5] in the simulator.
[1] https://github.com/torvalds/linux/blob/ac3a0c8472969a03c0496...
[2] https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42...
[3] https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZe...
[4] https://github.com/ben-manes/caffeine/blob/master/simulator/...
[5] https://github.com/ben-manes/caffeine/blob/master/simulator/...