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

HAL
open science

# Random injection control of multiprogramming in virtual memory

Erol Gelenbe, Alain Kurinckx

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

## To cite this version:

Erol Gelenbe, Alain Kurinckx. Random injection control of multiprogramming in virtual memory. [Research Report] IRIA-RR-166, IRIA. 1976, pp.28. hal-04716362

HAL Id: hal-04716362

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

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

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

RANDOM INJECTION CONTROL
OF MULTIPROGRAMMING
IN VIRTUAL MEMORY

E. GELENBE
A. KURINCKX

Rapport de Recherche N° 166

Juin 1976
RANDOM INJECTION CONTROL OF
MULTIPROGRAMMING IN VIRTUAL MEMORY

E. Gelenbe, A. Kurinckx

Résumé :

Nous proposons une nouvelle méthode de contrôle de la multiprogrammation d'un système à mémoire virtuelle. Un modèle mathématique d'un système géré par cette méthode est résolu à l'aide de la méthode de décomposition. Des expériences de simulation permettent de vérifier les prédictions du modèle et de comparer la méthode proposée avec le contrôle «optimal» et avec le comportement d'un système sans contrôle.

Abstract :

We propose a new method for the control of a multiprogrammed virtual memory computer system. A mathematical model solved by decomposition permits to justify that the method avoids thrashing. Simulation experiments are used to test the robustness of the predictions of the mathematical model when certain simplifying assumptions are relaxed and when a slightly simpler control technique based on the same principle is used. Comparisons are given with case when an «optimal» control is used and with that with no control.
# I - INTRODUCTION

It is well-known that virtual memory computer systems exhibit an inherently unstable behaviour if processes are allowed into the common memory with no control : [2] is an early analysis of the subject and [3] provides a theoretical explanation. This instability translates itself in practice by a system throughput which becomes close to zero and very high turnaround or response times. The analysis in [3] provides an indication of how system control to avoid this effect can be used : it suffices to limit the multiprogramming degree N (defined as the number of processes allowed to share main memory) to a value below N' such that θ(N'), the system throughput for this value of N, is still at an acceptable level, where θ(N) is predicted to have the form shown on Figure 1(b). Some of the results in [3] have been summarized in [4].

Using a mathematical and simulation model [6] developed to predict the throughput θ(N) of a virtual memory paged computer system, the problem of its feedback regulation so as to (i) avoid thrashing, and (ii) optimize its performance had been examined in [7]. Since the parameters of active processes such as paging rates for a given memory allocation, input-output rates, total CPU execution times, are necessarily time-varying, the approach used was an adaptive optimization algorithm. In view of the fact that characteristic of Figure 1(b) will vary with time, the algorithm in [7] to maintain the degree of multiprogramming close to its optimal value N₀ is a statistical maximum searching technique. This approach leads to a relatively elaborate estimation procedure.

A comprehensive review of the issues of virtual memory performance and control is given in [8], and [9, 10] contain suggestions and evaluations of heuristic control policies.

In this paper we investigate a new technique for virtual memory system management which calls for less information gathering than that of [7] : it does not necessitate an instantaneous estimate of N₀, the optimal
degree of multiprogramming but only an estimate of the throughput. An alleviation of supervisor functions and a greater possibility for decentralized management are potential advantages. This method avoids thrashing and operates the system close to optimum; it is not "optimal" however in the sense of the policy developed in [7].

In Section 2 a description of the method we propose and an approximate analysis are given. Section 3 is devoted to the presentation of simulation experiments showing the effectiveness of our approach and its comparison with the optimal control.

## 1.1 - Random injection control

Consider the idealized queueing network representation of the virtual memory system of Figure 2(a). A set of terminals $T_1, ..., T_L$ generate processes and these are immediately accepted into the CPU queue. Processes which are either in the CPU queue or in that of one or more of the peripheral or secondary memory unit queues $P_1, ..., P_n$ are allowed to acquire main memory. Assuming a demand-paging operation, main memory space will be acquired by an incoming process in an alternating sequence of page faults and CPU executions. When it has acquired a total of Q units of CPU execution time the process is placed in the set I of *impeded* processes and liberates the main memory space it occupied. For each impeded process a time interval is drawn at the end of which the process will be injected back into the active set, i.e. into the set of processes which share memory and other system resources. This time interval of duration $\tau$ will be chosen as a function of system parameters, and more particularly as a function of the throughput rate of the set of useful resources of the system (the "resource loop" of Figure 2(a)). Thus, in a way, the *impeded set of processes can be viewed as being in an artificial "think" state which is analogous to the "think" state of processes at terminals*. Though this is not necessary, we shall assume that $\tau$ is a random variable so that our control scheme is called *random injection control*.
## 2 - DESCRIPTION AND ANALYSIS OF THE PROPOSED CONTROL POLICY

