# Comparaison of static and dynamic allocation in a paged system

Geneviève Jomier

► To cite this version:

Geneviève Jomier. Comparaison of static and dynamic allocation in a paged system. [Research Report] IRIA-RR-296, IRIA. 1978, pp.23. hal-04716527

HAL Id: hal-04716527

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

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

COMPARISON OF
STATIC AND DYNAMIC
ALLOCATION IN
A PAGED SYSTEM

Geneviève JOMIER

Rapport de Recherche N° 296

Mai 1978
COMPARISON OF STATIC DYNAMIC ALLOCATION IN A PAGED SYSTEM

Geneviève Jomier*

Résumé :

Le but de ce travail est la comparaison de deux politiques d'allocation de la mémoire centrale dans un système de multiprogrammation paginé.

Dans «l'allocation statique» un processus n'est admis au partage de la mémoire que si on peut lui attribuer tout l'espace mémoire qui lui est nécessaire. Dans l'allocation dynamique, la mémoire est gérée en page à la demande et l'allocation de chaque processus évolue dans le temps.

Le système est modélisé par un réseau de files d'attente. Sa solution analytique permet de compa-
rer les temps de réponse des processus dans les deux cas en fonction de la taille des processus, de
leurs propriétés de localité et des taux d'échange mémoire centrale-mémoire secondaire.

Abstract :

The aim of this paper is the comparison of two different memory allocation policies in a multipro-
grammed system with a paged memory.

In the «static memory allocation» the central memory space needed is allocated to each process, when it is scheduled. In the «dynamic memory allocation» every process admitted to share the central memory sees the memory space allocated to it varies with time according to a page on demand strategy.

We use networks of queues to model the two policies. The analytical solution of these networks allows us to compare the mean response times as a function of the locality properties, the size and the rate of exchanges between central and secondary memory of the processes.
# I. Introduction.

The multiprogrammed systems performances depends on the multiprogramming degree CPU utilization (cf. Fig. 2 and 4).

This fundamental parameter is modified by the scheduler which introduces or not new processes candidate for execution in central memory. This introduction is function of the memory allocation policy in the system.

The study of different memory allocation policies may be done by modeling such systems by queueing networks composed of a queue (scheduler) and a resource loop network, in tandem (cf. Fig. 1 and 3). Processes circulate in resource loop when they are admitted to share memory.

Service time of scheduler queue will depend on the number and characteristics of the processes present in the resource loop. This condition does not allow us to obtain strict analytical solutions using Jackson or BCMP's theorem [Jac.63, BCMP.75].

Even exact numerical solutions, as proposed by Stewart [Ste.77], using a Markov chain describing the network behaviour cannot be used, because we have to many network states, and particularly to many non null state transitions.

So we must approximate and rather than numerical approximate solutions using iterative methods, as Chandy-Hezog and Woo developed [Chu.75-2], we prefered a method based on Courtois's decomposability [Cou.77] which permits to obtain analytical approximate results.
## II. The static memory allocation.

In the static memory allocation system every scheduled process has at its disposal the whole memory space necessary for it until the end of its execution.

We will be interested by memory space availability and not by contiguity or fragmentation problems in central memory, which are supposed solved by the paging system.

### 2.1. Presentation.

We model the static memory allocation system by the queueing network drawn on Figure 1.

It is composed of one queue corresponding to the scheduler followed by the "resource loop" network which has K queues corresponding to central processing unit, secondary memory and K-2 input/output units.

When a process enters the system it is queued in the scheduler queue, waiting for its share of memory.

A process is admitted to share memory when it may be allocated all the resources necessary for its execution, and in particular central memory space. It will then leave the scheduler queue and enter the resource loop for execution. It begins its execution in the system by entering the secondary memory queue, waiting for a transfer to central memory. Then, when it is present in central memory, it leaves the secondary memory queue and arrives at the central processing unit queue.

The execution of a process at the CPU may be interrupted by :

