KernelTrap: Page Replacement Design

“A university student studying operating systems asked about why
the Linux kernel uses two chained lists in its LRU (least recently
used) page replacement algorithm. Andrea Arcangeli, whose virtual
memory subsystem was merged into the 2.4.10 kernel, explained,
‘back then I designed it with two lru lists because by splitting
the active from the inactive cache allows to detect the cache
pollution before it starts discarding the working set.’ He went on
to add, ‘a page in the inactive list will be collected much more
quickly than a page in the active list, so the pollution will be
collected more quickly than the working set. Then the VM while
freeing cache tries to keep a balance between the size of the two
lists to avoid being too unfair, obviously at some point the active
list have to be de-activated too…'”

Complete Story