The aim of this section is to present and justify the random injection control method for virtual memory computer systems.

We will first present a mathematical model which is used as a framework for justifying and evaluating the approach; this model is not new [6] and has already been used in [7] to evaluate an adaptive control policy for optimizing a virtual memory system. Then, the random injection policy will be described. It will be analyzed in two parts. We first use approximate analysis using the decomposition method [3, 5] to show how random injection control avoids thrashing. Then simulations will be used to confirm these results and to show that it yields system performance comparable to that of an "optimal" control policy.

### 2.1 - The mathematical model

In the system of Figure 2(a) a total of L processes are either in *think* state at one of the terminals, or they are in *impeded* state (at I in Figure 2(a) or in the CPU queue or at one of the I/O devices $P_1, ..., P_n$). We shall model the system under the following assumptions:

- the time spent in *think* state by a process before entering or re-entering the CPU queue is exponentially distributed of parameter $\lambda$.

- service at $P_i$ is allocated on a first-come-first served basis; consecutive service times are i.i.d. (independent and identically distributed) random variables, exponentially distributed of parameter $\mu_i$.

- as in [6, 7] the relationship between allocated primary memory space $m$ and page-faulting behaviour of a process is established via the Belady-Kuehner life-time function $e(m)$ [1] shown in Figure 1(a) and the following model. In process time, the consecutive inter page-fault intervals of a process are i.i.d. exponential random variables of parameter $[e(m)]^{-1}$.
Similarly the consecutive I/O inter-request intervals to device $P_i$ ($2 \le i \le n$, where $P_i$ is the paging drum) is exponentially distributed of expectation $a_i$. Furthermore the total CPU execution time of a process between two terminal interaction is exponential of expectation $C$, and the total CPU execution time between two consecutive epochs it spends in the impeded state is exponential of expectation $Q$. Under these assumptions it is easily shown [6] that an uninterrupted execution interval of a process at the CPU is exponentially distributed of parameter $\alpha = [(e(m))^{-1} + \sum_{2}^{n}(a_i)^{-1} + C^{-1} + Q^{-1}]$. At the end of such an epoch, it can be shown [6] that the process directs itself with probability :

$$ - x_1 = (\alpha e(m))^{-1} \quad , \quad \text{to } P_1 $$

$$ - x_i = (\alpha a_i)^{-1} \quad , \quad \text{to } P_i, 2 \le i \le n $$

$$ - x_{n+1} = (\alpha Q)^{-1} \quad , \quad \text{into the impeded set} $$

$$ - x_{n+2} = (\alpha C)^{-1} \quad , \quad \text{to its terminal} $$

- total primary memory space is R

- the time $\tau$ spent in impeded state by a process is exponentially distributed of parameter $\delta$.

**Remark 1** : If the terminals and the impeded set were non-existent in Figure 2, and if $N$ is the total number of processes in the system circulating among the CPU and the peripheral devices, then the curve of Figure 1(b) is representative of the CPU utilization at statistical equilibrium as a function of $N$.

**Remark 2** : As stated in Section 1.1, the value of $N$ (the degree of multiprogramming) is the sum of the number of processes which are either in the CPU queue or in the peripheral device queues $P_1, \dots, P_n$. Thus the process in *think* or *impeded* states do not share memory. Also, in our mathematical model, all processes are statistically identical and share main memory
equally ; thus $m = R/N$.

**Remark 3** : In the simulation results given in Section 3 the service times at the peripheral devices are not exponential, and neither is the total CPU execution time of a process between two successive visits to the impeded state. Comparison between theoretical and simulation results will illustrate the robustness of the exponential assumptions (see also [6, 7] concerning this point).