- the end of the process : it leaves the system and frees its allocated resources.
- a service demand to secondary memory (transfer demand of system or of user modules necessary for process execution). Then the process leaves the CPU and enters the secondary memory queue.

- an input/output demand : in this case the process joins an input/output unit queue.

## 2.2. The model parameters.

### 1.2.1. The scheduler queue.

The stochastic process of system arrivals, which enter the scheduler queue, is supposed to be Poisson of rate $\lambda$.

We call $P$ the number of processes present in this queue, which is served in first-in-first-out order.

A process passes from scheduler queue to the resource-loop when all the resources necessary may be allocated to it : this occurs after a process departure from the resource loop (end of execution) or after an arrival to the scheduler queue.

Let $R$ be the vector of total system resources available for the user processes :

$$R = (R_1, \dots, R_\ell)$$

where $R_i$ is the number of units of resource i (e.g. $R_1$ is the number of memory pages, $R_2$ is the number of disk quantas, etc.). We shall denote by

$$D^k = (D_1^k, \dots, D_\ell^k)$$

the vector of resource demand of the k-th process; i.e. the k-th process needs $D_i^k$ units of resource i, $1 \le i \le \ell$, for its execution in the resource loop. We shall assume that the $D_i^k$ are independent and identically distributed random vectors : the processes are mutually independent from the point of view of their resource needs, and are statistically identical. Therefore we drop the index k. Let $r = (r_1, \dots, r_\ell)$ be a vector of positive integers. We shall note
$$ \Pi(r) = P[D_1 = r_1, D_2 = r_2, \dots, D_\ell = r_\ell] $$

the probability that a process demand vector has the value r.

Thus the probability that n processes can be simultaneously present in the resource-loop is

$$ \Pi_n = \sum_{r \le R} \Pi^{*n}(r) $$

where $\Pi^{*n}(r)$ is the n-th convolution power of $\Pi(r)$.

In our computation we will only consider the resource limitation on the central memory (i.e. $\ell = 1$ : only one resource is considered), which is generally the most critical resource, but it would be easy to introduce limitations on tape units or disk space etc.

### 2.2.2. The resource loop.

The resource loop model is a central server type queueing network [Gel. 73]. Let $\mu_o^{-1}$ be the average uninterrupted execution interval at the CPU and let $p_o$ be the probability that a process leaves the resource loop at the end of such an interval because its total execution time is completed. The rate at which this will occur is $1/c$, where c is the average total execution time of a process. Therefore

$$ \mu_o p_o = 1/c $$

Similarly if $p_1$ (respectively $p_i$) is the probability that a process leaves the CPU queue at the end of an uninterrupted execution interval to go to the secondary memory queue (respectively input/output unit i); the rate of occurrence of this event is $1/e$ (respectively $1/x_i$) where e is the average execution time between two successive calls for secondary memory services (respectively input-output unit services) for a process. Then we have

$$ \mu_o p_1 = \frac{1}{e} \quad \text{and} \quad \mu_o p_i = \frac{1}{x_i} \quad i=2, \dots, K $$
$$
\begin{array}{ll}
\text{These yield} & \mu_o = \frac{1}{c} + \frac{1}{e} + \sum_{i=2}^{K} \frac{1}{x_i} \\
\text{since} & \sum_{i=0}^{K} p_i = 1
\end{array}
$$

The service time distributions are supposed exponential of para-
meter $\mu_o$ for the CPU, $\mu_1$ for the .secondary memory, and of .parameter $\mu_i$
for the input/output unit i, i=2,...,K, where $\mu_i$, i=1,...,K are determined
by the characteristics of the devices, used in the system.

All the different queues of this system model are supposed to be
served in first-in-first-out order.

2.3. The solution method :

We use Courtois' decomposition method to solve the system model

[CoU. 71].

It allows us to consider the resource loop as an equivalent server,
when c is large compared to e and $x_i$. We may calculate the utilization
$A_o(n)$ of this equivalent server using Gordon and Newell's theorem
[G. N.67] where n is the users' number in the resource loop, i.e. the multi-
programming degree.

