On the paging-complexity of periodic arrangements

A simple model of a paging-system is investigated. The importance of the concept of pagination is stressed. The page-reference-strings under consideration stem from paginating simple loops, i.e. periodic sequences of consecutively accessed addresses. These reference strings are called periodic arrangements. The main objectives are: firstly, to prove a locality principle for this type of program structure: Given a pagination, generate as many references as possible to the same page in order to minimize page-traffic! Secondly, to show that this optimizing principle only holds for certain types of paging-algorithms, like Belady's algorithm and FIFO. It does no longer hold for the widely used paging-algorithm LRU, for instance.