- for the life-time function $e(m)$, we will use the usual form $e(m) = dm^k$ where $d$ and $k$ are constants. This particular form does not affect the theoretical analysis but simply the numerical results obtained.

## 2.2 - The random injection policy

The random injection policy for virtual memory management operates on the following principles. Some of these principles have already been given as assumptions of the model in previous sections, we repeat them here for clarity.

P1 - Only the processes which are either in the CPU queue or in the queues of devices $P_1, \dots, P_n$ share memory. As soon as a process enters the impeded set or leaves the CPU queue in order to return to the *think* state at a terminal, its main memory pages become available for other processes.

P2 - A process entering the *impeded* state will remain there for a *random time* duration function of N the degree of multiprogramming and of (M-N) the number of processes in impeded state where M is the total number of processes which are not in *think* state. At the end of this time the process joins the CPU queue. This random time is exponentially distributed of parameter $\hat{\delta}(N,t)$ which is time dependent. In our policy we set
$$ (1) \qquad \hat{\delta}(N,t) = \begin{cases} B \text{ constant, } N = 0 \\ h\hat{\beta}(N,t), & N > 1 \end{cases} $$

where h is a constant to be determined below, and $\hat{\beta}(N,t)$ Δt is the probability that in (t, t+Δt) a process leaves the resource loop to enter either the **impeded** or the **think** state. The constant B in (1) will be taken to be very large (B = ∞, for all practical purposes) since when N=0 there is no reason to retain a process in the impeded set (i.e. its entry and exit are simultaneous).

## 2.3 - Analysis of the random injection policy

In this section we shall present the equations governing the mathematical model of the virtual memory system controlled by the random injection policy. Only the equilibrium equations will be solved. It will be noticed that the exact solution to these equations is not known. Therefore an approximate solution based on the decomposition method of COURTOIS [3, 5] will be presented.

### 2.3.1 - The equations for the model

Consider the stochastic process {$V_t^i$}$_{t \in R^+$} represent the number of processes at the CPU queue if i=0, or at the queue of $P_i$ if $1 \le i \le n$, or in **impeded** state if i = n+1, and in **think** state (at the terminals) if n = n+2. We are interested in the joint probability distribution, for $t \ge 0$,

$$ p(v,t) = \Pr\{V_t^0 = v_1, \dots, V_t^{n+2} = v_{n+2} | V_0^0, \dots, V_0^{n+2}\} $$

where $v = (v_0, \dots, v_{n+2})$ is a vector of integers $0 \le v_i \le L$, $i = 1, \dots, n+2$ ($L$ is the total number of terminals and of user processes in the model). Under our assumptions the $p(v,t)$ satisfy the following system of differential difference equations :
$$ (2) \quad \frac{d}{dt} p(v,t) = -[(L-M)\lambda + \sum_{i=1}^{n} \mu_i + \alpha(N) + D(v)] p(v,t) \\ + (L-M+1)\lambda p(c(v,0,n+2),t) \\ + \sum_{i=1}^{n} \mu_i p(c(v,0,i),t) \\ + \sum_{i=1}^{n+2} (a_i)^{-1} p(c(v,i,0),t) \\ + D(c(v,0,n+1)) p(c(v,0,n+1),t) $$

where $a_{n+1} = Q$, $a_{n+2} = C$, $a_1 = e(m)$, and for any vector v we define

$$ (3) \quad c(v,i,j) = (v_0, \dots, v_{i-1}, \dots, v_j+1, \dots, v_{n+2}) $$

and in (2) any $p(\hat{v},t)$ such that $\hat{v}$ contains an element which is negative or larger than L is set to $p(\hat{v},t) = 0$ for all $t \ge 0$. Also we take $D(v) = 0$ if the $(n+1)$-th component of v is zero (i.e. $v_{n+1} = 0$). These conditions, together with the assumption that $\mu_i = 0$ in (2) if $v_i = 0$, suffice to define the boundary conditions of (2). Finally, notice that :

$$ L = \sum_{0}^{n+2} v_i, \quad M = \sum_{0}^{n+1} v_i, \quad N = \sum_{0}^{n} v_i $$

$D(v)$ is the arrival rate of processes from the impeded set to the CPU queue :

$$ (4) \quad D(v) = (M-N) \hat{\delta}(N,t) $$

