# A two level control scheme for multiprogrammed virtual
memory computer systems

Jacques Leroudier, Dominique Potier

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

## To cite this version:

Jacques Leroudier, Dominique Potier. A two level control scheme for multiprogrammed virtual memory computer systems. [Research Report] IRIA-RR-141, IRIA. 1975, pp.27. [hal-04716093]

HAL Id: hal-04716093

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

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

laboratoire de recherche
en informatique
et automatique

# A two level control scheme for multiprogrammed virtual memory computer systems

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

J.Leroudier, D.Potier

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n°141

Novembre 1975
# A TWO LEVEL CONTROL SCHEME FOR
MULTIPROGRAMMED VIRTUAL MEMORY COMPUTER SYSTEMS

J. Leroudier, D. Potier

## RÉSUMÉ :

Dans des articles précédents, nous avions présenté un modèle mathématique de système à mémoire virtuelle pour en évaluer les performances. Ce modèle était utilisé pour étudier le comportement des systèmes à mémoire virtuelle et plus particulièrement le phénomène d’écroulement. Dans cet article, nous utilisons le même modèle pour étudier le comportement du tambour de pagination lorsque le degré de multiprogrammation est optimum. Nous aboutissons à la conclusion que, si aucune ressource du système n’est saturée le taux d’utilisation de l’unité de pagination est au voisinage de 50 % chaque fois que le taux d’utilisation de l’Unité Centrale est maximisé. Un algorithme de contrôle adaptatif basé sur l’activité de l’unité de pagination est proposé et des comparaisons sont faites avec les résultats que nous avions précédemment obtenus. Nous montrons, de plus, que des performances optimales ne peuvent être obtenues que par une utilisation équilibrée des différentes ressources du système. Cette conclusion recoupe et étend les résultats théoriques de Buzen et ceux pratiques de Wulf.

## ABSTRACT :

In recent papers, we have presented an analytical model of virtual memory system performance which was used to provide a characterization of thrashing and some insight into the behaviour of virtual memory computer systems. In this paper, we shall use the same analytical model to investigate the behaviour of the paging drum when the degree of multiprogramming is set to its optimal value. The main conclusion, which corroborates the general feeling on performance of virtual memory systems, is that drum utilization remains in the 50 % range when ever CPU utilization is maximized, if no resource is saturated. An adaptive control algorithm based on the activity of the paging device is proposed and comparisons with our previous results are presented. Moreover, after further investigations we show also that optimal performance can only be achieved through a balanced use of the different resources of the system. This conclusion cross-checks and extends Buzen’s theoretical results and Wulf’s practical ones.
# A TWO LEVEL CONTROL SCHEME FOR
MULTIPROGRAMMED VIRTUAL MEMORY COMPUTER SYSTEMS

Jacques LEROUDIER, Dominique POTIER

IRIA - LABORIA
BP 5.
78150 LE CHESNAY
FRANCE

## I - INTRODUCTION

In recent papers [1, 2] we have presented an analytical model of virtual memory system performance which was used to provide a characterization of thrashing and some insight into the behaviour of virtual memory computer systems. We pointed out the existence of an optimal degree of multiprogramming with respect to the central processing unit (CPU) utilization and it was shown that the value of the optimal degree of multiprogramming was closely related to such program behaviour parameters as locality and I/O rate. These observations were used to support a method to control the degree of multiprogramming in a virtual memory computer system by estimating dynamically the activity of the resources of the system [2].

In this paper, we shall use the same analytical model to investigate the behaviour of the paging drum when the degree of multiprogramming is set to its optimal value.

The main conclusion, which corroborates the general feeling on performance of virtual memory systems [3, 4, 5], is that drum utilization remains in the 50 %/o range whenever CPU utilization is maximized, if no resource is saturated. The results are validated through simulation experiments in order
to relax some theoretical assumptions used in the analytical model and to take into account some detailed mechanisms such as CPU overheads. As an application, an adaptive control algorithm based on the activity of the paging device is proposed. The algorithm has been simulated and comparisons with results reported in [2] are presented.

Moreover, after further investigations we show also that optimal performance can only be achieved through a balanced use of the dif- ferent resources of the system. This conclusion cross-checks and extends Buzen's theoretical results [6] and Wulf's practical ones [7].

## II - THE MODEL