We may then study our system as the server equivalent to the resource
loop preceded by the scheduler queue which controls the multiprogramming
degree n.

In this method we consider that our system is represented by one
queue.

- the length of which is equal to N = n+p, sum of the number of jobs in
the resource loop and at the scheduler.

- the arrival process is the Poisson process of system arrivals with rate $\lambda$.

- service is first-in-first-out.

Analysis of the service time :

a) When every process arriving to the system is supposed to enter
immediatly into central memory (that supposes infinite memory
size), the utilization rate $A_o(n)$ of the equivalent server looks
like the solid curve of Figure 2.
b) When a deterministic control of the multi-programming degree is introduced [Cou.75], which limits n to a maximum value m, the utilization rate of the equivalent server is changed to $A'_o(N)$ where

$$A'_{o}(N, m) = \begin{cases} A_{o}(N) & \text{if } N \le m \\ A_{o}(m) & \text{if } N > m \end{cases}$$

(Figure 2, dashed curve).

c) In our case the maximum multiprogramming degree m is a random variable and $P[m=n] = \prod_n$, due to our policy of central memory allocation. Then the utilization rate of the equivalent server is chosen as

$$\alpha_o(N) = \sum_{n \ge 0} \prod_n A'_o(N, n)$$

Consequently the service time of the queue equivalent to our static allocation system has a service rate

$$\mu_o(N) = \alpha_o(N) \times \frac{1}{c}$$

where N is the total number of users present in the system.

The approximation of the system used in our model of static memory allocation comes to consider that each time a process leaves the system the whole content of the central memory is reexamined and the number of processes present in central memory determined according to the probability distribution of the central memory space size required.

Another suitable representation would have been to consider only the memory space freed by the process leaving the system and to compare it with the memory allocation demanded by the next candidate to the entry in resource loop. But we think that the approximation we made which permits an easy analytical solution has little incidence on our results, though this point requires further analysis.
# III. The dynamic memory allocation system.

## 3.1. Presentation.

The static memory allocation system is to be compared with a virtual
memory system with page-on-demand strategy modelled by the queueing network
model of Figure 3.

As in II we use the concept of an equivalent server to consider only
three queues corresponding to the CPU, the secondary memory and the input-
output unit.

We will only note the differences between this system and the static
allocation memory system, presented in II.

In the dynamic allocation case each process which shares memory space
has at its disposal a number of central memory pages depending on the memory
management algorithm used in the system.

We know that a control of the multiprogramming degree is necessary to
avoid the trashing due to a burst of page demands when there are too many
processes sharing memory, so that they cannot maintain their working set in
central memory [B.K.69].

The optimal multiprogramming degree depends on the locality of
processes submitted to the system. We caracterise locality using Belady's
life-time function [B.K.69]. We suppose that we have a control limiting
the maximum number of processes admitted to share central memory at the
value $n_k$ where $n_k$ is the multiprogramming degree which permits to attain
the maximum utilization rate of the CPU when processes have a locality
caracterised by a life-time function $e(s) = \sum_k s^k$, where s is the primary
memory space allocated to each process and a is a constant. As in the
static memory allocation, we have a queue of processes waiting to share
memory and which are introduced into the multiprogramming set by a sche-
duler.

## 3.2. The parameters of the model.

As in II we shall assume that the different queues are first-in-first-
out and that service times are exponentially distributed.

There is an important difference with the static allocation scheme in
the value of the parameters used for the secondary memory transfers, since
these will be carried out for single page rather than for the pages of the
whole task.
## CPU service rate : $\mu_0'(N)$

Let $e'$ be the mean time between two demands for service to the secondary memory, and $e'_1$ the life-time function, i.e. the mean compute time between two page demands for the executing process

$$e'_1 = a \left(\frac{M}{N}\right)^k$$

where M is the total size of central memory, N the multiprogramming degree, and a and k the Belady-Kuehner's parameters, assuming that primary memory space is equally shared among the N processes.

