RIA
laboria

laboratoire de recherche
en informatique
et automatique

Equivalence et décomposition
dans les réseaux de serveur d'échanges
avec application à un modèle
de système à partage de ressources

<figure><img src="image_1.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·101

Février 1975.
# ÉQUIVALENCE ET DÉCOMPOSITION DANS LES RÉSEAUX DE SERVEUR D'ÉCHANGES AVEC APPLICATION A UN MODELE DE SYSTEME A PARTAGE DE RESSOURCES

A. Brandwajn

## Résumé.

Nous présentons un modèle de système à accès multiple prenant en compte l'effet du partage de la mémoire entre processus. Nous obtenons une solution explicite approchée en utilisant des méthodes d'équivalence et de décomposition. Les résultats obtenus illustrent l'influence des paramètres du système et du comportement des programmes sur les performances du système (temps moyen de réponse et utilisation de l'UC).

## Summary.

A queueing network model of a time-sharing multiprogramming virtual memory system is presented including the effect of memory sharing among processes. An approximate explicit solution is obtained using equivalence and decomposition methods. The influence of system and program behavior parameters on system performance (mean response time and CPU utilization) is illustrated in the results obtained.
TABLE DES MATIERES

1.Introduction

2.Réseaux de files d'attente avec un serveur d'échanges

2.1.Notion de serveur équivalent

2.2.Décomposabilité presque complète

3.Modèle d'un système multiprogrammé de temps partagé à mémoire virtuelle

3.1 Description générale

3.2.Effet du partage de la mémoire

3.3.Les équation décrivant le comportement du système

3.4.Application des théorèmes d'équivalence et de décomposabilité
presque complète au modèle

3.5. Modèle d'un système de traitement de travaux par trains dans des conditions de forte charge

3.5.1.Le modèle et ses équations

3.5.2.Degré optimum de multiprogrammation dans un système sans entrées/sorties

3.6.Résultats du modèle
# 1-INTRODUCTION

Nous présentons dans ce rapport quelques résultats sur un type particulier de réseaux de files d'attente et leur application à la modélisation de systèmes d'exploitation.

Nous commençons par introduire la notion de serveur équivalent en prenant comme exemple les réseaux de serveur d'échanges par l'intermédiaire duquel un groupe de serveurs interagit avec le monde extérieur. Nous donnons aussi des conditions suffisantes pour qu'un tel réseau possède la propriété de décomposabilité presque complète qui fait que certaines parties du réseau peuvent être examinées (approximativement) comme si elles étaient indépendantes du reste du système.

Ayant élaboré ces outils, nous construisons et étudions un modèle de système de temps partagé à mémoire virtuelle paginée lequel prend en compte diverses caractéristiques du comportement des programmes, comme taux d'entrées/sorties, taux de défauts de page, localité des références à la mémoire, temps total de calcul. La résolution explicite du modèle est rendue possible grâce à l'équivalence et la décomposition. L'étude d'un modèle pouvant représenter un système de traitement de travaux par trains (batch) - intéressant par lui-même - constitue une étape de la solution. Les résultats obtenus mettent en évidence l'écroulement (thrashing) lorsque le nombre de consoles actives dépasse celui qui correspond au maximum de l'utilisation de l'unité centrale.
## 2. - RESEAUX DE FILES D'ATTENTE AVEC UN SERVEUR D'ECHANGES.

Ce chapitre est consacré à l'étude d'une classe particulière de réseaux de files d'attente : les réseaux dans lesquels les échanges de clients entre deux groupes de serveurs, ou entre le monde extérieur et un groupe de files d'attente, se font uniquement par l'intermédiaire d'un seul serveur que nous appellerons, pour cette raison, *serveur d'échanges*.

### 2.1 - Notion de serveur équivalent.

Considérons le réseau ouvert de files d'attente représenté sur la figure 1. Les clients arrivent dans le système B d'une source extérieure avec un débit d'arrivée $\lambda(n)$ fonction du nombre total courant $n$ de clients présents dans le système. Nous supposons que le temps qui sépare deux arrivées consécutives est une variable aléatoire distribuée suivant une loi exponentielle. Le système B comporte $(k+1)$ files d'attente avec des serveurs exponentiels dont $k$ (numérotés de 1 à k) constituent le sous-système C. Le temps moyen de service du serveur $i$, $1 \le i \le k$, est $1/u_i(n_i)$ lorsque le nombre de clients à ce serveur (y compris celui au service) est égal à $n_i$. Les arrivées de clients et leurs départs du système passent exclusivement par le serveur n°0 ; ce serveur est donc un serveur d'échanges d'après notre terminologie. Nous admettons que le temps de service du serveur 0 est une variable aléatoire qui suit la loi exponentielle de moyenne $1/u_0(n)$ lorsque le nombre total de clients dans le système B vaut n.

La figure 2 montre un exemple de réseaux de files d'attente de ce type.
Définition 2.1

Nous dirons que deux systèmes de files d'attente sont équivalents si et seulement si

1. Les distributions de probabilité du nombre total de clients dans chacun de ces 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.

Par "système" nous entendons ici toute partie d'un réseau de files d'attente sur laquelle nous fixons notre attention.

Dans la définition 2.1, il s'agit d'une équivalence "vu de l'extérieur" ; on peut la résumer en disant que deux systèmes équivalents interagissent de la même façon avec le monde extérieur du point de vue d'une certaine description de l'état du système.

Théorème 2.1

