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