Two cases are considered for $e'$ :

$$e' = \begin{cases} e'_1 \\ [e^{-1} + (e'_1)^{-1}]^{-1} \end{cases}$$

The first case, $e' = e'_1$, corresponds to the situation where the Belady function is supposed to express all the exchanges between central memory and secondary memory.

On the other hand, in the case $e' = [e^{-1} + (e'_1)^{-1}]^{-1}$ we consider that there is a superposition of two independent types of demands of exchange between central memory and secondary memory; the first ones are represented by $e'_1$ and essentially connected to the presence or the absence in central memory of the working set of the user, while the other ones represented by e concern, as for static memory allocation (2.1), transfers of system or of user modules necessary for process execution.

It follows that the service rate at the CPU depends on the multiprogramming degree N, and is calculated as in (2.2.)

$$\mu_0'(N) = \frac{1}{c} + \frac{1}{e'} + \sum_{i=2}^{K} \frac{1}{x_i}$$

## Secondary memory service rate : $\mu'_1$

In the dynamic memory allocation system each transfer concerns only one page while in the static allocation memory system transfers concern segments or modules which are usually several pages in size.

Thus the mean service time at the secondary memory in the dynamic memory allocation system $[\mu'_1]^{-1}$ will be lower than $\mu_1^{-1}$, mean service time
at the secondary memory in the static case.

### 3.3. The solution method.

The method used to solve this second model is the same as the one we developed in 2.3.a and 2.3.b.

Therefore for a given Belady's parameter k the utilization rate of the equivalent server is

$$ \alpha_o'(N) = \begin{cases} A_o(N) & \text{if } N \le n_k \\ A_o(n_k) & \text{if } N > n_k \end{cases} $$

where $n_k$ is the value of the multiprogramming degree for which we have the best utilization rate of the CPU. It is of course not totally realistic to assume that $n_k$ is perfectly known and that the control implied by the above expression (see Figure 4) can be maintained. Thus this model represents an "ideal" case for the dynamic memory allocation method.

## IV. Comparison of the two systems.

The comparison of these two systems is then reduced to the comparison of two M/M/1 queues with service rates $\mu_o(N)$ and $\mu_o'(N)$ which are functions of the queue length.

We are interested in the mean response time $T$, which is equal (Little's formula [Lit.61]) to mean queue length divided by the arrival rate $\lambda$:

$$ T = \frac{1}{\lambda} \sum_{N=0}^{\infty} N P_N $$

where $P_N$ is the probability that queue length equals N

$$ P_N = P_o \prod_{n=0}^{N-1} \frac{\mu(n)}{\lambda} \quad \text{and} \quad P_o = \left[ \sum_{N} \prod_{n=0}^{N-1} \frac{\mu(n)}{\lambda} \right]^{-1} $$

As the resource-loop is modelled by a Gordon and Newell queueing network [G.N.67] we may use Chandy Herzog and Woo's work on equivalence in queueing networks [CHW.75-1]. It allows us to replace our K-2 input/output unit queues by only one queue with exponential service and FIFO order. We call it the input/output queue and it is defined by

$x$ : mean virtual time between to successive input/output,

$\mu_2^{-1}$ : mean service time.
### 4.1. Values attributed to the different parameters :

The time unit is the millisecond. The parameter values we use are drawn from system measurements [SFER.76], [Ler.77].

#### 4.1.1. Parameters common to the two systems :

$\lambda^{-1}$ = 5000,10000 and 15000 m.sec, mean time between two successive process arrivals to system

c = 1000, 2000, 3000 msec, mean compute time necessary for a process execution

x = 20 msec, mean virtual time between two successive input/output.

$\mu_2^{-1}$ = 30 msec, mean service time for an input/output.

#### 4.1.2. Parameters specific to the dynamic memory allocation system.

The values of Belady-Kuehner's parameters used for the life time function $e'_1 = a(M/N)^k$ are suggested by Belady and Kuehner in [B.K.69] :

a = $10^{-2}$

k = 1.3 to 2.5, small values of k correspond to bad locality properties (k=1.3; 1.5) and values greater than 2 correspond to good locality

M = central memory size expressed in K words; we have chosen 128

N = multiprogramming degree, varying from 1 to 13 in this case. The evaluation of the variation domain of N is issued from results obtained on the CII SIRIS 8 operating system [SFER.76]

($\mu'_1$)$^{-1}$ = 5 msec mean service time at the secondary memory

#### 4.1.3. Parameters specific to the static memory allocation system.

The exchanges between central memory and secondary memory happen less often than in the case of dynamic allocation. But the mean service time will be longer because we have not transfer of one page, but transfers of modules the size of which is greater or equal to one page. For this reason we have taken for values of
$$e : \begin{cases} 1, & 2, & 5 \\ 10, & 20, & 50 \\ 100, & 200, & 500 \end{cases} \quad \text{msec}$$

and

$\mu_1^{-1}$: $(5*\alpha) \approx 5$ msec i.e. we consider that the mean service time at the secondary memory is equal to the mean transfer time of a page (5 msec) multiplied by $5\alpha$, a coefficient proportional to the processes half mean size ($=10(\alpha+1)$) as we will see.

The probability distribution of memory space demand used to calculate $\Pi_n$, has been approximated using the results of the SFER-SIRIS 8 evaluation [SFER 76]. We have considered that the distribution of demand by units of 10 K-words Poisson of parameter $\alpha$, translated by 1 at the origin i.e.

$$P[X = 10h] = K' \frac{e^{-\alpha} h^{-1}}{(h-1)!}$$

$h > 1$ (for avoiding demands of 0 K-word) and truncated at 13 i.e.:

$$Pr[demand > 128K-words] = Pr[X > 130] = 0$$

because the memory size is limited to 128 K. Thus we take

$$\alpha = 0.5, 1, 1.5, 2, 3, 5, 7$$

## V. Comparison of results:

The results presented graphically on Figure 5 and 6 correspond to a mean interarrival time to systems $\lambda = 10 000$ msec (resp. 15 000 msec) and a mean compute time by process c = 1000 msec (resp. 3000 msec): i.e a ratio of entry rate to service rate of 1/10 (resp. 1/5). They summarize the set of results we obtained for the different values of c and $\lambda$ considered.

On Figures 5 and 6 the mean response time is function of

- the parameter $\alpha$; $10 \times (\alpha+1)$ is the mean size in K-words of the processes, in the static memory allocation.

- the Belady's locality parameter k in the dynamic memory allocation.
For every value of e, mean time between two central memory secondary
memory exchanges due to transfer demands of system or user modules (but
not due to page faults) we have two curves :

- the first one corresponds to static memory allocation
  and increases with $\alpha$. We will note such curves by S.

- the other one noted correspond to dynamic memory allo-
  cation and decreases with D.

5.1. The static memory allocation curves family S :

The first thing we remark is an important incidence of the value
of e on the mean response time. For relatively small values of e (i.e.
e ≤ 50 msec for figure 5 and e ≤ 100 msec for figure 6, the mean res-
ponse time increases very quickly when the mean processes'size increases
I.E. when α increases the multiprogramming degree decreases,
and rapidly it comes to a situation where the queue indefinitely grows and
the mean response time tends to infinity.

Exemple : Figure 5, S : e= 50 msec and α = 6 or 7.

The explanation of this situation is that the relatively large
size of processes implies a very low mean multiprogramming degree (near 2
for α=5). Then the relatively frequent exchanges between central memory and
secondary memory involves a very poor CPU utilization rate. It follows that
the mean sojourn time in the resource loop becomes relatively long, and
particularly longer than the mean interarrival time. Therefore the system
will not be able to reach stationary state, the candidate processes queue
increasing indefinitely.

The same reason explains why for each α the mean response time
increases with e. So now we will be mainly interested by e ≥ 20 msec be-
cause when e < 20 msec the system cannot reach stationary state or is
close to transient state even for α relatively small, like α ≤ 2.

It is interesting to notice that we have a mean response time T varying
.) in figure 5 (c/λ = 1/10) from about 3000 msec to 12 500 msec for
e ≥ 50 msec (i.e. ratio 1 to 4),and from about 3000 msec to 2000 msec for
e ≥ 100 msec (i.e. ratio 1 to 2.3).
.) in Figure 6 (c/λ = 1/5) from about 10000 msec to 52 500 msec for e ≥ 100 msec (i.e. a ratio 1 to 5.25).

## 5.2. The dynamic memory allocation curves family D:

At the opposite of the static memory allocation case we notice here a relatively light incidence of e on the mean response time. This is due to the fact that the most of the exchanges central memory - secondary memory are consequences of page faults and not of transfers of users or system modules : it is easy to see that by comparing e to e₁ = a(N/λ)k. Consequently the curves obtained for different values of e are very close.

A second point is that in the dynamic memory allocation the situation of a response time indefinitely increasing does not appears in the cases figured in 5 and 6 for e ≥ 2 msec. (But it may appear for instance when λ = 5000 msec and c = 3000 msec i.e. c/λ = 3/5 when k = 1.3 or 1.5 : then system is overleaded).

Justification of that must be found in the fact that in dynamic memory allocation the multiprogramming degree may be maintained at an higher level than in static one.

So, in spite of supplementary exchanges secondary memory - central memory (here each exchange concerns only one page) the CPU utilization rate may be maintained at an higher level than in static allocation. And this avoids catastrophic increase of response time.

Finally we must notice that in dynamic memory allocation results about mean response time T are much more concentrated than in the other case :

Figure 5 for e ≥ 5 msec T varies from about 3000 msec to 7000 msec i.e. ratio 1 → 2.3
for e ≥ 20 msec from 3000 msec to 5500 msec i.e. 1 → 1.8
and for e ≥ 50 msec from 3000 msec to 5000 msec i.e. 1 → 1.7

Figure 6 for e ≥ 10 msec from about 10.000 msec to 40.000 msec i.e. ratio 1 → 4
and for e ≥ 50 msec from about 10.000 msec to 30.000 msec i.e. ratio 1 → 3.
### 5.3. The confrontation of the two families of curves.

Now if we compare the mean response time for $e \ge 20$ msec in the two cases, it appears on figure 6 (respectively 5) that

* if $\alpha \ge 4$ (resp. 3), i.e. mean central memory size necessary by process $\ge 50$ K-words (resp. 40), then dynamic allocation is quicker than static, except when $e \ge 100$ msec and $k \le 1.5$ (resp. 50 msec and 1.4), i.e. bad locality processes, then dynamic and static allocations are equivalent.

* if $\alpha \le 2$ (resp. $\lambda \le 1.5$), i.e. mean central memory size necessary by process $\le 30$ K-words (resp. 25), then static allocation is preferable for $k \le 1.5$ (resp. 1.4) and equivalent for $k > 1.5$ (resp. 1.4), i.e. good locality processes.

* if $\alpha$ is close to 3 (resp. 2), then

1) if $e \ge 50$ msec and $k \le 1.5$ static allocation is preferable

2) if $k \ge 1.7$ and $e \ge 50$ msec (resp. $> 50$ msec) dynamic allocation is equivalent to static allocation, or slightly better. The larger is $k$, the more favorable is dynamic allocation

