Page replacement for huge memory systems

Posted Nov 22, 2007 11:44 UTC (Thu) by forthy (guest, #1525)
Parent article: Page replacement for huge memory systems

Linux' page aging algorithm is very simple, and as pointed out by Rick, also doesn't scale well. This is about the same situation as it was with the scheduler before the O(1) scheduler came. People should remember that there isn't such a simple binary "active/inactive" flag for pages, as well. Pages have a usage history, which can be used to predict future use, and this should be used to implement a O(1) page replacement algorithm.

Basically, the simple two lists would have to be split up in a number of buckets - pages that have been used recently go to higher buckets, pages that haven't been used go to lower buckets. Different pages can start their live in different buckets - e.g. read-only cache pages probably start somewhere low, and can be evicted quickly. Picking a free page is then quite fast: Take an element of the lowest non-empty bucket. It doesn't have to be the least recently used one, random replacement strategies are not that bad, either.