Le système B qui se compose (comme sur la figure 1) d'un sous-système de k serveurs jacksoniens interconnectés de façon quelconque et d'un serveur d'échanges exponentiel de débit de service $u_0(n)$, le processus d'arrivée étant un processus de Poisson de paramètre $\lambda(n)$, lorsqu'il y a au total n clients dans le système, est équivalent au sens de la définition 2.1, à l'état stationnaire, si celui-ci existe, à un seul serveur exponentiel de débit de service $A_0(n)p_0(n)u_0(n)$ (voir figure 3 où

$A_0(n)$ est la probabilité conditionnelle stationnaire que le serveur d'échanges soit actif étant donné que le nombre de clients dans le système B est égal à n ;
<figure><img src="image_2.png" /><figcaption>Figure 1</figcaption></figure>
$p_o(n)$ est la probabilité qu'un client qui finit son service au serveur d'échanges quitte le système lorsque le nombre total de clients présents dans ce dernier est n.

L'existence de la solution stationnaire pour le système B implique l'existence de la solution stationnaire pour le système équivalent de la figure 3.

## Démonstration

Soit $p(n,t)$ la probabilité d'avoir $n$ clients dans le système B à l'instant $t$, et soit $\delta t$ un petit intervalle de temps.

Comme les temps de service de tous les serveurs sont des variables aléatoires distribuées suivant une loi exponentielle, et que le processus d'arrivée est un processus de Poisson, il est évident que l'état du système (défini par le nombre de clients à chacun des serveurs) à l'instant $t + \delta t$ ne dépend que de l'état à l'instant $t$.

Si l'on considère $p(n,t+\delta t)$, $n > 0$, il est clair que les seules valeurs possibles pour le nombre total de clients dans le système à l'instant $t$ (dont les probabilités de transition ne soient pas d'ordre supérieur à $\delta t$) sont $n, n+1, n-1$. Par conséquent, nous avons en posant $O(\delta t)$ pour toute fonction de $\delta t$ telle que

$$ (2.1) \qquad \lim_{t \to 0} \frac{O(\delta t)}{\delta t} = 0, $$

$$ (2.2) \qquad \begin{array}{l} p(n,t+\delta t) = p(n-1,t)\lambda(n-1)\delta t + p(n+1,t)Q_1(t) + p(n,t)Q_2(t) + O(\delta t), \\ \text{où} \\ Q_1(t)=\text{Prob} \left\{ \begin{array}{l} \text{1 départ du système et pas d'arrivée pendant } (t,t+\delta t] \mid n+1 \\ \text{clients dans le système à l'instant } t \end{array} \right\}; \end{array} $$
$Q_2(t)$ = Prob {pas de départ du système et pas d'arrivée pendant $(t,t+\delta t]$ | n clients dans le système à l'instant $t$}.

Appelons $A_o(n,t)$ la probabilité conditionnelle que le serveur d'échanges soit actif à l'instant $t$ étant donné que le nombre de clients présents dans le système est $n$, c'est-à-dire

$A_o(n,t) = \text{Prob}\{\text{serveur d'échanges actif à } t \mid n \text{ dans le système à t}\}$.

Nous avons

$$ (2.3) \qquad Q_1(t) = A_0(n+1,t)p_0(n+1)u_0(n+1)\delta t + O(t) $$

et

$$ \begin{align} Q_2(t) &= [1-A_0(n,t)+A_0(n,t)(1-p_0(n)u_0(n)\delta t)](1-\lambda(n)\delta t)+O(\delta t) = \nonumber \\ (2.4) \qquad &= [1-A_0(n,t)p_0(n)u_0(n)\delta t](1-\lambda(n)\delta t) + O(\delta t) = \nonumber \\ &= 1-\delta t[A_0(n,t)p_0(n)u_0(n)+\lambda(n)] + O(\delta t). \end{align} $$

En divisant les deux membres de (2.2) par $\delta t$ et en faisant tendre $\delta t$ vers zéro nous obtenons après substitution de (2.3) et (2.4), les équations différentielles aux différences pour le nombre total de clients dans le système

$$ (2.5) \qquad \left\{ \begin{aligned} \frac{d}{dt} p(n,t) &= -[A_0(n,t)p_0(n)u_0(n)+\lambda(n)] p(n,t) + \lambda(n-1)p(n-1,t) + \\ & \quad + A_0(n+1,t)p_0(n+1)u_0(n+1)p(n+1,t), \quad n=1,2,\dots \end{aligned} \right. $$

et de façon analogue

$$ (2.6) \qquad \frac{d}{dt} p(0,t) = - \lambda(0)p(0,t) + A_0(1,t)p_0(1)u_0(1)p(1,t). $$
<figure><img src="image_3.png" /><figcaption>Figure 2</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3</figcaption></figure>
Supposons que le système B possède un état stationnaire et posons

$$p(n) = \lim_{t \to \infty} p(n,t), \quad n=0,1,\dots;$$

$$A_o(n) = \lim_{t \to \infty} A_o(n,t), \quad n=1,2,\dots$$

Ces deux limites existent si l'état stationnaire existe pour le système B. Nous obtenons les équations aux différences pour $p(n)$ en prenant la limite de (2.5) et (2.6) lorsque $t \to \infty$

$$ (2.7) \quad \left\{ \begin{array}{ll} & -[A_o(n)p_o(n)u_o(n)+\lambda(n)] p(n)+\lambda(n-1)p(n-1)+A_o(n+1)p_o(n+1)u_o(n+1)p(n+1)=0 & n=1,2,\dots; \\ & \text{et} \\ & -\lambda(0)p(0) + A_o(1)p_o(1)u_o(1)p(1) = 0. \end{array} \right. $$

De toute évidence, (2.7) sont les équations d'une file d'attente M/M/1 avec un débit d'arrivée $\lambda(n)$ et un débit de service $u(n)=A_o(n)p_o(n)u_o(n)$ n étant le nombre de clients dans la file d'attente.

c.q.f.d.

Il est intéressant de remarquer que le système équivalent au système B est un serveur jacksonnien*, et que nous sommes donc capables, du moins formellement, de donner une expression pour la distribution stationnaire de probabilité du nombre total courant de clients dans B.

Une autre remarque intéressante concerne le comportement transitoire de B vu de l'extérieur : il résulte des équations (2.5) et (2.6) que le système B est équivalent à tout instant $t$ à une seule file d'attente avec un serveur "exponentiel" dont le débit est une fonction à la fois du nombre de clients dans la file et du temps $u(n,t)=A_o(n,t)p_o(n)u_o(n)$

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

* Un serveur jacksonnien est un serveur dont le débit dépend uniquement du nombre de clients dans la file d'attente du serveur.
A titre d'exemple, nous appliquerons le théorème 2.1 au réseau ouvert représenté sur la figure 2.

### Exemple 2.1

Le sous-système C consiste en un seul serveur dont le temps moyen de service est $1/u_1$ ; le débit de service $u_o$ du serveur d'échanges de même que les probabilités d'aiguillage ne dépendent pas du nombre total de clients dans le système $n$. Le débit d'arrivée est $\lambda$.

Soient $n_o$ et $n_1$ respectivement les nombres de clients au serveur d'échanges et au serveur C. Nous avons $n=n_o+n_1$. La distribution conjointe de probabilité de $n_o$ et de $n_1$ existe si

$$a = \frac{\lambda}{p_o u_o} < 1$$

et

$$b = \frac{p_1 u_o}{u_1} < 1.$$

Elle est alors donnée par

$$p(n_o, n_1) = (1-a)(1-b) \binom{n_o}{n_1}$$

A partir de $p(n_o, n_1)$ nous pouvons calculer la distribution de probabilité du nombre $n$ de clients dans le système $p(n)$, et la probabilité conditionnelle d'avoir $n_1$ clients au serveur C $p(n_1|n)$

$$p(n) = \sum_{n_o=0}^{n} p(n_o, n-n_o) = (1-a)(1-b) \frac{b^{n+1} - a^{n+1}}{b-a}$$

$$p(n_1|n) = \frac{p(n-n_1, n_1)}{p(n)} = (b-a) \frac{a^{n-n_1} n_1}{b^{n+1} - a^{n+1}}$$
La probabilité $A_o(n)$ du théorème 2.1 devient égale à

$$A_o(n) = 1 - p(n|n) = \frac{a(b^{n}-a^{n})}{b^{n+1}-a^{n+1}}$$

D'après le théorème 2.1, le réseau de files d'attente de la figure 2 est équivalent en ce qui concerne la distribution stationnaire de n, à une file d'attente M/M/1 avec un débit d'arrivée $\lambda$ et un débit de service $u(n) = A_o(n)p_o u_o$.

La solution stationnaire d'un tel système est donnée par les formules de JACKSON [Ja1]

$$p(n) = \frac{\sum_{k=0}^{\infty} \left[ \prod_{i=1}^{n} u(i) \right]^{k}}{\prod_{i=1}^{n} u(i)} = \frac{\sum_{k=0}^{\infty} \left[ \prod_{i=1}^{n} A_o(i) \right]^{k}}{\prod_{i=1}^{n} A_o(i)}$$

mais

$$\prod_{i=1}^{n} A_o(i) = \prod_{i=1}^{n} \frac{b^{i}-a^{i}}{b^{i+1}-a^{i+1}} = \prod_{i=1}^{n} \frac{b-a}{b^{n+1}-a^{n+1}}$$

et

$$\sum_{k=0}^{+\infty} \left[ \prod_{i=1}^{k} A_o(i) \right] = \sum_{k=0}^{+\infty} \frac{b^{k+1}-a^{k+1}}{b-a} = \frac{1}{(1-a)(1-b)}$$

Il en résulte

$$p(n) = (1-a)(1-b) \frac{b^{n+1}-a^{n+1}}{b-a}$$

ce qui est identique à la solution obtenue pour le réseau de départ.

Considérons maintenant le réseau fermé de files d'attente de la figure 4. Les sous-systèmes C et A comportent respectivement k et L-k serveurs jacksonniens (numérotés de 1 à k et de k+1 à L) interconnectés
de façon quelconque à l'intérieur de chacun des sous-systèmes, mais
qui interagissent avec le monde extérieur uniquement par l'intermédiaire
d'un serveur d'échanges. Nous admettons que le temps de service de ce
dernier est une variable aléatoire distribuée suivant une loi exponentielle
de moyenne 1/u₀(n) lorsque le nombre de clients dans le sous-système B
(serveur d'échanges et sous-système C) est égal à n. A tout instant t
l'état de A sera donné par le vecteur s̄=(īk+1, ..., īL), où i_j, k+1≤j≤L,
est le nombre de clients au serveur j du sous-système A, à cet instant.

Théorème 2.2

Dans le système considéré, à l'état stationnaire (qui existe
toujours le réseau étant fermé), le sous-système B est équivalent au
sens de la définition 2.1 à un seul serveur exponentiel avec les probabi-
lités d'aiguillage normées par rapport à p<sub>o</sub>(n) et un débit de service
égal à A<sub>o</sub>(n, s̄)p<sub>o</sub>(n) u<sub>o</sub>(n) (voir figure 5 ), où

A_o(n, s̄) est la probabilité conditionnelle stationnaire que le
serveur d'échanges soit actif étant donné qu'il y a n clients
dans le sous-système B et que l'état du sous-système A est s̄;
p_o(n) est la probabilité qu'un client qui termine son service au
serveur d'échanges se dirige vers le sous-système A lorsque le
nombre de clients dans B est n.

Démonstration

Soit p(n,s̄,t) la probabilité qu'il y ait n clients dans le
sous-système B et que le sous-système A soit dans l'état s̄=(īk+1, ..., īL)
à l'instant t. Soit également δt un petit intervalle de temps.

On voit aisément (parce que le sous-système A est un réseau
jacksonnien et que le serveur d'échanges est exponentiel) que l'état
du système (défini comme (n,s̄)) à l'instant t+δt dépend uniquement de
<figure><img src="image_6.png" /><figcaption>Figure 4</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 5</figcaption></figure>
l'état du système à l'instant $t$ et non de son passé.

Appelons $p_{\ell,j}(i_\ell)$, $k+1 \le \ell \le L$, $j=0, k+1, \dots, L$, la probabilité qu'un client qui quitte le serveur $\ell$ se dirige vers le serveur $n^\circ j$ (un serveur du sous-système A ou bien le serveur d'échanges). Soient aussi $u_\ell(i_\ell)$ le débit de service du serveur $\ell$ quand le nombre de clients à ce serveur est $i_\ell$, $\ell=k+1, \dots, L$, $0 \le i_\ell \le N$ (N est le nombre total de clients dans le système), et $p_{om}(n)$, $m=k+1, \dots, L$, la probabilité qu'un client qui termine son service au serveur d'échanges se dirige vers le serveur $m$ de A.

En ne considérant que les transitions dont la probabilité est d'ordre non supérieur à $\delta t$, nous avons

$$ (2.8) \qquad \left\{ \begin{aligned} p(n, \bar{s}, t+\delta t) &= p(n, \bar{s}, t) Q_1(t) + \sum_{m=k+1}^{L} p(n+1, b(\bar{s}, m), t) Q_2^m(t) + \\ & \quad + \delta t \sum_{\ell=k+1}^{L} p(n-1, a(\bar{s}, \ell), t) p_{\ell 0}(i_{\ell+1}) u_{\ell}(i_{\ell+1}) + \\ & \quad + \delta t \sum_{\substack{\ell,j=k+1 \\ j \ne \ell}}^{L} p(n, c(\bar{s}, \ell, j), t) p_{\ell j}(i_{\ell+1}) u_{\ell}(i_{\ell+1}) + O(\delta t), \end{aligned} \right. $$

où

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

$Q_2^m(t) =$ Prob { 1 départ du sous-système B vers le serveur $m$ de A pendant $(t, t+\delta t]$ état du système $(n+1, b(\bar{s},m))$ à l'instant $t$ } ;

$a(\bar{s}, \ell)$ est un vecteur identique au vecteur $\bar{s} = (i_{k+1}, \dots, i_L)$ à l'exception de la composante $i_\ell$ qui est remplacée par $i_\ell+1$ ;
$$
(2.9) \quad \begin{array}{ll}
b(\bar{s},m) & \text{est un vecteur identique à } \bar{s} \text{ à l'exception de la composante } i_m \\
& \text{qui est remplacée par } i_m - 1;
\end{array}
$$

c(\bar{s}, \ell, j) est un vecteur identique au vecteur \bar{s} à l'exception des composantes i_ℓ et i_j qui sont remplacées respectivement par
i_ℓ + 1 et i_j - 1;

O(δt) est donné par (2.1).

Nous admettons que

$$
(2.10) \quad \left\{
\begin{array}{ll}
p(n, \bar{s}, t) = 0 & \text{si le vecteur } (n, \bar{s}) \text{ contient un élément négatif ou supérieur} \\
& \text{à } N; \\[1em]
u_i(x_i) = 0 & \text{si } x_i = 0, i = k+1, \dots, L.
\end{array}
\right.
$$

Désignons par $A_o(n, \bar{s}, t)$ la probabilité conditionnelle que le serveur d'échanges soit actif à l'instant $t$ étant donné que l'état du système à cet instant est $(n, \bar{s})$. Nous avons

$$
(2.11) \quad \left\{
\begin{aligned}
Q_1(t) &= [1 - A_o(n, \bar{s}, t) + A_o(n, \bar{s}, t)(1 - p_o(n)u_o(n)\delta t)][1 - \delta t \sum_{\ell=k+1}^{L} (1 - p_{\ell\ell}(i_\ell))u_\ell(i_\ell)] + \\
&\quad + O(\delta t) = 1 - \delta t \left[A_o(n, \bar{s}, t)p_o(n)u_o(n) + \sum_{\ell=k+1}^{L} (1 - p_{\ell\ell}(i_\ell))u_\ell(i_\ell)\right] + O(\delta t)
\end{aligned}
\right.
\quad \text{et}
$$

$$
(2.12) \quad Q_2^m(t) = A_o(m+1, b(\bar{s},m), t) p_{om}(n+1) u_o(n+1) \delta t + O(\delta t).
$$

En utilisant (2.11) et (2.12) dans (2.8), nous obtenons les équations différentielles aux différences du système

$$
(2.13) \quad \left\{
\begin{aligned}
\frac{d}{dt} p(n, \bar{s}, t) &= -[u(n, \bar{s}, t) + \sum_{\ell=k+1}^{L} (1-p_{\ell\ell}(i_\ell))u_\ell(i_\ell)]p(n, \bar{s}, t) + \\
&\quad + \sum_{m=k+1}^{L} p_{om}(n+1)u_o(n+1)A_o(n+1, b(\bar{s},m), t)p(n, b(\bar{s},m), t)
\end{aligned}
\right.
$$
$$
(2.13) \quad \left\{
\begin{array}{l}
+ \sum_{\ell=k+1}^{L} p_{\ell 0}(i_{\ell}+1) u_{\ell}(i_{\ell}+1) p(n-1, a(\bar{s}, \ell), t) + \sum_{\substack{\ell, j=k+1 \\ j \neq \ell}}^{L} p_{\ell j}(i_{\ell}+1) u_{\ell}(i_{\ell}+1) p(n, c(\bar{s}, \ell, j), t) \\
\\
où \ u(n, \bar{s}, t) = A_{0}(n, \bar{s}, t) p_{0}(n) u_{0}(n), \ p_{0}(n) = \sum_{m=k+1}^{L} p_{0m}(n).
\end{array}
\right.
$$

Posons

$$
p(n, \bar{s}) = \lim_{t \to \infty} p(n, \bar{s}, t)
$$

$$
(2.14) \qquad A_0(n, \bar{s}) = \lim_{t \to \infty} A_0(n, \bar{s}, t)
$$

et

$$
u(n, \bar{s}) = \lim_{t \to \infty} u(n, \bar{s}, t) = A_0(n, \bar{s}) p_0(n) u_0(n).
$$

Les limites (2.14) existent parce que le système considéré atteint l'état stationnaire.

En passant à la limite pour $t \to \infty$ dans (2.13), nous obtenons
les équations aux différences que satisfait $p(n,\bar{s})$, c'est-à-dire qui
correspondent à l'état stationnaire :

$$
\begin{equation} \tag{2.15}
\begin{aligned}
& -\left[u(n, \bar{s}) + \sum_{\ell=k+1}^{L} (1-p_{\ell\ell}(i_\ell)) u_\ell(i_\ell)\right] p(n, \bar{s}) + \\
& \qquad + \sum_{m=k+1}^{L} \frac{p_{0m}(n+1)}{p_0(n+1)} u(n+1, b(\bar{s}, m)) p(n+1, b(\bar{s}, m)) + \\
& + \sum_{\ell=k+1}^{L} p_{\ell 0}(i_\ell+1) u_\ell(i_\ell+1) p(n-1, a(\bar{s}, \ell)) \\
& \qquad + \sum_{\substack{\ell, j=k+1 \\ j \neq \ell}}^{L} p_{\ell j}(i_\ell+1) u_\ell(i_\ell+1) p(n, c(\bar{s}, \ell, j)) = 0
\end{aligned}
\end{equation}
$$
On voit facilement que (2.15) sont les équations d'un système composé du sous système A connecté à un serveur exponentiel de débit de service $u(n, \bar{s}) = A_0(n, \bar{s}) p_o(n) u_o(n)$ lorsque le nombre de clients à ce serveur est $n$ et l'état de A est $\bar{s}$, les probabilités d'aiguillage $p_{om}(n)$, $m=k+1, \dots, L$, du serveur d'échanges étant remplacées par

$$ \frac{p_{om}(n)}{p_o(n)}, \quad m=k+1, \dots, L, $$

c'est-à-dire normées par rapport à $p_o(n)$.

c.q.f.d.

Il convient de remarquer que lorsque le sous-système A consiste en un seul serveur, le réseau équivalent devient un cas particulier de réseaux jacksonniens puisqu'alors

$$ A_0(n, \bar{s}) = A_0(n, N-n), \text{ et donc } u(n, \bar{s}) = u(n). $$

### Remarque

Dans les démonstrations des théorèmes 2.1 et 2.2 nous n'avons pas vraiment besoin (sauf pour l'existence de l'état stationnaire dans le théorème 2.2) de l'hypothèse que les temps de service des serveurs du sous-système C sont des variables aléatoires distribuées selon une loi exponentielle. Le nombre total courant de clients dans le sous-système B à l'instant $t+\delta t$ dépend uniquement de sa valeur à l'instant $t$ (et de $\bar{s}$ dans le théorème 2.2) à condition que le serveur d'échanges soit exponentiel et que le processus d'arrivée soit un processus de Poisson. Il en résulte que
**Théorème 2.3**

Si l'état stationnaire existe, les équivalences spécifiées dans les théorèmes 2.1 et 2.2 restent valables lorsque les temps de service des serveurs constituant les sous-système C sont des variables aléatoires distribuées selon une loi quelconque.

Nous avons utilisé les réseaux avec un serveur d'échanges pour introduire la notion de serveur équivalent. Cette méthode d'analyse, qui dépasse largement le cadre des réseaux de ce type (nous en verrons, d'ailleurs d'autres applications dans la suite), s'appuie sur un choix convenable des variables d'état, et permet, un peu à l'image de ce qui se fait dans les réseaux électriques, de simplifier bon nombre de réseaux de files d'attente en en remplaçant des parties par des serveurs équivalents. Les paramètres de ces derniers s'expriment en fonction des paramètres du réseau de départ, mais leur calcul effectif peut présenter de sérieuses difficultés. Dans le paragraphe suivant nous abordons le problème du calcul approché des paramètres du serveur équivalent pour une sous-classe des réseaux traités dans le théorème 2.2.

## 2.2 - Décomposabilité presque complète.

Considérons à nouveau le sous-système B sur les figures 1 et 4. De façon intuitive, si B interagit faiblement avec le monde extérieur (par exemple si le temps de relaxation de B après un changement intervenu dans le nombre de clients n est nettement inférieur au temps moyen entre deux changements consécutifs), on peut penser que la probabilité conditionnelle d'activité du serveur d'échanges $A_0(n)$ (ou $A_0(n,\bar{s})$) ne devrait pas être trop différente de la probabilité que le serveur d'échanges soit actif dans un réseau fermé obtenu en coupant les liens entre B et le monde extérieur.
<figure><img src="image_8.png" /><figcaption>Figure 6</figcaption></figure>
Les systèmes dans lesquels toutes les variables peuvent être,
de façon ou d'autre, réparties en un petit nombre de groupes si bien
que (i) les interactions entre les variables de chaque groupe s'étudient
comme si les interactions entre les groupes n'existaient pas, et (ii)
les interactions entre groupes s'étudient sans avoir à se référer aux
interactions à l'intérieur des groupes, portent le nom de **systèmes presque**
**complètement décomposables**. SIMON et ANDO [SIN] ont étudié ces systèmes
et ont démontré deux théorèmes. Il en résulte que, si les dépendances **entre**
**groupes** sont suffisamment faibles comparées à celles à **l'intérieur des**
**groupes**, le système peut être considéré, à court terme, comme un ensemble
de sous-systèmes indépendants qui s'analysent approximativement séparément
l'un de l'autre. A long terme, le système tout entier évolue sans trop
s'éloigner de l'état d'équilibre à l'intérieur de chacun des sous-systèmes.

La théorie de la décomposabilité presque complète a été appliquée
par COURTOIS [CO1] à une sous-classe de réseaux stochastiques de files
d'attentes de Jackson. Nous allons étudier dans quelles conditions le réseau
considéré dans le théorème 2.2, lorsque le sous-système A ne comporte
qu'un seul serveur exponentiel comme sur la figure 6 , est presque com-
plètement décomposable.
*

Soient $n_o$ et $n_\ell$, $\ell=1,...,k$, les nombres de clients respective-
ment au serveur d'échanges et aux k serveurs du sous-système C. Soient
aussi $u_\ell(n_\ell)$ le débit de service du serveur $\ell$, $1 \le \ell \le k$, lorsque le
nombre de clients à ce serveur est $n_\ell$, et $u_o(n)$, $n = \sum_{j=0}^k n_j$, le débit
de service du serveur d'échanges quand il y a n clients dans le sous-
système B.

*

Notre raisonnement sera analogue à celui de [CO1].
Le temps moyen de service de l'unique serveur de A, portant le numéro L, est $1/\lambda(i_L)$ lorsque le nombre de clients à ce serveur est égal à $i_L$. Nous avons $i_L + \sum_{j=0}^{k} n_j = N$, où n est le nombre total de clients qui circulent dans le réseau.

Les probabilités d'aiguillage à la sortie du serveur sont :
-pour le serveur d'échanges :
$$p_{om}(n), m=0,1,...,k,L, \text{ lorsque le nombre de clients dans le sous-système B est } n; \sum_{m} p_{om}(n) = 1, n=1,...,N;$$

-pour les serveurs de C :
$$p_{lj}(n_l), 1 \le l \le k, 0 \le j \le k, \text{ lorsque le nombre de clients au serveur n°l est } n_l; \sum_{j=0}^{k} p_{lj}(n_l)=1, n_l=1,...,N, \text{ pour tout } l=1,...,k;$$

-pour le serveur du sous-système A :
$$p_{Lq}(i_L), q=0 \text{ ou L, } i_L \text{ étant le nombre de clients au serveur.}$$

A tout instant t, le système est complètement décrit par la distribution conjointe de probabilité
$$p(n_0,n_1,...,n_k,i_L,t)$$

du nombre de clients dans chaque file d'attente à cet instant.

Les équations du réseau s'obtiennent facilement grâce à l'hypothèse que les temps de service sont des variables aléatoires indépendantes et distribuées selon une loi exponentielle
$$
\begin{equation}
\begin{aligned}
p(n_o, \dots, n_k, i_L, t+\delta t) = & \{1 - \delta t [ \alpha(i_L)\lambda(i_L)(1-p_{LL}(i_L)) + \alpha(n_o)u_o(n)(1-p_{oo}(n)) + \\
& \qquad + \sum_{\ell=1}^k \alpha(n_\ell)u_\ell(n_\ell)(1-p_{\ell\ell}(n_\ell))] \} p(n_o, \dots, n_k, i_L, t) + \\
& + \delta t \alpha(i_L+1)\lambda(i_L+1) (i_L+1)(1-p_{LL}(i_L+1))p(n_o-1, \dots, n_k, i_L+1, t) + \\
& + \delta t \alpha(n_o+1) u_o(n+1) p_{oL}(n+1) p(n_o+1, \dots, n_k, i_L-1, t) + \\
& + \delta t \sum_{\ell=1}^k \alpha(n_o+1) u_o(n) p_{o\ell}(n) p(n_o+1, \dots, n_\ell-1, \dots, i_L, t) + \\
& + \delta t \sum_{\substack{m=0 \\ m \neq \ell}}^k \sum_{\substack{\ell=1 \\ m \neq \ell}}^k \alpha(n_\ell+1) u_\ell(n_\ell+1) p_{\ell m}(n_\ell+1) p(n_o, \dots, n_\ell+1, \dots, n_m-1, \dots, i_L, t) + \\
& \qquad + O(\delta t),
\end{aligned}
\tag{2.17}
\end{equation}
$$

où $\delta t$ est un petit intervalle de temps, $O(\delta t)$ est donné par (2.1) et

$$
(2.18) \qquad \alpha(j) = \begin{cases} 0, & \text{si } j=0 \text{ ou } N+1 \\ 1, & \text{sinon.} \end{cases}
$$

Nous allons omettre $O(\delta t)$ et poser $\delta t=1$ si bien que l'équation (2.17) devient
sous forme matricielle

$P(t+1) = P(t)Q,$

où $P(t)$ est le vecteur des probabilités d'état $p(n_o, \dots, n_k, i_L, t)$ et
$Q=A+I$, $A$ étant la matrice des taux (débits) de transition et $I$ la matrice-
unité.

Nous choisissons l'unité de temps suffisamment petite pour
qu'aucun élément de la matrice Q nè soit négatif.
Chaque valeur de l'indice j, $j=1,..., \binom{K+N}{K}$, $K=k+2$, de la matrice Q se rapporte à un état différent $(n_o,...,n_k,i_L)$ du réseau. Nous choisissons un arrangement des lignes et des colonnes de Q tel que $i_L$ soit la variable qui varie le plus lentement dans le $(L+1)$-uple $(n_o,...,n_k,i_L)$, c'est-à-dire nous considérons d'abord tous les états possibles avec $i_L = 0$, ensuite avec $i_L = 1$, etc.

Désignons par $Q(N,K)$, $N > 0$, $K > 1$, la matrice Q d'ordre $\binom{K+N}{K}$ définie par cette numérotation des états.

**Lemme 2.1**

Les éléments de la matrice $Q(N,K)$ peuvent être partagés en $(N+1)$ sous-matrices principales $Q'(i_L), i_L=0,...,N$ de façon que l'ensemble des éléments non-diagonaux de chaque sous-matrice $Q'(i_L), i_L=X$, soit l'ensemble de toutes les probabilités de transition entre tout couple d'états distincts parmi les $\binom{K-1+N-X}{K-1}$ états avec $i_L=X$, c'est-à-dire $n = N-X$.

**Démonstration**

Il résulte de (2.17) que tout élément diagonal $q_{jj}$, où j se rapporte à un certain état $(n_o,...,n_k,i_L)$, est égal à
$$ (2.19) \qquad q_{jj} = 1 - \alpha(i_L)\lambda(i_L)(1-p_{LL}(i_L)) - \alpha(n_o)u_o(n)(1-p_{oo}(n)) - \sum_{\ell=1}^{k} \alpha(n_\ell)u_\ell(n_\ell)(1-p_{\ell\ell}(n_\ell)) $$

Il résulte aussi de (2.17) que tout élément non-diagonal $q_{jf}$ de $Q, j \neq f$, est différent de zéro seulement s'il existe un couple $(\ell,m), \ell \neq m$ tel que
$$
(2.20) \qquad \left\{
\begin{array}{l}
i_{j\ell} = i_{f\ell} + 1 \\
i_{jm} = i_{fm} - 1 \\
i_{jp} = i_{fp}, \forall p \neq \ell, m,
\end{array}
\right.
$$

où $i_{j\ell}$ est la valeur de $i_\ell$, $i_\ell = n_\ell$, $\ell=0,\dots,k$ ; $i_\ell = i_L$, $\ell=L$, associée
à la valeur j de l'indice dans la numérotation des états. Les seuls éléments
qui puissent être différents de zéro sont égaux à :

$$
(2.21) \qquad \left\{
\begin{array}{ll}
\alpha(n_\ell+1) u_\ell(n_\ell+1) p_{\ell m}(n_\ell+1) & \text{, pour } \begin{cases} \ell=1, \dots, k \\ m=0, \dots, k \end{cases} \\[1em]
\alpha(n_o+1) u_o(n) p_{o m}(n) & \text{, pour } \begin{cases} \ell=0 \\ m=1, \dots, k \end{cases} \\[1em]
\alpha(n_o+1) u_o(n+1) p_{o L}(n+1) & \text{, pour } \begin{cases} \ell=0 \\ m=L \end{cases} \\[1em]
\alpha(i_L+1) \lambda(i_L+1) (1-p_{LL}(i_L+1)) & \text{, pour } \begin{cases} \ell=L \\ ta=0 \end{cases}.
\end{array}
\right.
$$

Grâce à la numérotation des états on voit aisément que la
matrice Q(N,K) est stochastique ( $\sum_f q_{jf} = 1, \forall j$) et que les plus petites
valeurs de l'indice dans Q(N,K) se rapportent aux $\binom{K-1+N}{K-1}$ états - le
nombre de solutions entières distinctes de l'équation $\sum_{\ell=0}^{K-1} i_\ell = N$ -
avec $i_L=0$. De la même façon les $\binom{K-2+N}{K-1}$ valeurs suivantes de l'indice se
rapportent à tous les états avec $i_L=1$, et ainsi de suite jusqu'à $i_L=N$.
Par conséquent, tous les états peuvent être partagés en (N+1) ensembles qui définissent le même nombre de sous-matrices principales notées $Q'(i_L)$. Tous les éléments non-diagonaux de $Q'(i_L)$ représentent les probabilités de transition entre tout couple d'états distincts parmi les

$$ \binom{K-1+N-X}{K-1} \text{ états avec } i_L = X \ (n=N-X). \qquad \text{c.q.f.d.} $$

On déduit immédiatement de cette démonstration

**Lemme 2.2**

Tout élément non-diagonal de $Q(N,L)$ situé en dehors des sous-matrices principales $Q'(i_L)$ vaut soit zéro, soit

$$ \alpha(n_o+1) u_o(n+1) p_{oL}(n+1) \qquad (2.22) \text{ ou bien} \\ \alpha(i_L+1)\lambda(i_L+1)(1-p_{LL}(i_L+1)) $$

où $n=N-i_L$, $i_L$ correspondant à la colonne considérée dans la matrice.

Nous pouvons maintenant démontrer la proposition suivante.

**Théorème 2.4**

Si

$$ (2.23) \quad \left\{ \begin{array}{l} \alpha(i_L)\lambda(i_L)(1-p_{LL}(i_L)) + \alpha(n_o)u_o(n)p_{oL}(n) \ll \sum_{\ell=1}^k \alpha(n_\ell)u_\ell(n_\ell)(1-p_{\ell\ell}(n_\ell)) + \\ \qquad + \alpha(n_o)u_o(n) \sum_{m=1}^k p_{om}(n), \quad \text{pour } i_L=0,\dots,N, \end{array} \right. $$

la matrice stochastique $Q(N,K)$, $N > 0$, $K > 1$, définit un système presque complètement décomposable en (N+1) systèmes qui peuvent être représentés
par des matrices stochastiques $Q(X)$ d'ordre $\begin{pmatrix} N+K-X-1 \\ K-1 \end{pmatrix}$, $X=0, \dots, N$,
correspondant à toutes les interactions possibles entre les états $(n_o, \dots, n_k)$ avec $i_L=X$.

## Démonstration

Il résulte des lemmes 2.1 et 2.2 que nous pouvons écrire

$$ (2.24) \qquad Q(N,K) = Q^*(N,K) + E(N,K) $$

où

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

Tous les éléments de $Q^*(N,K)$ non représentés sont égaux à zéro ; les éléments non-diagonaux de $E(N,K)$ sont donnés par le Lemme 2.2 (formules (2.22)).

On peut montrer (voir p. 3.5 de [OJ]) qu'une condition suffisante pour que $Q(N,K)$ soit presque complètement décomposable en $Q'(0), \dots, Q'(N)$, est que la borne inférieure de la somme des éléments de toute ligne de chacune de ces sous-matrices soit suffisamment proche de l'unité. Tel est le cas lorsque l'inégalité (2.23) est satisfaite.

Il est clair que tout élément non-diagonal de $Q'(X)$, $X=0, \dots, N$, est identique à l'élément correspondant d'une matrice stochastique $Q(X)$ qui représente toutes les interactions possibles entre les états $(n_o, \dots, n_k)$ avec $i_L = X$, à condition que l'on utilise la même numérotation des états. $Q'(X)$ cependant n'est pas stochastique. La somme des éléments de sa j-ième
ligne $S'_j$ est égale à

$$ (2.25) \qquad S'_j = 1 - \alpha(i_L)\lambda(i_L)(1 - p_{LL}(i_L)) - \alpha(n_o)u_o(n)p_{oL}(n), \quad i_L=X, n=N-X, \\ \text{c'est-à-dire strictement inférieure à l'unité. Mais, mieux sera satisfaite} \\ \text{l'inégalité (2.23) et plus négligeables seront les deux derniers termes de} \\ \text{(2.25), si bien que } S'_j \to 1 \quad \text{et} \quad Q'(X) \to Q(X), X=0,\dots,N. $$

c.q.f.d.

Le théorème 2.4 donne une condition suffisante pour que le réseau de la figure 6 soit presque complètement décomposable. Les matrices stochastiques $Q(X)$ décrivent en fait le comportement d'un réseau fermé obtenu en coupant les liens entre les sous-systèmes B et A avec $N-X$ clients circulant dans ce réseau. On déduit des propriétés des systèmes presque complètement décomposables (citées en début de ce paragraphe) que la probabilité conditionnelle $A_o(n)$ que le serveur d'échanges soit actif étant donné qu'il y a n clients dans le sous-système B est approximativement égale à la probabilité que le serveur d'échanges soit actif dans le système fermé décrit par $Q(N-n)$. Le calcul de cette dernière probabilité ne pose aucun problème le réseau qui correspond à $Q(N-n)$ étant jacksonnien.

Une autre condition qui assure la décomposabilité presque complète du réseau considéré est

$$ (2.26) \qquad \begin{cases} 1 - \alpha(i_L)\lambda(i_L)(1 - p_{LL}(i_L)) - \alpha(n_o)u_o(n)p_{oL}(n) \gg \alpha(i_L)\lambda(i_L)(1 - p_{LL}(i_L)) + \\ \phantom{1 - \alpha(i_L)\lambda(i_L)(1 - p_{LL}(i_L))} + \alpha(n_o)u_o(n)p_{oL}(n). \end{cases} $$

L'inégalité (2.26) est moins restrictive que (2.23) ; nous lui préférerons toutefois cette dernière pour son indépendance des unités de temps. Des résultats en tous points semblables peuvent être obtenus
## 3 - MODELE D'UN SYSTEME MULTIPROGRAMME DE TEMPS PARTAGE A MEMOIRE VIRTUELLE

Dans ce chapitre nous allons élaborer et étudier un modèle de système de temps partagé avec multiprogrammation et mémoire virtuelle. Ce modèle permet de mettre en évidence l'important phénomène d'écroulement (thrashing) et d'en examiner la dépendance des divers paramètres du système des usagers et des programmes (localité des références à la mémoire, taille de celle-ci, caractéristiques de la mémoire secondaire, temps moyen de réflexion, etc...). Nous étudierons aussi un modèle stochastique de système de traitement de travaux par trains (batch). Dans le cas simple où le système ne comporte pas de disque de fichiers, nous donnerons une formule approchée qui permet de déterminer le nombre optimum de programmes admis à se partager la mémoire principale (degré de multiprogrammation).

### 3.1 Description générale

Soit le modèle de la figure 7. Elle représente l'architecture du système multiprogrammé de temps partagé en considération. Le système se compose d'un ensemble de terminaux à partir desquels un ensemble d'users (dont le nombre est égal à celui des terminaux) génèrent des commandes d'une unité centrale (UC), d'une mémoire secondaire (MS) (par exemple tambour ou disque à têtes fixes, LCS, etc...) et d'un disque de fichiers (DF). Une file d'attente des requêtes est associée à chacun de ces dispositifs ; l'ordre dans lequel ces requêtes sont satisfaites n'est pas pris en compte. Après avoir généré une commande, l'usager au terminal restera
inactif jusqu'à ce que le système ait fourni la réponse appropriée. De façon symbolique un usager qui a généré une commande entre dans la file d'attente de l'unité centrale. Nous utiliserons sans distinction les termes "usager" et "processus usager" ou encore simplement "processus".

Nous admettons que tous les processus sont statistiquement identiques et indépendants. Soient N et n respectivement le nombre total d'usagers et le degré courant de multiprogrammation. Si à un instant quelconque $n_0, n_1, n_2$ représentent respectivement le nombre de processus dans la file d'attente de l'UC, dans celle de la MS et du FD, alors nous avons

$$ (3.1) \qquad n = n_0 + n_1 + n_2, \quad 0 \le n \le N. $$

Dans le modèle, le comportement d'un usager au terminal est décrit par son temps de réflexion, c'est-à-dire le temps qui sépare la dernière réponse du système de la commande suivante générée par l'usager. Le comportement des processus dans le système est caractérisé par un temps de calcul suivi soit d'un défaut de page (après lequel le processus entre dans la file d'attente de la MS) soit d'une entrée/sortie (opération sur fichier) dans quel cas le processus rejoint la file d'attente du DF. Les processus qui terminent leur service à la MS ou au DF retournent dans la file d'attente de l'unité centrale. De façon symbolique la fin de l'exécution d'une commande est représentée par le départ d'un processus de l'UC aux terminaux. n étant le degré de multiprogrammation, nous supposons
## TERMINAUX

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

<figure><img src="image_11.png" /><figcaption>Figure 8</figcaption></figure>
que les probabilités qu'un défaut de page, une demande d'entrée/sortie ou une fin d'exécution de commande se produise pendant un petit intervalle de temps $(t,t+\delta t]$ lorsque l'unité centrale est active, valent respectivement

$$ (3.2) \qquad \frac{1}{q(n)} \delta t + O(\delta t), $$

$$ (3.3) \qquad \frac{1}{r(n)} \delta t + O(\delta t), $$

$$ (3.4) \qquad \frac{1}{c(n)} \delta t + O(\delta t), $$

où $O(\delta t)$ est donné par (2.1).

Soit $\tau$ la variable aléatoire qui représente les périodes d'exécution ininterrompue à l'unité centrale. Les hypothèses (3.2), (3.3), (3.4) équivalent à admettre que $\tau$ est distribuée suivant une loi exponentielle de paramètre (débit)

$$ (3.5) \qquad u_o(n) = \frac{1}{q(n)} + \frac{1}{r(n)} + \frac{1}{c(n)}. $$

Afin d'obtenir $p_1(n), p_2(n)$ et $p_o(n)$, respectivement la probabilité qu'un processus qui quitte l'UC se dirige à la mémoire secondaire, au disque de fichiers ou revienne aux terminaux, le nombre courant de processus qui s'exécutent dans le système étant $n$, il nous suffit de remarquer que d'après (3.2), (3.3), (3.4)

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

$$ (3.7) \qquad \begin{cases} p_2(n)u_o(n) = \frac{1}{r(n)}, \\ \text{et} \\ p_o(n) = 1 - p_1(n) - p_2(n) = \frac{1}{c(n)}. \end{cases} $$

$q(n), r(n), c(n)$ peuvent être interprétés comme étant respectivement le temps moyen de calcul entre deux défauts de pages consécutifs, le temps moyen de calcul entre deux demandes d'entrée/sortie consécutives et le temps moyen total d'unité centrale d'un processus (lorsque le degré de multiprogammation est $n$).
Nous admettrons que les temps de service à la MS et au FD aussi bien que le temps de réflexion d'un usager au terminal sont des variables aléatoires distribuées suivant la loi exponentielle de moyenne respectivement

$$ \frac{1}{u_1}, \frac{1}{u_2} \text{ et } \frac{1}{\lambda} $$

### 3.2 Effet du partage de la mémoire

Nous nous proposons d'utiliser notre modèle pour analyser l'effet du partage de la mémoire principale entre les processus dans le système. Nous avons donc besoin d'un modèle qui relie $q(n)$ à l'espace de mémoire alloué à chaque processus.

Les résultats expérimentaux [Bo1] indiquent que le temps moyen de calcul entre deux défauts de page consécutifs, $q$, pour un processus qui s'exécute dans un espace de mémoire $m$, a l'allure générale que montre la figure 9.

$q$ (appelé la fonction de durée de vie) peut être approché par une fonction de la forme

$$ q_1 = \alpha \min^k, $$

où $\alpha$ dépend à la fois de la rapidité des organes de calcul et des caractéristiques des programmes tandis que $k$ dépend de la localité des programmes et de la politique de gestion de la mémoire (par exemple,
algorithme de remplacement de page). BELADY et KUEHNER [Bel] indiquent
que k est compris entre 1,5 et 2,5 alors que SALTZER [Sal] affirme que k
est voisin de l'unité.

Récemment, CHAMBERLIN, FULLER et LIU [Ch1] ont proposé une autre approximation pour la fonction de durée de vie

$$
q_2 = \frac{2b}{1+\left(\frac{d}{m}\right)^2},
$$

où d est une mesure de l'espace de mémoire dont le processus a besoin
pour s'exécuter de façon efficace, c'est-à-dire le nombre de pages qui
assure au processus la moitié de sa durée de vie maximum ; b est l'espé-
rance mathématique du temps d'exécution entre défauts de page lorsqu'on
alloue au processus un espace de mémoire d.

Nous supposons que l'espace total de mémoire principale dispo-
nible est de taille M et que cet espace est également partagé par les
processus qui s'exécutent à un moment donné dans le système :

$$
(3.8) \qquad m = \frac{M}{n}.
$$

Ceci donne pour le temps moyen entre deux défauts de page consécutifs

$$
(3.9) \qquad q(n) = \alpha \left(\frac{M}{n}\right)^k
$$

avec la fonction de durée de vie de BELADY, et

$$
(3.10) \qquad q(n) = \frac{2b}{1+\left(\frac{dn}{M}\right)^2},
$$

si l'on utilise q₂.
<figure><img src="image_12.png" /><figcaption>Figure 9</figcaption></figure>
r et c sont supposés indépendants de m, n ou N ce qui
semble raisonnable.

3.3 Les équations décrivant le comportement du système

Nous aimerions utiliser les hypothèses concernant les
distributions des temps de service ainsi que leur relation avec le
comportement des programmes afin de calculer le temps moyen de réponse
du système et l'utilisation de l'unité centrale comme deux mesures
représentatives des performances du système.

Le comportement du système est entièrement décrit par la
distribution conjointe de probabilité

$$
p(n_o, n_1, n_2, n_c, t)
$$

des nombres de processus dans les trois files d'attente et de celui
d'usagers actifs aux terminaux à cet instant t ; notons que

$$
n_c = N - n_o - n_1 - n_2 = N - n.
$$

$$
\begin{equation}
\begin{aligned}
& \text{Les équations différentielles aux différences du système s'écrivent} \\
& \frac{d}{dt} p(n_o, n_1, n_2, n_c, t) = -[V_o + V_1 + V_2 + n_c \lambda] p(n_o, n_1, n_2, n_c, t) + \\
& \qquad (n_c + 1) \lambda p(n_o - 1, n_1, n_2, n_c + 1, t) + p_o (n+1) u_o (n+1) p(n_o + 1, n_1, n_2, n_c - 1, t) + \\
& \qquad u_1 p(n_o - 1, n_1 + 1, n_2, n_c, t) + u_2 p(n_o - 1, n_1, n_2 + 1, n_c, t) + \\
& \qquad p_1 (n) u_o (n) p(n_o + 1, n_1 - 1, n_2, n_c, t) + p_2 (n) u_o (n) p(n_o + 1, n_1, n_2 - 1, n_c, t),
\end{aligned}
\tag{3.11}
\end{equation}
$$
où nous posons

$$
(3.12) \qquad p(i,j,k,1,t) = 0
$$

pour tout i,j,k,1 négatif ou supérieur à N à tout instant t.

$$
(3.13) \qquad V_m = \begin{cases} u_m & \text{si } n_m > 0, \\ 0 & \text{sinon} \end{cases}
$$

pour m = 0, 1, 2.

Ces équations s'obtiennent sans difficulté grâce aux hypothèses
sur les temps de service et de réflexion. A cause de la propriété "d'oubli"
de la loi exponentielle, à tout instant t, la probabilité qu'un processus
qui s'exécute à l'unité centrale la quitte pendant l'intervalle de temps
(t,t+δt] pour se diriger par exemple à la file d'attente de la mémoire
secondaire est p₁(n)u₀(n)δt + o(δt), n étant le nombre de processus dans
le système à l'instant t, indépendamment de la quantité de temps d'unité
centrale que le processus a déjà obtenu, et des valeurs précédentes du
degré de multiprogrammation. La fonction o(δt) est donnée par (2.1).

La solution stationnaire de (3.11) est définie par

$$
(3.14) \qquad p(n_o, n_1, n_2, n_c) = \lim_{t \to \infty} p(n_o, n_1, n_2, n_c, t).
$$

$t \to \infty$

On peut montrer que (3.14) existe pour le système étudié et que cette
limite est indépendante des conditions initiales p(n₀,n₁,n₂,n_c,0) en
considérant la chaîne de Markov à temps continu
$$
(3.15) \qquad \bar{p}(t+\delta t) = A \bar{p}(t),
$$

où $\bar{p}(t)$ est le vecteur des probabilités conjointes du nombre de processus
dans chaque file d'attente et du nombre d'usagers actifs aux terminaux
au temps t, A est la matrice stochastique de transition (une fonction de $\delta t$),
et (3.11) est obtenu en posant

$$
(3.16) \qquad \frac{d}{dt} \bar{p}(t) = \lim_{t \to 0} \frac{\bar{p}(t+\delta t) - \bar{p}(t)}{\delta t} .
$$

Il est possible de montrer que la matrice A-I possède une valeur propre O
et que toutes ses autres valeurs propres sont à partie réelle négative,
si bien que

$$
\lim_{t \to \infty} \bar{p}(t),
$$

existe et est indépendante des conditions initiales.

On voit facilement (à cause de la dépendance du paramètre de la
distribution du temps de service à l'unité centrale de n qui est la somme
des nombres de processus dans les trois files d'attente) que ce modèle n'est
pas un cas particulier des réseaux stochastiques de JACKSON, et que la
solution stationnaire de notre modèle ne peut être obtenue par une
application directe de son résultat. Par conséquent, une autre approche
est nécessaire.

Dans le paragraphe suivant nous utiliserons une partie des théorèmes du chapitre 2 pour obtenir une solution approchée des équations d'équilibre du système.
### 3.4 Application des théorèmes d'équivalence et de décomposabilité presque complète au modèle

On remarque aisément que notre modèle est un cas particulier du réseau de files d'attente de la figure 4. L'ensemble des terminaux peut être considéré comme un seul serveur exponentiel de débit de service $λ(n_c) = λn_c$, lorsque le nombre d'usagers actifs aux terminaux est $n_c$ ; ce serveur constitue le sous-système A. L'unité centrale est le serveur d'échanges, et le sous-système C se compose de la mémoire secondaire et du disque de fichiers. Ainsi donc le théorème 2.2 peut être appliqué et l'ensemble composé de l'UC, de la MS et du DF peut être remplacé par un seul serveur exponentiel de débit de service $u(n, \bar{s}) = A_0(n, \bar{s})p_0(n)u_0(n)$, d'après (2.16). Dans notre cas $\bar{s} = (n_c) = (N-n)$ c'est-à-dire l'état de A est entièrement défini par n, le nombre de processus qui s'exécutent dans le système à un moment donné. Ainsi nous obtenons un réseau équivalent de files d'attente (voyez figure 8) composé de deux serveurs jacksonniens de débit de service respectivement $λn_c$ et $u(n) = A_0(n)p_0(n)u_0(n)$ où $n_c+n = N$.

On sait que la distribution stationnaire de probabilité du nombre de processus qui s'exécutent dans le système, $n$, est égale à

$$ (3.17) \qquad p(n) = \frac{1}{H} \frac{\lambda^n}{(N-n)!} \prod_{i=1}^{n} u(i) , $$

où

$$ H = \sum_{n=0}^{N} \frac{\lambda^n}{(N-n)!} \prod_{i=1}^{n} u(i) $$
Compte tenu de (3.7) nous écrivons

$$ \prod_{i=1}^{n} u(i) = \prod_{i=1}^{n} A_{o}(i) p_{o}(i) u_{o}(i) = \frac{1}{c} \prod_{i=1}^{n} A_{o}(i) $$

ce qui donne

$$ (3.18) \qquad p(n) = \frac{1}{H} \frac{(\lambda c)^n}{(N-n)! \prod_{i=1}^{n} A_o(i)} $$

$$ H = \sum_{n=0}^{N} \frac{(\lambda c)^n}{(N-n)! \prod_{i=1}^{n} A_o(i)} $$

Dans la solution (3.18) il y a toujours une fonction inconnue $A_o(i) = \text{Prob}\{\text{UC active} | i \text{ processus s'exécutent dans le système}\}$, $i=1, \dots, N$. Afin de calculer $A_o(i)$, nous profiterons de la nature physique du problème, c'est-à-dire des valeurs des paramètres du modèle.

Le temps moyen de réflexion d'un usager au terminal est de l'ordre de

$$ 1/\lambda = 10 \text{ s.} $$

Des valeurs courantes pour les temps moyens de service de la MS et du DF pourraient être

$$ 1/u_1 = 10 \text{ ms} $$

et

$$ 1/u_2 = 50 \text{ ms.} $$

Supposons que le temps moyen de calcul d'un processus soit $c=1$ s et qu'il y ait $N=50$ terminaux. Nous avons alors
$(N-i)\lambda + p_o(i)u_o(i) \le 0,006$ , pour tout $i=1,...,N,$
et

$u_1+u_2+u_o(i) (1-p_o(i)) \ge 0,002$ , pour tout $i=1,...,N,$

si l'on pose pour le temps moyen de calcul entre deux requêtes d'E/S
$r=50$ ms. Aussi pourrons-nous admettre pour pratiquement toutes les
valeurs intéressantes des paramètres du modèle que

$$
\begin{equation} \tag{3.19}
\begin{aligned}
& (N-i)\lambda + \alpha(n_o)u_o(i)p_o(i) \ll \sum_{\ell=1}^{2} \alpha(n_\ell)u_\ell + \alpha(n_o)u_o(i) \sum_{\ell=1}^{2} p_\ell(i), \\
& \qquad \qquad \qquad \qquad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad i=1,\dots,N; \forall n_o, n_1 = 0,\dots,N.
\end{aligned}
\end{equation}
$$

Mais alors d'après le théorème 2.4 le système est presque complètement
décomposable et A_o(i) est approximativement égal à la probabilité que
l'unité centrale soit active dans le réseau fermé de files d'attente
représenté sur la figure 10 quand le nombre total de processus qui y
circulent est égal à i. Le réseau de la figure 10 peut être considéré
comme un modèle de système multiprogrammé de traitement de travaux par
trains (batch) [Bui]; le paragraphe suivant sera donc consacré à son
 étude.

3.5 Modèle d'un système de traitement de travaux par trains dans des conditions de forte charge.*

<footnote>* Ce paragraphe reprend en partie le travail [Brl] effectué en commun avec les autres membres du groupe de recherche sur la modélisation au LABORIA - IRIA.</footnote>
<figure><img src="image_13.png" /><figcaption>Figure 10</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 11</figcaption></figure>
### 3.5.1. Le modèle et ses équations

Considérons un système multiprogrammé à mémoire virtuelle paginée ; le système comporte une unité centrale (UC), une mémoire secondaire (MS) et un disque de fichiers (DF) (voyez figure 10). Tout comme dans le système de temps partagé décrit au paragraphe 3.1, à chacun de ces dispositifs est associée une file de requêtes.

Soit $i$ le nombre d'usagers (processus), tous statistiquement identiques et indépendants, qui s'exécutent dans le système. Désignant par $n_0$, $n_1$, $n_2$ respectivement les nombres d'usagers dans les files d'attente de l'UC, de la MS et du DF, nous avons à tout instant

(3.20)

$$i = n_0 + n_1 + n_2.$$

Dans le modèle, le comportement des processus est caractérisé par un temps de calcul suivi soit par un défaut de page après lequel avec une probabilité $p_1^i$ le processus entre dans la file d'attente de la MS, soit par une entrée/sortie de fichier auquel cas avec une probabilité $p_2^i$ le processus entre dans la file d'attente DF. Les processus qui terminent leur service à la MS ou au DF retournent dans la file d'attente de l'unité centrale. Nous supposons que le système travaille dans des conditions de charge telle qu'un degré de multiprogrammation constant $i$ puisse être maintenu. Ainsi la boucle autour de l'UC représente les processus qui après un service à l'UC, avec une probabilité $p_0^i$ quittent le système, mais sont immédiatement remplacés par un nouveau processus qui entre dans la file d'attente de l'unité centrale.
Nous faisons des hypothèses sur les temps de service semblables à celles des paragraphes 3.1 et 3.2 si bien que nous avons

$$ (3.21) \qquad p_o^i = p_o(i), \quad p_1^i = p_1(i), \quad p_2^i = p_2(i), $$

où

$p_o(i), p_1(i)$ et $p_2(i)$ sont données par (3.6) et (3.7).

Posons

$$ (3.22) \qquad u_o^i = u_o(i) \text{ de } (\dots, 5). $$

L'évolution du système est complètement décrite par la distribution conjointe de probabilité

$$ p^i(n_o, n_1, n_2, t) $$

du nombre de processus dans les trois files d'attente à tout instant $t$ ;
$n_o+n_1+n_2 = i$. Les équations différentielles aux différences du système s'obtiennent de la manière habituelle

$$ \frac{d}{dt} p^i(n_o, n_1, n_2, t) = - [V_o(l-p_o^i) + V_1 + V_2] p^i(n_o, n_1, n_2, t) + $$

$$ (3.23) \qquad u_1 p^i(n_o-1, n_1+1, n_2, t) + u_2 p^i(n_o-1, n_1, n_2+1, t) + $$

$$ u_o^i p_1^i(n_o+1, n_1-1, n_2, t) + u_o^i p_2^i(n_o+1, n_2-1, t), $$

où nous avons posé

$$ (3.24) \qquad p^i(l,j,k,t) = 0 $$
pour tout $\ell,j,k$ négatif ou supérieur à $i$, et

$$v_m = \begin{cases} u_m, & \text{sin } n_m > 0, \\ 0, & \text{sinon,} \end{cases}$$

pour $m=0,1,2$.

Le modèle est un cas particulier des réseaux de Jackson [Jal] et la solution stationnaire $p^i(n_o, n_1, n_2) = \lim_{t \to \infty} p^i(n_o, n_1, n_2, t)$ s'écrit

$$(3.25) \qquad p^i(n_o, n_1, n_2) = \frac{1}{G(i)} \left( \frac{p_1^i u_o^i}{u_1} \right)^{n_1} \left( \frac{p_2^i u_o^i}{u_2} \right)^{n_2},$$

où

$$(3.26) \qquad G(i) = \sum_{n_1, n_2} \left( \frac{p_1^i u_o^i}{u_1} \right)^{n_1} \left( \frac{p_2^i u_o^i}{u_2} \right)^{n_2}, \quad 0 \le n_1 + n_2 \le i.$$

On vérifie facilement cette solution par remplacement direct dans (3.23)

avec

$$\frac{d}{dt} p(n_o, n_1, n_2, t) = 0.$$

Comme il s'agit d'un système de traitement de travaux par trains, le débit du système (nombre moyen de processus traités par unité de temps) constitue une mesure adéquate des performances du système. Ce débit s'obtient de la façon suivante. En moyenne chaque processus effectue au total $\frac{1}{p_o^i}$ passage par l'unité centrale utilisant donc un temps moyen total de calcul

$$\frac{1}{p_o^i u_o^i}$$
Dans une longue période de temps T, l'UC est active pendant un temps $A_o^i T$, où $A_o^i$ est la probabilité que la file d'attente de l'UC soit non vide.

$A_o^i$ appelé utilisation de l'unité centrale est égal à

$$A_o^i = \sum_{\substack{0 \le n_1 < i \\ 0 \le n_2 < i}} p^i(n_o, n_1, n_2),$$

c'est-à-dire directement de (3.26) (voyez [Bu1])

$$(3.27) \qquad A_o^i = \frac{G(i-1)}{G(i)}.$$

Il s'en suit que le nombre moyen de processus traités pendant le temps T vaut

$$A_o^i T u_o^i p_o^i$$

et que le débit du système devient égal à

$$\theta^i = A_o^i u_o^i p_o^i.$$

Compte tenu de (5.21) nous avons

$$\theta^i = \frac{1}{c} A_o^i.$$

### 3.5.2 Degré optimum de multiprogrammation dans un système sans entrées/sorties

Considérons maintenant un modèle à deux serveurs composé d'une unité centrale et d'un dispositif de mémoire secondaire (voir figure 11).

Sans prendre ainsi en compte le comportement lié aux entrées/sorties nous allons aborder le problème de la détermination analytique d'une expression pour le degré de multiprogrammation $i_o$ qui maximise le
débit du système. Ceci apparaît comme une tâche difficile pour le
modèle à trois serveurs (c'est-à-dire avec un disque de fichiers), et
même dans le cas simplifié que nous considérerons nous saurons seulement
obtenir une valeur approchée qui constitue en même temps une borne
inférieure.

De l'équation (3.23) adaptée au cas du système à deux
serveurs (en posant $p_2^i = 0$, ou ce qui revient au même $r=\infty$) nous obtenons

$$
(3.28') \qquad A_0^i = \frac{1}{1+y(i)},
$$

où

$$
(3.29) \qquad y(i) = \frac{z^i (1-z)}{1-z^i}
$$

et

$$
(3.30) \qquad z = \frac{i^k}{\alpha u_1^k},
$$

en utilisant la fonction de durée de vie de Belady (3.9).

Posons

$$
(3.31) \qquad b = \frac{1}{\alpha u_1^k}.
$$

Il est clair que maximiser $A_0^i$ revient à minimiser $y(i)$.

Considérons le cas

$$
(3.32) \qquad \frac{1}{u_1} \ll \alpha \frac{M^k}{i^k}
$$
où le temps moyen de calcul entre deux défauts de page consécutifs d'un
processus est nettement supérieur au temps moyen de service de la mémoire
secondaire. Nous avons alors

$z \ll 1,$

et donc

$$
u(i) \approx y_1 = z^i .
$$

En considérant i comme une variable continue et en prenant

$$
\frac{dy_1}{di} = 0
$$

nous voyons que $y_1$ atteint son minimum pour

$$
(3.33) \qquad i_1 = \frac{1}{e} \left(\frac{1}{b}\right)^{\frac{1}{k}} .
$$

Les divers exemples numériques (figures 12 à 15) montrent que $i_1$
est un bon estimateur du degré optimum de multiprogrammation $i_o$. Nous
allons voir maintenant que

$$
(3.34) \qquad i_1 \le i_o .
$$

Soit la fonction

$$
(3.35) \qquad y_2 = \frac{z^{\frac{i}{k}}}{1-z^{\frac{i}{k}}}
$$

Notons que $y_2$ aussi bien que $y_1$ est minimisée par $i_1$ et l'on peut montrer qu'elles n'ont qu'un seul minimum positif. Remarquons également que

$$
(3.36) \qquad y(i) = y_2(1-z),
$$

et que (1-z) est une fonction positive décroissante de i. C'est pourquoi
entre 0 et i₁, où y₂ est une fonction décroissante, y(i) sera aussi une
fonction décroissante et la valeur de i qui minimise y ne saurait se
trouver dans l'intervalle ouvert (0,i₁). Ceci montre que i₁ est une
borne inférieure de i₀.
<figure><img src="image_15.png" /><figcaption>Figure 12</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Figure 13</figcaption></figure>
3.6 - Résultats du modèle.

Ainsi nous obtenons une solution approchée pour le nombre
total de processus dans les trois files d'attente en posant

$$
(3.37) \qquad A_o(i) \approx A_o^i
$$

(où $A_o^i$ est donné par (3.27)) dans (3.18).

Remarquons aussi que $p^i(n_o, n_1, n_2)$ donné par (3.25) est approximativement égal à la probabilité d'avoir $(n_o, n_1, n_2)$ processus dans les trois files d'attente du modèle de départ conditionnée sur le fait que $n_o+n_1+n_2=i$, c'est-à-dire

$$
(3.38) \qquad p(n_o, n_1, n_2 \mid \sum_{j=0}^{2} n_j = i) \approx p^i(n_o, n_1, n_2).
$$

Nous pouvons par conséquent calculer des valeurs approchées pour les
probabilités d'état p(n₀, n₁, n₂, n₃) comme étant

$$
(3.39) \qquad p(n_o, n_1, n_2, n_c) = p(N-n_c) p^{N-n_c}(n_o, n_1, n_2).
$$

Le temps moyen de réponse W du système s'obtient grâce à la formule de
LITTLE (voyez [Li1]) :

$$
W = \frac{\bar{n}}{\lambda(N-\bar{n})},
$$

où $\bar{n}$ est le nombre moyen total de processus dans les trois files d'attente
En considérant $\bar{n}$ comme une variable nous avons

$$
(3.40) \qquad \frac{\Delta W}{W} \approx \frac{N}{N-\bar{n}} \frac{\Delta \bar{n}}{\bar{n}} .
$$

Nous voyons que pour $\bar{n}$ voisin de N une petite erreur relative sur $\bar{n}$ entraînera une importante erreur sur W, par exemple prenons
<figure><img src="image_17.png" /><figcaption>Figure 14</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Figure 15</figcaption></figure>
$N = 20,$

$\bar{n} = 19,$

$$ \bar{\frac{\Delta n}{n}} = 0,5 \%, $$

alors

$$ \frac{\Delta W}{W} \approx \frac{20}{20-19} 0,5 \% = 10 \%. $$

C'est la raison pour laquelle, quand le système est saturé ($\bar{n}$ devient proche de N), les valeurs obtenues pour l'espérance du temps de réponse peuvent être entachées d'erreur.

Les résultats numériques obtenus à partir de notre modèle avec la fonction de durée de vie de Belady (3.9) sont présentés sur les figures 16 à 31 où nous avons tracé l'utilisation de l'unité centrale et le temps moyen de réponse du système en fonction de N (le nombre de terminaux) pour un large spectre de paramètres du système. Dans ces exemples le temps moyen de calcul d'un processus c et le temps moyen de réflexion d'un usager $1/\lambda$ sont maintenus constants respectivement à 500 ms et 10 s. Nous avons posé $\alpha= 0,01$ et pour le temps moyen de calcul entre deux requêtes successives d'entrée/sortie r=20 ms.

Les figures 16 et 17 montrent l'effet du nombre de terminaux N respectivement sur l'utilisation de l'unité centrale et le temps moyen de réponse pour un ensemble de paramètres du système avec une mémoire principale de taille M=128 pages. Nous constatons qu'une amélioration du comportement des programmes (l'exposant de localité k de (5.9) augmentant de 1,5 à 2,5) peut provoquer un très important accroissement de l'utilisation de l'UC de même qu'une amélioration du temps moyen de réponse du système. Nous voyons aussi qu'il existe un nombre optimum
de terminaux qui maximise l'utilisation de l'unité centrale, et que,
si N dépasse ce nombre, l'utilisation de l'UC accuse une baisse
brutale tandis que le temps moyen de réponse monte très rapidement. Les
mêmes courbes sont tracées sur les figures 18 et 19 pour une mémoire
principale de 256 pages mais les autres paramètres inchangés. Nous notons
un accroissement marqué de l'utilisation de l'unité centrale et du
nombre optimum de terminaux, et une importante amélioration dans l'espé-
rance du temps de réponse. L'effet du temps moyen de service du support
de pagination de la mémoire secondaire ($t_{MS} = \frac{1}{u_1}$) est illustré par les
figures 22, 23 et 20, 21 où $t_{MS}$ est ramené de 10 ms (sur les figures
22, 23) à 5 ms sans modifier les autres paramètres. L'influence de la
rapidité du disque de fichier, est étudiée sur les figures 22, 23 et
16, 17.

Les mêmes résultats numériques obtenus avec l'approximation
de CHAMBERLIN de la fonction de durée de vie sont tracés sur les
figures 24 à 31. Les courbes portant les numéros 1, 2 et 3 sur chaque
figure correspondent respectivement aux valeurs suivantes des paramètres
b et d dans (3.10) :

b = 20 ms , d = 60 pages ;

b = 25 ms , d = 50 pages ;

b = 10 ms , d = 15 pages .

Ces valeurs ont été empruntées à[Ch1]. Nous avons posé comme précédemment
c=500 ms, 1/λ = 10 s et r=20 ms.

Nous voyons que ces courbes présentent le même comportement
que celles obtenues avec la fonction de durée de vie de Belady.

Dans l'ensemble, il apparaît que le temps moyen de réponse
du système croît relativement lentement avec N (le nombre de terminaux)
jusqu'à ce que la valeur de N qui maximise l'utilisation de l'unité
centrale soit atteinte ; lorsque le nombre de terminaux dépasse cette
M=128 pages

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

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

0.7 utilisation d'UC

0.5

k=2,5

0.3

k=2,0

k=1,5

0.1

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

nombre de terminaux N

<caption>Figure 16</caption>

temps moyen de réponse (s)

13

9

7

5

3

1

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

nombre de terminaux N

k=1,5

k=2,0

k=2,5

<figure><img src="image_19.png" /><figcaption>Figure 17</figcaption></figure>
M= 256 pages
tMS=5 ms

tDF=30 ms

utilisation d'UC

<figure><img src="image_20.png" /><figcaption>Figure 18</figcaption></figure>

temps moyen de réponse (s)

<figure><img src="image_21.png" /><figcaption>Figure 19</figcaption></figure>
M=256 pages

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

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

utilisation d'UC

temps moyen de réponse (s)

<figure><img src="image_22.png" /><figcaption>Figure 20</figcaption></figure>

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

nombre de terminaux N

<caption>Figure 21</caption>
M=256 pages

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

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

utilisation d'UC

0.7

0.5

2,5

0.3

1,5

0.1

4

8

12

16

20

24

28

nombre de terminaux N

<figure><img src="image_24.png" /><figcaption>Figure 22</figcaption></figure>

4

8

12

16

20

24

28

temps moyen de réponse (s)

15

13

11

9

7

5

3

1

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

nombre de terminaux N

<caption>Figure 23</caption>
M=128 pages

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

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

utilisation d'UC

0.7

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

0.5

1

0.3

0.1

4

8

12

16

20

24

nombre de terminaux N

Figure 24

temps moyen de réponse (s)

15

13

11

9

7

5

3

1

1

2

3

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

4

8

12

16

18

20

24

28

nombre de terminaux

Figure 25
M=256 pages

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

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

utilisation d'UC

0.7

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

1

0.55

0.3

0.1

4

12

16

20

24

28

nombre de terminaux N

<caption>Figure 26</caption>

temps moyen de réponse (s)

15

13

11

9

7

5

3

1

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

4 8 12 16 20 24 28

nombre de terminaux N

<caption>Figure 27</caption>
M=256 pages

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

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

utilisation d'UC

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

nombre de terminaux N.

<caption>Figure 28</caption>

temps moyen de réponse (s)

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

nombre de terminaux N.

<caption>Figure 29</caption>
M=256 pages

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

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

utilisation d'UC

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

nombre de terminaux N

<caption>Figure 30</caption>

temps moyen de réponse (s)

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

nombre de terminaux N

<caption>Figure 31</caption>
M = 256 pages

k = 2

t<sub>1/2</sub> = 10 ms

M = 256 pages

k = 2

t<sub>1/2</sub> = 10 ms

<figure><img src="image_34.png" /><figcaption>Figure 32</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>Figure 33</figcaption></figure>
valeur, le temps de réponse "explose". C'est pourquoi il semble qu'un bon point de fonctionnement du système se situe légèrement en dessous du nombre de terminaux qui maximise l'utilisation de l'unité centrale.

Considérons un système sans entrées/sorties. La formule (3.18) reste valable pour la distribution de probabilité du nombre courant de processus dans le système. Nous avons, comme pour le modèle complet,

$$ (3.41) \qquad A_o(i) \approx A_o^i, $$

mais $A_o^i$ est cette fois l'utilisation de l'unité centrale dans le modèle à deux serveurs de 3.5. Ce résultat peut être déduit soit de la connaissance du régime transitoire de la partie de traitement du système (l'unité centrale et la mémoire secondaire), soit du théorème 2.4 sur la décomposabilité presque complète. Notons que, dans ce cas, l'inégalité (2.26) s'avère plus convaincante que (2.23).

Nous avons, comme précédemment

$$ (3.42) \qquad p(n_o,n_l|n_o+n_l=i) \approx p^i(n_o,n_l), $$

et donc les probabilités d'état $p(n_o,n_l,n_c)$ valent approximativement

$$ (3.43) \qquad p(n_o,n_l,n_c) \approx (N-n)p^{N-n_c}(n_o,n_l). $$

L'espérance du temps de réponse se calcule en utilisant la formule de LITTLE et (3.40) reste évidemment valable.
Les résultats numériques obtenus montrent un comportement semblable à celui du système avec un disque de fichiers. Sur les figures 32, 33 et 34, 35 nous avons représenté l'utilisation de l'unité centrale et le temps moyen de réponse pour deux ensembles de paramètres du système.

L'approximation de la fonction de durée de vie utilisée est celle de Belady (3.9). On remarque que le fait d'augmenter le temps moyen de calcul c des processus a pour effet d'augmenter l'utilisation maximum de l'unité centrale et de hâter l'écroulement du système. De façon générale, celui-ci semble plus marqué que dans le cas du modèle avec des entrées/sorties.
<figure><img src="image_36.png" /><figcaption>Figure 34</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>Figure 35</figcaption></figure>
REFERENCES

[Jal] J.R.Jackson "Jobshop-like queuing systems"
Management Science,10,1,Octobre 1963,pp.131-142.

[Sil] H.Simon et A.Ando
"Aggregation of variables in dynamic systems"
Econometrica, Vol.20, n°2, avril 1961, pp.114-138.

[Anl] A.Ando et F.M.Fisher
"Near-decomposability, partition and aggregation
and the relevance of stability discussions"
International Economic Review, vol.4, n°1, pp.53-67 (1963).

[Col] P.Courtois
"On the near-complete-decomposability of networks
of queues and of stochastic models of multiprogramming
computing systems"
Carnegie Mellon, novembre 1971.

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

[Sal] J.Saltzer "A simple linear model of demand paging performance" Comm. ACM, 17,4, pp.181-186 (1974).

[Ch1] D.Chamberlin, S.Fuller, L.Liu
"An analysis of page allocation strategies for
multiprogramming systems with virtual memory"
IBM J.Res.Develop.septembre 1973.

[Bul] J.Buzen "Queueing network models of multiprogramming"
Thèse Ph.D., Harvard University, 1971.

[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 in-
formatique, IRIA, Toulouse, juin 1973.

[Lil] J.Little "A proof of the queueing formula $L=\lambda W$"
Operations Research, 9, 1961, pp.383-387.