The model represented in figure 1 has been described in detail in [1, 2]. It consists of a CPU, a secondary memory (SM) device and a filing disk (FD). A queue of requests is associated with each device and the order in which these requests are satisfied is assumed to be FIFO.

A fixed number n of statistically identical and independent processes (user programs) 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 queues, respectively, then

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

The behaviour of processes is characterized by a computation time followed by either a page fault after which the process enters the SM queue or an I/O request in which case the process enters the FD queue. Processes which terminate their service at the SM of at the FD return to the CPU queue. The feedback loop around the CPU queue represents processes which depart from the system but which are immediately replaced by a new process, thus maintaining a constant degree of multiprogramming.

Let $\tau$ be the random variable representing uninterrupted computation time at the CPU, and let $t_{pf}, t_{io}, t_c$ be the random variable representing
respectively the computation times between two consecutive page faults, between two consecutive I/O operations, and the total computation time of a process (user program). With the assumption of no overlap between processing and I/O operations, $t_{io}$ and $t_c$ are entirely intrinsic to a program, whereas $t_{pf}$ is not and depends on the way memory is allocated to programs. Now, we define $T_{cpu}$, $T_{pf}$, $T_{io}$ and $T_c$ as the mean values of $\tau$, $t_{pf}$, $t_{io}$ and $t_c$ and let $T_{sm}$ and $T_{fd}$ be the mean service times of SM and FD. According to [1], we have the following relations between CPU, SM and FD utilizations, respectively $A_{cpu}(n)$, $A_{sm}(n)$ and $A_{fd}(n)$:

$$ (2) \qquad A_{sm}(n) = \frac{p_{sm} T_{sm}}{T_{cpu}} \qquad A_{cpu}(n), $$

$$ (3) \qquad A_{fd}(n) = \frac{p_{fd} T_{fd}}{T_{cpu}} \qquad A_{cpu}(n), $$

where $p_{sm}$ and $p_{fd}$ are respectively the probabilities for a process leaving CPU to enter the SM and FD queues. The probabilities $p_{sm}$ and $p_{fd}$ can be computed and following [1] we have

$$ (4) \qquad p_{sm} = \frac{T_{cpu}}{T_{pf}}, $$

$$ (5) \qquad p_{fd} = \frac{T_{cpu}}{T_{io}}, $$

and (2) and (3) become:

$$ (6) \qquad A_{sm}(n) = \frac{T_{sm}}{T_{pf}} \qquad A_{cpu}(n), $$

$$ (7) \qquad A_{fd}(n) = \frac{T_{fd}}{T_{io}} \qquad A_{cpu}(n). $$

It is important to notice that these equations can be written without any assumptions about the distribution functions of $t_{pf}$, $t_{io}$, $t_c$ and of the service times at SM and FD. They can be simply derived from a theorem
by Chang and Lavenberg [8] and they express the process flow conservation in the network.

Now if we assume that $t_{pf}$, $t_{io}$, $t_c$ and service times at SM and FD are independent exponentially distributed random variables, the model is then a particular case of Jackson's networks[9] and $A_{cpu}(n)$ can be simply computed [10]. As a matter of fact the steady state behaviour of the system is completely characterized by the joint probability distribution $p(n_0, n_1, n_2)$ of the number of processes in the three queues and the stationary solution is given by :

$$ (8) \qquad p(n_0, n_1, n_2) = \frac{1}{G(n)} \left(\frac{T}{T_{pf}}\right)^{n_1} \left(\frac{T_{fd}}{T_{io}}\right)^{n_2}, $$

where

$$ (9) \qquad G(n) = \sum_{n_1, n_2} \left(\frac{T_{pf}}{T}\right)^{n_1} \left(\frac{T_{fd}}{T_{io}}\right)^{n_2}. $$

The CPU utilization $A_{cpu}(n)$ is quite simply the probability of a non-empty CPU queue, that is :

$$ (10) \qquad A_{cpu}(n) = \sum_{\substack{1 \le n_0 \le n \\ 0 \le n_1 \le n}} p(n_0, n_1, n_2). $$

From (8) and (9), $A_{cpu}(n)$ can be written as

$$ (11) \qquad A_{cpu}(n) = \frac{G(n-1)}{G(n)}. $$

