mjhjmtu

Linux uses the unused portions of memory for file caching, and it cleans up the space when needed.

My question is about how it picks a victim page for replacement?
There are various algorithms (LRU, FIFO, LFU and random replacement)

I'd like to know
1) What page replacement algorithms are used in Linux kernel for OS file cache?

2) If possible, I'd like to know how it have evolved over time in Linux kernel. I assume that its algorithm and implementation might change overtime considering "reasonable" changes in trends. How can I find those? Do I need to read kernel source codes?

Linux MM does seem to be a bit arcane and challenging to track down.

Linux literature makes heavy mention of LRU (Least Recently Used) in the context of MM (memory management). I haven't noticed any of the other terms being mentioned.

If you're not familiar with how basic LRU is implemented in practice for virtual memory, I came across an interesting introduction (first four paragraphs) in this article on the incomparable LWN.net.

There is a design outline around version 2.6.28-32 here:

http://linux-mm.org/PageReplacementDesign

It suggests Clock-PRO is used for file pages. There is an original paper available on it. There is an old description of Clock-PRO on LWN.net, again including some practical implementation details. Apparently Clock-PRO "attempts to move beyond the LRU approach", a variant of which is "used in most systems". It seems to put more weight on frequency.

I believe one consideration is that it's not practical to implement LFU replacement. The kernel can't track every single read of a page, not when mmap() is used to access file cache pages (e.g. this is how most programs are loaded in memory), because the performance overhead would be prohibitive.

Linux-mm has another design document for implementing Clock-PRO in Linux. This one doesn't talk about it being merged in; it was written a few months before the LWN article about it. http://linux-mm.org/ClockProApproximation

More recent descriptions are that Linux merely "uses some ideas" from Clock-PRO, and is actually a "mash of a number of different
algorithms with a number of modifications for catching corner cases and
various optimisations".

The above quote was answered a question by Adrian McMenamin. McMenamin went on to complete an MSc project in 2011, testing modifications to Linux page replacement based on the "working set model". It includes a brief description of Linux page replacement. The "variant of LRU" is named as "the 2Q [two-queue] approach for database management", a number of references are provided, and there is a diagram illustrating movement between the two queues and other state transitions. He also describes Linux as using a partial implementation of CLOCK-PRO.

I expect the LRU concept, as opposed to the other possibilities you mention, was established from the start. And the most significant change was the introduction of Clock-PRO based features, i.e. putting some more weight on frequency.

In 2013 Linux gained "thrash detection-based file cache sizing". This is probably also relevant to the question.