# Modèle d'un système de temps partagé à mémoire virtuelle avec commande du degré de multiprogrammation

## Alexandre Brandwajn

### ► To cite this version:

Alexandre Brandwajn. Modèle d'un système de temps partagé à mémoire virtuelle avec commande du degré de multiprogrammation. [Rapport de recherche] IRIA-RR-102, IRIA. 1975, pp.15. hal-04716082

HAL Id: hal-04716082

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

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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
RIA
laboria

laboratoire de recherche
en informatique
et automatique

Modèle d'un système de temps partagé
à mémoire virtuelle avec commande
du degré de multiprogrammation

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

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n·102

Février 1975
MODELE D'UN SYSTEME DE TEMPS PARTAGÉ A MÉMOIRE
VIRTUELLE AVEC COMMANDE DU DEGRÉ DE MULTIPROGRAMMATION

A. Brandwajn

Résumé.

Nous considérons un modèle stochastique d'un système à accès multiple comportant un mécanisme de commande du degré de multiprogrammation. La solution explicite approchée obtenue par la méthode de l'équivalence et de la décomposition permet une étude simple de l'efficacité de la commande du degré de multiprogrammation pour éviter l'écroulement du système.

Summary.

A queueing network model of a virtual memory multi-access system is presented including a mechanism for controlling the degree of multiprogramming. The efficiency of this control in order to avoid thrashing, is studied using an approximate explicit solution obtained by equivalence and decomposition methods.

Ce rapport correspond à une partie de l'article "A model of a time-sharing
virtual memory system solved using equivalence and decomposition methods"
à paraître dans ACTA INFORMATICA.
TABLE DES MATIERES

1. Introduction

2. Commande tenant compte uniquement du degré de multiprogrammation

3. Commande tenant compte du degré de multiprogrammation et du nombre de processus en attente d'admission en mémoire

4. Comportement transitoire du sytème commandé
# 1- Introduction

Dans le système de temps partagé qui fait l'objet du rapport LABORIA n°101[Br2], une commande d'usager arrivant au système était inconditionnellement admise dans la file d'attente de l'unité centrale, c'est-à-dire à participer au partage de la mémoire principale. On sent intuivement que c'est la raison pour laquelle le système s'écroule (l'utilisation de l'unité centrale tombe de façon dramatique et le temps de réponse explose) lorsque le nombre de terminaux connectés au système dépasse une certaine valeur.

Dans ce rapport nous étudions deux façons de commander le degré de multiprogrammation dans un système de temps partagé à mémoire virtuelle.

Le lecteur trouvera dans[Po1] une discussion détaillée de l'application des mécanismes de commande optimale. L'approche que nous présentons ici est essentiellement différente de[Po1] dans ce que nous donnons des résultats analytiques pour des mécanismes de commande qui ne sont pas nécessairement optimaux par rapport à un certain critère de performances.

Considérons le système représenté sur la figure 1. Il comporte, comme le système du rapport [Br2], un ensemble de terminaux, une unité centrale, un dispositif de mémoire secondaire (MS) et un disque de fichiers (DF). Ces trois derniers dispositifs, à chacun étant associée une file d'attente de requêtes, constituent la partie de traitement (R) du système dans laquelle les usagers partagent la mémoire principale.

Le mécanisme de commande est modélisé par une file d'attente Q et un interrupteur de commande CS. Une demande générée par un usager doit maintenant traverser ce dispositif de commande avant d'être admise en mémoire.
## TERMINAUX

<figure><img src="image_3.png" /><figcaption>Figure 1</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 2</figcaption></figure>
L'interrupteur de commande CS est caractérisé par une fonction
de commande qui décrit la position de CS. Cette fonction f(k,n) peut prendre
seulement deux valeurs 0 et 1 :