This system of differential difference equations will possess an unique solution $p(v,t) > 0$ such that $\sum_v p(v,t) = 1, t \ge 0$, if all the state transition rates are positive and finite. However the available theory [11] does not provide the equilibrium solution. In the following section we resort to an approximate solution method.
### 2.3.2 - Approximate solution via decomposition

The approximate analysis technique for queueing networks developed in [3, 5] is suited to systems composed of subsystems where the time constants of inter-subsystem interactions are appreciably larger than those associated with interaction within each subsystem. This makes it possible to use equilibrium results for each subsystem in the global system model.

In our analysis we apply the technique several times to our model. These successive simplifications are shown on Figures 3(a) and 3(b), for the model of Figure 2(a).

As a first step we will approximate the system of Figure 2(a) by the model shown on Figure 3(a). Let $\hat{\beta}(N,t)\Delta t$ be the probability that a process leaves the resource loop to enter either the *impeded* or *think* state in the interval $(t, t+\Delta t)$ when the number of processes in the resource loop is N. We may write

$$ \hat{\beta}(N,t) = [x_{n+1}(N) + x_{n+2}(N)] \alpha(N) A(N,t) $$

where $A(N,t)$ is the probability that the CPU is not idle when there are N processes in the resource loop at time t. The approximation consists of replacing $A(N,t)$ by $A_0(N)$:

$$ (5) \qquad \hat{\beta}(N,t) \approx \beta(N) = [x_{n+1}(N) + x_{n+2}(N)]\alpha(N) A_0(N) $$

where $A_0(N)$ is the stationary probability that the CPU queue in the closed model of Figure 2(b) (i.e. the resource loop with N processes, and with no interactions with the terminals or with the impeded set) is not empty. This approximation will be valid [3, 5] if for $1 \le i \le n$,

$$ (6) \qquad \alpha(N)[x_{n+1}(N) + x_{n+2}(N)] \ll \mu_i \\ h\beta(N) \ll \mu_i, \quad h\beta(N) \ll \alpha(N)x_i(N) \\ \lambda(L-M) \ll \mu_i, \quad \lambda(L-M) \ll \alpha(N)x_i(N) $$
and if

$$ (7) \quad x_{n+1}(N) + x_{n+2}(N) \ll x_i(N), \quad 1 \le i \le n. $$

The second step is to approximate the model of Figure 3(a) by that of Figure 3(b) : the impeded set and the resource loop are replaced by a single server of service rate $\gamma(M)$ where M is the total number of processes in the system to the exception of those present at the terminals. By arguments similar to those yielding (5), we approximate $\hat{\gamma}(M,t)\Delta t$, the probability that a process returns to its terminal in $(t,t+\Delta t)$, by $\gamma(M)\Delta t$ where the approximation is valid if

$$ (8) \quad \lambda(L-M) \ll \delta(N), \quad x_{n+1}(N) \gg x_{n+2}(N), \quad \lambda(L-M) \ll \frac{x_{n+1}(N)}{x_{n+1}(N) + x_{n+2}(N)} \quad \beta(N) $$

$\gamma(M)$ is given by

$$ (9) \quad \gamma(M) = \sum_{N=1}^{M} \frac{x_{n+2}}{x_{n+1} + x_{n+2}} \quad \beta(N) \ p(N/M) $$

where $p(N/M)$ is the stationary probability of having N processes in the resource loop given that there are M processes in either the impeded set or in the resource loop supposing no interaction with the terminals for the subsystem of Figure 3(c).

After some computations, given in the Appendix, we obtain the expression

$$ (10) \quad \gamma(M) = \left( \sum_{N=1}^{M} \frac{h^{N-1}}{A_O(N)(M-N)!} \right)^{-1} \sum_{N=1}^{M} \frac{h^{N-1}}{(M-N)!} $$

On Figure 4 we present some numerical values for $\gamma(M)$ as a function of M, h and of k (the exponent in the Belady life-time function in (3)). Here $n=2$ (there are two peripheral units), and the parameter values used are given on the figure.

If k is small, i.e. when the effectiveness of the control is important, we see that for well-chosen values of h, $\gamma(M)$ does not vary appreciably as M increases which is the property we desire. However a more
practical approach to understanding the effect of the random injection policy is to compare $\gamma(M)$ to the throughput of the resource loop $\beta^*(N)$ when the control is not applied where

