# Analysis of program behaviour

Patrice Burgevin, Philippe Ingels, Jacques Leroudier

► To cite this version:

Patrice Burgevin, Philippe Ingels, Jacques Leroudier. Analysis of program behaviour. [Research Report] IRIA-RR-237, IRIA. 1977, pp.17. hal-04716428

HAL Id: hal-04716428

https://inria.hal.science/hal-04716428v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

ANALYSIS
OF
PROGRAM BEHAVIOUR

Patrice BURGEVIN
Philippe INGELS
Jacques LEROUDIER

Rapport de Recherche N° 237

Juin 1977

17p.
ANALYSIS OF PROGRAM BEHAVIOUR

Patrice Burgevin*, Philippe Ingels*, Jacques Leroudier**

Résumé :

Par interprétation de l'exécution de programmes soumis à un CII 10070, nous avons recueilli des données caractérisant le comportement d'un programme durant son exécution. Les résultats obte-nus concernent l'activité des programmes vis-à-vis de leur espace d'adressage et vis-à-vis des unités d'E/S. Ces observations sont utilisées pour valider et caractériser des modèles de comportements de programmes tels que piles LRU, durées de vie, ensembles de travail, et pour mettre en éviden-ce les relations qui lient ces différents modèles.

Abstract :

By interpreting the execution of programs on a CII 10070 computer, data on the characteristics of program behaviour during their execution have been collected. The results concern the activity of programs in their address space and the time interval distributions between the I/O requested by a program. These observations have been used to validate and to characterize models of program behaviour such as the LRU stack, the life time function and the working-set, and to point out the relationships between these different models.

<footnote>* University of Rennes - Department d'Informatique - B.P. 25A - 35031 Rennes Cédex (France)</footnote>

<footnote>** IRIA/LABORIA - B.P. 105 - 78150 Le Chesnay (France)</footnote>
# 1 - INTRODUCTION

Performance of virtual memory computer systems are very sensitive to the behaviour of programs in their address space, undoubtedly more than classical system [1, 2, 3, 4]. Programs with highly scattered references will lead to an important paging activity which may cause a degradation of the performance known as "thrashing" [5]. There have been many attempts to analyse such phenomena by use of mathematical or simulation models, which all rely on models of program behaviour. The validation of these models is thus an essential part of the validation of the model of system performance itself, and it is the aim of this paper to present data which characterize program behaviour and to use them to validate the existing models.

The data presented below concern program behaviour in a paged memory and the I/O activity of programs. When necessary, the replacement policy was assumed to be LRU.

# 2 - DATA COLLECTION

The data were collected by interpreting the execution of programs running on CII-10070 computer. The traces obtained contain the sequence of the addresses referenced by a program and its I/O requests. Twenty different programs were measured [4] and five of them were chosen so as to be typical of the population of programs submitted to the system. Three of them are standard compilers of the Computing Center of the University of Rennes and the two others are programs chosen in the batch. Their global characteristics are as follows :

Program A : FORTRAN compiler (30 K words) compiling two different modules.

Program B : execution of a user's FORTRAN program (16 K words).

Program C : LP 70 compiler (15.5 K words) compiling a program of about 500 cards.

Program D : LISP interpreter (14 K words).

Program E : execution of a COBOL user's program (7.5 K words).

Each trace contains at least $3 \times 10^6$ references. In order to illustrate the results obtained, the execution traces of the different programs are given in figure 1 which displays the raw information that will be analysed in this paper.
The X-axes represent the execution time given in seconds (in reality, the time is expressed as a number of references and we have considered that a reference was equal to a microsecond) and the numbers of the referenced pages are plotted on the Y-axes. A dash on the graph indicates the pages referenced by the program at a given instant of time.

The program A is the FORTRAN compiler, compiling two different modules. It may be seen by comparing the two parts of the visual trace on both side of the vertical line L that the behaviour of the compiler is the same for the two modules, and therefore seems to be independent of the programs it compiles. It may be also noted that there is a clear change of behaviour at the instant represented by the vertical line K (cf. § 4).

