``Token-ordered LRU: an effective page replacement policy and its 
implementation in Linux systems"

Song Jiang and Xiaodong Zhang

Performance Evaluation, Vol. 60, Issue 1-4, 2005, pp. 5-29.

Abstract

Most computer systems use a global page replacement policy based on
the LRU principle to approximately select a Least Recently Used page
for a replacement in the entire user memory space. During execution
interactions, a memory page can be marked as LRU even when its program
is conducting page faults. We define the LRU pages under such a
condition as false LRU pages because these LRU pages are not produced
by program memory reference delays, which is inconsistent with the
LRU principle. False LRU pages can significantly increase page faults,
even cause system thrashing. This poses a more serious risk in a large
parallel systems with distributed memories because of the existence of
coordination among processes running on individual node.  In the case,
the process thrashing in a single node or a small number of nodes could
severely affect other nodes running coordinating processes, even crash
the whole system.  In this paper, we focus on how to improve the page
replacement algorithm running on one node.

After a careful study on characterizing the memory usage and the thrashing
behaviors in the multi-programming system using LRU replacement.
we propose an LRU replacement alternative, called token-ordered LRU,
to eliminate or reduce the unnecessary page faults by effectively
ordering and scheduling memory space allocations.  Compared with
traditional thrashing protection mechanisms such as load control, our
policy allows more processes to keep running to support synchronous
distributed process computing.  We have implemented the token-ordered
LRU algorithm in a Linux kernel to show its effectiveness.