Check out the new USENIX Web site. next up previous
Next: Kernel 2.0 Up: Adaptive Page Replacement to Previous: Introduction

Variations of Page Replacement in Linux Kernel

Being an LRU approximation, the page replacement implementation in Linux is based on the following framework. The interacting processes are arranged in an order to be searched for NRU (Not Recently Used) pages when few free pages are available in the user space, and/or they are demanded by interacting processes. The system examines each possible process to see if it is a candidate from which NRU pages can be selected for replacement. The kernel will then check through all of the virtual memory pages in the selected process. In other words, it conducts its search for replaced pages in a process by process, then a page by page fashion. However, at some level of competition for memory, different implementations of this search can affect the memory usage behavior.

There are two ways in which page replacement can affect the possibility of thrashing. One is how many NRU pages are allowed to take away from a process continuously, another is how easily an NRU page can be produced. When the accumulated size of working sets of all active processes exceeds the available memory size, the amount of pages allowed to be replaced continuously from a process once it is selected determines the distribution of memory shortage among the processes. If only a small amount of NRU pages in each process is allowed to replace at a time, the memory shortage can spread all over the processes by searching the victim page from one process to another. If the replacement policy allows a large amount of pages to be evicted from a process once at a time, and it also has prepared enough NRU pages for eviction, memory shortage can concentrate on one or a few particular processes, which helps others have their working set established more easily. This alternative reduces the possibility of thrashing. However, in such an arrangement, the chance for the other processes to be searched for NRU pages is reduced. Thus it becomes hard to distinguish active pages in a working set from inactive pages in the other processes. This arrangement may also prevent memory space held by inactive pages from being reused by processes lacking memory space. In the following analysis of function swap_out() of Kernel 2.0, 2.2 and 2.4, where major steps regarding how to select a process for page replacement are shown in the respective flow charts, we can see the design challenge in page replacement policies.



Subsections
next up previous
Next: Kernel 2.0 Up: Adaptive Page Replacement to Previous: Introduction
Song Jiang 2001-09-09