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

HAL
open science

# The rate control policy for virtual memory management

Erol Gelenbe, Israel Mitrani, Alain Kurinckx

► To cite this version:

Erol Gelenbe, Israel Mitrani, Alain Kurinckx. The rate control policy for virtual memory management. [Research Report] IRIA-RR-295, IRIA. 1978, pp.25. hal-04716530

HAL Id: hal-04716530

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

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

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

THE RATE CONTROL
POLICY FOR
VIRTUAL MEMORY
MANAGEMENT

Erol GELENBE
Alain KURINCKX
Isi MITRANI

Rapport de Recherche N° 295

Mai 1978
THE RATE CONTROL POLICY FOR VIRTUAL MEMORY MANAGEMENT

Erol Gelenbe, Alain Kurinckx, Isi Mitrani

Résumé :

Nous décrivons un algorithme de contrôle de la multiprogrammation des systèmes à mémoire virtuelle. Il consiste à introduire les processus dans l'ensemble multiprogrammé à un taux proportionnel à leur taux de sortie. Un processus est éliminé si le nombre de défauts de page qu'il produit depuis sa dernière entrée dans l'ensemble multiprogrammé dépasse une valeur déterminée.

Un modèle du système ainsi contrôlé nous permet de montrer que la politique empêche l'écroulement de se manifester et que les performances obtenues sont proches de celles fournies par un contrôle optimal. Nous calculons également les temps moyens de réponse des différentes classes de tâches.

Abstract :

We present an algorithm for the control of a multiprogramming virtual memory system which introduces processes into the multiprogramming set at a rate proportional to their departure rate, and which eliminates processes if their paging activity exceeds a certain level.

A model of the system with this control policy allows us to show that it avoids thrashing, and that its performance is close to that obtained by an «optimal» control. We also obtain response time curves for different classes of tasks.

Key words : Virtual memory, mutiprogramming, adaptive control, scheduling.
# 1. INTRODUCTION

Multiprogramming systems with virtual memory are now an appreciable portion of the operating systems being used in practice. Many of these do not use fully the possibilities offered by the dynamic process and resource management mechanisms, however, because of the relative cost of the control policies which they require in order to provide satisfactory performance in the presence of widely different and time-varying workloads.

The central performance issue in virtual memory systems is that of maintaining the multiprogramming degree at a level which optimizes performance [1,2]. The difficulty of this problem has three main sources. The workload, mostly composed of user programs, determines the optimal level of multiprogramming, and its characteristics vary with time. This time variation results both from the introduction of new programs into the workload and from the time-varying nature of program behaviour. The only predictions which can be made about resource requirements will depend on measurements of program behaviour in the immediate past. Yet such predictions, if they are to be sufficiently detailed (such as in the case of working sets), need special hardware if they are to be carried out without an unacceptable computational cost. Finally, the reaction times of the control algorithms and the transient behaviour of the system under control must be fast enough to justify an elaborate control procedure.

In this paper, we shall present a control algorithm which circumvents most of these difficulties. The algorithm is based on two main ideas :

- the degree of multiprogramming must be regulated on the basis of global system behaviour rather than on individual process behaviour,

- it must be discriminatory against programs which introduce undesirable perturbations on system performance, such as a large number of page-faults.
This control policy combines these two principles by injecting
processes into the multiprogramming set on the basis of global system
throughput and by choosing a process for elimination on the basis of the
number of page-faults it does during a given period of activity.

The control policy proposed in [1] is one which explicitly seeks the maximum of useful CPU utilisation or system throughput. The policy proposed here does not attempt to maximize throughput explicitly. The "L=S" policy described in [3] attempts to maintain the average time between page-faults at a value close to the time necessary for transferring a non-resident page to primary memory, while the "50 %" heuristic also presented in [3] regulates the degree of multiprogramming so as to maintain the paging device busy at most half of the time during a given time interval.

The control algorithm presented here can be viewed as an extension
and refinement of the *random injection policy* introduced in [4]

