In the multiprogramming context, mainly there are two methods to eliminate thrashing. One is local replacement, another is load control. A local replacement requires that the paging system select pages for a program only from its allocated memory space when no free pages can be found in their memory allotments. Unlike the global replacement policy, the local policy needs a memory allocation scheme to satisfy the need of each program. Two commonly used policies are equal and proportional allocations, which can not capture dynamically changing memory demand of each program [2]. As a result, the memory space may not be well utilized. On the other hand, an allocation dynamically adapting to the demand of individual programs will shift the scheme to the global replacement. The VMS [5] is a representative operating system using a local replacement policy. The memory is partitioned into multiple independent areas, each of which is localized to a collection of processes that compete with one another for memory. Unfortunately, this scheme can be difficult to administer [6]. Researchers and system practitioners seem to have agreed that a local policy is not an effective solution for virtual memory management. Our patch is built on the global replacement policy of Linux.
A commonly used load control mechanism is to suspend/reactivate, even swapping out/in processes to free more memory space after the thrashing is detected. The 4.4 BSD operating system[8], AIX system in the IBM RS/6000[4], HP-UX 10.0 in HP 9000 [3] are the examples to adopt this method. In addition, HP-UX system provides a ``serialize()" command to run the processes once at a time after thrashing is detected. Compared with load control, our patch works to the same objective but not through action on the whole processes, instead through adaptively adjusting page replacement algorithms. Memory allocation scheduling at this level allows us to carefully consider the tradeoff between CPU and memory utilization.