A CLOCK-Pro page replacement implementation [LWN.net]

A CLOCK-Pro page replacement implementation

Posted Aug 18, 2005 7:42 UTC (Thu) by lacostej (guest, #2760)
Parent article: A CLOCK-Pro page replacement implementation

Once again a great article. Thanks.

to post comments

A CLOCK-Pro page replacement implementation

Posted Aug 25, 2005 11:58 UTC (Thu) by forthy (guest, #1525) [Link]

I've proposed something like this probably 5 years ago. Well, I've only
started a discussion, and didn't write code, and the discussion was turned
down, because the Linux kernel maintainer back then thought the VM was
"good enough" (I don't think so).

The main point in the scheme I proposed is a multi-level list of pages,
not just a two-level as it is now. Pages which have been accessed recently
elevate by one level, pages which didn't go down one level. That way,
frequently used pages end up on the top, while unused pages quickly turn
down to the bottom, making them subject for eviction. Page scanning should
depend on page age, i.e. recently allocated pages should be scanned more
often than old pages.

New pages, however, don't start at the top, but (maybe depending on how
they were allocated) somewhere in between.

My other pet peeve is the page size. My rule of thumb for random data
access is that access time and transfer time should be about the same.
I.e. 4k pages, which take 10ms to access and 0.1ms to transfer, are ways
too small. The swap in bandwidth is about 400k/s. You can write a small
memory hog which evicts most of the other programs in a second (writing
out sequential pages is easy), and then wait for a minute to have them
demand-page in again (no easy read-in of sequential pages).

At the time where the page size decission was made (~1985), the 4k size
did make sense, taking my rule of thumb into account (same 10ms access
time, but clearly less than 1MB/s transfer). Fortunately, it's only a few
years when the next larger native page size on x86 (2MB) will fit in well
with the rule of thumb, and then should be used.