In section 2 we will describe the control algorithm in detail and
present the model which will be used to analyze its behaviour and effects.
Section 3 will be devoted to the solution of the model which will include
a new approximate solution technique for multi-class closed queueing net-
work models. Section 4 contains numerical results illustrating system per-
formance in the presence of this control policy.

## 2. THE CONTROL POLICY AND ITS MODEL

### 2.1 The rate control policy (RCP)

Consider the multiprogramming system structure shown on Figure 1.
A set of terminals generates processes which enter into the *active set*
of tasks. In the active set a process uses the system ressources, compo-
sed of the CPU, the I/O devices and the secondary memory system. We assu-
me that the memory space is composed of fixed size pages which are the
units of transfer of information between primary and secondary memory.
Each process of the active set is allocated some fraction of primary me-
mory space (i.e. at least one page), its other pages being in secondary
memory. Transfers between I/O devices and primary memory take place in terms of variable length blocks. The size of the active set is the multi-programming degree.

The execution of a process in the active set is composed of a visit to the CPU queue, followed by an I/O operation or a page-fault, with a return back to the CPU queue, and so on. The process can leave the active set because it has terminated its execution; in that case it "returns" to the terminal from which it originated. This means simply that the process relinquishes the resources it was using in the active set (including its primary memory space) and that control returns to the terminal. In our control policy, which we call the *rate control policy* (RCP), the process can also be forced to leave the active set. In this case it enters the *impeded set* (see Figure 1). This forced departure will take place as soon as the process has done *M+1* page faults, where *M* is a parameter of the RCP. Once again the primary memory pages of a process which is forced to leave the active set to enter the impeded set become free for allocation to other processes. Thus some processes which arrive to the end of their execution without doing *M+1* page faults will never enter the impeded set, while others which have a high paging activity can pass through it several times. The role of the parameter *M* plays a role analogous to that of the CPU quantum in a conventional time-sharing scheduler, since it forces a process to relinquish its resources if it requires more than *M* accesses to the secondary memory.

This mechanism for eliminating processes is accompanied by another mechanism used for bringing back processes from the impeded set into the active set. This will be based on the rate at which processes leave the active set. Let

$$t_1 < t_2 < \cdots < t_n < t_{n+1} < \cdots$$

be instants at which processes leave the active set either because they have done *M+1* page faults or because their execution has ended. We define an estimated interdeparture time $e_n$ whose value is not modified in the interval from $t_n$ to $t_{n+1}$, and such that

$$e_n = (t_n - t_{n-1})\alpha + (1-\alpha)e_{n-1}, \quad n > 2$$

$$e_2 = t_2 - t_1$$
where $0 < \alpha < 1$ is a parameter used to render the estimate $e_n$ more or less "memoryless", that is, more or less responsive to the past history of events. In the interval of time between $t_n$ and $t_{n+1}$ each impeded process is assigned a residence time $D_n = H e_n$. $D_n$ represents the time during which the impeded process should remain in the impeded set, starting from the instant at which it enters it. Suppose that a given process enters the impeded set at time $t_n \le \tau < t_{n+1}$; it is assigned the time $\ell_n = \tau + D_n$ as the instant at which it should leave the impeded set. But if $\ell_n > t_{n+1}$ at time $t_{n+1}$, when the new value $D_{n+1}$ is computed, the following action will be taken :

$$if |D_{n+1} - D_n| < 0.1 D_n \text{ then } \ell_{n+1} \leftarrow \ell_n$$

else if $D_{n+1} < t_{n+1} - \mathcal{Z}$ then enter process into active set

$$else \quad \ell_{n+1} \leftarrow \ell_n + D_{n+1} - D_n.$$

This procedure allows as to make sure that the most up-to-date value of the output rate of processes from the active set is used to compute the output rate from the impeded set. The value $0.1 D_n$ is used to avoid taking action when the relative difference between $D_{n+1}$ and $D_n$ is not significant.

Thus the RCP removes processes from the active set of the basis of their paging activity, and reintroduces them on the basis of the total output rate from the active set.

