An Approach to Program Behavior Modeling and Optimal Memory Control
Percy Tzelnic, Izidor C. Gertner · Journal of the ACM · 1982
A new technique is proposed for analyzing models of (paged) virtual memory management This technique, which is based on recent developments in the theory of optimal control, permits the use of a very general model of program behavior.In contrast to existmg studies of program behawor, staUstically confined to Markov models, a general jump stochastic process is used here to describe the page reference generator A model of memory management is formally defmed as three component processes: the program behavior, the memory allocation, and the control process.Equations linking the evolution of the memory allocation process with the other two processes are derived.Necessary and sufficient conditions for an optimal control policy are given as a set of optunality equations.Although these equaUons can be numerically solved for small s~ze problems, an analyUc solution is presented for the case of stationary ranking of pages.The equations of motion of the memory allocation process are used m apphcations where the performance of a given control pohcy is to be assessed for specified program behavior Another use of the proposed technique is the formulation of a Markov phase behavior model The hfetime function calculated in this model is shown to be m good agreement with empirical results.