A theorem on linear diophantine equations and the paging-complexity of loop-chains

摘要

For a given reference-structure the following problem is posed: Find a partition of a program's (resp. ist data) addresses in pages of limited size and a paging-algorithm such that the “page-fault-rate” is minimized. A “paging-complexity” (of reference-structures) is introduced in order to measure optimal performance. It is shown that the paging-complexity of a concatenation of simple loops is the arithmetic mean of the paging-complexities of the loops involved. The proof rests on a theorem on linear diophantine equations which may deserve attention for its o