In [10] Buzen proposes an algorithm to compute simply $G(n)$ and hence $A_{cpu}(n)$. We have used this algorithm to obtain the numerical results we present in the next sections of this paper. It should be noted that $A_{cpu}(n)$, and hence $A_{sm}(n)$ and $A_{fd}(n)$, do not depend on $T_c$.
It remains to characterize $T_{pf}$ which depends on the process behaviour but also on the system and, in particular, on the memory allocation policy. Assuming that memory is allocated to processes on a page-on-demand basis we shall use experimental evidence to relate the mean time $T_{pf}$ between two consecutive page faults of a program (process in the system) to the amount of space allocated to this program. Belady and Kuehner [11] have proposed the following model to fit their measurements :

$$ (12) \qquad T_{pf} = a m^k, $$

for a program executing in memory space of size m, where a depends on the processing speed as well as on program characteristics while k depends on program locality and on the memory management strategy. A more complex model has been presented by Chamberlin and Liu [11] which is supposed to provide a better fit of the mean of the real life-time function $T_{pf}$ :

$$ (13) \qquad T_{pf} = \frac{2b}{1 + \left(\frac{d}{m}\right)^2}, $$

where d is the memory space size which ensures a program to have a mean time between page faults which is half its maximal "life time", b is the mean time between the page faults when the program executes in memory space of size d.

However, all the computations we have done show no significant differences between the results obtained from the two models, and we shall therefore restrict our attention in the sequel to the first life-time model.

Furthermore, we shall assume that the core memory available is of size M and that it is equally shared among processes (user programs) which yields :

$$ (14) \qquad m = \frac{M}{n}, $$

$$ (15) \qquad T_{pf} = a \left(\frac{M}{n}\right)^k. $$
To summarize, the model is characterized by the following set of parameters :

n degree of multiprogramming,

M total memory size,

$T_{sm}$, $T_{fd}$ mean service times at the SM and FD stations,

a, k parameters of the life-time model,

$T_{io}$ virtual mean time between I/O operations,

and we shall investigate in the next section the behaviour of $A_{cpu}(n)$, $A_{sm}(n)$, $A_{fd}(n)$ for a wide range of these parameters.

### III - THE CRITERION UNDER CONSIDERATION

We are interested by two kinds of performance measures. We want, on one hand, to have a good utilization of the different resources in the system and, on the other hand, to ensure a satisfactory system's response time. These two imperatives can be conciliated by considering the ratio :

$$ (16) \quad D(n) = \frac{\text{real execution time of n programs with no multiprogramming}}{\text{real execution time of n programs with multiprogramming of degree n}} $$

$D(n)$ that we call "dilatation" measures the expansion of the real time which is obtained by multiprogramming n programs. We can evaluate $D(n)$ if we notice that $D(n)$ is also the ratio of the program throughputs with and without multiprogramming:

$$ (17) \quad D(n) = \frac{\text{program throughput with multiprogramming of degree n}}{\text{program throughput with no multiprogramming}} $$

Let $T_{pf}(1)$ be the mean time between page faults when a program is alone in the system, then the program throughput with no multiprogramming writes :

$$ \left[ T_c + \frac{T_c}{T_{io}} T_{fd} + \frac{T_c}{T_{pf}(1)} T_{sm} \right]^{-1}, $$
when the degree of multiprogramming is n, the program throughput is simply :

$$ \frac{A_{cpu}(n)}{T_c} $$

Hence, D(n) is expressed by :

$$ (18) \qquad D(n) = A_{cpu}(n) \left( 1 + \frac{T_{fd}}{T_{io}} + \frac{T_{sm}}{T_{pf}(1)} \right), $$

where $T_{pf}(1) = a(\frac{M}{1})^k$.

From (6) and (7), we can write :

$$ (19) \qquad D(n) = A_{cpu}(n) \left( 1 + \frac{T_{sm}}{T_{pf}(1)} \right) + A_{fd}(n) $$

So D(n) is not only a measure of the system's response time but also of the resource utilizations, since it can be expressed as their sum. The term $\frac{T_{sm}}{T_{pf}(1)}$ comes from the existence of a virtual memory, and it can usually be neglected, if the size of the memory is appropriate because then $T_{pf}$ is large compared to $T_{sm}$. Hence D(n) can be approximated by :

