An anomaly in space-time characteristics of certain programs running in a paging machine

ABSTRACT

The running time of programs in a paging machine generally increases as the store in which programs are constrained to run decreases. Experiment, however, have revealed cases in which the reverse is true: a decrease in the size of the store is accompanied by a decrease in running time. An informal discussion of the anomalous behavior is given, and for the case of the FIFO replacement algorithm a formal treatment is presented.

REFERENCES

• 1: B. Randell , C. J. Kuehner, Dynamic storage allocation systems, Communications of the ACM, v.11 n.5, p.297-306, May 1968 [doi>10.1145/363095.363138]
• 2: BELADY, L.A. A study of replacement algorithms for a virtual storage computer. IBM Syst. J. 5, 2 (1966), 78-101.
• 3: Gerald H. Fine , Calvin W. Jackson , Paul V. Mc Isaac, Dynamic program behavior under paging, Proceedings of the 1966 21st national conference, p.223-228, January 1966 [doi>10.1145/800256.810701]
• 4: O'NEILL, R. W. Experience using a time-sharing multiprogramming system with dynamic address relocation hardware. Proc. AFIPS 1967 Spring Joint Comput. Conf., Vol. 30, Thompson Book Co., Washington, D. C., pp. 611-621.
• 5: BRAWN, B., AND GUSTAVSON, F. An evaluation of program performance on the M44/44X System, Pt. I. IBM Res. Rep., RC-2083, IBM Corp., 1968. Also as Program behavior in a paging environment, Proc. AFIPS 1968 Fall Joint Comput. Conf., Vol. 33, Pt. 2, Thompson Book Co., Washington, D. C., pp. 1019-1032.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms

Keywords:
demand paging, paging machines, replacement algorithm