Introduction

Linux adopts the clock algorithm, an LRU approximation, to conduct its page replacement. In a multiprogrammed environment, the global LRU approximation replacement algorithm selects an LRU page for replacement throughout the entire user memory space of the computer system. The risk of low CPU utilization increases if the memory page shortage happens all over the interacting processes. For example, a process is not able to access its resident memory pages when the process is resolving page faults. These already obtained pages may soon become LRU pages when memory space is being demanded by other processes. When the process is ready to use these pages in its execution turn, these LRU pages may have been replaced to satisfy requested allocations of other processes. The process then has to request the virtual memory system to retrieve these pages by replacing LRU pages of others. The page replacement may become chaotic, and could cascade among the interacting processes, eventually causing system thrashing. Once all interacting processes are in the waiting queue due to page faults, the CPU is doing little useful work. This situation is affected by the following conditions: (1) the size of memory space in the system, (2) the number of processes, (3) the dynamic memory demands of each process, and (4) the page replacement algorithm. A robust page replacement algorithm allows the system to keep enough processes active in memory to keep the CPU busy. When a page replacement algorithm fails to prevent thrashing, some operating systems, such as FreeBSD and Solaris, employ the memory load control mechanism to suspend, even swap out some processes for a period of time. However, the memory load control has its drawbacks. It introduces too much intervention to the suspended/swapped processes. Some processes even can not afford to stop for a certain time period. After suspension or swapping out, the whole memory space of the processes can be lost, thus more efforts are needed thereafter in activation or swapping in. Moreover, process swapping is an expensive operation for both systems and user programs [8].

The most destructive aspect of thrashing is that, although thrashing may have been triggered by a brief, random peak in workload (such as all of the users of a system happening to press Enter at the same second), the system might continue thrashing for an indefinitely long time. Considering large variations of memory demands from multiple processes and dynamic memory demands in their lifetimes of the processes, page replacement algorithms should be robust enough to deal with thrashing. Linux developers have tried to provide a solution to address the issue by improving the page replacement performance. Its main idea is to let one or more memory-intensive processes release more memory pages, in order to help others build up their working sets and then make full use of CPU cycles. In this paper, we first analyze the variations of page replacement in Linux kernels on this aspect. Considering the conflicting interests between CPU utilization and memory utilization, we show the effectiveness of the effort in this direction is limited. Our experiments also show serious thrashing could be easily found in Linux kernels. We propose a Linux patch to enhance the capability of replacement algorithms to eliminate the thrashing by dynamically monitoring system conditions and adjusting replacement algorithms accordingly. We implement the patch, and the resulting performance and its analysis are provided to show its effectiveness.