$$ (20) \qquad D(n) \approx A_{cpu}(n) + A_{fd}(n). $$

It should be noticed that equation (20) is similar to the one written in [2, eq.(7)] which was obtained with another approach. In [2] "dilatation" is defined as a measure of the parallelism between the resources of the system. Thus, our criterion takes into account the three following measures :

- parallelism between system resources,

- resource utilizations,

- system's response time,

which are shown to be related.
## IV. SECONDARY MEMORY UTILIZATION

Having defined the model and a measure of performance we can now use the model to investigate the behaviour of the secondary memory when the degree of multiprogramming is set to the value which maximizes D(n). From equation (18), it can be noticed that D(n) is also maximized when $A_{cpu}(n)$ is maximized and therefore we shall restrict our attention in this section to $A_{cpu}(n)$.

Three series of experiments have been performed and the results are presented in the figures 2, 4 and 5. The experiments consist in computing $A_{cpu}(n)$ and $A_{sm}(n)$ for different values of three important parameters of the model : the mean service time $T_{sm}$ of the secondary memory, the mean time between I/O requests $T_{io}$, the coefficient k of the life-time function. The functions $A_{cpu}(n)$ and $A_{sm}(n)$ are then plotted on the same graph so that the behaviour of the secondary memory can be simply related to the measure of performance $A_{cpu}(n)$, and hence to D(n).

Several observations can be made from the figures 2, 4 and 5. First, of all, all the $A_{sm}(n)$ curves are monotonic increasing S-shaped functions, with an inflexion point located between $A_{sm}(n) = 0.4$ and $A_{sm}(n) = 0.6$ which roughly corresponds to the maximum value of $A_{cpu}(n)$. In order to check this point the portions of $A_{cpu}(n)$ and $A_{sm}(n)$ corresponding to the values of n for which $0.4 \le A_{sm} \le 0.6$ have been outlined. We can observe that for all the experiments the outlined portions correspond to the maximum values of $A_{cpu}(n)$, and it can be consequently inferred that the optimum working range of the system can be simply characterized by the load of the secondary memory device. The second observation is important with respect to this first conclusion : the fact that the inflexion point of $A_{sm}(n)$ is located within the optimum working range means that the sensitivity $\frac{\Delta n}{\Delta A_{sm}(n)}$ is minimum in this zone. The model has been extended and simulated in order to take into account CPU overheads and constant service times at the SM. The results are presented in figure 3 and point out the same relation between $A_{cpu}(n)$ (user's useful computation) and $A_{sm}(n)$. The practical implication of this result is that an optimum degree of multiprogramming can be satisfactorily obtained from the estimation of $A_{sm}(n)$.
The last observation to be made is that these conclusions have been obtained for a wide range of architecture and process behaviour parameters, $T_{sm}$, $T_{io}$, k, and it can therefore be thought that they do not depend on a particular combination of parameters, but express some basic aspects of the behaviour of multiprogrammed virtual memory computer systems. It would have been more satisfactory to derive our results from some mathematical properties of $A_{cpu}^{(n)}$ and $A_{sm}^{(n)}$ rather than from mere observations of the curves. Unfortunately, we have been unable to exhibit such properties, and, to our knowledge, this is still an open problem.

It remains to verify that the results we have obtained are in good agreement with experimental observations made on multiprogrammed virtual memory systems. The general opinion shared by people dealing with such systems is that optimum performance is achieved when there is practically no request waiting behind the paging channel which means that the secondary memory load does not exceed 0.6 or so. For instance, Rodriguez-Rosell states in [3] that "measurements of the paging and disk file channel queues indicate that before thrashing no queues are formed at the I/O channels". During discussions with Adams [5] about the EMAS systems it was pointed out that their system was operating at its maximum efficiency when the paging drum channel was busy fifty percent of the time. More precise figures can be derived from measurements made on the IBM - CP67 system [3, fig. 1 and 3] and performance prediction made on the MULTICS system [13, table 5-7, p 227]. It should be noted that in the IBM - CP67 case, the fraction of memory pages which has been written is missing in [3] and was assumed to be equal to 0.35. The results are presented in Tables I and II and show good agreement with the observations derived from the model.

The conclusions we have arrived at can be summarized in the two following principles :

## PRINCIPLE I :

In a multiprogrammed virtual memory computer, optimum performance is achieved if the utilization of the secondary memory remains in the [0.4, 0.6] interval.
## PRINCIPLE II :

At the optimum working point the sensitivity of the degree of multiprogramming to the utilization of the secondary memory is minimum.

These two principles have direct implications for the regulation of the degree of multiprogramming. Principle I gives a simple indicator of optimum system behaviour. Principle II says that an optimum degree of multiprogramming can be simply estimated by measuring the utilization of the secondary memory and that errors in the measurements will not affect much the estimation of the optimum degree of multiprogramming. In the next section, we present an adaptive algorithm for the control of the degree of multiprogramming based on these two principles.

## V - ADAPTIVE CONTROL OF THE DEGREE OF MULTIPROGRAMMING

The function of an adaptive control is to maintain the system's in operation so that the measure of performance D(n) is optimized. The control scheme is based on the two Principles stated in the previous section and the structure of the controller represented in figure 6 is kept similar to the one presented in [2] : an estimator EST of system behaviour uses measurements on the secondary memory device to estimate its utilization ; an optimizer OPT computes decisions using the estimates provided by EST as well as a knowledge of the system state ; OPT furnishes commands to the switch K controlling the access of users waiting in the queue Q into the resource loop. The solid lines in figure 6 indicate the cycle a user will follow and the dotted lines represent the flow of information to the various units of the controller.

The controller has been implemented in a simulation model of a virtual memory time-sharing system. This simulation model is an extension of the analytical model described in section II where CPU overheads and non-exponential service time distributions are also taken into account. The different units
of the controller perform the following operations.

1) **EST**: Let $X_i$ be the most recent value of the secondary memory utilization which is measured. EST computes a smoothed unbiased estimate $Z_i$ of the secondary memory utilization as follows [2].