$$ \beta^*(N) \approx x_{n+2}(N) \alpha(N) A_0(N) $$

The comparison is given on Figure 5. However when $k$ is relatively large (e.g. $k = 2.5$, on Figure 6) the system with no control has a better performance than the controlled system. The influence of the parameter $h$ will be seen in the simulation experiments (Section 3) where it is evident that as long as $h$ is sufficiently small, it can vary by an order of magnitude without affecting sensibly the behaviour of the controlled system.

Notice that in the theoretical model examined above the value of $Q$ has no effect.

## 3 - THE SIMULATION EXPERIMENTS

The theoretical analysis using the decomposition technique is a first-order approximation [5] when the inequalities (6) - (8) are satisfied. Thus it has to be verified whether the approximation is sufficiently good in the context of our model.

However the purpose of the simulation experiments we have conducted is not restricted to this point. We also use them to evaluate the following aspects :

- If the random injection control is not based on a continuous estimation of $\beta(N,t)$ does its effect still remain valid ?

- If the main distributions associated with the model are not exponential, is the mathematical model a robust predictor of system performance ?

The simulations will allow us to give affirmative replies to these two questions and also to investigate the effect of certain model parameters such as $h$ or $Q$. We shall also compare the random injection control to the optimum control obtained by limiting the degree of multiprogramming.
## 3.1 - Description of the simulator

The simulation model has been programmed with the following assumptions :

- The simulator corresponds to the system of Figure 3(a), where the value of $A_0(N)$ necessary to the computation of $\beta(N)$ is obtained by a separate simulator in which the service time at each peripheral device ($P_1$ and $P_2$) is constant (rather than exponential as in the mathematical model).

- In the simulation the total execution time of each process is constant (rather than exponential) of value $C$, and so is the execution time $Q$ after which a process is placed into the *impeded* set.

- The random injection control in the simulator differs from that in the mathematical model. Since in practice it may be difficult to set $\hat{\delta}(N,t) = h\beta(N,t)$ at all times $t$, we have chosen to take a relatively unfavorable value for $\delta(N,t)$ in the simulator. If a process enters the impeded set at a time $t'$ when the value of the degree of multiprogramming was $N_{t'}$, we allow it to remain in the impeded set for a random duration exponentially distributed of parameter $h\beta(N_{t'})$; thus the parameter used is not fully "up-to-date".

## 3.2 - Confidence interval computations

For the computation of confidence intervals associated with the measurements made in the simulations we have used the classical method [12,13] of subdividing the measurements into contiguous blocks such that the average values over each block of the parameter value are very weakly correlated. The block length chosen is of 25 measurements. However we have also computed confidence intervals without this scheme and the results are appreciably the same<fnref n="1" />).

<footnote n="1">1) Though the purpose of our paper is not to comment on simulation methodology, we were not surprised by the identity of these results because of known properties of asymptotic normality of certain functions associated with Markov processes [14].</footnote>
Although the primary performance measure which we are interested in is the average response time of a user, we do not give these measurements directly. In fact we observed that the confidence intervals associated with response time when directly measured were very large because of the relatively small number of samples. Therefore we measure the average number of processes which are *not* at the terminals as well as the related confidence interval, and the arrival rate of processes from the terminals. We then use these quantities in Little's formula $W.λ(L - E{M}) = E{M}$ in order to compute the estimated average response time $\hat{W} = \hat{M}/λ(L - \hat{M})$. The confidence interval of $\hat{W}$, ($W_1, W_2$) is obtained as follows : $W_1 = M_1/λ(L - M_1)$ and $W_2 = M_2/λ(L - M_2)$, where $\hat{M}$ is the estimated value of $E{M}$ and ($M_1, M_2$) is the corresponding confidence interval.

### 3.3 - The simulation results

Comparison of the theoretical results developed in Section 2 with the simulations is given in Figures 7, 8, 9.

