Locality in Page Reference Strings

Abstract

A probabilistic model is presented of program material in a paging machine. The sequences of page references in the model are associated with certain sequences of LRU stack distances and have reference patterns formalizing a notion of “locality” of reference. Values for parameters of the model can be chosen to make the page-exception characteristics of the generated sequences of page references consistent with those of actual program traces. The statistical properties of the execution intervals (times between page-exception) for sequences of references in the model are derived, and an application of these results is made to a queuing analysis of a simple multiprogrammed paging system. Some numerical results pertaining to the program model and the queuing analysis are given.