Let $Y_i$ be given by

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

then.

$$Z_i = \lambda_i Y_i$$

where

$$\lambda_i = \frac{1}{1 - (1-\alpha)^i}$$

The variance $V(Z_i)$ of $Z_i$ is computed as well in order to build a confidence interval CI of the secondary memory utilization.

2) **OPT**: updates the current estimate $n*$ of the optimal degree of multiprogramming according to the estimate of the secondary memory utilization provided by EST. OPT is based on a threshold $S$, which is a parameter of the controller chosen between 0.4 and 0.6 from Principle I. OPT, when it is activated, computes an optimal degree of multiprogramming $n*$ which is transferred to $K$:

* if $S \in CI$ $n*$ remains $n*$

* if $S > CI$ $n*$ is increased by 1

* if $S < CI$ $n*$ is decreased by 1.

It should be recalled that the control scheme takes into account only the introduction of process into the multiprogramming set, and that processes cannot be forced to leave the system.

In the simulations which have been run, $S$ has been chosen equal to 0.5. However, in a real system some tuning up of the controller would certainly be necessary in order to determine the best value of $S$.
The simulation experiments presented in [2] have been exactly repeated. They consist in running a single simulation with two different loads : LOAD II for 200 sec., then LOAD I for 300 sec., then LOAD I for 200 sec. LOAD I and LOAD II have different localities and I/O rates so that the optimum degree of multiprogramming is 6 for LOAD I and 18 for LOAD II. The same improvements in system performance as in [2] have been obtained and, moreover, it can be shown by comparing the figures 7a and 7b that the control based on the secondary memory utilization adapts itself to load variations three times faster than the previous scheme based on CPU and FD utilizations. One reason for this result is that in the present case the decision is based on the estimation of one point : the secondary memory utilization, rather than on the estimation of a function as in [2]. It should also be noted that the measurements and the operations performed by EST and OPT are simpler in the present case.

## VI - BALANCING CPU AND FD

We have presented in the previous section an adaptive control scheme which estimates the size of the multiprogramming set which maximizes system performance and ensures that thrashing is prevented. However, another level of optimization is still necessary in order to determine, within the multiprogramming set, the mix of programs which will ensure optimal utilization of both CPU and FD.

This problem of improving system performance by balancing the load of the different resources is commonly felt as a crucial one by computer center managers and has been studied by several authors [4, 6, 7, 15]. However, most of these studies, excepting [7], concern the partition of a given load among different peripheral units and do not investigate the question of balancing CPU and I/O devices in relation with paging activity.

