An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine The running time of programs in a paging machine generally increases as the store in which programs are constrained to run decreases. Experiments, 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. CACM June, 1969 Belady, L. A. Nelson, R. A. Shedler, G. S. paging machines, demand paging, replacement algorithm 4.30 CA690609 JB February 17, 1978 9:59 AM 1879 4 1884 1884 4 1884 1901 4 1884 2095 4 1884 2277 4 1884 2297 4 1884 2365 4 1884 1754 5 1884 1884 5 1884 1884 5 1884 1884 5 1884 2022 5 1884 2085 5 1884 3006 5 1884 1751 6 1884 1751 6 1884 1884 6 1884 1884 6 1884 1884 6 1884 2374 6 1884 2373 6 1884 2595 6 1884