<figure><img src="image_3.png" /><figcaption>Figure 1 : Programs A and B</figcaption></figure>
<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /><figcaption>Figure 1 : Programs C, D and E</figcaption></figure>
In all experiments the page replacement algorithm used is LRU which assumes that the least probable page to be referenced is the least recently referenced page. The LRU policy was simulated with different page sizes for the five programs by using their traces. In all cases it was observed that the probability for a page to be referenced decreases as its rank in the LRU stack increases. This observation roughly justifies the choice of the LRU algorithm as illustrated in figures 2A and 2B which give the LRU stack probabilities for program B and C with a page size of 512 words.

<table><caption>Program B
Figure 2A</caption><thead><tr><td>Rank</td><td>Reference probability</td></tr></thead><tbody><tr><td>1</td><td>0.530</td></tr><tr><td>2</td><td>0.370</td></tr><tr><td>3</td><td>0.031</td></tr><tr><td>4</td><td>0.031</td></tr><tr><td>5</td><td>0.013</td></tr><tr><td>6</td><td>0.016</td></tr><tr><td>7</td><td>0.012</td></tr></tbody></table>

<table><caption>Program C
Figure 2B</caption><thead><tr><td>Rank</td><td>Reference probability</td></tr></thead><tbody><tr><td>1</td><td>0.534</td></tr><tr><td>2</td><td>0.270</td></tr><tr><td>3</td><td>0.089</td></tr><tr><td>4</td><td>0.033</td></tr><tr><td>5</td><td>0.012</td></tr><tr><td>6</td><td>0.08</td></tr><tr><td>7</td><td>0.08</td></tr></tbody></table>

## 3 - LIFE-TIME OF A PROGRAM BETWEEN PAGE FAULTS

Most models of performance evaluation of paged virtual memory systems are based on a queueing network representation [3]. This framework implies that memory requirements have to be expressed in some way or another as demands on servers, i.e. as time requirements. This transformation can be done by life-time function (LTF) which relates, for a given program, the mean time between page faults to the size of memory allocated to the program. The following sections are devoted to the characterization of the life-time function.
## 3.1 - The mean of the life-time

We want to estimate parameters that can be used in queueing models of virtual memory systems [3]. In this kind of model, the system performance, measured as utilization ratios of the different units (CPU, channels, etc...), is much more sensitive to the expected values of the random variables used in the model than to their global distributions [3, 18] : this is true at least for virtual memory systems which are not in phase of "thrashing" [9] (cf. § 3.3). From this point of view, we first look for expressions of the mean life-time of the programs between page faults, in terms of their allocated space. BELADY and KUEHNER proposed in [6] the following expression :

$$ (1) \qquad \bar{e} = as^k $$

where $\bar{e}$ is the mean life-time between page faults and s the space allocated to the program. Thus, the graph of the function $\bar{e}(s)$ on a logarithmic scale should be a straight line. In the figure 3, we give this graph for the program A and get results that are close to CHU and OPDERBECK's in [7].

<figure><img src="image_7.png" /><figcaption>Figure 3</figcaption></figure>
e is expressed in number of references (in our case, a reference is almost equivalent to a microsecond) and s in K words of 32 bits. The graph shows that Belady's model tends to underestimate e. Three other models were tested, namely

$$ (2) \quad \bar{e} = \exp[a(\text{Log } s)^k] $$

$$ (3) \quad \bar{e} = \exp[\exp(as^k)] $$

$$ (4) \quad \bar{e} = \exp[as^k] $$

The best fit, based on the least square approximation [8], was obtained for the expression (4). This result is illustrated in figure 4 which presents the experimental graph $\bar{e}(s)$ and approximation (1) and (4).

<figure><img src="image_8.png" /><figcaption>Figure 4</figcaption></figure>
## 3.2 - Variation of the parameters a and k according to the page size

In an operating system with a memory hierarchy with several levels the pages have different sizes at each level. It is the case, for instance, for machines with a cache, a core memory and a virtual memory on a drum or a disk. We may observe from figure 3 that, for a hierarchy level with a small memory size, pages at this level should also be small. More generally, the page size should vary in the same way as the size of the memory level which is considered. In order to model the behaviour of program in memory hierarchies it is therefore necessary to know the dependency on the page size of the parameters a and k of the mean of the life-time functions. In particular, such an approach was taken in [12] to study the performance of a two level memory hierarchy by using the same life-time function for the cache and the memory.

