Previous studies have shown that a program's behavior can be characterized as a sequence of transitions between phases of execution during which some subset of the program's segments is referenced. The nature of the phases (sometimes called localities or regimes), and the characteristics of the transitions between neighboring phases, will determine the performance of the program on a virtual memory system. We here investigate methods for identifying those “major” phases in programs which correspond to intervals of distinctive referencing behavior. Experimental measurements on symbolic reference strings generated by production Algol-60 programs are used to determine the properties of these phases and the transitions between them. The experimental results are discussed in terms of current models for program behavior and also with regard to their implications for memory management systems.

The characteristics of computational processor requirements of a sample of Algol-60 programs have been measured. Distributions are presented for intervals of processor activity as defined by input-output requests and segment allocation requests occurring within the Johnston contour model and within a stack model in which array allocations are treated separately. The results provide new empirical data concerning the behavior of this class of programs. Some implications of the empirical results which may influence computer system design and performance are presented and discussed.

Contemporary paged virtual memory systems often use associative registers to reduce access time to frequently-referenced pages. Here we examine the analogous use of associative registers in descriptorbased, symbolically-segmented virtual memory systems, where each segment contains an entire data structure as defined in a high-level language. Symbolic trace data from production Algol 60 programs were used to determine performance improvement as a function of the number of associative registers in the system. Our results indicate that, even for reasonably large programs, a hit ratio of 0.9 is achieved with only 4 associative registers. Increasing the number of associative registers to 8 gives a hit ratio of 0.98, which with current technology gives a performance improvement of at least 80% in addressing speed over a similar system without associative registers.

Distributions of segment sizes have been measured under routine operating conditions on a computer system which utilizes variable-sized segments (the Burroughs B5500). The most striking feature of the measurements is the large number of small segments - about 60% of the segments in use contain less than 40 words. Although the results are certainly not installation-independent, they should be relevant to the design of new computer systems, especially with respect to the organization of paging schemes.