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 [interview], 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."

Rik van Riel [interview], author of the reverse mapping virtual memory code that was merged into the 2.5 kernel [story] noted, "since memory size has increased a lot more than disk speed over the last decade (and this is likely to continue for the next decades), the quality of page replacement algorithms is likely to become more and more important over time." In response to a proposal to split the LRU into two parts, one for the page cache and the other for mapped pages, Nick Piggin [interview] replied, "I actually had patches to do 'split active lists' a while back. They worked by lazily moving the page at reclaim-time, based on whether or not it is mapped. This isn't too much worse than the kernel's current idea of what a mapped page is." Rik offered some ideas on to how to further tune it, "for each list we keep track of: 1) the size of the list 2) the rate at which we scan the list 3) the fraction of (non new) pages that get referenced. That way we can determine which list has the largest fraction of 'idle' pages sitting around and consequently which list should be scanned more aggressively."

Nick Piggin, a college student living in Canberra Australia, has been working on an anticipatory I/O scheduler for the Linux kernel [story].

When a process reads data from a disk, the default "deadline" I/O scheduler can offer poor performance if a streamed write is happening at the same time. The reason is that many read operations require multiple reads, each reporting a result back before the next can be scheduled. Thus, each of these reads has to wait behind a queue of writes, resulting in the aforementioned performance problem. The anticipatory scheduler solves this problem nicely by pausing for a few milliseconds after each read, "anticipating" the next read request [story].

In this interview, Nick offers much more detail behind the operation of the anticipatory scheduler. His goal is to stablize and tune [story] the new scheduler, aiming utimately for inclusion into the 2.5 development kernel tree as the default Linux I/O scheduler [story]. The latest version of Nick's anticipatory scheduler can be found here in Andrew Morton's [interview] -mm kernel branch.

Ingo Molnar has been contributing to Linux kernel development since 1995 with an impressive list of accomplishments. Most recently his O(1) scheduler was merged into the 2.5 development kernel, as well as much work to enhance the handling of threads. Other highly visible contributions include software-RAID support and the in-kernel Tux web and FTP servers.

In this interview, Ingo explores how he started working on the Linux kernel noting, "it might sound a bit strange but i installed my first Linux box for the sole purpose of looking at the kernel source." He goes on to explain the concepts behind his new O(1) scheduler, and to describe many of his other kernel efforts. This interview was conducted over several months, and covers a lot of interesting ground...

Rusty Russell's new module loader was recently merged into Linus' 2.5 kernel tree [story]. This new implementation aims to cleanup and reduce the amount of code in the kernel and user space required to load a kernel module. Additionally, it now removes the requirement that kernel and user space code for modutils have to be in sync.

Dave Jones currently lives in London, employed by SuSE as a Linux kernel hacker. In the past six months since he graduated from the University of Glamorgan he has gotten involved in an impressive range of kernel related projects, including Powertweak, x86info, OProfile and the Kernel Janitors Project. Additionally, he maintains a -dj patch for the 2.5 development kernel, helping to sync it with the stable 2.4 kernel as well as offering increased stability.