We present in figures 5A and 5B the variations of a in terms of the page size for the five programs (figures 5A and 5B are respectively obtained from expressions (1) and (4)).

Note: the numerical values of a and k are given for s being measured in K words of 32 bits.

<figure><img src="image_9.png" /><figcaption>Figure 5A</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 5B</figcaption></figure>
We note that the parameter a decreases with the page size for all the programs considered and for the two models of the mean life-time function. In the case of Belady-Kuehner's model it seems possible to explain such a phenomenon. Consider the expression (1) : $\bar{e} = a s^k$ we have two implicit units of memory allocation in it. The first one is the unit of s, the allocated space, which is measured in K words and the second one is the unit of the space removed by the replacement algorithm, which is measured in pages. Thus we can interpret a as the mean time for a program to have a reference outside one unit of allocated space (here 1 K word) :

$$ \bar{e} = a(1)^k = a $$

Of course, a depends on the machine cycle [6] because $\bar{e}$ is expressed in a number of references, but a also measures the program fragmentation. The meaning of the decreasing of a with the page size is the following : if we allocate 1 K to the program, the best strategy is to have many small pages instead of having only a large one, because then all the information in memory will be relevant and the life-time the largest.

In Figures 6A and 6B, we present the variations of the parameter k.

<figure><img src="image_11.png" /><figcaption>Figure 6A</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 6B</figcaption></figure>

We may notice that, except for small page sizes, the estimated value of k increases with the page size. For the anomaly observed for small page sizes, it
should be noted that, in this case, there are fewer measurements and that the observations might not be statistically significant. However, we may also infer from this observation that the behaviour of programs changes drastically when small set of instructions are considered rather than large set as in the case of large page size. This point will be discussed more completely in section 4.

As done with the coefficient a, it is possible to interpret the coefficient k in the case of Belady-Kuehner's model. For a given allocated space s, the larger k is, the longer the mean time $\bar{e}$ between page faults is $\bar{e} = as^k$

Thus k seems to measure the property of a program to stay (or not to stay) in a given amount of memory. Usually this property is called the program "locality" [5, 6, 13, 15].

Because we used such a life-time function in a global model of a system [3, 19], we want inside more details and we found out that the parameters a and k were not independent.

Considering all page sizes and the five different programs we have computed the correlation between log a and k :

$$ (5) \qquad \rho(k, \log a) = 0.75 $$

The relatively high value obtained indicates that there exists a relationship between log a and k. By computing linear regressions of log a as a function of k and k as a function of log a we are led to propose, if $\bar{e}$ is expressed in milliseconds :

$$ (6) \qquad k \approx -\log a + 1 \quad \text{or} \quad a \approx 10^{-k+1} $$

We must to not that :

1. (6) is true for a given program but also from one program to another

2. there is a relation between the fragmentation and the locality,

3. as a consequence of point 2, the effect of the fragmentation is to decrease the useful space allocated :

$$ (7) \qquad \bar{e} = 10^{-k+1} s^k = 10\left(\frac{s}{10}\right)^k \quad (\bar{e} \text{ in milliseconds}). $$
We give the variation ranges of k :

<table><thead><tr><th></th><th>Small pages</th><th>Large pages</th></tr></thead><tbody><tr><th>page sizes in words</th><td>16, 32, 64, 128</td><td>256, 512, 1024</td></tr><tr><th>k</th><td>2 ≤ k ≤ 4<br>mean value : 3.3</td><td>4 ≤ k ≤ 7<br>mean value : 5.0</td></tr></tbody></table>

### 3.3 - Distribution of life-time intervals

For reason of mathematical simplicity, the distribution of life-time intervals is usually assumed to be exponential when the life-time function model is used in a model of performance evaluation for virtual memory computer systems. However this assumption is not validated by the observed samples as shown by the results presented in figures 7A and 7B, where the distribution of the life-time intervals has been approximated by an hyperexponential distribution for programs A and C (for a given s). The estimation of the parameters of the hyperexponential distributions has been obtained by a mixture resolution method developed in [10] by A. SCHROEDER, which has already been applied to a similar problem [11].