We see that except for large values of L the agreement is very good notwithstanding the important differences between the theoretical model and the simulation. It is important to note that the 95 % confidence intervals are much larger for small k (Figure 7) than for larger values of k (Figures 8, 9) and the sensitivity of the confidence intervals to k is very large. On the other hand the sensitivity of the model to the *distribution* of the time spent in the impeded set is very small : on Figure 8 a constant time is compared with an exponentially distributed time spent in impeded state.

## 4 - CONCLUSION

In this paper we have proposed a new method for the control of multiprogramming in a virtual memory system. The method has been justified using a mathematical model. A simulation model in which most probability distributions associated with the mathematical model have been modified so then used to test the control scheme and the robustness of the model predictions.
Our results prove the interest of the random injection control policy for virtual memory systems. Of course, adaptive control procedures are valid only if the system overhead associated with the control is not unacceptably high. In a follow-up paper [14] we will examine the effect of overhead ; we shall also introduce and analyze an *optimal* random injection control and present a statistical algorithm to implement it.

The theory predicts that $Q$, as we have chosen it, will have no
effect on the average response time of the system ; the simulations (see
Figure 10) confirm that its effect is not significant on the *average*
response time. Of course it will have an effect, similar to that of the
quantum of a time-sharing discipline, on the response time of processes
having longer or shorter execution time. In practice, one would use a
smaller value of $Q$ for those processes which have a high page fault rate
and a larger $Q$ for those which have fewer page faults ; this point will be
discussed in [14].

On Figure 11 we have used simulation experiments to evaluate the
effect of $h$. These results confirm the numerical predictions (see Figure 4).
The small values of $h$ are worse when $L$ is small, since there we need little
if any control of multiprogramming. The best value lies around $h = 0.01$ for
large values of $L$, as indicated by the simulations (Figure 10) and the
numerical studies (Figure 4).
# APPENDIX

Outlined here are the details of the derivation of the resulting equivalent server (7). $\gamma(M)$ is given by

$$ (A1) \qquad \gamma(M) = \sum_{N=1}^{M} \frac{x_{n+1}}{x_{n+1} + x_{n+2}} \quad \beta(N) p(N/M) $$

Recall that $p(N/M)$ is the steady state probability of having N processes in the resource loop given that there are M processes in either the impeded set or in the resource loop. We obtain this probability by solving the equilibrium equations for the system of figure 3(c).

$$ (A2) \qquad \begin{aligned} p(N/M) [\beta(N) + \delta(N) (M-N)] = & p(N+1/M) \beta(N+1) \\ & + p(N-1/M) \delta(N) (M-N+1), \quad 1 \le N < M \end{aligned} $$

$$ p(1/M) \beta(1) = p(0/M) \delta(0)M $$

$$ p(M/M) \beta(M) = p(M-1/M) \delta(M-1) $$

The solution of these equations is

$$ (A3) \qquad p(N/M) = p(0/M) = \frac{\prod_{i=0}^{N-1} \delta(i) (M-i)}{\prod_{i=1}^{N} \beta(i)} \quad 0 \le N \le M $$

and we obtain $p(0/M)$ by using the condition

$$ \sum_{N=0}^{M} p(N/M) = 1 $$

This yields the result :

$$ (A4) \qquad p(0/M) = \left[ \sum_{N=1}^{M} \frac{\prod_{i=0}^{N-1} \delta(i) (M-i)}{\prod_{i=1}^{N} \beta(i)} + 1 \right]^{-1} $$

Using this value, and (1), expressions (A2) and (A3) become
$$ (A5) \qquad p(N/M) = p(O/M) \frac{h^{N-1} B}{(N) \prod_{i=0}^{N-1} (M-i)} \quad 1 \le N \le M $$

$$ p(O/M) = \left[ \sum_{N=1}^{M} \frac{h^{N-1} B}{\beta(N) \prod_{i=0}^{N-1} (M-i) + 1} \right]^{-1} $$

and replace $p(N/M)$ by its value in (A1) :

$$ (A6) \qquad \gamma(M) = B \rho(O/M) M! \sum_{N=1}^{M} \frac{x_{n+1}}{x_{n+2} + x_{n+1}} \frac{h^{N-1}}{(M-N)!} $$

$$ p(O/M) = \left(1 + B N! \sum_{N=1}^{M} \frac{h^{N-1}}{\beta(N) (M-N)!}\right)^{-1} $$

We know that

