Some Parameters Affecting The Performance Of Paged Storage Hierarchies*
M. S. Doyle, J. Wesley Graham · INFOR Information Systems and Operational Research · 1975
In this paper, two examples of memory hierarchies are examined: the cache or buffer system, and the virtual memory system. These examples are shown to differ mainly in the mapping function which determines where a given page may reside in the first level of the hierarchy. We also examine the operation of the replacement algorithm which determines the page to be removed from main storage when an absent page is referenced. The inclusion property associated with a class of replacement algorithms known as stack algorithms is described, and some examples of this class are presented.Some experimental observations on the effects of page size are presented, which indicate that page size is a parameter of fundamental importance to the performance of a storage hierarchy. The class of singly determined stack algorithms is then defined, and is shown to include both the popular Least Recently Used (LRU) replacement algorithm, and an optimal algorithm. Singly determined stack algorithms are then shown to have certain properties which could simplify an analysis of the effects of page size on the number of page faults experienced by a storage hierarchy.