Minimization of demand paging for the LRU stack model of program behavior

The minimization of page faults in a demand paging environment where program behavior is described by the LRU stack model is studied. Previous work on this subject considered a specific type of stack probability distribution. As there exist practical situations which do not satisfy this assumption, we extend the analysis to arbitrary distributions. The minimization is stated as an optimization problem under constraints, a method to obtain a class of optimal solution is presented, and a fixed-space replacement algorithm to implement these solutions is proposed. The parameters of this replacement algorithm can be varied to adapt to specific stack probability distributions and to the number of allocated pages in memory. This paper also determines a necessary and sufficient condition for the optimality of the LRU algorithm.