Improving Virtual Memory Performance by Off-Line Page Clustering

A. new approach to the improvement ot paging systems performance is presented. The method is especially suited to those system which have a relatively smail page size. It consists of defining for each program clusters of pages that will always be fetched into memory and returned to the secondary store as a single entity. The algorithm buildic.g these clusters takes into account the memory policy under which programs are to run and operates upon data extracted from a trace of the program being reorganized and attempts to minimize its space~tim.e product. We prove that our algorithm simultaneously minimizes linear combinations of upper and lower bounds tor page fault frequency and mean memory occupancy of all programs to be run under a working set policy, provided that the paging behavior of the pro· gram can be described by a stochastic model haVing a steadystate solution.. These claims are confirmed by empirical evidence obtained from. lraceoodriven simulations. which. show that the method can substantially improve the performance of some programs running under a working set policy.