In models of virtual memory computer systems, it is generally assumed that the time intervals between the page (or segment) faults, often called lifetimes, are independent from each other. Due to the phase-transition behaviour in many real programs this is not always true, and strong correlations may exist between successive lifetimes. These correlations may have a notable effect on the system behaviour. This paper describes a series of experiments where autoregressive -moving average (ARMA) models are used to describe the correlation structure in sequences of lifetimes. It is shown that many real program executions can be described with models having four parameters only, i.e. with the ARMA(1,1) models. The models can be used as parts of simulation models for instance, and they also give us better understanding about the program behaviour in general.

A simple Markov chain model is used to estimate the effect of the cache flushes. The model assumes LRU stack model of program behaviour and geometrically distributed lengths of task switch intervals. Given the LRU stack depth distribution, one may easily compute estimates of miss ratios for caches of all sizes with any desired average task switch interval. The model is validated with three reference strings recorded from simulations of large B7800 Extended Algol programs. The estimates obtained with the Markov model are within 12% error margin from the results obtained by cache simulation.

Experimnental results are given about the performance of six sorting algorithms in a virtual memory based on the working set principle. With one exception, the algorithms are general internal sorting algorithms and not especially tuned for virtual memory. Algorithms are compared in terms of their time requirements, space requirements, and space-time integrals. The relative performances of the algorithms vary from one measure to the other. Especially in terms of a space-time integral, quicksort turns out to be the best algorithm, also in a working set virtual memory environment.

The BLI-model of program behaviour is sometimes referred to as an exact measure of the locality structure of the programs. However, only limited experimental data is available of the applicability of the BLI-model. In this paper the characteristics of the BLI-model are studied with relatively large empirical data. References to code segments, data segments and references to paged data segments are used in the experiments. The good coverage percentages reported in earlier studies with data segments, are present in our data also. However, the code referencing behaviour turns out to be totally different. Typically only some 50% of the execution time is covered with BLI's of acceptable length. This is shown to be a consequence of occasional references to segments not belonging to the phase or joining the phase during the phase. The behaviour of paged data segments is typically nearer to the behaviour of the code segments than that of the data segments. The BLI-model is also compared with the VMIN-algorithm. A relatively close correspondence between reasonably long BLI's and the VMIN-sets is observed. In general, the results reported in this paper indicate, that the BLI-model can be used with data segments only, or when information concerning short stable phases of the execution is sufficient.