Empirical and analytical studies of program reference behavior [Page reference behavior modeling and evaluation of multiprogramming paging systems, Thesis]
Abbas Rafii, USDOE · 1976
Several aspects of program reference behavior, page reference behavior modeling, and evaluation of multiprogramming paging systems are considered . An experimental treatment of the generated working set size and LRU stack distance strings of actual programs is given first. The effects of page size and other parameters on the distribution, serial correlation, and frequency domain behavior are studied. A number of working set size models are discussed, and the ability to capture the observed degree of the serial dependency in the working set size string is examined. Then some new results on the performance and cost of many practical paging systems are presented, and the related evaluation techniques are discussed. The independent reference model is used to find some analytical results for the expected page fault rate of some algorithms. The potential of program behavior models in predicting performance of different page replacement algorithms is demonstrated. Next, the development of a useful, simple and analytically tractable program page reference model is examined. A new technique to estimate the parameters of an independent reference model is proposed. It is shown that one can obtain a model with predictive capabilities. The potential of expanding the model into the areas of simple program restructuring techniques and evaluation of memory hierarchies with unequal read/write cost is discussed. Finally, some basic relations between the interaction of device scheduling and page scheduling in a multiprogramming virtual memory system are investigated. Queueing analysis and trace driven simulations are used to show the effect of memory allocation policies and various service disciplines on the resource utilization and job waiting times. Some interesting implications of partitioning memory among competing jobs are explored. 100 figures, 21 tables.