f(k,n) = {0 , si l'interrupteur de commande est {ouvert,
        1       fermé,

lorsqu'il y a k processus dans Q et n processus dans R.

Nous admettons que les changements de position de l'interrup-
teur de même que l'introduction d'un usager de Q dans R prennent un temps
nul.

Les hypothèses concernant les variables aléatoires qui repré-
sentent les temps de service à l'unité centrale, à la mémoire secondaire
et au disque de fichier, aussi bien que le temps de réflexion d'un usager
au terminal, sont les mêmes que celles du rapport [Br2], si bien que

$$
(1.1) \qquad p_1(n)u_o(n) = \frac{1}{q(n)}
$$

$$
(1.2) \qquad p_2(n)u_o(n) = \frac{1}{r}
$$

$$
(1.3) \qquad p_o(n)u_o(n) = \frac{1}{c}
$$

où $u_o(n)$ est le débit de service de l'unité centrale lorsque le degré de
multiprogrammation vaut $n$, $c$ est le temps moyen total de calcul d'un processus,
$r$ est le temps moyen de calcul entre deux demandes d'entrées/sorties
fichier consécutives et $q(n)$ est le temps moyen de calcul entre deux
défauts de pages consécutifs lorqu'il y a n usagers en mémoire, et il
est donné par

$$
(1.4) \qquad q(n) = \alpha\left(\frac{M}{n}\right)^k, \text{ avec l'approximation de Belady [Bel],} \\
\qquad \text{ou bien}
$$

$$
(1.5) \quad q(n) = \frac{2b}{1 + \left(\frac{dn}{M}\right)^2}, \text{ si l'on utilise l'approximation de Chamberlin [Ch1].}
$$
M est la taille de la mémoire physique allouable, k, b, d sont des para-
mètres qui dépendent entre autres de la localité des programmes.

2 - <u>Commande tenant compte uniquement du degré de multiprogrammation.</u>

Supposons d'abord que la fonction de commande soit

$$
(2.1) \quad f(k,n) = h_1(k,n) = \begin{cases} 1, & \text{si } n < m_o, \\ 0, & \text{si } n = m_o; \end{cases}
$$

$0 < m_o < N$ ; N étant le nombre total d'usagers.

Notons que l'état exact du système à un instant donné n'est
pas considéré dans la fonction de commande de l'interrupteur ; l'état
de R est décrit globalement par le degré de multiprogrammation. Nous
allons voir maintenant que la partie de traitement R peut être remplacée
par un seul serveur.

Définition 2.1

Nous dirons que deux sous-systèmes de files d'attente sont
<u>équivalents</u> si et seulement si

1. Les distributions de probabilité du nombre total de clients dans chacun de ces sous-systèmes sont identiques ;

2. Les distributions de probabilité des variables décrivant l'état des systèmes avec lesquels les systèmes équivalents interagissent sont les mêmes.

Théorème 2.1

Dans le système de la figure 1 , à l'état stationnaire,
le sous-système R est équivalent au sens de la définition 2.1 à un
seul serveur exponentiel de débit de service (voyez fig. 2 )

$$
(2.2) \qquad u(k,n) = A_o(k,n)p_o(n)u_o(n),
$$
où

A₀(k,n) est la probabilité stationnaire que l'unité centrale soit active conditionnée sur le fait qu'il y a k processus en attente dans Q et que le degré de multiprogrammation est n ;

p<sub>o</sub>(n) est la probabilité qu'un processus qui termine son service à l'unité centrale se dirige aux terminaux.

## Démonstration

Soit p(k,n,n<sub>c</sub>,t) la probabilité qu'il y ait respectivement k processus en attente d'admission dans Q, n processus dans R et n<sub>c</sub> usagers actifs aux terminaux. (k,n,n<sub>c</sub>), k+n+n<sub>c</sub>=N, sera l'état du système. Appelons δt un petit intervalle de temps.

Les seuls états stables* compatibles avec la fonction de commande h<sub>1</sub>(k,n) sont :

$$k=0 \text{ et } n=0,1,\dots,m_o;$$

(2.3) et

$$k=1,2,\dots,N-m_o \text{ et } n=m_o.$$

En ne considérant que les transitions dont la probabilité est d'ordre non supérieur à δt, nous obtenons par exemple :

$$ (2.4) \qquad \begin{cases} p(0,m_o,n_c,t+\delta t) = p(0,m_o,n_c,t)Q_1(t)+p(0,m_o-1,n_c+1)\lambda(n_c+1) + \\ \qquad \qquad +p(1,m_o,n_c-1,t)Q_2(t) + O(\delta t), \end{cases} $$

où

$$ Q_1(t) = \text{Prob}\{\text{pas de changement dans l'état du système pendant } (t,t+\delta t] \mid \text{état } (0,m_o) \text{ à l'instant } t \}; $$

$$ Q_2(t) = \text{Prob}\{1 \text{ départ du sous-système R aux terminaux pendant } (t,t+\delta t] \mid \text{état du système } (1,m_o) \text{ à l'instant } t \}; $$

<footnote>* stable - de probabilité non nulle à l'état stationnaire.</footnote>
$O(\delta t)$ désigne toute fonction de $\delta t$ telle que

$$ (2.5) \qquad \lim_{\delta t \to 0} \frac{O(\delta t)}{\delta t} = 0. $$

Désignons par $A_0(k,n,t)$ la probabilité que l'unité centrale soit active conditionnée sur le fait que l'état du système est $(k,n)(n_c=N-k-n)$ à l'instant $t$. Nous avons

$$ (2.6) \qquad \begin{cases} Q_1(t) = [1-A_0(0,m_o,t) + A_0(0,m_o,t)(1-p_o(m_o)u_o(m_o)\delta t)][1-n_o\lambda\delta t] + O(\delta t) \\ = 1-\delta t[A_0(0,m_o,t)p_o(m_o)u_o(m_o) + n_o\lambda] + O(\delta t), \end{cases} $$

et

$$ (2.7) \qquad Q_2(t) = A_0(1,m_o,t)p_o(m_o)u_o(m_o)\delta t + O(\delta t). $$

Si l'on pose

$$ (2.8) \qquad u(k,n,t) = A_0(k,n,t)p_o(n)u_o(n), $$

l'équation différentielle correspondant à (2.4) s'écrit

$$ (2.9) \qquad \begin{cases} \frac{d}{dt} p(0,m_o,n_c,t) = -[u(0,m_o,t) + n_c\lambda]p(0,m_o,n_c,t) + \\ \qquad + (n_c+1)\lambda p(0,m_o-1,n_c+1,t) + u(1,m_o,t)p(1,m_o,n_c-1,t) \end{cases}. $$

Posons

$$ (2.10) \qquad \begin{cases} p(k,n,n_c) = \lim_{t \to \infty} p(k,n,n_c,t) \\ A_0(k,n) = \lim_{t \to \infty} A_0(k,n,t) \end{cases} $$

$$ (2.11) \qquad \text{et} \qquad u(k,n) = \lim_{t \to \infty} u(k,n,t) = A_0(k,n)p_o(n)u_o(n). $$

On montre que l'état stationnaire existe pour le réseau considéré et donc les limites (2,10) existent elles aussi.
Il suffit de passer à la limite pour $t \to \infty$ dans (2.9) pour obtenir l'équation d'équilibre qui correspond à (2.4) :

$$ (2.12) \qquad -[u(0,m_o)+n_c \lambda]p(0,m_o,n_c)+(n_c+1) \lambda p(0,m_o-1,n_c+1)+u(1,m_o)p(1,m_o,n_c-1) = 0. $$

Les équations d'équilibre pour d'autres états du système s'obtiennent de façon analogue.

On voit aisément que l'on arrive à des équations en tous points identiques aux équations d'équilibre d'un système composé de l'ensemble des terminaux, de la file Q des processus en attente, de l'interrupteur CS avec $h_1(k,n)$ comme fonction de commande et d'un serveur exponentiel R avec sa file d'attente, le débit de service de R étant $u(k,n) = A_0(k,n)p_0(n)u_0(n)$.

c.q.f.d.

Il est clair que le système équivalent obtenu en remplaçant la partie de traitement par un seul serveur de débit $u(k,n)$ est un cas particulier du réseau fermé de deux stations de service analysé dans [Br3]. En effet, l'ensemble de terminaux peut être représenté par un serveur exponentiel de débit de service

$$ (2.13) \qquad \mu(k,n) = (N-n-k) \lambda = n_c \lambda, $$

et par conséquent la distribution stationnaire de probabilité des nombres de processus en attente et en traitement s'obtient comme un cas particulier des résultats présentés dans [Br3].

Remarquons que le fait d'avoir défini l'état par le couple $(k,n)$ nous arrange bien vu que nous avons choisi l'espérance du temps de réponse comme critère de performances du système.
On montre facilement que si l'on a

$$
(2.14) \qquad (N-i)\lambda + x(n_o)u_o(i)p_o(i) \le \sum_{\ell=1}^{2} x(n_\ell)u_\ell + x(n_o)u_o(n_o)\sum_{\ell=1}^{2} p_\ell(i), \\
\qquad \qquad \qquad \qquad \qquad \qquad \qquad i=1, \dots, N; \quad \Psi_{n_o, n_1} = 0, \dots, N,
$$

où $x(k)=0$ si $k=0$, et 1 sinon,

le système de la figure 1 jouit de la propriété de décomposabilité presque
complète : pour n=0,...,m₀⁻¹ k vaut zéro et le système se comporte comme
si la file d'attente Q et l'interrupteur de commande n'existait pas ;
pour n=m₀ et k≠ 0 le nombre de processus dans R est maintenu constant : Q
joue le rôle de tampon de séparation entre les terminaux et la partie de
traitement R.

La démonstration rigoureuse de la propriété de décomposabilité
presque complète est facile à faire et nous ne la présenterons pas.

Il résulte des propriétés des systèmes presque complètement décom-
posables que nous avons

$$
(2.15) \qquad A_0^{(k,n)} \approx A_0^{(n)} = A_0^{n},
$$

où $A_0^n$ est la probabilité à l'état d'équilibre que l'unité centrale soit
active dans le système fermé représenté sur la figure 3 et est donnée
par la formule (3.26) de [Br2].

Nous avons la distribution stationnaire de probabilité

$$
(2.16) \qquad \left\{
\begin{array}{ll}
p(k,n) = G \frac{(\lambda c)^k}{(N-m_o-k)! [A_o(m_o)]^k} & \frac{(\lambda c)^n}{(N-n)! \prod_{i=1}^n A_o(i)}; \\
\text{où} &
\end{array}
\right.
$$
<figure><img src="image_5.png" /><figcaption>Figure 3</figcaption></figure>
$$
\left\{
\begin{array}{l}
\displaystyle \frac{1}{G} = \frac{1}{(N-m_o)!} \sum_{n=0}^{m_o-1} \frac{(\lambda c)^n}{\prod_{i=1}^{n} (N-n)! \Pi_{o} A_o(i)} + \\[2ex]
\displaystyle + \frac{(\lambda c)^{m_o}}{\prod_{i=1}^{m_o} (N-m_o)! \Pi_{o} A_o(i)} \sum_{k=0}^{N-m_o} \frac{(\lambda c)^k}{\prod_{o} (N-m_o-k)![A_o(m_o)]^k}
\end{array}
\right.
$$

Comme pour le modèle du rapport [Br2], le temps moyen de réponse du système se calcule à l'aide de la formule de Little [Li1].

L'efficacité de la commande est illustrée sur les figures 4 et 5
qui montrent le temps moyen de réponse en fonction de N (le nombre de
terminaux) pour un ensemble de paramètres du système. Sur la figure 4
nous voyons l'effet de la variation du degré maximum de multiprogrammation
m_o pour le modèle avec la fonction de durée de vie de Belady l'exposant
de localité k étant égal à 2,0. Nous constatons qu'il existe une valeur
optimale de m_o qui minimise l'espérance du temps de réponse et fait qu'il
croît avec N beaucoup plus lentement que dans un système sans commande du
degré de multiprogrammation. Les mêmes conclusions peuvent être tirées des
courbes de la figure 5 sur laquelle nous avons représenté l'effet de la
variation de m_o pour le modèle avec l'approximation de Chamberlin de la
fonction de durée de vie de paramètres b=20ms et d = 60 pages.

Dans le cas où la partie de traitement R ne comporte pas d'entrées/
sorties, les résultats restent valables : R peut être remplacé par un seul
serveur exponentiel de débit u(k,n) = A₀(k,n)p₀(n)u₀(n). Pour obtenir A₀(k,n)
nous pouvons utiliser la connaissance du régime transitoire du modèle
fermé à deux serveurs (voyez [Br1] ), ou bien le théorème sur la décompo-
sabilité presque complète en faisant appel à l'inégalité moins restrictive
M=128 pages
t<sub>MS</sub>=5 ms
t<sub>DF</sub>=30 ms

temps moyen de réponse (s)

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

nombre de terminaux N

M=128 pages
t<sub>MS</sub>=5 ms
t<sub>DF</sub>=30 ms

temps moyen de réponse (s)

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

nombre de terminaux N.
(2.26) de [Br2]. Toutes les deux conduisent au même résultat

$$ (2.17) \qquad A_o(k,n) \approx A_o(n) = A_o^n, $$

où $A_o^n$ est la probabilité stationnaire que l'unité centrale soit active dans le modèle fermé à deux serveurs, et est donnée par la formule (3.28) de [Br2].

Il est clair que la distribution stationnaire de probabilité du nombre de processus respectivement en attente d'admission en mémoire et en traitement est donnée par la formule (2.16) avec (2.17).

### 3 - Commande tenant compte du degré de multiprogrammation et du nombre de processus en attente.

Un simple raisonnement suffit pour se convaincre que dans un système où le débit d'arrivée est $\lambda$ indépendamment du nombre de processus déjà présents dans le système, on n'a aucune raison de se préoccuper du nombre de processus en attente si l'on veut améliorer le temps moyen de réponse. Le mieux que l'on puisse faire est d'assurer que le maximum de processus quittent le système par unité de temps ; en d'autres mots, il faut maintenir autant que possible le degré de multiprogrammation qui maximise le débit du système et ceci quel que soit le nombre de processus dans la file d'attente $Q$. A première vue, cet argument ne s'applique pas à notre modèle, puisque l'on peut dire qu'accélérer le débit de la partie de traitement R revient à augmenter le nombre d'usagers actifs aux terminaux et par cela même le débit d'arrivée des demandes. Essayons donc une fonction de commande de l'interrupteur CS qui tient compte de la longueur de la file des processus en attente d'admission en mémoire $Q$ en empêchant qu'elle dépasse une certaine limite $k_o$ :
$$
(3.1) \quad f(k,n) = h_2(k,n) = \begin{cases} 1, & \text{si } 0 \le n \le m_o^* - 1 \\ 0, & \text{si } n = m_o^* \text{ et } k=0,1,\dots,k_o \\ 1, & \text{si } k > k_o \\ 0, & \text{partout ailleurs ;} \end{cases} \\
\qquad 0 < k_o < N, \quad 0 < m_o^* < N, \quad m_o^* + k_o < N.
$$

On montre facilement que, comme pour la fonction de commande h₁(k,n) (6.1),
la partie de traitement R est équivalente au sens de la définition 2.1 à un
seul serveur exponentiel de débit de service

$$
u(k,n) = A_0(k,n) p_0(n) u_0(n),
$$

où $A_0(k,n)$ est la probabilité conditionnelle à l'état d'équilibre que l'unité centrale soit active étant donné que l'état est $(k,n)$.

On montre également qu'il suffit que l'inégalité (2.14) soit satis-
faite pour que le système soit presque complètement décomposable. Nous
obtenons par conséquent

$$
A_0(k,n) \approx A_0(n) = A_0^n,
$$

$A_0^n$ étant donné par la formule (3.26) de [Br2].

La distribution stationnaire de probabilité est donnée par

$$
(3.2) \quad p(k,n) = \begin{cases} G \frac{(\lambda c)^k (N-m_o^*)!}{(N-m_o^*-k)! [A_o(m_o^*)]^k} \frac{(\lambda c)^n}{(N-n)! \prod_{i=1}^n A_o(i)}, & \text{pour } n=0,\dots,m_o^* \\ G \frac{(\lambda c)^k}{[A_o(m_o^*)]^{k_o}} \frac{(\lambda c)^n}{(N-k_o-n)! \prod_{i=1}^n A_o(i)}, & \text{pour } n=m_o^*,\dots,N-k_o \\ \end{cases} \quad k=0,\dots,k_o
$$

G est la constante de normalisation.
M=128 pages
t<sub>MS</sub> = 5 ms

t<sub>DF</sub> = 30 ms

M = 128 pages

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

t<sub>FD</sub> = 30 ms

c = 500 ms

t<sub>r</sub> = 10 s

<figure><img src="image_8.png" /><figcaption>Figure 6
nombre de terminaux N</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 7</figcaption></figure>

<figure><img src="image_10.png" /></figure>
La figure 6 montre les résultats numériques obtenus avec la fonction de commande $h_2(k,n)$. Nous y avons tracé le temps moyen de réponse du système en fonction du nombre de terminaux N avec $k_0$ (la longueur stable maximum de la file d'attente Q) en paramètre pour une valeur de $m_0^*$ qui est optimum lorsque l'interrupteur est commandé suivant la fonction $h_1(k,n)$. Nous voyons que l'espérance du temps de réponse du système passe de façon monotone de la courbe pour le système sans commande ($k_0=0$) à la courbe pour la fonction de commande $h_1(k,n)$ ($k_0=N$).

Ce résultat n'est pas surprenant. Le débit d'arrivée des demandes est de toute évidence une fonction décroissante de $m=k+n$

$$n_c \lambda = (N-m) \lambda ;$$

le débit de service du serveur équivalent à la partie de traitement R vaut

$$u(k,n) \approx A_0^n / c,$$

où c est le temps moyen total de calcul d'un processus, et $A_0^n$ est l'utilisation de l'unité centrale dans le réseau fermé de la figure 3. $A_0^n$ est une fonction unimodale de n avec un seul maximum pour $n=i_0$. Dans ces conditions on montre que la valeur optimum (celle qui minimise l'espérance du temps de réponse du système) pour $m_0$ dans une fonction de commande $h_1(k,n)$ est approximativement égale (pour un système presque complètement décomposable) à la valeur i qui maximise l'utilisation de l'UC $A_0^i$ dans le système de la figure 3

$$ (3.3) \qquad \begin{cases} m_0 \approx i_0 \\ A_0^i \ge A_0^i, \quad \forall i = 1, \dots, N; \end{cases} $$

et qu'aucune autre fonction de commande $h_1(k,n)$ ou $h_2(k,n)$ ne peut assurer un meilleur temps moyen de réponse.
Notons que la fonction de commande $h_1(k,n)$ avec $m_o = i_o$ assure une
utilisation presque optimale de l'unité centrale (c'est-à-dire une utilisa-
tion proche, à forte charge, du mieux que l'on puisse faire dans un système
fermé : $A_o^i$) et empêche ainsi l'écroulement du système.

Une telle politique de commande est également facile à implanter
dans un système réel.

4 - Comportement transitoire du système commandé

Le fait que le système possède la propriété de décomposabilité pres-
que complète permet d'obtenir plus facilement des renseignements sur son
comportement transitoire. En effet, nous pouvons étudier à part le compor-
tement transitoire de la partie de traitement R qui constitue la réponse
transitoire du système à court terme, et le comportement transitoire de
l'ensemble en supposant que la partie de traitement est en état d'équilibre ;
ceci constitue la réponse transitoire de l'ensemble du système.

Nous nous limiterons au cas où l'interrupteur est commandé suivant
la fonction h₁(k,n) (2.1). Les équations différentielles aux différences
du système équivalent en prenant le couple (k,n) comme état s'écrivent :

$$
\begin{equation}
\begin{aligned}
\frac{d}{dt} p(0,0,t) &= - \mu(0)p(0,0,t) + u(0,1,t)p(0,1,t); \\
\frac{d}{dt} p(0,n,t) &= - [\mu(n)+u(0,n,t)]p(0,n,t) + \mu(n-1)p(0,n-1,t) + \\
&\qquad + u(0,n+1)p(0,n+1,t), \quad n=1,2,\dots,m_o-1;
\end{aligned}
\tag{4.1}
\end{equation}
$$
$$
\begin{equation} \tag{4.1}
\left\{
\begin{aligned}
\frac{d}{dt} p(0, m_o, t) &\rightarrow [\mu(m_o) + u(0, m_o, t)] p(0, m_o, t) + \mu(m_o-1) p(0, m_o-1, t) + u(1, m_o, t) p(1, m_o, t) \\
\frac{d}{dt} p(k, m_o, t) &\rightarrow [\mu(k+m_o) + u(k, m_o, t)] p(k, m_o, t) + \mu(k+m_o-1) p(k-1, m_o, t) + \\
&\qquad \qquad + u(k+1, m_o, t) p(k+1, m_o, t); \\
\frac{d}{dt} p(N-m_o, m_o, t) &\rightarrow u(N-m_o, m_o, t) p(N-m_o, m_o, t) + \mu(N-1) p(N-m_o-1, m_o, t),
\end{aligned}
\right.
\quad \text{où} \quad \mu(i) = (N-i)\lambda,
\end{equation}
$$

$$
\begin{equation} \tag{4.2}
\begin{gathered}
u(k,n,t) = A_0(k,n,t)p_0(n)u_0(n) = A_0(k,n,t)/c, \\
A_0(k,n,t) = \Pr\{\text{unité centrale active à l'instant } t \mid \text{état du système } (k,n) \text{ à } t\}.
\end{gathered}
\end{equation}
$$

Les équations (4.1) décrivent le comportement transitoire aussi
bien du système avec que sans entrées/sorties. Dans ce deuxième cas, seule
la probabilité $A_0(k,n,t)$ sera différente.

Grâce à la forme particulière de la fonction de commande, le système
(4.1) peut être transformé en

$$
\begin{equation} \tag{4.3}
\left\{
\begin{aligned}
\frac{d}{dt} \tilde{p}(0,t) &= - \mu(0) \tilde{p}(0,t) + \tilde{u}(1,t) \tilde{p}(1,t); \\
\frac{d}{dt} \tilde{p}(m,t) &\rightarrow [\mu(m) + \tilde{u}(m,t)] \tilde{p}(m,t) + \mu(m-1,t) \tilde{p}(m-1,t) + \tilde{u}(m+1,t) \tilde{p}(m+1,t), & m=1, \dots, N-1; \\
\frac{d}{dt} \tilde{p}(N,t) &= - \tilde{u}(N,t) \tilde{p}(N,t) + \mu(N-1) \tilde{p}(N-1,t),
\end{aligned}
\right.
\end{equation}
$$

où nous avons posé

$$
\begin{equation} \tag{4.4}
\left\{
\begin{array}{@{}l@{}}
m = k+n, \\
\tilde{u}(m,t) = u(k,n,t),
\end{array}
\right.
\end{equation}
$$
ce qui est licite puisque à chaque valeur de m correspond un seul couple $(k,n)$. Le fait qu'une telle transformation soit possible, montre bien que grâce à la fonction de commande nous avons été capables de régler le débit du serveur équivalent à la partie de traitement R. Qui plus est, l'ensemble formé de la file des processus en attente d'admission en mémoire Q et de la partie R est lui-même équivalent à un seul serveur "exponentiel" de débit $\tilde{u}(m,t)$. En régime stationnaire ce débit devient

$$ (4.5) \qquad \tilde{u}(m) = A_0(k,n)p_0(n)u_0(n) = A_0(k,n)/c. $$

Si l'on pose dans (4.3)

$$ (4.6) \qquad \tilde{u}(m,t) \approx A_0^n/c, $$

où $A_0^n$ est donné par (3.26) de [Br2], la solution du système fini d'équation différentielles (4.3) décrira l'évolution globale du système. Pour ce qui est du comportement transitoire de la partie de traitement, dans le cas où le système comporte un disque de fichiers, l'étude doit être numérique.; lorsque les processus ne font pas d'entrées/sorties, nous disposons des résultats analytiques présentés dans [Br1].

En ce qui concerne l'évolution du système tout entier, elle est dans ce dernier cas aussi décrite par les équations différentielles aux différences (4.3) à condition de prendre pour $A_0^n$ dans (4.6) l'utilisation de l'unité centrale dans le modèle fermé à deux serveurs.

On remarque également que dans le cas particulier où $m_0 = N$, les équations (4.3) décrivent l'évolution du système sans commande du degré de multiprogrammation.
REFERENCES

[Bel] L.Belady
"A study of replacement algorithms for a virtual-storage computer"
IBM Syst.J.,5,2,pp.78-101 (1966).

[Br1] A.Brandwajn,e.a.
"Modèle de système multiprogrammé à mémoire virtuelle paginée"
in Compte rendu des journées d'études sur les recherches en
mesure,simulation, modélisation des systèmes informatiques
IRIA, Toulouse, juin 1973.

[Br2] A.Brandwajn
"Equivalence et décomposition dans les réseaux de serveur d'échanges
avec application à un modèle de système à partage de ressources"
Rapport Laboria n° 101, 1975.

[Br3] A.Brandwajn
"Control schemes in queueing networks"
à paraître.

[Ch1] D.Chamberlin,e.a.
"An analysis of page allocation strategies for multiprogramming
sytems with virtual memory"
IBM J.Res.Develop., septembre 1973.

[ol] D.Potier,e.a.
"Gestion optimale d'un ordinateur multiprogrammé à mémoire virtuelle"
in 5-th Conference on optimization techniques, Springer Berlin, 1973.

[il] J.D.Little
"A proof of the queueing formula $L = \lambda W$"
Operations Research,9, 1961, pp.383-387.
La figure 7 montre un exemple de comportement transitoire. Nous y avons représenté l'espérance du nombre d'usagers dans le système en fonction du temps dans trois cas. La fonction de durée de vie est approchée par (1.5) avec b=20 ms et d =60 .