The explicit densities obtained are :

- for program A :

$$f_A(x) = 10^{-3} (9.92e^{-0.01x} + 0.38e^{-0.001x})$$

- for program C :

$$f_C(x) = 0.00065e^{-0.0015x} + 0.031e^{-0.0553x}$$

<figure><img src="image_13.png" /><figcaption>Figure 7A</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 7B</figcaption></figure>
The same approximations have been performed for all the programs considered and for different values of s, and have given the same satisfactory results, except for program B.

The conclusion that the life-time intervals are not exponentially distributed indicates that mathematical models of performance evaluation which assume exponential distributions will tend to underestimate the effect of page faults and hence the congestion of the system. Recent results reported in [9, 18] show that the error term for the CPU utilization factor is not negligible, when system performance collapses ("thrashing"), this error can reach 20 % for a coefficient of variation of the life-time interval distribution equal to 3.3.

## 4 - STUDY OF THE WORKING SET OF A PROGRAM

In 1968 DENNING introduced the notion of working set [13] and proposed it as a way to prevent "thrashing" in virtual memory systems : a program can be admitted to be multiprogrammed in core memory only if there is space enough to contain its working set. Several theoretical studies have been done since that time, which essentially deal with the working set size distribution. One important hypothesis these studies rely on is a stationarity assumption for the distribution [14, 15].

For the five programs, we have studied the working set size distributions, for different page sizes and different "window size" varying from 100 to 2000 references (approximately from 0.1 millisecond to 2 milliseconds). These distributions vary from one program to another, and we give on figure 8A the histogram obtained for program D with a page size of 512 words and a "window size" of 2000 references.

<figure><img src="image_15.png" /><figcaption>Figure 8A</figcaption></figure>
We have been particularly interested in this program because of the evident non stationarity of its working-set size distribution (figure 8B).

<figure><img src="image_16.png" /><figcaption>Figure 8B</figcaption></figure>

To point out this property, the global reference string of the program D has been divided into 6 sub-strings of 500,000 references each. The principal elements of the global distribution are found in the 2nd, 3rd and 5th sub-strings (figures 9A and 9B). For a reason of clarity, the results concerning the 1st, 4th and 6th sub-strings have not been represented since they are very close to the other ones.

<figure><img src="image_17.png" /><figcaption>Figure 8C</figcaption></figure>

Though the distribution of the working-set size is not stationary, we have observed -as BRYANT did [16]- the stationarity of the variation of the working-set size and that the distribution of this new variable is unimodal (figure 8C) :

$$ \Delta W_i = W_i - W_{i-1} $$

where $W_i$ is i-th measurement of the working-set size.
Moreover, we examined the validity of the predictive model of working-set size proposed by BRYANT [16] by studying the autocorrelation function $\rho(k)$ of our sample ($\rho(k)$ is the correlation between $W_i$ and $W_{i+k}$). For all our programs, this function is decreasing and independent of the page size. In figure 9A, we give $\rho(k)$ for different page sizes for the program A. On the contrary $\rho(k)$ may greatly depend on the "window" size (figure 9B, $\rho(k)$ for the program B).

<figure><img src="image_18.png" /><figcaption>Figure 9A</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Figure 9B</figcaption></figure>

For a "window" of 2000 references (about 2 milliseconds) $\rho(k)$ is regularly decreasing while for a "window" of 1000 references the decreasing is very noisy. The last point seems to be related to a "locality" phenomenon that can be observed only if the working set is large enough : i.e. as shown in § 3.2 if the amount of data considered is sufficient.

## 5 - PROGRAM LIFE-TIME BETWEEN I/O

In order to define completely the behaviour of the programs, their lifetimes between I/O requests have to be analyzed. This characteristic is specific to each program and greatly depends on the program considered. For some of them we found empirical life-time distributions similar to the ones observed by JALICS and LYNCH [17]. We give in figures 10A, 10B, 10C and 10D these distributions respectively for the programs B, A, E and C.

We have to notice that the results we have obtained are an order of magnitude smaller than JALICS and LYNCH'S ones. This is due we have measured time intervals between logical I/O (between Supervisors Calls) instead of physical I/O.
<figure><img src="image_20.png" /><figcaption>Figure 10A</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Figure 10B</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>Figure 10C</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 10D</figcaption></figure>