In order to examine this problem we use the analytical model presented in section II and the measure of performance D(n) defined in section III.
Let $D* = D(n*)$ be the value of the measure of performance for the optimal degree of multiprogramming $n*$. In other words, $D*$ represents the system performance when the size of the multiprogramming set is optimum. We can now look at the behaviour of $D*$ as a function of $\frac{T_{io}}{T_{pf}}$ for different values of $k$ in order to study the performance of the optimum multiprogramming set size for different values of the mean I/O rate of the programs belonging to this set. $D*$ is plotted in figure 8 as a function of $\frac{T_{io}}{T_{pf}}$ for $k$ varying from 1.5 to 2.5. It can be observed that $D*$ is maximized for values of $\frac{T_{io}}{T_{pf}}$ close to 1, and that the sensitivity of $D*$ to $\frac{T_{io}}{T_{pf}}$ is largely dependent on $k$. For large values of $k$, i.e. $k \ge 2$, overall performance is maximized for $\frac{T_{io}}{T_{pf}} = 1$, which means the utilizations of CPU and FD are balanced as can be seen from equation (7). When $k$ is small, i.e. $k < 2$, the optimum is obtained for $\frac{T_{io}}{T_{pf}} < 1$. However, in this case, there is no sensible variations of $D*$ with $\frac{T_{io}}{T_{pf}}$ due to the fact that paging then dominates system activity.

From these observations, we can state the following principle :

### PRINCIPLE III :

An optimal mix of programs within the multiprogramming set is achieved when the mean virtual time between consecutive I/O of the programs belonging to the multiprogramming set is equal to the mean service time of the I/O device.

Principle III provides the basis of a control scheme for selecting which program enters the multiprogramming set : the program should be selected so that the quantity $\frac{T_{io}}{T_{pf}}$ measured for the multiprogramming set is as close as possible to the mean service time $T_{fd}$ of the I/O device.

It can be noticed that Principle III rejoins the intuitive control based on balanced device utilizations proposed by Wulf in [7]. Another obvious consequence of Principle III is that fastest devices should be more loaded than
slower ones. This point has been analysed in detail by Buzen [6] and similar conclusions were obtained.

## VII - CONCLUSION

We have presented in this paper a two level optimization of multiprogrammed virtual memory computer performance. The basic principles of the optimization schemes have been derived from the analysis of a model of virtual memory time-sharing system and experimental observations have been presented to verify our conclusions. The first level of optimization, based on the utilization of the secondary memory, determines the optimal size of the multiprogramming set, and the second level of optimization balances the utilization of the CPU and of the I/O devices. Simulation experiments of the first level have shown a significant improvement with regards to [2]. The implementation of the second level of optimization is presently being done. It sets some new problems about the exponential smoothing of the estimates which have been pointed out by Wulf [7] and requires further investigations in order to determine the values of the smoothing constants.
<table><thead><tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>system efficiency [3]</td><td>0.17</td><td>0.28</td><td>0.31</td><td>0.29</td><td>0.21</td><td>0.16</td></tr><tr><td>Real page fault rate [3] (msec<sup>-1</sup>)</td><td>0.9</td><td>1.6</td><td>2.4</td><td>3.0</td><td>3.6</td><td>4.2</td></tr><tr><td>Secondary memory utilization</td><td>.15</td><td>.26</td><td>.39</td><td>.49</td><td>.58</td><td>.68</td></tr></tbody></table>

TABLE I

Secondary memory utilization in IBM - CP67.

(The length of time required to complete a page fetch is taken equal to 1.35 the mean service time of the secondary memory to take into account the swap out of written pages, which yields $T_{sm} = 1.35 \times 12 = 16.2$ msec).
<table><thead><tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>user's useful computation [14]<br>A<sub>cpu</sub>(n)</td><td>55.4</td><td>63.7</td><td>65.5</td><td>65.1</td><td>63.9</td><td>62.5</td><td>61.3</td><td>60.2</td></tr><tr><td>mean virtual time between page fault [14]<br>T<sub>pf</sub>(n) (msec.)</td><td>98.5</td><td>55.9</td><td>41.7</td><td>34.7</td><td>30.5</td><td>27.7</td><td>25.8</td><td>24.3</td></tr><tr><td>page fault rate<br>A<sub>cpu</sub>(n)/T<sub>pf</sub>(n) (msec.)</td><td>.562</td><td>1.14</td><td>1.57</td><td>1.88</td><td>2.10</td><td>2.26</td><td>2.38</td><td>2.48</td></tr><tr><td>secondary memory utilization<br>A<sub>cpu</sub>(n) T<sub>pf</sub>(n)/T<sub>sm</sub></td><td>0.20</td><td>0.40</td><td>0.55</td><td>0.66</td><td>.73</td><td>.79</td><td>.83</td><td>.87</td></tr></tbody></table>

