Donald Bren School of Information and Computer Sciences

A generalized cost function is presented which is useful for comparing the performance of memory paging algorithms. This function is a close approximation to the real space-time produce and is expressed in terms of the number of page faults and the amount of memory occupied at the time of the fault. By using this function, it is also easy to determine the dynamic memory requirements of a program.

A demand paging algorithm is developed and shown to be optimal with respect to the cost function. Even though the algorithm is unrealizable, it is useful as a theoretical lower bound on the cost for processing any reference string.