This control algorithm is subject to two modifications: when the multiprogramming degree is below a threshold value (typically 2 or 3, in our simulation experiments) the RCP is "turned off" and a process is immediately injected into the active set as soon as the multiprogramming degree falls below this value.

## 2.2 A mathematical model of a multiprogramming system controlled by the RCP

In this section we shall outline the presentation of a mathematical model whose purpose is to evaluate the effect of the RCP. The model is shown in Figure 2. The set of terminals which generate user processes
are represented by a finite source of jobs with exponential holding time; since jobs can belong to several classes the average holding times can be different for each class. Each job class j is characterized by its average total CPU execution time $C_j$, its life-time function $E_j$ and its average time between I/O requests $S$ given in process time. This last parameter is in fact chosen to be identical for all classes since our analysis bears principally on the behaviour of jobs with respect to their paging activity. The life-time function, whose form will be given later, is the average time between page faults of the process in process time. It will depend here essentially on the primary memory space allocated to the process and to a "locality coefficient" $k_j$ which is a property of the j-th class. A large $k_j$ will mean that the process will page-fault less frequently for a given primary memory allocation. These assumptions are consistent with those made about program behaviour in other studies of similar problems [1,2,3,4].

Let $1/\mu_0$ denote the average uninterrupted execution time at the CPU; when processor sharing (round-robin) scheduling is used at the CPU, interruptions due to the end of the quantum are not included in this average time. The program behaviour parameters given above will be combined with our definition of $\mu_0$ to obtain a suitable set of parameters to drive the model of Figure 2.

