Re: Why active list and inactive list?

Rik van Riel
2007-01-23T02:24:55Z

Christoph Lameter wrote:
> On Mon, 22 Jan 2007, Rik van Riel wrote:
>
>> It would be really nice if we came up with a page replacement
>> algorithm that did not need many extra heuristics to make it
>> work...
>
> I guess the "clock" type algorithms are the most promising in that
> area. What happened to all those advanced page replacement endeavors?
> What is the most promising of those? You seem to have done a lot of work
> on those.

CLOCK-Pro seems the most promising algorithm, because it can
act well both as a first level cache (operating system running
applications) and as a second level cache (operating system
running as a file server), because it tracks both recency and
frequency well.

However, there are a few unanswered questions on clock-pro.

The big one is how we are to do some background aging in a
clock-pro system, so referenced bits don't just pile up when
the VM has enough memory - otherwise we might not know the
right pages to evict when a new process starts up and starts
allocating lots of memory.

At least we've solved the problems of keeping track of the
recently evicted pages in a cheap way, and balancing the
pressure/hotness of different caches against each other.

--
Politics is the struggle between those who want to make their country
the best in the world, and those who believe it already is. Each group
calls the other unpatriotic.