3) if $e \in [20,50[$ static allocation is preferable for $k \ge 1.5$ and equivalent if $k < 1.5$

## VI. Conclusion :

Finally, we may resume our work by two points which appear as the most important :

1) The first one is the great variability in the mean response time in the static memory allocation case, and peculiarly the very important slackening that may be introduced by processes which need a large central memory size allocation.
2) The second point is the conclusion that static allocation is better for processes needing small central memory allocation especially if they have bad locality properties. And dynamic allocation will be prefered for middle-size or large processes, and especially if they have good locality properties.

These conclusions must be conditioned on the following three elements :

a) The approximation we have made for the static memory allocation, indicated in II.

b) For the dynamic memory allocation we have considered that the system is maintained at the optimal multiprogramming degree for the CPU use, function of the Belady's parameter k. This is hardly ever the case in practice.

c) We did not take account of the overhead in the two cases. But for the evaluation of its influence we must notice that an overhead time appears especially at transfers between central memory - secondary memory, and it diminishes the "useful" CPU utilization rate. These events, as we see, are more numerous for dynamic allocation than for static : so overhead will tend to be unfavorable for the demand paging system.

These three points are to be taken into account. The differences in mean response time between the two systems is so important, however, that their role must not be over estimated.
<figure><img src="image_2.png" /><figcaption>Figure 2. UTILIZATION RATE OF CPU IN STATIC CASE</figcaption></figure>