Figure 10

## 6 - CONCLUSION

From the raw information consisting of traces of addresses referenced by programs during their execution, we have analysed several variables which characterize the program behaviour. This fact allowed us to consider different models of program behaviour and to cross-check each other. Concerning the life-time function between page faults, Belady's model was validated and another one proposed. By analysing variation of the parameters of both models according to the page size we were able to describe the different life-time functions in a memory hierarchy. In order to express all the aspects of program behaviour as time intervals between events, we completed our work by studying life-times between I/O. This emphasis on the life-time functions comes from their interest in virtual memory system modelling [3, 9, 19]. We also pointed out some results which concern the validity of the stationarity and the exponential assumptions made in most models of computer systems.

## ACKNOWLEDGEMENTS

The authors would like to thank all the members of the research group at IRIA and at the University of Rennes who participated to this work and more particularly D. POTIER and A. SCHROEDER from IRIA and J. LENFANT from the University of Rennes.
REFERENCES

[ 1 ] BRAWN B.S., GUSTAVSON F.G. - "Program behaviour in a paging environment" - Fall Joint Computer Conference 1968.

[ 2 ] RODRIGUEZ-ROSELL J., DUPUY J.P. - "The evaluation of a time-sharing page demand system" - Spring Joint Computer Conference 1972.

[ 3 ] BADEL M., GELENBE E., LEROUDIER J., POTIER D. - "Adaptive optimization of a time-sharing system's performance" - IEEE Proceedings on Interactive Computer Systems - June 1975.

[ 4 ] LENFANT J., BURGEVIN P. - "Empirical data on program behaviour" - International Computing Symposium 1975 - North-Holland Publishing Co - Antibes - June 1975.

[ 5 ] DENNING P.J. - "Thrashing : its causes and prevention" - Fall Joint Computer Conference - 1968.

[ 6 ] BELADY L.A., KUEHNER C.J. - "Dynamic space-sharing in computer systems" - CACM Vol. 12, n° 5 - May 1969.

[ 7 ] CHU W.W., OPDERBECK H. - "Performance of replacement algorithms with different page sizes" - COMPUTER - November 1974.

[ 8 ] LINNIK Y.V. - "Méthode des moindres carrés" - Dunod Paris - 1963.

[ 9 ] POTIER D., LEROUDIER J., BADEL M. - "Un modèle d'analyse des performances d'ordinateurs multiprogrammés à mémoire virtuelle" - Rapports IRIA-LABORIA n° 152 - January 1976.

[10] SCHROEDER A., - "Analyse d"un mélange de distributions de probabilité de même type" - Revue de Statistique Appliquée, Vol. XXIV, n°1, - 1976.

[11] LEROUDIER J., SCHROEDER A. - "A statistical approach to the estimation of service times distributions for operating systems modeling" - International Computing Symposium 1975 - North-Holland Publishing Co - Antibes - June 1975.

[12] GELENBE E. - "Page size in demand paging systems" - Acta Informatica 3 - 1975.

[13] DENNING P.J. - "The working-set model for program behaviour" - CACM - Vol. 11, n° 5 - May 1968.

[14] DENNING P.J., SCHWARTZ S.C. - "Properties of the working set model" - CACM - Vol. 15, n° 3 - March 1972.

[15] LENFANT J. - "Comparison of the working sets and bounded locality intervals of a program" - 2nd International Workshop on Modelling and Performance Evaluation of Computer Systems - Stresa - Italy - October 1976.

[16] BRYANT P. - "Predicting working-set sizes" - IBM Journal of the Research and Development - May 1975.

[17] JALICS P.J., LYNCH W.C. - "Selected measurements of the PDP-10 TOPS-10 time-sharing operating system" - IFIP 74 - North-Holland publishing Co - August 1974.

[18] POTIER D. - "Modèles à files d'attente et algorithmes de gestion optimale des ressources des systèmes informatiques" - Thèse d'Etat - Grenoble University - January 1977.

[19] LEROUDIER J. - "Systèmes adaptatifs à mémoire virtuelle" - Thèse d'Etat - Grenoble University - May 1977.