$$ \frac{x_{n+1}}{x_{n+2} + x_{n+1}} = \frac{1/C}{1/C + 1/Q} $$

Let $B$ tend to infinity. The limit of (A6) is

$$ \lim_{B \to \infty} \gamma(N) = 1/C \sum_{N=1}^{M} \frac{h^{N-1} (M-N)!}{A_0(N) (M-N)!} $$

which is the expression given in (7).

Notice that we set $B \to \infty$ (as mentioned in the discussion following equation (1)) to represent the fact that when $N=0$, no time is spent by processes in the impeded set.
<figure><img src="image_5.png" /><figcaption>figure 1(a)</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>figure 1(b)</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>figure 2(a)</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>figure 2(b)
Resource loop</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>figure 3(a)</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>figure 3(b)</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>figure 3(c)</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>figure 4</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>figure 5</figcaption></figure>
Average processing rate in
$10^{-2}$/seconds

$k = 2.5$

For other parameter values, see fig. 4

<figure><img src="image_14.png" /><figcaption>figure 6</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>figure 7</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>figure 8</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>figure 9</figcaption></figure>
Average Response Time W
 seconds)

Simulation results (without confidence intervals)
Influence of Q

k = 1.5

For other parameter values, see fig. 4

<figure><img src="image_18.png" /><figcaption>figure 10</figcaption></figure>

Number of
Terminals
<figure><img src="image_19.png" /><figcaption>figure 11</figcaption></figure>
[ 1 ] L. BELADY, C.J. KUEHNER, "Dynamic Space Sharing in Computer Systems", CACM 12, 5, May 1969, 282-288.

[ 2 ] P. DENNING, "Thrashing : Its Causes and Prevention", Proc. AFIPS 68, Fall Joint Comput. Conf., 33, 915-922.

[ 3 ] P.J. COURTOIS, "On the Near Complete Decomposability of Networks of Queues and of Stochastic Models of Multiprogramming Systems", Carnegie-Mellon University, Computer Science Department, Research Report, November 1971.

[ 4 ] P.J. COURTOIS, "Decomposability, Instabilities, and Saturation in Multiprogramming Systems", CACM 18, 7, July 1975, 371-377.

[ 5 ] P.J. COURTOIS, "Error Analysis in Nearly-completely Decomposable Stochastic Systems", Econometrica, 43, 4, July 1975, 691-709.

[ 6 ] A. BRANDWAJN, J. BUZEN, E. GELENBE, D. POTIER, "A Model of Performance for Virtual Memory Systems", Proc. ACM-SIGMETRICS Symposium, Montreal, September 1974, to appear in IEEE Trans. Software Engineering.

[ 7 ] M. BADEL, E. GELENBE, J. LERLOUDIER, D. POTIER, "Adaptive Optimization of a Virtual Memory System", Proc. IEEE, Special Issue on Interactive Systems, June 1975.

[ 8 ] P. DENNING, S. GRAHAM, "Multiprogrammed Memory Management", Proc. IEEE, Special Issue on Interactive Systems, June 1975.

[ 9 ] P. DENNING, S. GRAHAM, "Multiprogramming and Program Behaviour", Proc. ACM-SIGMETRICS, 3, 4, September 1974.

[10] J. LERLOUDIER, D. POTIER, "Principles of Optimality for Multiprogramming", Intern. Symp. on Computer Performance, Modelling, Measurements, Evaluation, Harvard, March 29, 1976.

[11] E. GELENBE, R.R. MUNTZ, "Exact and Approximate Solutions to Probabilistic Models of Computer System Behaviour - Part I", to appear in Acta Informatica.

[12] J. LERLOUDIER, M. PARENT, "Quelques aspects de la modélisation des systèmes informatiques par simulation a évenements discrets", RAIRO. Informatique, Vol. 10, n° 1, Janvier 1976, p.5 à 26.

[13] R.W. CONWAY, "Some Tactical Problems in Digital Simulation", Management Sciences, 10, 1, October 1963.

[14] P. LE GALL, "Convergence des Simulations et Application aux Réseaux Téléphoniques", AFIRO monographies de recherche opérationnelle, 7, 1968.

[15] E. GELENBE, A. KURINCKX, "Optimal and Sub-optimal Random Injection Control of Multiprogramming", in preparation.