<figure><img src="image_3.png" /></figure>
<figure><img src="image_4.png" /><figcaption>Figure 4. UTILIZATION RATE OF CPU IN DYNAMIC CASE</figcaption></figure>

<figure><img src="image_5.png" /></figure>
<caption>Figure 5</caption>

$c= 1000$ msec
$\lambda=10000$ msec

<figure><img src="image_6.png" /></figure>
<figure><img src="image_7.png" /></figure>

Figure 6

{ c=3000msec
λ=15 000msec

Mean response time
function of Belady's k
dynamic allocation

--- Mean response time
function of
static allocation

S(i) : static case
for e=i msec

D(i) : dynamic case
for e=i msec
[BCMP.75] Baskett, Chandy, Muntz, Palacios.

"Open, closed and mixed networks of queues with different classes of customers."
JACM 22, 2, 1975, pp. 248-260.

[B.K.69] Belady L.A., Kuehner C.J.

"Dynamic space-sharing in computer systems."
CACM, Vol 12, N° 5, May 1969.

[CHW.75.1] Chandy K.M., Herzog U., Woo L.

"Parametric Analysis of Queueing Networks"
IBM J. Res. Develop. January 1975, pp. 36-42.

[CHW.75.2] Chandy K.M., Herzog U., Woo L.

"Approximate Analysis of General Queueing Networks"
IBM J. Res. Develop. January 1975, pp. 43-49.

[Cou.71] Courtois P.J.

"On the near-complete decomposability of networks of queues and stochastic models of multiprogramming computing systems."
MBLE Report, Belgium, November 1971.

[Cou.75] Courtois P.J.

"Decomposability, Instabilities and Saturation in multiprogramming systems."
CACM July 1975, Vol. 18 N°7.

[Cou.77] Courtois P.J.

"Decomposability, Queueing and Computer system applications."
ACM Monograph Series, Academic Press 1977.

[Gel.73] Gelenbe E.

"Modèles de comportement de systèmes informatiques."
Thèse d'Etat, Université Paris VI, Novembre 1973.

[G.N.67] Gordon W.J., Newell G.F.

"Closed queueing systems with exponential servers."
Operations Research, April 1967.

[Jac.63] Jackson.J.R.

"Jobshop-like queueing systems."
Management Science, 10, 1, Octobre 1963.
[Ler.77] Leroudier J.

"Systèmes adaptatifs à mémoire virtuelle."
Thèse d'Etat, Université de Grenoble, Mai 1977.

[Lit.61] Little.

"A proof for the Queueing Formula $L = \lambda W_*$"
Operations Research, 9, pp. 383-387, (1961).

[Sfer.76] SFER.

"Résultats de l'évaluation du système CII Siris 8,
sur différents sites."
Rapport final de la Convention IRIA n° 75 - 022
du 01.01.1975. Document CERT ONERA, Toulouse.

[Ste.77] Stewart W.

"A new approach to the numerical analysis of
markovian models"
in Computer Performance, Yorktown Heights
K.M. Chandy and M. Reiser Editors, August 1977.