RIA
laboria

1

laboratoire de recherche
en informatique
et automatique

Adaptive optimization
of the performance
of a virtual memory computer

Marc Erol
M. Badel, E. Gelenbé

J. Leroudier, D. Potier
J. Lenfant

Jacques
J. Lenfant

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 88

Novembre 1974
# ADAPTIVE OPTIMIZATION OF THE PERFORMANCE
OF A VIRTUAL MEMORY COMPUTER

M. BADEL, E. GELENBE, J. LEROUDIER, D. POTIER, J. LENFANT

## RESUME

La régulation du degré de multiprogrammation détermine pour une part importante les performances d'un ordinateur à mémoire virtuelle. Dans ce papier, on présente une approche différente de celles le plus souvent utilisées pour la régulation du degré de multiprogrammation, qui sont pour la plupart définies à partir des principes de l'ensemble de travail.

On définit un organe de contrôle, dit contrôleur, qui a pour fonction d'agir sur le système étudié afin d'optimiser une mesure de performance donnée. Le contrôleur est conçu pour un ordinateur dont la ressource critique est la mémoire centrale et pour lequel une régulation inefficace conduirait à un écoulement -ou thrashing- des performances à cause d'une charge de pagination trop élevée.

Dans la première partie du papier, le comportement du système que l'on souhaite contrôler est analysé à l'aide d'un modèle analytique. Le système est formé d'un ensemble de terminaux et d'une "boucle de ressources" (u.c., mémoire secondaire, disque de fichiers) partagée par les utilisateurs. A partir d'hypothèses classiques sur le comportement des programmes (p.e. la fonction de durée de vie), le débit de la boucle est obtenu en fonction du degré de multiprogrammation n (nombre d'utilisateurs se partageant les ressources à un instant donné) et des paramètres du système. Ces résultats sont validés et étendus à l'aide de simulations d'un modèle plus détaillé (dépassements et hypothèses non-exponentielles) et fournissent ainsi une meilleure compréhension de l'ensemble que l'on désire contrôler.

Dans la seconde partie, un critère de performance -la dilatation- lié à l'utilisation des ressources est défini. A partir des résultats analytiques et des résultats de simulation, om peut montrer qu'il existe une valeur $n_0$ du degré de multiprogrammation qui maximise ce critère. La régulation de n à $n_0$ est obtenue en contrôlant l'accès des usagers à la boucle de ressources. La valeur $n_0$ est estimée en temps réel à partir d'une estimation continue des deux premiers moments du critère. A l'aide de ces estimations, la décision d'introduire ou non un nouvel utilisateur dans la boucle est prise chaque fois qu'un utilisateur est issu des terminaux ou quitte la boucle.

La réalisation du contrôleur et de ses différentes fonctions a été complètement simulée. Les résultats des simulations montrent qu'une amélioration très sensible des performances est obtenue et que la régulation du degré de multiprogrammation suivant les caractéristiques des programmes des utilisateurs se fait rapidement. Les aspects pratiques de l'application de ce système de contrôle sont abordés en conclusion.

<footnote>+ Chaire d'Informatique de l'Université de Liège, Belgium.</footnote>
ADAPTIVE OPTIMIZATION OF THE PERFORMANCE

OF A VIRTUAL MEMORY COMPUTER

M. BADEL, E. GELENBE, J. LEROUDIER, D. POTIER, J. LENFANT.

ABSTRACT

It is known that the regulation of the degree of multiprogramming is
perhaps one of the most important factor determining the overall performance of a
virtual memory computer. In this paper we present an approach which differs some-
what from the approaches usually taken to regulate the degree of multiprogramming,
which are mainly derived from the working-set principles.

We design a controller which will regulate the system in order to optimize a given performance measure. The controller is applied to a system where the critical resource is primary memory and we are only concerned with systems were ineffective regulation leads to the phenomenon known as thrashing due to extensive paging activity.

In the first section, the dynamics of the system we wish to regulate are
investigated using an analytical model. The system consists of a set of terminals
and of a resource loop (CPU, secondary memory device, file disk) shared by the
users. Using classical assumptions about program behaviour (e.g. life-time function),
the throughput of the RL is obtained as a function of the degree of multiprogramming n
(number of users sharing the resources at a given instant of time) and of the system
parameters. This result provides a greater insight of the "plant" we wish to control.
The mathematical results are validated and extended with data from simulation expe-
riments using a more detailed model (overheads and non-exponential assumption).

In the next section, a criterion called "dilatation" based on the utilizat-
tion of the different resources is defined. From the analytical and simulation results
of the first section, it can be shown that there exists a value n<sub>0</sub> of the degree of
multiprogramming which maximizes this criterion. The regulation of n to n<sub>0</sub> is achieved
by controlling the access of the users to the RL. The value of n<sub>0</sub> is estimated in
real-time through a continuous estimation of the two first moments of the criterion.
Using these estimations, the decision of introducing or not a new user in the RL is
taken whenever a user leaves a terminal or departs from the RL.

Extensive simulation experiments were conducted, where the implementation
of the different functions of the controller have been thoroughly simulated. They have
shown that the control scheme leaves to an improvement of the system performance in
mean response time and resource utilization, and, overall, adapts in real time the
degree of multiprogramming to the characteristics of the users (the adaptation is
performed in 4 sec. or so for a unit variation of the optimal degree of multipro-
gramming). A discussion of practical application of results ends the paper.
# I-PREFACE

It is known that the regulation of the degree of multiprogramming as a function of instantaneous system state and program behaviour parameters (e.g. working sets) is perhaps the most important factor determining the overall performance of a virtual memory computer. The literature on this subject is abundant [7,8,14].

Among the regulation methods which have been proposed those which have attracted the greatest attention and which seem to have had the greatest success in practice have been derived from the working set principle [6]. Some notable exceptions to this exist and it is worthwhile to mention the virtual memory scheduler of the time-sharing system MTS running on the IBM 360/67 [13] computer

The working-set strategy, as well as some others, is based on a conservative approach: the scheduler will not admit a process to share real memory if it "beleives" (by an estimation of the process working set size, or otherwise) that this would result in a level of paging activity causing a serious degradation of system performance.

In this paper we take an approach which is philosophically somewhat different. We propose the design of a scheduler (henceforth called the controller) which will regulate the system in order to *optimize* a given performance measure, rather than simply prevent undesirable system behaviour. This follows closely the approach in control engineering practice where "regulators" have been replaced by optimizing feedback control systems.

# II-INTRODUCTION

Though the approach presented here can be extended to system for which the critical resource is not real memory, here we shall only be concerned with systems in which ineffective regulation leads to a phenomenon known as thrashing [8], e.g. the reduction of useful throughput due to excessive paging activity.

In order to motivate the method we propose, we shall examine in details the dynamics of the system we wish to regulate. In figure 1 a time-sharing multi-programmed virtual memory system is shown together with the controller. The latter consists of an estimator (EST) of system behaviour using measurements obtained at A on the various traffic patterns in the system, an optimizer (OPT) which computes decisions using the estimates provided by EST as well as with knowledge of the system state; OPT furnishes commands to the switch (K) controlling the access into the resource loop (RL) of users waiting in the
queue (Q).

The time-sharing system consists of a set of terminals from which a set of users (whose number is equal to that of terminals) generate commands. When a command is generated, the user at the terminal will remain inactive until the system provides the proper response. Symbolically, a user having generated a command enters Q and remains there until it is admitted into RL by K. The terms "user" and "user process" or just "process" will be used interchangeably. The solid lines in figure 1 indicate the cycle a user will follow and it is in the RL that a number (the degree of multiprogramming) of users execute sharing a pool of resources. The dotted lines in figure 1 represent the flow of information to the various units of the controller. The information is used by OPT to control the access of users to the resource loop so as to maximize a given performance criterion; for instance this criterion could be the expected response time of the incoming users.

In the first part of the paper, we shall recall the results which were obtained in [3] through analytical modelling and simulation on the performance of the resource loop. Those results provide a characterization of thrashing and a greater insight of the "plant" we wish to control. The second part is devoted to the presentation of the controller and to a discussion of results.

# III-INVESTIGATION OF THE RESOURCE LOOP

## 3.1 The Model

Consider the model described in Figure 2. It represents the system architecture of the multiprogrammed paged virtual memory computer under consideration. The system consists of a CPU, a secondary memory device (SM) (e.g. fixed head disk or drum) and a file disk (FD). A queue of requests is associated with each device; the order in which these requests are satisfied is not taken into consideration. N statistically identical and independent processes (users) execute in the system, so that if at any time $n_0, n_1, n_2$ are the numbers of processes in the CPU, SM, FD queue respectively, then

$$ (1) \qquad n = n_0 + n_1 + n_2 $$

In the model, the behaviour of processes is characterized by a compute time followed by either a page fault (after which the process enters the SM queue) or an input-output (file request) in which case the process enters the SM queue. Processes
which terminate their service at the SM or at the FD return to the CPU queue. The processes enter thr RL at A with there total compute time which is decreased by the effective execution time after each pass through the CPU, and leave the RL (at B) when all the computation time is consumed.

In a first simulation the RL was "closed" with A and B being the same point in Figure 2, to allow comparison with analytical results. Then the RL was connected to terminals.

The behaviour of the users is represented by three probabilistic laws : the exponential distributions of the total amount of compute time, the process time between two successive I/O requests, and the process time between two successive page faults. The distribution of service time to a customer (in the sense of queuing theory) at the different units of the RL are as follows :

- the CPU service time at a pass of execution is the minimum of the remaining compute time and the process time to the next page fault and I/O request.

- the service times at the SM and I/O device are allowed to obey arbitrary (general) distribution functions.

A theoretical treatment of the model with exponential service times is given in [1] and in somewhat different form in [3].

Experimental evidence [1] indicates that the mean time between page faults $q$ for a process executing in memory space $m$ is approximated by a function of the form

$$ (2) \qquad q = am^k $$

where $a$ depends on the processing speed as well as on the program characteristics while $k$ depends on program locality and on memory management strategies. The form in (2) does not take into account the "saturation" effect visible in this function for large values of $m$ and is therefore only valid for a range of values of $m$. This region of validity is, however, the region of interest since it is there that the effect of limiting memory availability to a process is apparent. Belady and Kuehner [1] indicate that $k$ is in the range 1.5 $k$ 2.5; $r$ is assumed independent of $m$ or $N$, which seems reasonable. For further discussion of this or related points see [3]. We shall assume that total primary memory available is of size $M$ and that it is equally shared among processes :

$$ (3) \qquad m = M/N $$
## 3.2 Simulation results compared with analytical results

Different simulation runs have been performed for various modifications for various modifications of the model, the aim being to observe the influence of non-exponential service parameters as well as that of system overhead. The simulation model has been written in SIMULA 67 with an observed run time to model time ratio of roughly six. The simulation model has been validated by running it with exponential service times and no overhead so as to verify that its behaviour, at least under these conditions, is identical to the predictions of a mathematical model. This approach was quite useful to us in removing a certain number of programming errors in the simulator.

In our simulation the total compute time of each process is still exponentially distributed. A constant execution time at the CPU, representing system overhead, has been added to each CPU service termination. The duration of this overhead is dependent upon the reason for the termination of the CPU pass; it is

- $a_0$ if the process has terminated its computation and has been replaced by a new process in the CPU queue,

- $a_1$ if a page fault has occured,

- $a_2$ if an I/O operation is requested.

The simulation results have been plotted on Figures 3(a) and 3(b), where the light overhead conditions correspond to $a_0=1$ ms, $a_1= 0.5$ ms, $a_2= 2$ ms. The heavy overhead conditions correspond to $a_0 = 1$ ms, $a_1 = 2$ ms, and $a_2= 2$ ms. These values are representative of similar quantities in real systems. The CPU utilization shown in Figures 3(a) and (b) is the useful fraction obtained by deducing the overhead from the real CPU utilization which is shown on Figure 3(c). In the examples we have examined we see that the non-exponential service times at the disk and SM device do not change significantly the region in which useful CPU utilization is maximized with exponential assumptions. The significant influence is that of overhead on real CPU utilization.

In Figures 3(a,b,c) primary memory size is fixed at 128 pages and program behaviour is kept constant while varying the degree of multiprogramming. The effect of varying the locality of programs (the parameter k in this case) is examined in Figure 4 with the remaining parameters kept constant. We see that increasing k from 1.5 to 2.5 can produce a dramatic increase in the optimal degree of multiprogramming as well as an improvement of throughput as the degree of multiprogramming is increased. As a consequence, it is clear that in a real system, where program behaviour is time-varying, some regulation has to be performed if one wishes the system to perform under close to optimal performance. It is to this subject that the rest of this paper is devoted.
4.1-The basic design considerations.

The problem for the adaptive controller is to maintain the system in
operation so that at all times the measure of performance is optimized. A
definition of this measure is given in the next section. The basic physical
assumptions concerning the system to be controlled are the following:

A1 - The measure to be maximized (the criterion) is a function only of the degree of multiprogramming n, or equivalently n is the only parameter the controller is allowed to modify. This assumption of course simplifies the problem considerably. Other parameters which could be used to improve the system performance could be related to various scheduling disciplines making a choice about the user jobs to be admitted in the RL. The scope of this study has been limited purposely to the control of the degree of multi-programming.

A2 - The measure has a single extremum as a function of n. This is justified by the simulation and analytical results given above.

A3 - The characteristics of user processes vary "slowly" with respect to the internal time constants (e.g. service times of resources) of the RL.

The modifications in the behaviour of users are detected by EST which
provides data to OPT in order to compute the optimal degree of multipro-
gramming with respect to the measure. Those functions are performed under
the following broad considerations:

D1 - The degree of multiprogramming n is regulated to a value n₀ which is computed by OPT using a heuristic (presented in 4.3.2) derived from the assumption that the criterion has a single maximum (A2). n₀ varies with changes in the workload.

The heuristic takes into account the fact that in some cases the criterion
maximum is reached for several consecutive values of n, those values of n
not being equivalent with respect to the response time. As a matter of
fact, due to overhead effects through paging and quantum allocation, the
user's response time increases with n.

D2 - EST performs measurements in order to build an estimate of the
criterion function which weights more heavily recent events rather than past
events.

D3 - The different functions of the controller are achieved on occurence of normal system events, except for EST. The activation of EST is forced by a watch-dog clock which ensures that in all cases measurements are taken.

The control scheme considered in this paper takes only into account
the introduction of processes into RL and not the elimination of processes (for instance, of those whose paging activity is excessive). Processes are assumed to leave RL due to events which are independent of the control.

## 4.2 - The criterion.

The main objectives we want to achieve through the dynamic optimization of the degree of multiprogramming are to maximize the utilization factor of the different processors and to minimize the users response time. We define a criterion based on the utilization factors of the different resources and we verify that this criterion is also related to the users response time.

Let us consider a RL with K resources and assume a time interval $[t_{i-1}, t_i]$ during which a constant number n of users share the resources. Let us define $ts_j^k$ as the service received by j-th user from resource k during the time interval $[t_{i-1}, t_i]$ ($ts_j^k$ does not include waiting times). If n=1 we have

$$ (4) \qquad \frac{\sum_{k=1}^{K} ts_{1}^{k}}{t_{i}-t_{i-1}} \leq 1 $$

If more than one process shares the resources, the sum of all the services $ts_j^k$ received by the users can exceed $t_i - t_{i-1}$ due to the parallelism of the resources:

$$ (5) \qquad \frac{n \sum ts_j^k}{j=1 k=1} < K $$

This ratio can be written:

$$ (6) \qquad \frac{K \sum ts_j^k}{\sum_{k=1}^{n} \frac{j=1}{t_i - t_{i-1}}} \qquad \text{where} \qquad \frac{n \sum ts_j^k}{\frac{j=1}{t_i - t_{i-1}}} = \tau_i^k(n) $$

is the utilization of the resource k in the i-th interval of time, when the degree of multiprogramming is n. We define:

$$ (7) \qquad X_i(n) = \sum_{k=1}^{K} \tau_i^k(n) c_k $$
where $c_k$ is a constant representing the relative importance of the k-th resource. $X_i(n)$ will be used as our criterion for the dynamic optimization of the degree of multiprogramming. We may note that $X_i(n)$ measures the effectiveness of the use of the parallelism of the set of resources and expresses that more than one unit of service time can be processed in one unit of real time. In the following, $X_i(n)$ will be called "dilatation".

We now turn to the response time. We may note that (6) can be rewritten

$$ (8) \qquad \sum_{j=1}^{n} \frac{\sum_{k=1}^{K} ts_{j}^{k}}{t_{i-1} - t_{i-1}} = \sum_{j=1}^{n} E_{i}^{j} $$

where $E_i^j$ is the ratio of the sum of services received during $[t_{i-1}, t_i]$ to the time spent in the system during $[t_{i-1}, t_i]$ for the j-th user. This ratio is a measure of the time spent by a user in the system, e.g. its response time, with respect to its service requirements. By optimizing $X_i(n)$ with respect to n, we maximize in each interval of time $[t_{i-1}, t_i]$ the ratio $E_i^j$ and, as a consequence, the minimization of the users response time is achieved.

We may now further justify the assumption A1. Extensive simulations runs showed that there always exists a unique maximum $n_0$ for the criterion $X_i(n)$ (see Fig. 5,6). It should be pointed out that $X_i$ is computed using only services required by users: CPU time and I/O processing time, excluding overheads and SM service. This has been already explained in section 4.1 when we justified design consideration D1.

## 4.3 - Design of controller functions.

In this section we present the essential functions realized by the controller. They have been implemented in the simulation model of a virtual memory time-sharing system described in section 5 where detailed results of simulation are given. A theoretical justification for each of the design decisions cannot be given because of the complexity of the problem, but (as in most practical design) these are supported by evidence that the approach is reasonable and that the resulting performance is good. We refer to the description given in Figure 1 and give the basic functions realized by the control switch K, the estimator EST and the optimizer OPT.

At each instant of time the estimated optimal value of n, say $\bar{n}_0$, is stored; this variable can only be modified by OPT. When either an external arrival to Q or the departure of a process from RL occurs (these are called events) K is activated. Measurements of the criterion are collected after each event or on a watch-dog clock top, so that during each measurement
interval n remains constant (design consideration D3). If the current value of n is less than $\bar{n}_0$, K introduces exactly one process from Q (if Q is non-empty) into RL; otherwise no process is introduced. K then calls EST and enters a dormant state.

### 4.3.1 - Description of EST

Let $X_i$ be the most recent value of the criterion which is measured after the last event. EST uses the set of all measured values of the criterion to construct its estimate $Z_i$ and to compute the variance $V(Z_i)$ of $Z_i$. These will be furnished to OPT. These quantities are constructed as follows [10].

Let $Y_i$ be given by $(i=1,2,...)$

$$ (9) \quad Y_i = \alpha X_i + (1-\alpha) Y_{i-1}, \quad 0<\alpha\le 1 $$

with $Y_0 = 0$. $Y_i$ is the i-th biased exponential estimate of the criterion:

$$ (10) \quad Y_i = \sum_{j=0}^{i-1} \alpha^{j} (1-\alpha)^{i-j} X_{i-j} $$

where $\alpha$ can be chosen so as to determine the relative importance of "old" measurements. $Y_i$ is a biased estimate because if

$$ (11) \quad E\{X_i\} = E\{X_j\} \quad \text{for all } i \text{ and } j $$

then

$$ (12) \quad E\{X_i\} \neq E\{Y_i\} $$

An unbiased estimate $Z_i$ is obtained by normalizing, that is by taking

$$ (13) \quad Z_i = \lambda_i Y_i $$

where

$$ (14) \quad \lambda_i = \sum_{j=0}^{i-1} \alpha^{j} (1-\alpha)^{i-j} = \frac{1}{1-(1-\alpha)^i} $$

It is easily verified that $E\{Z_i\} = E\{X_i\}$ if (11) is valid.

The variance $V(Z_i)$ is also computed by EST since in making a decision OPT will benefit from additional information regarding the dispersion of the estimates. From (13) we have

$$ (15) \quad V(Z_i) = \lambda_i^2 V(Y_i) $$
and from (9) we have :

$$
\begin{align*}
(16) \quad V(Y_i) &= E\{(Y_i - E\{Y_i\})^2\} \\
&= \alpha^2 V(X_i) + (1-\alpha)^2 V(Y_{i-1}) + 2\alpha(1-\alpha) \mathrm{Cov}(X_i, Y_{i-1})
\end{align*}
$$

where Cov(.,,) is the covariance. We now assume that Cov(Xᵢ, Yᵢ-₁) is zero ; this
is justified if Xᵢ is independant of Yᵢ-₁ which generally will not be the case.
However it may be justified if the time tᵢ-tᵢ-₁ is long. This has been verified
by simulation by computing Cov(Xᵢ, Yᵢ-₁). In (16) we shall replace V(Xᵢ) by a
quantity computed from the estimator Yᵢ. We have :

$$
(17) \quad \hat{V}(X_i) = E(X_i^2) - [E(X_i)]^2
$$

Let us define uᵢ as :

$$
(18) \quad u_i = \beta X_i^2 + (1-\beta)u_{i-1} \qquad 0_i < \beta < 1
$$

We obtain an unbiased estimator w_i of E(X_i^2) by :

$$
(19) \quad w_i = u_i u_{i-1} \quad \text{where} \quad \mu_i = \frac{1}{1-(1-\beta)^i}
$$

with :

$$
(20) \quad E(X_i^2) = E(w_i)
$$

We now compute E(Yᵢ²). We have :

$$
(21) \quad V(Y_i) = E(Y_i^2) - E(Y_i)^2
$$

and, from (13) :

$$
(22) \quad [E(X_i)]^2 = [E(Z_i)]^2 = \lambda_i^2 [E(Y_i)]^2
$$

Equality (22) yields :

$$
(23) \quad [E(X_i)]^2 = \lambda_i^2 E(Y_i^2) - \lambda_i^2 V(Y_i)
$$

we now have :

$$
(24) \quad V(X_i) = \mu_i E(w_i) - \lambda_i^2 E(Y_i^2) + \lambda_i^2 V(Y_i)
$$

Solving (24) and (16) for V(Yᵢ) we get :

$$
(25) \quad V(Y_i) = \frac{1}{1-\alpha^2 \lambda_i^2} \left\{ \alpha^2 [\mu_i E(w_i) - \lambda_i^2 E(Y_i^2)] + (1-\alpha)^2 V(Y_{i-1}) \right\}
$$

and from equation (15), we obtain V(Zᵢ). In practice E(Wᵢ) and E(Yᵢ²) will be computed using the unbiased estimates wᵢ and Yᵢ².

Summarizing this discussion, if an *event* is either an arrival to Q, a
departure from RL or a watch-dog clock top, then the measurements giving the
i-th sample X_i of the criterion are collected after the i-th event. The esti-
mator EST uses X_i to update its i-th estimate Z_i of the criterion as well as
the approximate value of the variance $V(Z_i)$. Note that the parameters $\alpha, \beta$ in the exponential estimators can be adjusted so as to render the estimates (and hence the control) more or less responsive to the time variation of the work-load as discussed in section 4.3.3.

### 4.3.2 - Description of CPT

The optimization is achieved using the algorithm described below : OPT is activated every p events, where p is computed from $\alpha$ using :

$$ (26) \quad s = (1-\alpha)^p \quad \Longleftrightarrow \quad p = \left\lfloor \frac{\text{Log } s}{\text{Log}(1-\alpha)} \right\rfloor $$

where s is a threshold.

If the p events had occured for the same value n of the degree of multi-programming equation (26) would mean that when OPT is reactivated, the measurements made on occurence of those events would be given a weight in the estimation of the criterion equal to 1-s. Since the measurements are made for three consecutive values of n, equation (26) ensures that when OPT is reactivated, measurements made on the occurence of the last p events weight at most 1-s in the estimation of the criterion for those three consecutive values of n. Let us denote by $\overline{n_0}$ the greater of those three values. At each activation of OPT, $\overline{n_0}$ is updated, adding or subtracting one, or remains the same, according to the rules 1 2 and 3, where A, B, C, are the estimates of the criterion for the values $\overline{n_0}-2, \overline{n_0}-1, \overline{n_0}$ of n :

$$ \text{1 : if } A \prec C \text{ and } \left| \begin{array}{l} \text{if } B \prec C \text{ then } \overline{n_0} \rightarrow \overline{n_0}+1 \\ \text{if } B \succ C \text{ then } \overline{n_0} \rightarrow \overline{n_0}-1 \\ \text{if } B \approx C \text{ then } \overline{n_0} \rightarrow \overline{n_0}+1 \end{array} \right. $$

$$ \text{2 : if } \quad A \succ C \text{ then } \overline{n_0} \rightarrow \overline{n_0}-1 $$

$$ \text{3 : if } \quad A \approx C \text{ then same actions as in case 1} $$

We may note that A, B and C would be asymptotically gaussian random variables if the $X_i$ were independant. Although it is not the case in general, a Cramer-Von Mises test has validated the gaussian assumption. This assumption is used to perform the comparisons between A, B and C using the estimates of the variances of A, B and C. The optimizer uses the following rules :

$$ A - B + \epsilon \sqrt{\sigma_A^2 + \sigma_B^2} < 0 \Longleftrightarrow B \succ A $$

$$ B - A + \epsilon \sqrt{\sigma_A^2 + \sigma_B^2} > 0 \Longleftrightarrow B \prec A $$

$$ \text{otherwise} \quad B \approx A $$
where ε is related to the confidence needed : ε=1 for a 84% confidence, ε=0.68 for a 5% confidence. When $\bar{n}_0$ = 3, the action $\bar{n}_0$ + $\bar{n}_0$-1 is not performed. For the same reason, at the start of the system $\bar{n}_0$ is set to a value greater or equal 3. Between two consecutive activations of OPT, K is operated so that the degree of multiprogramming remains at value $\bar{n}_0$, whenever it is possible.

The speed of adaptation is very sensitive to the choice of the parameters of EST. In practice, the best results were obtained by decreasing α and the period P of the watch-dog clock. Several simulations were run with different values for α, s and P (see the figures 8 and 9).

# V - SIMULATION AND EVALUATION OF THE ADAPTIVE CONTROL SCHEME

## 5.1 - Description of the simulator

The simulator presented in section 3.4 has been extended in the following directions:

- the users may have different statistical characteristics (locality, I/O requests, CPU time, etc...) and their statistical characteristics may be time varying (i.e. the distribution laws are functions of time). This extension allows to study how the adaptive control reacts when users characteristics change during a simulation run (the users are generated through 20 terminals).

- queue Q and switch K are added to the simulator; the estimator EST and the optimizer OPT are implemented in the way it would be done in a real system in order to show the feasibility of this approach. CPU overheads are simulated at each activation of EST, OPT and K.

- extensive statistics on the behaviour of the system are provided by the simulator during the simulation runs, and measurements are made in order to evaluate and compare the performances of different policies. The SIMULA 67 program is composed of roughly five hundred cards.

## 5.2 - The evaluation of the performance

Performance is evaluated through measurements from the point of view of both users and resource utilization.

a - The users satisfaction is evaluated by the following quantity named efficiency:

$$E = \frac{\Sigma \text{ service times}}{\Sigma \text{ service times} + \Sigma \text{ waiting times}}$$
b - The use of the resources is evaluated directly by the utilization factors of each processor.

## 5.3 - Simulation results

All the simulation experiments were performed with the following parameters:

- 20 terminals with exponentially distributed thinking time of mean value 8 seconds.

- total CPU execution time of any program is exponentially distributed with mean value of 800 milli-seconds.

- time intervals between page faults and I/O requests are exponentially distributed

- the lifetime function used in the simulation is

$$e = 0.01 \left(\frac{M}{n}\right)^k$$

where M=512 pages, n is the instantaneous degree of multiprogramming and e is expressed in milli-seconds.

- the secondary memory device service time is constant and equal to 5 milliseconds. The file disk service time is exponentially distributed with mean value of 30 milliseconds.

- CPU overheads have value 2 milliseconds for I/O service, 1 millisecond for paging service, 0.5 millisecond for process switching and each activation of EST, OPT and K.

- the CPU quantum is set to an infinite value (FIFO scheduling).

These parameters were chosen so as to drive the system in a thrashing zone if no control is performed.

### 5.3.1 - The criterion

The mean value of the measure of performance used as the criterion of optimization is represented on figures 5,6. The dashed curves correspond to the mean value plus or minus one standard deviation. Those measurements were obtained for two different static time-sharing loads with programs of locality 2 and mean time between I/O of 20 milliseconds for LOAD II, and programs of locality 1.5 and mean time between I/O of 30 milliseconds for LOAD I. As it could have been predicted from the theoretical results of section II higher locality leads to more steady performance for large degrees of multiprogramming.
### 5.3.2 - The adaptive control

From figures 5 to 7, it can be seen that, with LOAD I, the system goes into trashing if no control is performed, and that with LOAD II, the control should allow all the programs to enter the resource loop since the criterion is maximized. The adaptibility of the control to modifications of the behaviour of the programs was verified by running a single simulation with different loads: LOAD II for 200 seconds, then LOAD I for 300 seconds, and again LOAD II for 200 seconds. The estimate $\bar{n}_0$ of the degree of multiprogramming computed by EST and OPT and the value of $n_0$ obtained by the previous measurements are reported on figure 9. The results show that the control adapts itself to load variations, and that the trashing is prevented (see figure 10).

### 5.3.3 - Improvements in the performance

Two simulations were run for LOAD I and LOAD II with control and without control. The results are summarized on figure 7 and show that in all cases thrashing is prevented when the control is applied. Results with LOAD I show how the control allows a better and more balanced use of the resources: the CPU and the file disk utilizations are maximized, the paging activity is decreased to more acceptable value and is no longer a bottleneck for the system, and, as a consequence, overheads are reduced from 24% to 12%. As to mean response time and mean efficiency, they are improved by about 40% and 80%. LOAD II is characterized by the fact that it behaves well even if no control is performed : this remains true when a control is applied, and no significant modifications of the performance is sensed. However, it is worth nothing that as the mean value of the degree of multiprogramming is reduced from 13.5 to 9, the paging drum utilization passes from 24% to 11%.

## VI - CONCLUSION

We have presented a method to regulate the degree of multiprogramming in a virtual memory computer system where programs are allocated main storage according to a demand-paging algorithm. Therefore, our approach is relevant when no other control is performed on core allocation to programs. We know that in this case a deterioration of the system performance may occur due to the extensive paging activity as the degree of multiprogramming becomes large.

In our approach, the regulation of the number of programs which share the main storage is achieved through a continuous estimation of the activity of the system, and the degree of multiprogramming is regulated to a value which maximizes this activity. In the presented model, the control is only
performed on the access of the programs to the resource loop. More complex
control schemes based on different classes of programs, or allowing programs
to be swapped out before they have completed their execution could be devised.
Such an approach would be based on an a priori estimation of the requirements
of programs [12]. This extension will be presented in a further work.

Two series of simulation experiments were conducted. In the first one,
it was shown that the adaptive control leads to an improvement of the system
performance in mean response time and utilization of the resources. In the
second series of experiments, we simulated a time varying load and verified
that the adaptive scheme performed correctly. It is worth noting that the
implementation of the different functions of the controller have been thoroughly
simulated : as a consequence it could be implemented in a real system.
REFERENCES

[1] BELADY L. and KUEHNER C.J., Dynamic space sharing in computer systems - Comm. ACM, Vol 12 n°5, May 1969.

[2] BLEVINS P.R. and RAMAMOORTHY C.V., Aspects of a dynamically adaptive operating system - Technical report n°132, July 1971, University of Texas, Austin, Texas.

[3] BRANDWAJN A., Equivalence and decomposition methods with application to a model of a time-sharing virtual memory system - in Proceedings of "Aspects théoriques et pratiques des Systèmes d'Exploitation", IRIA-Rocquencourt, France, April 1974.

[4] BRANDWAJN A., BUZEN J., GELENBE E., POTIER D., A model of performance for virtual memory systems - ACM SIGMETRICS Symposium, Montreal 1974.

[5] BUZEN J., Queuing network models of multiprogramming - Ph.D. Thesis, Harvard University, Cambridge 1971.

[6] DENNING P.J., The working set model for program behaviour - Comm. ACM, May 1968.

[7] DENNING P.J., Virtual memory - Computing Surveys 2, n°3 (Sept 1970).

[8] DENNING P.J., Thrashing: its causes and preventions - AFIPS Conference Proceedings, FJCC 33 (1968).

[9] GELENBE E., POTIER D., BRANDWAJN A., LENFANT J. - Gestion optimale d'un ordinateur multiprogrammé à mémoire virtuelle - Proceedings of the 5th Conference on Optimization Techniques, Springer-Verlag, 1973.

[10] GOODELL R., BROWN R., Smoothing, forecasting and prediction of discrete time series - Prentice Hall (1962).

[11] JACKSON J.R., Jobshop-Like queuing systems - Management Science, 10,1, October 1963.

[12] LEROUDIER J., Analyse d'un système à partage de ressources, RIRO, Octobre 1973.

[13] MOORE C.G., Network models for large scale time sharing systems - Ph.D. Thesis, University of Michigan, 1971.

[14] RODRIGUEZ-ROSSEL J., DUPUY J.P., The evaluation of a time sharing page demand system - AFIPS Conference SJCC, 1972.

[15] SALTZER J.H., A simple linear model demand paging performance - Comm. ACM, Vol 17 n°4, April 1974.

[16] GELENBE E., Modèles de systèmes informatiques - Thèse d'Etat, Université PARIS VI, Novembre 1973.
<figure><img src="image_1.png" /><figcaption>Figure 1</figcaption></figure>
<figure><img src="image_2.png" /><figcaption>Figure 2</figcaption></figure>
<caption>Figure 3 (a)</caption>

PROCESSOR UTILIZATION

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

DEGREE OF MULTIPROGRAMMING

M = 128 pages

K = 1.5

t<sub>SM</sub> = 5 ms

t<sub>FD</sub> = 30 ms
<figure><img src="image_4.png" /><figcaption>Figure 3 (b)</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 3 (c)</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 4</figcaption></figure>

M = 128 pages

K = 2.5

t<sub>SM</sub> = 10 ms

t<sub>FD</sub> = 30 ms
<figure><img src="image_7.png" /><figcaption>Figure 5</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 6</figcaption></figure>
<table><caption>Figure 7</caption><thead><tr><th></th><th>Without control</th><th>With control</th></tr></thead><tbody><tr><td rowspan="6">LOAD I</td><td>CPU utilization</td><td>0,59</td><td>0,72</td></tr><tr><td>CPU utilization without overhead</td><td>0,35</td><td>0,60</td></tr><tr><td>Paging drum utilization</td><td>0,97</td><td>0,29</td></tr><tr><td>File disk utilization</td><td>0,53</td><td>0,90</td></tr><tr><td>Mean response time</td><td>33,12</td><td>18,79</td></tr><tr><td>Mean degree of multiprogramming</td><td>16,09</td><td>4,98</td></tr><tr><td rowspan="6">LOAD II</td><td>Mean efficiency</td><td>0,06</td><td>0,11</td></tr><tr><td>CPU utilization</td><td>0,78</td><td>0,73</td></tr><tr><td>CPU utilization without overhead</td><td>0,66</td><td>0,65</td></tr><tr><td>Paging drum utilization</td><td>0,24</td><td>0,11</td></tr><tr><td>File disk utilization</td><td>0,99</td><td>0,97</td></tr><tr><td>Mean response time</td><td>15,79</td><td>16,53</td></tr><tr><td></td><td>Mean degree of multiprogramming</td><td>13,55</td><td>8,98</td></tr><tr><td></td><td>Mean efficiency</td><td>0,13</td><td>0,12</td></tr></tbody></table>
α = 0.10
s = 0.10
P = 500 milliseconds

<figure><img src="image_9.png" /><figcaption>Figure 8</figcaption></figure>
$$ 
\begin{array}{l}
\alpha = 0.05 \\
\text{s} = 0.25 \\
\text{P} = 100 \text{ milliseconds}
\end{array}
 $$

<figure><img src="image_10.png" /><figcaption>Figure 9</figcaption></figure>
<table><caption>Figure 10</caption><thead><tr><th></th><th>Without control</th><th>with control</th></tr></thead><tbody><tr><td>CPU utilization</td><td>0,65</td><td>0,89</td></tr><tr><td>CPU utilization without overhead</td><td>0,49</td><td>0,68</td></tr><tr><td>Paging drum utilization</td><td>0,54</td><td>0,45</td></tr><tr><td>File disk utilization</td><td>0,67</td><td>0,88</td></tr><tr><td>Mean response time (seconds)</td><td>25,35</td><td>18,67</td></tr><tr><td>Mean degree of multiprogramming</td><td>14,17</td><td>11,08</td></tr><tr><td>Mean efficiency</td><td>0,09</td><td>0,19</td></tr></tbody></table>