1
$\begingroup$

I had been curious as to which page replacement algorithm is used in OSes like Windows and Linux. I could find that most information on the internet pointed at LRU(Least Recently Used) Algorithm.

But I was reading Modern Operating Systems by A. Tenenbaum and H. BOS, and it's stated that-

"LRU is an excellent algorithm, but it cannot be implemented without special hardware. If this hardware is not available, it cannot be used."

If this is the case then not all computers will have such special hardware. Then, how is LRU implemented in such systems running Windows or Linux?

Improve this question
$\endgroup$
3
$\begingroup$

The Linux kernel uses a (very rough) approximation of LRU, which is the reason why you find mention of LRU, even though it is not the true LRU algorithm. Here is a description taken from the source:

Per node, two clock lists are maintained for file pages: the inactive and the active list. Freshly faulted pages start out at the head of the inactive list and page reclaim scans pages from the tail. Pages that are accessed multiple times on the inactive list are promoted to the active list, to protect them from reclaim, whereas active pages are demoted to the inactive list when the active list grows too big.

You can find the full details here: https://github.com/torvalds/linux/blob/master/mm/workingset.c

Improve this answer
$\endgroup$
1
  • $\begingroup$ By the way, this is fairly common with algorithms in Operating Systems. As a general rule, every bit of time that the OS spends figuring out how to best execute user code is ironically time that it is not executing user code. So, in many cases there is a tradeoff between the most accurate algorithm that however needs a lot of time, or a "good enough" algorithm that is much faster. E.g. Linux's O(1) Task Scheduler is by all means not perfect, but it is very fast, and runs in constant time, regardless of the number of Tasks and the number of CPUs. $\endgroup$
    – Jörg W Mittag
    Jun 26 '21 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.