TABLE II

Secondary memory utilization in MULTICS

(T<sub>sm</sub> = 35 msec.)
<figure><img src="image_4.png" /><figcaption>FIGURE 1</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>**Figure 2** : A<sub>cpu</sub>(n) and A<sub>sm</sub>(n) as functions of n

M = 512, k = 1.5, a = 0.01msec., T<sub>io</sub> = 30 msec., T<sub>fd</sub> = 30 msec.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 3 : A<sub>cpu</sub>(n) and A<sub>sm</sub>(n) as function of n</figcaption></figure>

M = 512, k = 1.5, a = 0.01 msec., T<sub>io</sub> = 30 msec., T<sub>fd</sub> = 30 msec.

Context switching overhead 0.5 msec.

file i/o overhead 2.0 msec.

paging i/o overhead 1.0 msec.
<figure><img src="image_7.png" /><figcaption>Figure 4 : A<sub>cpu</sub>(n) and A<sub>sm</sub>(n) as functions of n

M = 512, k = 1.5, a = 0.01 msec., T<sub>fd</sub> = 30 msec., T<sub>sm</sub> = 10 msec.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>figure 5 : $A_{cpu}(n)$, $A_{sm}(n)$ as functions of n</figcaption></figure>

M = 512, k = 2, a = 0.01 msec., T<sub>fd</sub> = 30 msec., T<sub>sm</sub> = 10 msec.
<figure><img src="image_9.png" /><figcaption>Figure 6</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 7a: Estimate of the optimal degree of multiprogramming obtained by applying Principles I and II.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 7b: Estimate of the optimal degree of multiprogramming obtained from experiments reported in [2].</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Figure 8 : L* as function of T<sub>io</sub>/T<sub>fd</sub></figcaption></figure>

M - 256, a = 0.1, T<sub>sm</sub> = 10 msec.
REFERENCES

[ 1 ] M. BADEL, E. GELENBE, J. LENFANT, J. LEROUDIER, D. POTIER - "Adaptive optimization of the performance of a virtual memory computer" - Proceedings of the workshop on computer architecture and networks - IRIA - August 1974.

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

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

[ 4 ] P.J. DENNING - "Multiprogrammed memory management" - IEEE Proceedings on Interactive Computer Systems - June 1975.

[ 5 ] J.C. ADAMS, G.E. MILLARD - "Performance measurements on the Edinburgh Multi Access System" - ICS 75 - Antibes - June 1975.

[ 6 ] J.P. BUZEN - "Analysis of system bottlenecks using a queueing network model" - ACM-SIGOPS - Workshop on System performance evaluation - Harvard - April 1971.

[ 7 ] W.A. WULF - "Performance monitors for multiprogramming systems" - Second Symposium on Operating Systems Principles - Princeton - October 1969.

[ 8 ] A. CHANG, S.S. LAVENBERG - "Work-rates in closed queueing networks with general independent servers" - IBM Research Report RJ 989 - 1972.

[ 9 ] J.R. JACKSON - "Jobshop like queueing systems" - Management Science 10, 1 - October 1963.

[10] J.P. BUZEN - "Computational algorithm for closed queueing networks with exponential servers" - CACM, Vol. 16, nº 9 - September 1973.

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

[12] D.D. CHAMBERLIN, S.H. FULLER, L.Y. LIU - "A page allocation strategy for multiprogramming systems" - IBM Research Report RC 3848 - May 1972.

[13] J.C. ADAMS - "Architecture and performance evaluation of EMAS" - Seminars on modeling and system performance evaluation - IRIA - October 1975.
[14] A. SEKINO - "Performance evaluation of multiprogrammed time-shared computer systems" - Ph.D. Thesis - Project MAC TR-103 - MIT - September 1972.

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