Managing locality sets: the model and fixed-size buffers

A memory-management model based on describing reference behavior in terms of locality-set sequences is proposed. Specialized for fixed-size buffers, this model is used to define the PSETMIN and SETMIN strategies which are proven to minimize the number of page faults in the presence and absence of prepaging, respectively. In contrast to MIN, they are also realizable for certain computations. The methodology for obtaining the locality-set sequence of a computation in advance is illustrated for relational database management systems with multiattribute-index catalogs, and the concomitant performance gains are discussed. In general, for applications that maintain their own organized collections of data, optimal locality-set management of individual computations provides an alternative to the widely used general-purpose strategies based on heuristics