Virtual memory systems maintain information about the pattern of page use in order to facilitate page replacement. Typically, some LRU-like policy is used for page replacement, and so the operating system kernel must maintain information about the recency of last use for each page. Such information tends to be either some kind of queue to impose an ordering among the pages (such as the Segmented FIFO policy), or some kind of marker to divide pages into recency categories (such as the CLOCK policy and its use of hardware reference bits.)
This information is ordinal, as the policies outlined are concerned only with choosing the page with the lowest priority for eviction. However, some newer policies for virtual memory management also rely on cardinal recency information. Specifically, the concept of a LRU queue histogram has been proposed for a number of different studies: EELRU, adaptive compressed caching, demand prepaging, and Patterson, et al.'s filesystem caching and prefetching. In virtual memory systems, keeping a perfect histogram would introduce unreasonable overhead for the same reason that perfect LRU replacement would. So, we propose approximations to keeping this cardinal histogram information, on-line, in a manner that is sufficiently accurate for the policies that rely on the information, but without introducing high overhead.
This project involves the implementation and experimentation with recency information gathering in a real OS kernel. Specifically, we are modifying a recent version of the stable line of kernels (version 2.4.20), drastically changing its virtual memory management subsystem. We are debugging these changes first with User-Mode Linux (UML), which itself required some modifications, and then on an Intel i386 machine. We expect that this experimental version of the kernel will only operate on those two architectures.