In this model, the behaviour of the jobs is probabilistic and the system is composed of five "service stations" : the CPU, the I/O unit, the secondary memory device (SM), the terminals and the impeded set whose role has been described in section 2.1. The movement of tasks among these five stations is represented by the transition probabilities ($p_{k, \ell; m, m'}^j$): this is the probability that a job of class j ending its service at station k then joins the queue at station l; m is the number of page faults the job had accumulated during its current residence in the resource loop (if applicable) and m' is the new value of this parameter after the transition.

Stations 0,1,2,3,4, denote the CPU, the SM, the I/O unit, the impeded set, and the terminals, respectively. Therefore (see Figure 2) whichever $k=4$ or $k=3$ we have $m=0$, and $m$ increases by one only during the transition from the CPU to the SM queue.
Since a task enters the impeded set at its (M+1)-th page fault we can
only have m=M, m'=0 if k=0 and l=3. We shall deduce these transition
probabilities from the program behaviour parameters E<sub>j</sub>, C<sub>j</sub>, S given
above. This, assuming a full CPU queue the rate at which processes of
class j enter the I/O device queue is

$$
(2.1) \qquad \mu_0 p_{0,2;m,m}^j = 1/S
$$

and the corresponding rate for the SM device is

$$
(2.2) \qquad \mu_0 p_{0,1;m,m+1}^j = 1/E_j \quad \text{for } m<M
$$

The rate of departures towards the terminals (due to the end of task
execution) must be

$$
(2.3) \qquad \mu_0 p_{0,4;m,0}^j = 1/C_j
$$

and the rate of departure into the impeded set for processes having
already done M page faults must be

$$
(2.4) \qquad \mu_0 p_{0,3;M,0}^j = 1/E_j
$$

For processes with m<M, the first three terms must sum to $\mu_0$ for any j. Thus

$$
(2.5) \qquad \mu_0 = [1/S + I/E_j + I/C_j]
$$

Similarly, we can add the rate equalities

$$
(2.6) \qquad \mu_0 p_{0,2;M,M}^j = 1/S
$$

$$
(2.7) \qquad \mu_0 p_{0,4;M,0}^j = 1/C_j
$$

to (2.4) to obtain once again (2.5). If we eliminate the dependency on
the number of page faults done by a process, we can write

$$
(2.8) \qquad \mu_0 p_{0,3}^j = 1/(M+1)E_j
$$

as the rate of departure of class j processes towards the impeded set, and

$$
(2.9) \qquad \mu_0 p_{0,1}^j = M/(M+1)E_j
$$

as their rate of departure towards the SM device, because for each (M+1)
page faults, one on the average will result in a departure to the impeded
set and M will yield transitions into the SM queue.
This preliminary analysis indicates that $\mu_0$; the service rate at the CPU, will depend on the number of active processes (i.e. the ones sharing primary memory space), as will the transition probabilities. This is already an indication that it will not be possible to solve this model exactly even if the service times at the I/O and SM device are taken to be exponential of parameters $\mu_2$ and $\mu_1$, respectively.

In the mathematical model, it will be assumed that the time spent by a task in the impeded set is exponentially distributed of parameter $\delta$; the correspondance between this rate and the output rate from the active set (as described in section 2.1) will be modelled by taking

$$ \delta = h\beta $$

where $\beta$ is the computed output rate from the active set and $h$ is a constant of proportionality.
### 3. ANALYSIS AND EVALUATION OF THE PAGE-FAULT COUNT METHOD

It is clear that process elimination from the resource loop should permit to distinguish between "good" and "bad" processes with respect to their paging behaviour. The impeded processes should be those which contribute most to thrashing, i.e. those which have page faults most often. To this end, a process is removed from the resource loop, and joins the impeded set, at its (M+1)-th page fault, for some M fixed in advance. The choice of M (to be discussed later) is such that only "bad" processes tend to be removed before their completion.

The model described in section 2 is not of a kind for which a closed-form solution is available. However, there are recognisable interface levels such that the interactions across them are weak. Processes circulate inside the resource loop at a much higher rate than that at which they enter or leave it. Good approximation can be achieved, therefore, by decomposing the general model into more easily manageable sub-models [6].

As a first step, we consider the resource loop as a closed network with a fixed number $N_j$ of class j processes circulating inside (j=1,2,...,J). An analysis of this closed network will enable us to replace the whole of the resource loop by a single state-dependent server which gives simultaneous service to all processes present (with rates depending on the process class and on the numbers $N_1, ..., N_J$).

#### 3.1 The resource loop as a closed network

The object of this analysis is to determine the steady-state probability $\pi_j(N_1, N_2, ..., N_J)$ that a class j process is in service at the CPU (that probability determines the rate at which class j processes depart from the resource loop to return to the terminals) ; and the probability $\pi_j^M(N_1, N_2, ..., N_J)$ that a class j process which has already had M page-faults is in service at the CPU (that probability determines the rate at which class j processes leave the resource loop to join the impeded set). Process classes will be distinguished solely on the basis of their lifetime functions

$$ (3.1) \qquad E_j = a_j s_j^k, \quad j = 1, 2, ..., J. $$
Note that a class j process is identified by the parameters $a_j, k_j$ of the lifetime function, and also by the amount of memory $s_j$ which is allocated to it. This allows us, if necessary, to consider different primary memory allocation to processes of different classes.

The closed network can be analysed exactly, under a suitable set of assumptions, by bringing it into the framework of separable queueing network models for which product form solutions are known to exist. The "counting" of page faults can be modeled by splitting class j into M+1 sub-classes $(j,o), (j,1), \dots, (j,M)$. A process of class $(j,i)$ becomes, after a page fault, a process of class $(j,i+1)$ if $i = 0, 1, \dots, M-1$ and it becomes a process of class $(j,o)$ if $i = M$. To give an idea of the analysis, consider the case where the resource loop consists of a CPU and a paging drum only, to be denoted node 0 and node 1 respectively. Assume that processes are served at node 0 according to the processor-sharing discipline, and at node 1 according to the first-come-first-served discipline; with average required service times for class $(j,i)$, $E_j$ at node 0 (for all $i = 0, 1, \dots, M$) and $1/\mu_1$ at node 1 (for all $j = 1, 2, \dots, J$ and $i = 0, 1, \dots, M$). Assume that the distributions of the required service times are exponential (these assumptions can be relaxed significantly; we make them here in order to keep the presentation simple).

We are interested in the steady-state distribution of the aggregate system state $(k_j, n_1, n_2, \dots, n_J)$, where $k_j$ is the number of class $(j,M)$ processes at the CPU and $n_j$ is the total number of class $(j,i)$ processes at the CPU, $i = 0, 1, \dots, M$; $k_j = 0, 1, \dots, n_1$, $n_j = 0, 1, \dots, n_J$, $j = 1, 2, \dots, J$. Using the standard product-form solution of the network (see Baskett et al, [5]) we obtain, after some algebra,

$$P(k_j, n_1, n_2, \dots, n_J) = \frac{1}{G} n! E_j^k \frac{1}{k!} (ME_j)^{n_j-k_j} \frac{1}{(n_j-k_j)!}$$

$$(3.2) \qquad \prod_{s=1}^{J} \left[ ((M+1)E_s)^{n_s} \frac{1}{n_s!} \right]^{\frac{1}{s}}. \\ s \neq j$$

$$(N-n)! (M/\mu_1)^{N-n} \prod_{s=1}^{J} \frac{1}{(N_s - n_s)!}$$
where $n = n_1 + n_2 + \cdots + n_J$, $N = N_1 + N_2 + \cdots + N_J$ and G is a normalisation constant determined from the condition

$$ (3.3) \qquad \sum_{n_1=0}^{N_1} \sum_{n_2=0}^{N_2} \cdots \sum_{n_J=0}^{N_J} \sum_{k_j=0}^{N_j} P(k_j, n_1, n_2, \ldots, n_J) = 1 . $$

A further aggregation gives us the probability that a process of class (j,M) is in service at the CPU :

$$ (3.4) \qquad \pi_j^M(N_1, N_2, \ldots, N_J) = \sum_{n_1=0}^{N_1} \cdots \sum_{n_J=1}^{N_J} \cdots \sum_{n_J=0}^{N_J} \sum_{k_j=1}^{N_j} \frac{k_j}{n} P(k_j, n_1, n_2, \ldots, n_J). $$

Similarly, the probability that a process of any of the classes (j,o), (j,1),..., (j,M) is in service at the CPU is equal to

$$ (3.5) \qquad \pi_j(N_1, N_2, \ldots, N_J) = \sum_{n_1=0}^{N_1} \cdots \sum_{n_J=1}^{N_J} \frac{n_j}{n} \cdots \sum_{n_J=0}^{N_J} \sum_{k_j=1}^{N_j} P(k_j, n_1, n_2, \ldots, n_J). $$

It can be seen from the above that the effort required to evaluate the quantities of interest is not negligible. Moreover, that effort grows rather rapidly when the model is generalised - input/output devices added, exponential assumptions relaxed, etc.. On the other hand, an exact solution is rarely necessary, especially in view of the fact that the system parameters are not usually known and have to be estimated. A reasonable approximation obtained easily is often much preferable to an exact solution obtained with difficulty.

With that observation in mind, we propose a very simple and intuitive method for obtaining the probabilities $\pi_j$ and $\pi_j^M$. The method utilises the context in which the resource loop is placed, i.e. the full model including the terminals and the impeded set.

First, the closed network is solved, for fixed values of $N_1, N_2, \ldots, N_J$, by lumping all classes together, i.e. by considering a single process class with a lifetime function
$$E = \sum_{j=1}^{J} d_j E_j$$

where $d_j = N_j/N$ is the proportion of class j processes (the other parameters - transition probabilities, drum and I/O device service times - are also averaged, if different). That solution (which can be carried out quite easily) yields the over-all utilisation fo the CPU, denoted by $A_o$.

Let $C_j$ be the average total CPU time required by a class j process between two consecutive visits to the terminals, and suppose that the distribution of that time is exponential. Then, while a class j process is being served by the CPU, it leaves the resource loop to return to the terminals at rate $1/C_j$. Similarly, while a class j process is being served by the CPU, it leaves the resource loop to join the impeded set at rate $1/[(M+1)E_j]$ (it is ejected at the $(M+1)$th page fault). Therefore, in the CPU virtual time of a class j process, the average interval between consecutive departures from the resource loop is

$$(3.6) \qquad Q_j = \left[ \frac{1}{C_j} + \frac{1}{(M+1)E_j} \right]^{-1} = \frac{(M+1)C_j E_j}{C_j + (M+1)E_j}.$$

Intuitively, the proportion of all CPU busy time which is devoted to class j processes can be approximated by

$$(3.7) \qquad q_j = \frac{d_j Q_j}{\sum_{s=1}^{J} d_s Q_s}.$$

Further, the class j processes who have had M page faults occupy approximately a fraction $1/(M+1)$ of that proportion. We therefore set

$$(3.8) \qquad \pi_j^{(N_1, N_2, \dots, N_J)} = q_j A_o$$

$$\pi_j^M(N_1, N_2, \dots, N_J) = q_j A_o / (M+1)$$

The virtue of this approximative method is that it eliminates the very fast proliferation of system states caused by the multiple process classes.
## 3.2 Validation of the approximate solution of the resource loop model

The predictions of the approximate analysis were compared against the simulated performance of a resource loop consisting of a CPU, a paging drum and an I/O device (disk), with two process classes with different characteristics. The simulation experiments were also used to evaluate the following aspect: if some distributions associated with the model are not exponential is the mathematical model a robust predictor of CPU activities for each class ?

The simulation model was programmed with the assumptions of the mathematical model except for service time distributions at paging drum and I/O device which were assumed constant rather than exponential.

Comparison of the theoretical results with simulation is given in Figures 3,4. In these experiments, there are $N_1$ processes with $k_1$, the coefficient of the Belady life-time function equal to 1.8 and $N_2$ processes with $k_2$ equal 1.5; all the other parameters are given on the figures.

Figure 3 displays the probability that the CPU is serving a process of class 1 as a function of $N_1$ for different values of $N_2$. In the case $N_2=0$, the mathematical solution is exact (with exponential assumptions) and the results are very close. In the other cases we see that, except for small values of $N_1+N_2$, the agreement is rather good. When the optimal degree of multiprogramming is obtained for values of $N_1+N_2$ less than 3 or 4, we observe that it is underestimated by the approximate method. Moreover the CPU activities are overestimated below this optimal value and underestimated above it.

Figure 4 shows the same results for class 2; the theoretical results seem to be more accurate than in the case of class 1.

It is possible that the difference in the optimal degrees of multiprogramming is due to the simulation; it is well-known that simulations which do not run long enough to reach the steady-state lead often to values of the utilisation factors which are too small.

On the basis of this validation exercise, it seems that the approximate method yields results which are in good agreement with the observed model behaviour. That method was therefore used in all subsequent numerical computations.
### 3.3 Approximate analysis of the full model with two processes classes

Suppose that there are $K_1$ terminals of class 1 and $K_2$ terminals of class 2, with think times distributed exponentially with means $1/\lambda_1$, and $1/\lambda_2$ respectively. After one level of decomposition, the resource loop can be replaced by a single server which, when in state $(N_1, N_2)$, returns processes of class j to their terminals at rate

$$ (3.9) \qquad \xi_j(N_1, N_2) = \frac{1}{C_j} \pi_j(N_1, N_2) \quad j = 1,2 $$

and it sends processes of class j to the impeded set at rate

$$ \gamma_j(N_1, N_2) = \frac{1}{E_j} \pi_j^M(N_1, N_2), \quad j = 1,2. $$

Let $\beta_j(N_1, N_2)$ be the sum of $\xi_j(N_1, N_2)$ and $\gamma_j(N_1, N_2)$.

The rate $\delta_j$ at which each process of class j is re-injected into the resource loop from the impeded set should, for a balanced system, be in some way proportional to the rate at which the processes leave the resource loop. Here we will set

$$ \delta = h(\beta_1 + \beta_2) $$

The state of the system is defined by the two vectors $(N_1, N_2)$ and $(L_1, L_2)$, where $N_j$ and $L_j$ are the numbers of class j processes in the resource loop and in the impeded set respectively ($j=1,2$). The number of class j processes in "think state" is, of course, $K_j - N_j - L_j$. Those two vectors constitute, under suitable exponential assumptions, a finite-state Markov process whose steady-state distribution can be obtained by solving a system of $(K_1+2) \cdot (K_2+2)$ linear equations, a difficult task for large values of $K_1$ and $K_2$.

If the two process classes have very different lifetime function characteristics, the problem can be simplified by applying another level of decomposition. Suppose that M can be chosen in such a way that processes of one of the classes, say class 2, are ejected from the resource loop much more often than those of the other class. Then, if the resource loop and the impeded set are considered in isolation, with $I_1$ and
$I_2$ processes of class 1 and class 2 circulating among them, it can be assumed that all $I_1$ processes are in the resource loop. The probabilities $P(I_1,N_2|I_1,I_2)$ that there are $N_2$ processes of class 2 in the resource loop, given $I_1$ and $I_2$, ($N_2 = 0,1,...,I_2$) can be obtained by solving an $(I_2+1)$-state Markov process.

Finally, the resource loop and the impeded set are replaced by a single server which, when in state $(I_1,I_2)$, sends processes of class j to the terminals at rate

$$ (3.10) \qquad \zeta_j(I_1, I_2) = \sum_{N_2=0}^{I_2} \beta_j(I_1, N_2) P(I_1, N_2|I_1, I_2), \quad j = 1,2 $$

The system state is now defined by the vector $(I_1,I_2), I_1=0,1,...,K_1; I_2=0,1,...,K_2$. The steady-state distribution of that vector is obtained by solving a system of $(K_1+1) \cdot (K_2+1)$ linear equations. From the joint distribution of $I_1$ and $I_2$ one can compute the marginal distribution of $I_j$ ($j=1,2$) and hence the average number $E[I_j]$ of class j processes in the resource loop and in the impeded set. The average number of class j processes at the terminals is $K_j \cdot E[I_j]$ and therefore the rate at which class j processes leave the terminals is $(K_j \cdot E[I_j])\lambda_j, j=1,2$. An application of Little's formula yields the following expression for the average response time $W_j$ of class j processes :

$$ (3.11) \qquad W_j = \frac{E[I_j]}{(K_j - E[I_j])\lambda_j}, \quad j=1,2. $$

The above computations were carried out to obtain the numerical results in Figures 5,6.

### 3.4 The choice of M

The function of the control parameter M is twofold: first, to present thrashing effectively, and second, to ensure that "good processes"- processes which do not have page faults often- are not ejected from the
resource loop often. To fulfill the first objective M should not be too
large (otherwise there would be no control), and to fulfill the second,
it should not be too small. This trade-off can be assessed by evaluating
the probability $p_j$ that a process of class j is ejected from the resour-
ce loop before it is completed. Under exponential assumptions about
total execution and inter-page fault times, we can write

$$
(3.12) \quad p_j = \left[ \frac{1/E_j}{(1/E_j) + (1/C_j)} \right]^M = \left( \frac{C_j}{C_j + E_j} \right)^M \quad j=1,2.
$$

Suppose that class 1 is "much better" than class 2, i.e. E₁ >> E₂, and
that it is possible to choose M so that C₁ << ME₁ and C₂ >> ME₂. Then we
would have p₁ ~ 0, p₂ ~ 1 and both objectives would be satisfied. If the
difference between the two classes is not so extreme, and it is not
possible to achieve p₁ ~ 0 without at the same time having p₂ ~ 0 (and
hence losing all control), the decision is much less clear-cut. One
way to proceed would be to fix a threshold T > 1 and then choose the
smallest value of M for which (p₁/p₂) > T, if such a value exists. It
should be remembered that if T is close to 1 then the hypothesis on
which our approximation of the full model was based will not hold. That
does not mean, of course, that the control itself will not work ; it
simply will not distinguish between the process classes.
4. DISCUSSION OF THE RESULTS AND CONCLUSIONS

In this paper we have presented a method for controlling the
performance of a virtual memory multiprogramming system based on two
principles : on the one hand one tries to adapt the level of multipro-
gramming by balancing rates of injection of tasks by monitoring the
throughput of the active set and by using a pool of impeded tasks
as an additional source , and on the other hand tasks are eliminated from the
active set as a function of paging activity. The first principle is
similar to the one examined in [ 4 ], while the second principle serves
to create a distinction between processes which disturb the system
and those which can run efficiently with the memory space which has been
allocated to them. This method is particularly simple to implement
because it does not require detailed measurements of program or
system behaviour : departure rates of processes from the active set
and the page fault count of each process are easy to measure and
need a negligible amount of space for storage.

The method we propose has been evaluated using a mathematical
model with two classes of tasks, the main class distinction being based
on the locality of each class represented by Belady's life-time function.
In order to carry out the analysis of the model, we have developed a new
approximate solution method for closed queueing networks with multiple
customer classes, and have validated this approach against simulation
experiments. This solution method has then been combined with the
decomposition method in order to compute the response times for each class
of tasks for a system controlled using the RCP method.

The numerical results shown on Figures 5 and 6 are representative of
the performance which can be expected from a system controlled by the
RCP policy. On Figure 5 we see the effect of the RCP for the "good" class
of processes. These processes have a large value of the locality coefficient
(k₁=1.8). We have plotted the average response time W₁ for this class as
a function of K₁, the total number of process of this class which the system
contains, for different values of K₂ the total number of "bad" processes whose
coefficient of locality is k₂=1.5. Obviously the response time is considerably
smaller than that for the system without control. On the same figure we
have also plotted the response time obtained with a control policy which does
not discriminate between classes : this is the random injection control
approach [4] which differs from the RCP only in the fact that now the processes
are eliminated from the active set on the basis of the total CPU time they
have obtained (i.e. a CPU quantum is used for process elimination). We see
that class 1 receives a very favorable treatment with the RCP. In Figure 6
the roles are now reversed : of course, class 2 receives a better treatment
with the random injection policy, but this effect is only significant when the
total number of processes in the system is high.

From the results obtained for the random injection policy [4] we can
deduce that the performance of the RCP will be close to that obtained
by an "optimal" policy based on maintaining the degree of multiprogramming
at the level which maximizes the throughput of the active set. We can make
this claim because the average response time over all classes for the RCP
is essentially the same as that obtained by the random injection policy.

Several other properties of the RCP remain to be investigated. These
concern essentially its capacity to react rapidly to variations in program
behaviour, as well as to matters concerning the overhead introduced by
the elimination and introduction of processes to the active set. These
problems will be examined in another paper.
References

[1] Badel, M., Gelenbe, E., Leroudier, J., Potier, D., "Adaptive optimisation of a time-sharing system's performance", Proceedings IEEE 63, 958-965 (1975).

[2] Leroudier, J., Thèse de Doctorat d'Etat, Grenoble (1977).

[3] Denning, P., Kahn, K., Leroudier, J., Potier, D., Suri, R., "Optimal multiprogramming", Acta Informatica 7, 197-216 (1976).

[4] Gelenbe, E., Kurinckx, A., "Random injection control of multiprogramming in virtual memory", IEEE Trans. on Software Engineering 4, 2-17 (1978).

[5] Baskett, F., Chandy, K., Muntz, R., Palacios-Gomez, J., "Open, closed, and mixed networks of queues with different classes of customers", Journal ACM 22, 248-260 (1975).

[6] Courtois, P., "Decomposability, instabilities, and saturation in multi-programming systems", Communications ACM 18, 371-377 (1975).
<figure><img src="image_3.png" /><figcaption>**Figure 1.** Structure of a virtual memory multiprogramming system controlled by the rate control policy (RCP).</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 2.** Queueing network model of a multiprogramming system under the effect of the rate control policy (RCP).</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 3</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 4</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 5</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 6</figcaption></figure>