# Un modèle d'analyse des performances d'ordinateurs multiprogrammés à mémoire virtuelle

Dominique Potier, Jacques Leroudier, Marc Badel

► To cite this version:

Dominique Potier, Jacques Leroudier, Marc Badel. Un modèle d'analyse des performances d'ordinateurs multiprogrammés à mémoire virtuelle. [Rapport de recherche] IRIA-RR-152, IRIA. 1976, pp.43. hal-04716345

HAL Id: hal-04716345

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

Un modèle d'analyse
des performances d'ordinateurs
multiprogrammés
à mémoire virtuelle

D. Potier, J. Leroudier,
M. Badel

Rapport de Recherche n° 152
Janvier 1976
UN MODELE D'ANALYSE DES PERFORMANCES
D'ORDINATEURS MULTIPROGRAMMÉS A MÉMOIRE VIRTUELLE

D. Potier, J. Leroudier, M. Badel

IRIA/LABORIA

Abstract :

We present in this paper a global model of a virtual memory computer system. The model is analyzed and we point out simple relations between architecture parameters, program behaviour parameters and some performance measures such as resource utilization or overhead ratio. An analytical and a simulation method are used to solve the model and the comparison of the results which are obtained show that the analytical solution provides satisfactory results even if the necessary assumptions do not hold.

Résumé :

Nous développons dans cet article un modèle global d'ordinateur multiprogrammé à mémoire virtuelle. Le modèle est analysé et un certain nombre de lois de fonctionnement sont dégagées qui mettent en évidence des relations simples entre les paramètres de l'architecture, les paramètres de comportement des programmes et les mesures de performances : utilisation des ressources, taux d'overhead. Deux méthodes de résolution, par analyse mathématique et par simulation sont présentées et les résultats obtenus montrent que la méthode de résolution mathématique fournit, même dans le cas où les hypothèses nécessaires à son application ne sont pas satisfaites, des résultats comparables à ceux obtenus par simulation.

<figure><img src="image_3.png" /></figure>
# I - INTRODUCTION

Les années soixante avec la machine ATLAS[30] ont vu l'apparition des premiers ordinateurs à mémoire virtuelle [19]. Le mécanisme de traduction dynamique des adresses permettait de résoudre élégamment les problèmes de gestion et de partage de la mémoire dans les ordinateurs importants de l'époque conçus pour travailler en temps partagé. Les programmes pouvaient alors être déchargés de la mémoire principale et y être rechargés à des emplacements physiques différents, sans que soit nécessairement préservée la contiguité logique de l'information dans la mémoire physique.

En plus d'un avantage propre au temps partagé, ce mécanisme permet d'exécuter des programmes dont l'espace d'adressage a une taille supérieure à celle de la mémoire physique de la machine, sans que pour celà l'utilisateur ait à consanguire d'arbres de recouvrement (overlay). Cette possibilité est mise en oeuvre en ne chargeant que la partie utile d'un programme à un instant donné (les instructions en cours et les données accédées) et en modifiant cette partie utile à la demande au cours de l'exécution (chargement "à la demande"). C'est alors que le terme de mémoire virtuelle prend son plein sens et que le mécanisme de traduction dynamique des adresses est exploité au mieux de ses possibilités.
Une telle solution se généralisa rapidement à d'autres machines telles que GE 645 et IBM 360/67 sur lesquelles furent implémentés des systèmes d'exploitation qui utilisaient les mécanismes de traduction d'adresses : MULTICS [9] MTS [42], CP67 [34]. Actuellement, ces mécanismes sont disponibles sur les ordinateurs de haut de gamme récents tels que IBM 370 ou CII-IRIS 80 exploités sous les systèmes d'exploitation VM [27] ou VS chez IBM, et GEMAU [26] développé à l'Université de Grenoble.

Toutefois, les avantages apportés aux utilisateurs par la technique de la mémoire virtuelle se traduisent par une charge supplémentaire sur certaines ressources du système. D'une part, les algorithmes d'allocation dynamique des blocs d'information, ou page, ainsi que les tables nécessaires pour réaliser la traduction entre adresses virtuelles et adresses réelles augmentent le volume du système d'exploitation et réduisent d'autant l'espace mémoire disponible aux utilisateurs. D'autre part, par le jeu du mécanisme d'allocation dynamique, chaque fois qu'une page référencée ne se trouve pas en mémoire principale, le programme en cours d'exécution est interrompu, son contexte sauvegardé, les algorithmes de pagination sont exécutés et les transferts de la page requise et éventuellement de la page à décharger sont initialisés. Ces opérations entraînent un dépassement ("overhead") du temps d'unité centrale au détriment de l'exécution des programmes utilisateurs. Enfin, la pagination a pour effet d'imposer un échange important d'information entre la mémoire principale et la mémoire secondaire qui supporte la mémoire virtuelle. On conçoit alors que le mécanisme de pagination va faire apparaître, à forte charge, un goulot d'étranglement sur la mémoire secondaire en imposant des temps d'attente à chaque transfert de pages de plus en plus importants dûs à l'encombrement du canal de pagination. Lorsque le nombre de programmes qui se partagent les ressources du système augmente, le chargement à la demande des pages et la libre compétition des programmes dans la mémoire physique provoquent un phénomène en avalanche connu sous le nom d'écroulement ou thrashing. [21, 38] qui peut conduire à une dégradation importante des performances du système.
Nous voyons donc qu'à côté de problèmes spécifiquement "système" liés à la gestion des espaces virtuels, le fonctionnement des machines à mémoire virtuelle pose des problèmes de performances qu'il est difficile d'appréhender directement en raison de la complexité même de l'organisation de ces machines. Durant ces dix dernières années, de nombreux travaux ont été publiés dans cette direction pour étudier les performances de différents algorithmes de pagination [11, 20, 22, 36] et pour évaluer les performances de systèmes à mémoire virtuelle [5, 24, 35, 37, 41]. Dans le même temps s'est développé l'étude des lois de comportement des programmes vis à vis des ressources qu'ils utilisent : mémoire centrale, unité entrée-sortie, unité centrale, et plusieurs modèles de ces comportements ont été proposés [8, 11, 13, 17, 31]. Associé à un modèle d'architecture de système, ce type de modèle permet de caractériser et d'analyser globalement les performances d'une architecture en faisant apparaître les relations entre les phénomènes de comportement de programme et l'organisation de l'architecture, et en permettant une analyse quantitative de ces relations [5].

Nous développons dans cet article un modèle global d'ordinateur multiprogrammé à mémoire virtuelle à partir de l'approche présentée dans [5]. Le modèle est organisé pour prendre en compte les aspects essentiels de tels systèmes, et ne représente donc pas le modèle d'un système particulier. Toutefois, le lecteur qui souhaiterait se référer à un système concret peut trouver un exemple simple dans le système CP-67 [34] ou VM [27]. Le but de cette étude est de proposer une analyse quantitative du fonctionnement d'un ordinateur multiprogrammé à mémoire virtuelle, et d'atteindre ainsi à une compréhension physique des phénomènes.

Le paragraphe 2 est consacré à la présentation du modèle utilisé et des hypothèses retenues. Dans le paragraphe 3 le modèle est analysé et un certain nombre de lois de fonctionnement sont dégagées qui mettent en évidence des relations simples entre les paramètres de l'architecture, les paramètres de comportement des programmes et les mesures de performances : utilisation des ressources, taux d'overhead. Deux méthodes de résolution, par analyse mathématique et par simulation sont présentées au paragraphe 4 et les résultats obtenus montrent que la méthode de résolution mathématique fournit, même dans le cas où les hypothèses nécessaires à son application ne sont pas satisfaites, des résultats comparables à ceux obtenus par simulation. Dans le dernier paragraphe, le modèle est utilisé pour étudier le comportement du système modélisé sous différentes hypothèses de fonctionnement et dégager quelques principes de gestion d'un système multiprogrammé à mémoire virtuelle.
## 2 - LE MODELE

### 2.1 - Structure et hypothèses

Le modèle est construit pour représenter les fonctions fondamentales du système étudié :

- allocation de l'unité centrale

- gestion de la mémoire

- gestion des entrées-sorties

et le comportement des programmes vis à vis de ces ressources. Chacune des fonctions citées est caractérisée de façon globale, sans que soient détaillés les mécanismes associés à chaque traitement ; ainsi, une opération d'entrée-sortie sur disque sera uniquement représentée par un temps de service -somme du temps d'accès -déplacement du bras et délai de rotation- et du temps de transfert.

Les évènements auxquels donne lieu l'exécution des programmes sont décrits comme des processus stochastiques. Ces évènements sont supposés indépendants entre eux et nous analysons le modèle dans l'hypothèse où tous les programmes sont représentés par le même modèle de comportement. Les mesures de performances qui nous intéressent concernant des problèmes d'engorgement et des phénomènes d'attente, nous modélisons l'architecture du système par un réseau de files d'attente où chaque ressource du système est représentée par un serveur avec une file d'attente associée.

En fonction de ces hypothèses de base, le modèle représenté sur la figure 1 est défini comme suit.

#### 2.1.1 - Les consoles

Le comportement des utilisateurs est modélisé par leur temps de réflexion $τ$, c'est-à-dire le temps qui s'écoule entre l'instant où l'utilisateur reçoit le contrôle de sa console et l'instant où il envoie une nouvelle commande au système. Soit $F_d(t)$ la fonction de distribution de $τ$, et d sa valeur moyenne. Remarquons que $d=0$ signifie que le nombre de programmes dans le système est maintenu constamment égal au nombre de consoles noté $N$.
### 2.1.2 - Le système

#### a - Gestion de l'unité centrale (UC)

Les programmes arrivant des consoles sont mis en file d'attente derrière l'UC dans l'ordre de leur arrivée dans cette file. L'exécution d'un programme sur l'UC peut être interrompue pour quatre raisons différentes :

1. fin de quantum : auquel cas le programme est remis en attente d'UC.

2. défaut de page : dans ce cas le programme est remis en attente derrière la mémoire secondaire.

3. entrée-sortie : dans ce cas le programme est mis en attente derrière le disque de fichier.

4. fin d'exécution : dans ce cas le programme quitte le système et le contrôle est rendu à la console qui l'avait généré.

#### b - Gestion de la mémoire secondaire (MS)

Les demandes de transfert de page arrivant à la MS sont traitées dans l'ordre "premier-arrivé-premier-servi". Le fonctionnement détaillé de la MS n'est pas pris en compte et il est uniquement représenté par le temps total nécessaire pour traiter un défaut de page. Ce temps est considéré comme une variable aléatoire de distribution $F_{MS}(t)$ et de moyenne $T_{MS}$.

Remarquons qu'il correspond en général à deux opérations, une écriture et une lecture qui peuvent se réduirent à une lecture dans le cas où la page remplacée n'a pas été modifiée. La valeur moyenne $T_{MS}$ représente donc le temps moyen de traitement d'un défaut de page par la mémoire secondaire, y compris éventuellement la réécriture de la page déchargée.

#### c - Gestion du disque de fichiers (DF)

Le disque de fichiers est géré comme la MS et son fonctionnement est uniquement caractérisé par le temps total nécessaire pour exécuter une
demande d'E/S. Comme précédemment, ce temps est considéré comme une variable
aléatoire de distribution $F_{DF}(t)$ et de moyenne $T_{DF}$;

### 2.1.3 - Le comportement des programmes

L'exécution d'un programme sur l'UC donne lieu à différents évènements provoqués par la demande ou la libération des ressources UC, MS et DF. En raison de l'hypothèse de base d'indépendance de ces différents évènements, le modèle de comportement de programme utilisé est obtenu par la superposition des modèles de comportement vis à vis de chacune des ressources. Nous avons donc successivement

- le modèle de temps UC total requis pour l'exécution d'un programme considéré comme une variable aléatoire de distribution $F_c(t)$ et de moyenne $c$;

- le modèle d'entrée-sortie : le temps virtuel entre deux E/S d'un programme est considéré comme une variable aléatoire de moyenne $r$ distribuée suivant $F_r(t)$;

- le modèle de défaut de page : le temps virtuel entre deux défauts de page consécutifs d'un programme est considéré comme une variable aléatoire de moyenne $e$ distribuée suivant $F_e(t)$;

- le modèle d'allocation de quantum UC : la durée d'un quantum est supposée constante et égale à $q$;

La figure 2 représente ces quatre modèles et leur superposition
qui fournit le modèle de comportement.

Le temps moyen UC total et le taux d'entrée-sortie sont intrinsèques au programme et leurs valeurs ne dépendent donc pas de l'état du système. En revanche, le taux de défaut de page n'est pas intrinsèque au programme et dépend en particulier de l'allocation de la mémoire physique. Pour représenter cette dépendance, nous utilisons le modèle de durée de vie de BELADY et KUEHNER [8] qui relie le temps moyen $e$ entre deux défauts de page consécutifs d'un programme au nombre de pages $m$ qui lui sont allouées. Cette relation s'écrit

$$ (1) \qquad e = \alpha m^k, $$
où $\alpha$ dépend du cycle de base de la machine et de la programmation des programmes, et $k$ mesure la localité des programmes. Les observations rapportées dans [ 8 ] et [13] montrent que

$$1 \le k \le 4.$$

Les valeurs supérieures de $k$ correspondant à des programmes ayant la propriété de s'exécuter dans des espaces de petites tailles avec un taux de défaut de page acceptable.

Les programmes étant représentés par le même modèle de comportement (cf. 2.1), on admet qu'en moyenne ils se partagent également l'espace de mémoire disponible $M$, soit une allocation mémoire pour chaque programme de :

$$(2) \qquad m = \frac{M}{n},$$

et

$$(3) \qquad e = \alpha \left(\frac{M}{n}\right)^k,$$

où $n$ est le degré de multiprogrammation, c'est-à-dire le nombre de programmes se partageant la mémoire :

$n = N$ - le nombre de consoles actives.

### 2.1.4 - Les overheads

Les overheads représentent les temps d'unité centrale propres à l'exécution du moniteur. Ils apparaissent à chaque interruption de service d'un programme sur l'unité centrale, et correspondent aux opérations de changement de contexte, de pagination, et de lancement d'une entrée-sortie. Ces quantités sont considérées dans le modèle comme constantes avec pour valeurs :

* $O_c$ dans le cas de la fin d'exécution d'un programme,

* $O_e$ dans le cas d'une faute de page,

* $O_r$ dans le cas d'une entrée-sortie,

* $O_q$ dans le cas d'une fin de quantum.
## 2.2 - Les critères de performance

Nous nous intéressons à deux catégories de mesures de performances. D'une part, l'utilisation des ressources du système : UC, MS, DF, d'autre part le bénéfice obtenu par la multiprogrammation mesuré par le rapport

$$D(n) = \frac{\text{Débit du système en multiprogrammation de degré n}}{\text{Débit du système en monoprogrammation}}$$

$D(n)$, appelé "dilatation" [4, 33], mesure la dilatation du temps réel obtenu par la multiprogrammation de n programmes. L'utilisation de l'UC, de la MS et du DF pour un degré de multiprogrammation n donné sont notés respectivement, $A_{UC}^{(n)}$, $A_{MS}^{(n)}$ et $A_{DF}^{(n)}$.

Dans la suite nous présentons les techniques de résolution du modèle qui permettent d'obtenir les mesures de performances ci-dessus définies en fonction d'une part des paramètres de l'architecture M, $T_{MS}$, $T_{DF}$, N et des paramètres de comportement de programmes c, r, $\alpha$, k, d. Ces études sont menées à degré de multiprogrammation constant en supposant $d=0$ c'est-à-dire qu'un programme dont l'exécution est achevée est immédiatement remplacé par un autre programme et l'on a donc

$$n = N.$$

Par la suite la notation n sera seule utilisée.

En résumé le modèle est défini par deux familles de paramètres :

- Les paramètres de l'architecture qui décrivent la configuration, les caractéristiques des unités périphériques (MS, DF), et certains éléments du système d'exploitation :

n degré de multiprogrammation,

M nombre de pages de la mémoire physique,

$T_{MS}$ temps moyen d'accès et de transfert d'une page par la MS,

$T_{DF}$ temps moyen d'accès et de transfert d'un enregistrement sur la DF

q valeur du quantum UC,

$O_c, O_e, O_r, O_q$ overheads,
■ Les paramètres de comportement des programmes et des utilisateurs :

d temps moyen de réflexion aux consoles,

c temps moyen UC total requis pour l'exécution d'un programme,

r temps moyen virtuel entre deux E/S consécutives,

α, k paramètres de la loi de durée de vie.

Par ailleurs, les variables dont les moyennes sont définies ci-dessus sont plus complètement caractérisées par leurs lois de distribution $F_{MS}(t)$, $F_{DF}(t)$, $F_d(t)$, $F_c(t)$, $F_r(t)$, $F_e(t)$. Dans les deux paragraphes qui suivent nous établissons des relations simples entre les différents paramètres et les mesures de performances sans qu'il soit nécessaire de préciser les lois de distribution, et nous montrerons ensuite en calculant les mesures de performances que les résultats obtenus sont peu sensibles à la forme de ces lois.

## 3 - ANALYSE DU MODELE

### 3.1 - Propriétés générales du modèle

Avant de résoudre complètement le modèle proposé par une technique ou une autre, il convient de noter qu'un certain nombre de résultats importants peuvent être obtenus simplement, en l'absence de toute hypothèse supplémentaire. Ces résultats sont établis en appliquant à notre modèle les théorèmes de CHANG et de LAVENBERG [18] sur les réseaux de files d'attente. Ces théorèmes, dont les énoncés et les hypothèses sont rapportés en Annexe I, permettent d'écrire des relations simples entre les taux d'utilisation des unités dans un réseau à files d'attente, et les paramètres du réseau. Appliqués au modèle étudié, ils conduisent aux deux relations suivantes (cf. Annexe I) :

$$ (5) \qquad A_{MS}(n) = \Pi_e \frac{T_{MS}}{s} A_{UC}(n), $$

$$ (6) \qquad A_{DF}(n) = \Pi_r \frac{T_{DF}}{s} A_{UC}(n), $$

où s désigne le temps moyen entre deux interruptions consécutives sur l'UC, y compris les overheads éventuels, lorsque l'UC est active, et $\Pi_e$ et $\Pi_r$, la
probabilité que l'interruption soit dûe respectivement à un défaut de page et
à une requête d'entrée-sortie. Pour évaluer s, Π<sub>e</sub> et Π<sub>r</sub>, considérons une période
de fonctionnement du système où l'UC a été active pendant une durée de temps T,
et soit T' la durée pendant laquelle l'activité de l'UC a été consacrée
uniquement aux programmes utilisateurs. Dans le cas où $\underline{\underline{O}}_c = \underline{\underline{O}}_e = \underline{\underline{O}}_r = \underline{\underline{O}}_q = 0$,
on a évidemment T = T'. Pour évaluer dans le cas général la relation entre T et
T', remarquons que sur la durée T il s'est produit en moyenne

$\frac{T'}{c}$ fins d'exécution,

$\frac{T'}{e}$ défauts de page,

$\frac{T'}{r}$ entrée-sortie,

$\frac{T'}{q}$ fins de quantum,

soit un nombre d'interruptions égal à

$$
T'\left(\frac{1}{c} + \frac{1}{e} + \frac{1}{r} + \frac{1}{q}\right),
$$

et un overhead total donné par

$$
T'\left( \frac{\bigcirc}{c} + \frac{\bigcirc}{e} + \frac{\bigcirc}{r} + \frac{\bigcirc}{q} \right),
$$

On en déduit que le temps moyen s entre deux interruptions
consécutives sur l'UC s'écrit :

$$
(7) \qquad s = \frac{T}{T'\left(\frac{1}{c} + \frac{1}{e} + \frac{1}{r} + \frac{1}{q}\right)},
$$

et que

$$
(8) \quad T = T' \left( 1 + \frac{\bigcirc}{c} + \frac{\bigcirc}{e} + \frac{\bigcirc}{r} + \frac{\bigcirc}{q} \right),
$$

d'où finalement

$$
(9) \quad s = \frac{\begin{smallmatrix} \bigcirc & \bigcirc & \bigcirc & \bigcirc \\ 1 & + \frac{\bigcirc}{c} & + \frac{\bigcirc}{e} & + \frac{\bigcirc}{r} + \frac{\bigcirc}{q} \\ \hline \frac{1}{c} + \frac{1}{e} + \frac{1}{r} + \frac{1}{q} \end{smallmatrix}}{\frac{1}{c} + \frac{1}{e} + \frac{1}{r} + \frac{1}{q}} .
$$
Les probabilités $\Pi_e$ et $\Pi_r$ s'obtiennent directement à partir du rapport des nombres d'évènements, soit

$$ (10) \qquad \Pi_e = \frac{\frac{T}{e}}{T\left(\frac{1}{c} + \frac{1}{e} + \frac{1}{r} + \frac{1}{q}\right)} = \frac{s}{e} \frac{1}{1 + \frac{\bigcirc}{c} + \frac{\bigcirc}{e} + \frac{\bigcirc}{r} + \frac{\bigcirc}{q}} = \frac{1}{e} \frac{1}{\frac{1}{c} + \frac{1}{e} + \frac{1}{r} + \frac{1}{q}} $$

$$ (11) \qquad \Pi_r = \frac{\frac{T}{r}}{T\left(\frac{1}{c} + \frac{1}{e} + \frac{1}{r} + \frac{1}{q}\right)} = \frac{s}{r} \frac{1}{1 + \frac{\bigcirc}{c} + \frac{\bigcirc}{e} + \frac{\bigcirc}{r} + \frac{\bigcirc}{q}} = \frac{1}{r} \frac{1}{\frac{1}{c} + \frac{1}{e} + \frac{1}{r} + \frac{1}{q}} $$

Par définition $A_{UC}(n)$ représente l'utilisation totale de l'UC. Soit $A'_{UC}(n)$ l'utilisation de l'UC consacrée aux programmes. A partir de l'équation (8), on a

$$ (12) \qquad A'_{UC}(n) = A_{UC}(n) \frac{1}{1 + \frac{\bigcirc}{c} + \frac{\bigcirc}{e} + \frac{\bigcirc}{r} + \frac{\bigcirc}{q}} $$

et les relations (5) et (6) s'écrivent finalement

$$ (13) \qquad A_{MS}(n) = \frac{T_{MS}}{e} A'_{UC}(n) $$

$$ (14) \qquad A_{DF}(n) = \frac{T_{DF}}{r} A'_{UC}(n). $$

Evaluons de la même façon le critère D(n). En notant $e_1 = \alpha (\frac{M}{1})^k$ la durée de vie d'un programme s'exécutant seul sur le système, son temps total moyen d'exécution s'écrit alors

$$ c + \frac{\bigcirc}{r} T_{DF} + \frac{\bigcirc}{r} \bigcirc + \frac{c}{e_1} T_{MS} + \frac{c}{e_1} \bigcirc $$

Lorsque le degré de multiprogrammation est n, l'utilisation de l'UC consacrée aux programmes étant dans ces conditions $A'_{UC}(n)$, le débit moyen du système est alors

$$ \frac{A'_{UC}(n)}{c} $$

et on en déduit

$$ (15) \qquad D(n) = A'_{UC}(n) \left[ 1 + \frac{T_{DF}}{r} + \frac{\bigcirc}{r} + \frac{T_{MS}}{e_1} + \frac{\bigcirc}{e_1} \right] $$

$$ (15bis) \qquad D(n) = A'_{UC}(n) + A_{DF}(n) + A'_{UC}(n) \left[ \frac{\bigcirc}{r} + \frac{\bigcirc}{e} + \frac{T_{MS}}{e_1} \right] $$
La "dilatation" s'exprime donc comme une somme des taux d'utilisation de l'U.C. et de DF à laquelle s'ajoute un terme correctif exprimant l'influence des overheads et de la virtualisation de la mémoire (possibilité d'exécuter des programmes plus grands que la mémoire physique). Cette somme de taux d'utilisation constitue une mesure du parallélisme de fonctionnement entre les unités du système (cf. [4]).

Remarquons de nouveau que les relations que nous avons écrites (équations (12), (13), (14), (15)) ont été obtenues en l'absence de toute hypothèse sur les distributions des intervalles de temps entre défauts de page et entre entrées-sorties, et sur les distributions de temps de service à la mémoire secondaire et au disque de fichier. Dans toutes ces relations, seuls les rapports simples $T_{MS}/e$, $T_{DF}/r$ et $\mathcal{O}_c/c$, $\mathcal{O}_e/e$, $\mathcal{O}_r/r$ et $\mathcal{O}_q/q$ interviennent. Chacune de ces quantités exprime le rapport d'un paramètre de comportement de programme, par exemple le temps moyen $r$ entre deux entrées-sorties consécutives, et d'un paramètre de l'architecture associé à ce comportement, par exemple le temps moyen de service $T_{DF}$ du disque de fichier, ou l'overhead $\mathcal{O}_r$ provoqué par le lancement d'une entrée-sortie.

En raison de leur généralité, ces relations ont un intérêt important pour l'évaluation des performances du système étudié. Ainsi, le taux d'overhead $\mathcal{O}$, défini comme le rapport entre l'activité de l'UC en overhead et l'activité de l'UC consacrée aux programmes, s'écrit, à partir de (12) ou de (8),

$$ (16) \qquad \mathcal{O} = \frac{\mathcal{O}_c}{c} + \frac{\mathcal{O}_e}{e} + \frac{\mathcal{O}_r}{r} + \frac{\mathcal{O}_q}{q} $$

L'équation (16) met en évidence la liaison entre le taux d'overhead et le taux de défauts de page $1/e$. Cette observation est illustrée sur la figure 3 où $\mathcal{O}$ est tracé en fonction de $n$ pour $M = 128$, $k = 1.5$, $\alpha = 0.01$, $c = 800$, $r = 20$, $q = 100$, $\mathcal{O}_c = \mathcal{O}_q = 1$, $\mathcal{O}_e = \mathcal{O}_r = 2$, l'unité étant la milliseconde.

D'autre part, également à partir de l'équation (12), on peut déduire que, puisque on a toujours,

$$ A_{UC}(n) \le 1, $$

l'activité de l'UC consacrée aux programmes est limitée par les overheads comme ci-dessous

$$ (17) \qquad A'_{UC}(n) \le \frac{1}{1 + \frac{\mathcal{O}_c}{c} + \frac{\mathcal{O}_e}{e} + \frac{\mathcal{O}_r}{r} + \frac{\mathcal{O}_q}{q}} $$
Dans les mêmes conditions que précédemment, la valeur maximum de $A'_{UC}(n)$ est représentée sur la figure 4. On constate de nouveau la limite physique imposée par les overheads sur les performances.

L'effet des overheads a également une conséquence directe sur la dilatation $D(n)$. A partir de (15) et (17), il vient

$$ (18) \qquad D(n) \le \frac{1 + \frac{T_{DF}}{r} + \frac{\sigma_r}{r} + \frac{T_{MS}}{e_1} + \frac{\sigma_e}{e_1}}{1 + \frac{\sigma_c}{c} + \frac{\sigma_e}{e} + \frac{\sigma_r}{r} + \frac{\sigma_q}{q}} $$

L'équation (18) permet d'écrire la condition à partir de laquelle la dilatation devient supérieur à 1, pour n donné, $D(n) > 1$ si

$$ (19) \qquad \frac{T_{DF}}{r} > \frac{\sigma_c}{c} + \frac{\sigma_e}{e} + \frac{\sigma_q}{q} - \frac{T_{MS}}{e_1} - \frac{\sigma_e}{e_1} \quad \text{, avec } e = \alpha \left(\frac{M}{n}\right)^k $$

Il convient de noter que la condition (19) est une condition nécessaire, mais pas suffisante pour assurer une dilatation supérieure à 1.

Les relations (12), (13), (14), et (15) ont également une application directe dans l'évaluation de systèmes par simulation ou mesures. En effet, elles permettent de réduire le nombre de grandeurs à mesurer du fait des liaisons simples qui existent entre elles, et de faciliter l'interprétation des résultats en fournissant un modèle de référence.

Toutefois, afin de poursuivre l'exploitation du modèle, il reste à calculer explicitement les quantités inconnues et principalement, en la circonstance, $A'_{UC}(n)$ en fonction des différents paramètres du modèle. Deux approches de résolution du modèle soit par la théorie des réseaux de files d'attente, soit par simulation, sont présentées dans le paragraphe suivant.

## 3.2 - Résolution du modèle

### 3.2.1 - Méthode analytique

Les techniques de calcul de la solution stationnaire d'un réseau de files d'attente [12, 25, 28] où les files d'attente sont gérées suivant la politique PAPS (Premier Arrivé, Premier Servi) ne sont applicables que si les distributions de temps de service aux différents serveurs sont des lois exponentielles négatives.
Pour ces raisons, nous supposerons que $F_c(t)$, $F_r(t)$, $F_e(t)$, $F_{MS}(t)$ et $F_{DF}(t)$ sont des distributions exponentielles négatives. Dans le cas $O_c = O_e = O_r = O_q = 0$ et $q = \infty$ (pas de quantum), on peut alors montrer [5] que le temps de service ininterrompu à l'UC est distribué également suivant une loi exponentielle de moyenne s donnée par l'équation (9), et que le réseau de files d'attente est un réseau de JACKSON [28]. Lorsque les overheads sont pris en compte, le temps de service ininterrompu à l'UC n'est plus distribué suivant une loi exponentielle, et les résultats de JACKSON ne s'appliquent pas. Dans ce cas nous calculerons une solution approchée en supposant que ces temps suivent une loi exponentielle de moyenne s donnée par l'équation (9), et les résultats obtenus seront validés par la simulation.

Dans ces deux hypothèses, la résolution se ramène au calcul de $A_{UC}(n)$ puisque toutes les autres quantités cherchées s'en déduisent. La méthode de calcul dûe à BUZEN [14] est donnée en Annexe II, et consiste à exprimer la quantité $A_{UC}(n)$ sous la forme

$$ (20) \qquad A_{UC}(n) = \frac{G(n-1)}{G(n)}, $$

les $G(n)$ étant calculés par récurrence. Notons que dans le calcul de $G(n)$ n'interviennent également que les rapports simples entre paramètres de l'architecture et paramètres de comportement correspondants, définis dans le paragraphe précédent. Les résultats obtenus par la méthode analytique sont présentés et discutés dans le paragraphe 3.3.

### 3.2.2 - Solution du modèle par simulation

Il s'agit dans ce cas de simuler le modèle par une simulation à évènements discrets [32] reproduisant la séquence des évènements définis plus haut. Deux types de résultats peuvent être obtenus par la simulation. D'une part on peut valider les résultats fournis par la méthode mathématique en étudiant par simulation les performances obtenues dans le cas d'hypothèses non exponentielles sur les distributions. La comparaison des résultats permet alors d'apprécier la robustesse du modèle, c'est-à-dire sa sensibilité à certaines hypothèses. D'autre part, la simulation permet de prendre en compte des mécanismes
dont l'analyse est difficile, sinon impraticable, par les outils mathématiques.
Dans cette voie, nous étudierons l'effet d'un tampon de pagination en mémoire
centrale sur les performances du système.

3.3 - Comparaison des deux méthodes

Dans ce paragraphe les résultats obtenus par chacune des approches
de résolution sont présentés et discutés afin de connaître la validité de la
méthode de résolution analytique suivant les hypothèses faites sur les distribu-
tions et les overheads. Le but de cette première série d'expériences est de
montrer que la méthode de résolution analytique peut être le plus souvent utilisée
pour exploiter le modèle, et qu'on peut ainsi éviter d'avoir recours à des simu-
lations coûteuses.

Les expériences de validation de la méthode de résolution analyti-
que portent sur deux points. Tout d'abord étudier les conséquences sur les
résultats des hypothèses de distribution exponentielle faites sur les temps de
service de la mémoire secondaire et du disque de fichier. Ensuite, vérifier que
l'approximation faite pour le calcul de la solution dans le cas où les overheads
ne sont pas nuls est satisfaisante.

Sauf précisions contraires, les expériences ont été conduites avec
le choix de paramètres suivant ; M = 128 pages, k = 1.5, α = 0.01, r = 20, c = 800,
T<sub>MS</sub> = 5, T<sub>DF</sub> = 30, q = ∞, l'unité étant la milliseconde. Les simulations, écrites
en langage SIMULA, ont été conduites pendant un temps simulé de 45 secondes,
correspondant à un temps d'exploitation sur CII-IRIS 80 de 5 à 7 minutes. La durée
de 45 secondes a été fixée afin d'atteindre une précision de l'ordre de 5°/° sur
la valeur des quantités mesurées A<sub>UC</sub>(n) et A'(<sub>UC</sub>)(n) et permettre ainsi une comparaison
valable avec les résultats fournis par la résolution analytique du modèle. Il
convient de noter que cette méthode demande moins de 0.001 minute sur CII-IRIS 80
pour le calcul de A<sub>UC</sub>(n) et A'(<sub>UC</sub>)(n).

Les résultats obtenus pour le premier aspect sont rassemblés sur
les figures 5 et 6. Ils montrent qu'en dépit de l'hypothèse exponentielle la
résolution analytique produit des résultats très proches de ceux obtenus par
simulation avec des distributions non-exponentielles, par exemple avec temps de
service constant à la mémoire secondaire ou au disque de fichier, avec une
erreur relative qui ne dépasse pas 12 °/°, et qui est le plus souvent du même
ordre de grandeur que la précision des résultats obtenus par simulation [ 6 ].
Lorsque les overheads sont pris en compte, la résolution analytique n'est qu'approchée puisque les hypothèses exponentielles sur les intervalles de temps entre évènements ne sont plus satisfaites. La comparaison des résultats calculés avec ceux fournis par la simulation est présentée sur les figures 7 et 8. Les conclusions sont semblables à celles obtenues plus haut, et l'approximation donnée par la résolution analytique peut être considérée comme très satisfaisante.

Les observations sur la faible sensibilité de $A_{UC}(n)$ aux types de distributions intervenant dans le modèle, à la condition que les moyennes restent identiques, est à rapprocher des conclusions présentées dans [16] où, pour un système fermé à deux serveurs, dont l'un est général et l'autre exponentiel, les erreurs obtenues lorsque le serveur général est approché par un serveur exponentiel sont systématiquement calculées. On montre que dans le cas où le serveur général a une distribution de service de type Erlang, ce qui est le cas pour un disque ou un tambour, l'erreur commise sur l'utilisation du serveur général ne dépasse pas 10 % si celui-ci est approché par un serveur exponentiel. Il convient de remarquer que ces conclusions ont plusieurs applications pratiques simples : d'une part lorsqu'un modèle est utilisé pour faire de la prédiction de performance d'un système réel, on ne peut se contenter de mesurer uniquement la moyenne des grandeurs utiles sans se préoccuper, par exemple, de leur second moment ; d'autre part, lorsqu'en simulation on représente un temps de service par une variable aléatoire, on peut alors générer celle-ci suivant une distribution quelconque, et on choisira en général une distribution simple à générer.

Dans le paragraphe suivant nous exploitons le modèle à l'aide de la méthode analytique afin d'étudier l'influence des différents paramètres de l'architecture et du comportement des programmes sur les performances. Pour terminer, la simulation est utilisée afin d'analyser l'effet du tampon de pagination.

# 4 - EXPLOITATION DU MODELE

## 4.1. - Influence du comportement des programmes sur les performances

A l'aide du modèle défini précédemment, et en utilisant les résultats fournis par sa résolution analytique, nous pouvons étudier les performances d'un système multiprogrammé à mémoire virtuelle pour différents types de comportements de programme. Les performances du système sont simplement illustrées par la fonction D(n) qui représente la dilatation du temps réel apportée par la multiprogrammation en fonction du degré de multiprogrammation. Les paramètres de comportement de programmes qui interviennent dans les performances sont les
coefficients $\alpha$ et $k$ de la fonction de durée de vie, et le coefficient $r$ représentant le temps moyen entre deux entrées-sorties.

Les résultats sont rassemblés sur les figures 9 à 13. La forme de la courbe $D(n)$ illustre le phénomène d'écroulement : jusqu'à un certain point, l'efficacité $D(n)$ croît lorsque le degré de multiprogrammation augmente et passe alors par un maximum. Si on accroît encore le nombre de programmes se partageant les ressources, la dilatation décroît alors rapidement. Ce phénomène, étudié et mesuré sur des systèmes réels comme le système CP-67 [38], s'explique simplement à partir du modèle en observant sur les figures 9, 10, 12 l'évolution de $D(n)$ et de $A_{MS}(n)$, utilisation de la mémoire secondaire : l'écroulement apparaît directement lié à la surcharge de la mémoire secondaire provoquée par l'augmentation du taux de défauts de page lorsque les programmes doivent s'exécuter dans des espaces physiques de plus en plus petits. Cette relation entre le phénomène d'écroulement et la charge de la MS sera plus complètement analysée dans le paragraphe 4.3.

Des deux paramètres $\alpha$ et $k$ qui interviennent dans la fonction de durée de vie, définie comme le temps virtuel moyen entre deux défauts de page consécutifs d'un programme, le paramètre $k$ joue le rôle le plus important : $\alpha$ est davantage lié à la vitesse de la machine utilisée, et en partie au langage de programmation utilisé, tandis que les études faites sur $k$ à partir de la simulation de programmes réels [8] ont montré qu'il s'agit d'un paramètre intrinsèque du programme, et largement dépendant de ses propriétés de localité. L'étude de l'influence du paramètre $k$ sur les performances du système doit donc permettre de montrer comment les propriétés de localité des programmes interviennent dans le fonctionnement des systèmes multiprogrammés à mémoire virtuelle. Les résultats sont rassemblés sur la figure 9, pour $k$ variant entre 1.5 et 3. Ils illustrent de façon très sensible le rôle déterminant de $k$, ou des propriétés de localité des programmes, sur les performances, à la fois sur la dilatation maximum qui peut être atteinte et sur le degré optimum de multiprogrammation avant l'écroulement : ainsi dans les conditions de l'expérience pour $k = 1.5$ la multiprogrammation conduit à des performances inférieures à celles obtenues en mono-
programmation dès que n est supérieur à 3, alors que pour k = 2.5, plus de 6 programmes peuvent se multiprogrammer sans que l'écroulement soit atteint.

L'influence du taux d'entrée-sortie, représenté par le paramètre r, temps moyen virtuel entre deux entrées-sorties consécutives d'un programme est rapportée sur la figure 10. De toute évidence, la multiprogrammation étant fondée sur la simultanéité entre le traitement des entrées-sorties par le DF et le déroulement des programmes sur l'UC, l'efficacité ne peut être supérieure à 1 que si le taux d'entrée-sortie est suffisant. C'est ce qui apparaît sur les courbes de la figure 10 tracées avec k = 1.75. Lorsque r diminue, l'efficacité maximum augmente jusqu'à ce que le DF soit saturé comme le montrent les courbes $A_{DF}(n)$ en fonction de n de la figure 11. Les variations correspondantes de $A_{MS}(n)$ en fonction de n sont représentées sur la figure 10.

Deux conclusions importantes peuvent être dégagées de ces observations de l'influence du comportement des programmes sur les performances d'un système multiprogrammé à mémoire virtuelle. L'existence d'une plage de fonctionnement optimum, largement dépendante du type de comportement des programmes, explique la nécessité, dans un tel système, d'opérer une régulation du degré de multiprogrammation [4, 33]. La sensibilité des performances aux propriétés de localité des programmes montre le besoin d'appréhender de façon quantitative les phénomènes de comportement de programme et de les améliorer dans le sens d'une meilleure localité : c'est un des objectifs des travaux sur la structuration des programmes [23].

## 4.2 - Influence des paramètres de l'architecture sur les performances

Nous avons vu lors de l'analyse du modèle que les mesures de performances étudiées ne dépendent que des rapports sans dimension du type $\frac{T_{MS}}{e}$, $\frac{T_{DF}}{r}$, $\frac{O_r}{r}$, etc... C'est-à-dire que l'influence des paramètres de l'architecture sur les performances est "duale" de celle des paramètres de comportement de programme : doubler le temps moyen entre deux entrées-sorties consécutives r produit les mêmes effets que diminuer de moitié le temps de service du disque de fichier $T_{DF}$ et de l'overhead d'entrée-sortie $O_r$. Il est donc inutile de
répéter toutes les expériences précédentes. Toutefois, en ce qui concerne la mémoire centrale et la mémoire secondaire, la situation est sensiblement différente puisque le rapport intéressant s'écrit alors

$$ (24) \qquad \frac{T_{MS}}{e} = \frac{T_{MS}}{\alpha \left(\frac{M}{n}\right)^k}, $$

et la relation entre les différents paramètres n'est plus aussi simple que précédemment. Cependant, pour la capacité M de la mémoire centrale, il suffit de remarquer qu'elle apparaît dans les résultats par l'intermédiaire du rapport M/n, et que, par exemple, doubler la capacité de la mémoire centrale disponible aux utilisateurs permet, à performances égales, de doubler le degré de multiprogrammation. L'influence du paramètre $T_{MS}$ est rapportée sur la figure 12. Il apparaît essentiel et détermine la possibilité de multiprogrammer dans des conditions satisfaisantes : ainsi la figure 12 montre que le support des mémoires virtuelles doit être suffisamment rapide pour que la multiprogrammation soit possible. Remarquons enfin que, d'après la relation (24), la vitesse de la MS doit être doublée si la vitesse de l'UC, mesurée par $\alpha$, est également doublée, toutes choses demeurant égales par ailleurs. Les remarques et les résultats précédents montrent comment, à partir du modèle utilisé, les paramètres importants de l'architecture peuvent être estimés et les rapports qu'il convient de respecter entre les performances des différentes unités afin d'assurer des performances satisfaisantes.

### 4.3. - Caractérisation de la charge de la mémoire secondaire

Les résultats précédents ont montré que la mémoire secondaire joue un rôle essentiel dans le fonctionnement de l'ensemble du système, et que la charge, ou l'utilisation de la mémoire secondaire, est un facteur déterminant du phénomène d'écroulement.

Cette observation a également été faite sur les ordinateur multi-programmés en fonctionnement, et, plus précisemment, il a été constaté que les performances étaient les plus satisfaisantes lorsqu'il n'y avait pratiquement
pas de temps d'attente derrière la mémoire secondaire, ce qui revient à dire
que la charge de la mémoire secondaire se situe autour de 50 °/°. Parmi les
systèmes où cette remarque a été faite, citons IBM-CP-67 [3, 8], EMAS [1, 2], MULTICS
[41]. Afin de préciser ce résultat expérimental, il apparaît intéressant
d'utiliser le modèle pour caractériser au point de fonctionnement optimum du
système, c'est-à-dire le degré de multiprogrammation n* pour lequel la dilatation
D(n) est à son maximum D* = D(n*), la charge A<sub>MS</sub>(n*) de la mémoire secondaire.

A partir des figures 9, 10, 12 nous avons reporté sur la
figure 13 les valeurs de A<sub>MS</sub>(n) en fonction de n pour lesquelles

$$
\frac{A_{MS}(n) - A_{MS}(n*)}{A_{MS}(n*)} < 0.05
$$

Les valeurs de n* étant relevées à partir des trois séries d'expériences décrites précédemment : k variable, r variable, T<sub>MS</sub> variable. Nous constatons une concentration des points A<sub>MS</sub>(n) dans la zone comprise entre 0.3 et 0.6, et ceci indépendamment des valeurs des paramètres k, r, T<sub>MS</sub>, etc... Ce résultat, qui rejoint les observations expérimentales citées plus haut, fournit une condition simple de fonctionnement satisfaisant d'un ordinateur multiprogrammé à mémoire virtuelle, et un indicateur aisément mesurable du phénomène d'écroulement qui peut être utilisé pour opérer une régulation du degré de multiprogrammation comme rapporté en [33].

4.4. - Détermination de la taille optimale du tampon de pagination

Soit b le nombre de pages du tampon de pagination en mémoire principale, et m le nombre moyen de pages d'un programme présent en mémoire principale, y compris éventuellement les pages situées dans le tampon. Dans ces conditions, nous pouvons distinguer deux types de défaut de page :

- _vrai défaut de page_ : la page référencée est absente de la mémoire principale. Après détermination de la page à remplacer celle-ci est déchargée, si elle a été modifiée, dans le tampon. Si celui-ci est plein, il est alors entièrement déchargé sur la mémoire secondaire.
- faux défaut de page : la page référencée se trouve dans le tampon, il y a alors suspension de l'exécution du programme en cours de traitement et déroulement des algorithmes de pagination, mais le défaut de page ne donne lieu à aucun transfert de page entre la mémoire secondaire et la mémoire principale.

Afin d'étudier la taille optimale du tampon, les hypothèses suivantes sont retenues. Les intervalles de temps entre défauts de page sont supposés distribués suivant une loi exponentielle dont la moyenne suit la loi de Belady (cf. eq. (1)).

Le temps moyen $e'$ entre deux vrais défauts de page est donc donné par

$$e' = \alpha m^k,$$

où, en admettant comme en 2.1.3 que les programmes se partagent également les pages disponibles,

$$m = \frac{M}{n},$$

soit

$$(25) \qquad e' = \alpha \left(\frac{M}{n}\right)^k.$$

Il reste à évaluer le temps moyen de service de la mémoire secondaire et l'overhead de pagination en fonction de b. Notons $x_a$ le temps moyen d'accès de la mémoire secondaire, $x_t$ le temps moyen de transfert d'une page et $\rho$ la proportion des pages modifiées. Dans l'hypothèse où il n'y a pas de tampon de pagination, le temps moyen de service à la mémoire secondaire par défaut de page s'écrit :

$$(26) \qquad T_{MS} = (1+\rho)(x_a + x_t).$$
Lorsque le tampon a une taille de b pages, le temps moyen de service à la mémoire secondaire par vrai défaut de page devient alors :

$x_a + x_t$ pour remonter la page manquante, ceci à chaque défaut;

$x_a + bx_t$ pour décharger le tampon, tous les $\frac{b}{\rho}$ défauts de page, puisque avec une probabilité $\rho$ un défaut de page donne lieu à un déchargement. Soit finalement

$$ (27) \qquad T_{MS} = x_a \left[1 + \frac{\rho}{b}\right] + x_t \left[1 + \rho\right], $$

qui se réduit évidemment à (26) pour $b=1$.

On remarque que $T_{MS}$ est une fonction décroissante de b, le rôle du tampon de pagination va donc être de diminuer le temps d'accès moyen à la mémoire secondaire. Notons que l'influence de b sur $T_{MS}$ se fait au travers du terme $x_a$ qui est le temps moyen d'accès à la page sur le support externe de la mémoire (27) reflète donc bien ce qui se passe dans la réalité : l'existence d'un tampon de pagination permet d'optimiser le temps d'accès à la page en jouant à la fois sur le délai de rotation, dans le cas général d'une mémoire tournante, et sur le mouvement du bras de lecture/écriture, s'il s'agit d'un disque, mais ne permet pas d'optimiser le temps de transfert de la page qui ne dépend que du débit du canal de pagination.

Par ailleurs, il faut se souvenir que l'optimisation dûe au tampon de pagination porte sur les pages modifiées (donc écrites) qu'il faut recopier sur la mémoire secondaire. Si le pourcentage de telles pages est très faible, toute optimisation peut devenir inutile, c'est ce qu'indique le paramètre $\rho$ dans (27). Pour fixer les idées, signalons que $\rho$ mesuré par RODRIGUEZ-ROSELL [38] dans CP-67/CMS était de 70 %. Notons que $\rho$ n'est pas seulement lié au pourcentage des instructions écrivant en mémoire (de 10 % [10] à 30 % [31] suivant les auteurs), mais aussi à leur répartition en mémoire, donc au comportement des programmes vis à vis de l'adressage.
Evaluons maintenant, le temps moyen e'' entre deux défauts de page quelconques, y compris les faux défauts de page :

$$ (28) \qquad e'' = \alpha \left( \frac{M-b}{n} \right)^k, $$

où $\frac{M-b}{n}$ représente le nombre de pages d'un programme présentes en mémoire principale, non compris celles situées dans le tampon.

On en déduit l'overhead de pagination qui devient $\frac{\sigma_e}{e''}$, d'où l'overhead total

$$ (29) \qquad \theta = \frac{\sigma_c}{c} + \frac{\sigma_e}{e''} + \frac{\sigma_r}{r} + \frac{\sigma_q}{q}. $$

Si le tampon de pagination a pour effet de diminuer le temps moyen de service à la mémoire secondaire $T_{MS}$, en revanche l'overhead augmente avec b du fait que le taux total de défaut de page croît. Devant ces deux effets contraires du tampon, nous cherchons à en déterminer une taille optimale b*, telle que b* soit suffisante pour améliorer d'une manière significative le temps de réponse de la mémoire secondaire et assez petite pour limiter à une valeur raisonnable l'overhead introduit.

Les résultats présentés sur les figures 14 et 15 ont été obtenus en simulant le mécanisme de tampon que nous venons de décrire. Sur la figure 14, nous donnons le taux d'utilisation par les programmes de l'UC (en trait plein) en fonction de la taille du tampon attribué à chaque programme (le tampon est supposé équitablement partagé - voir (28) - et cette taille est donc $b/n$), tandis que sur la figure 15, nous donnons le même taux d'utilisation de l'UC (en trait plein) en fonction directement de la taille b du tampon global. Sur ces figures nous constatons que la présence d'un tampon améliore dans tous les cas l'utilisation de l'UC en réduisant le temps d'accès à la MS. Sur la figure 14 on remarque que quelque soit le degré de multiprogrammation, on atteint un palier pour un tampon de 5 pages alloué à chaque programme, un tampon plus grand n'améliorant pas les performances.
En fait un tampon plus grand provoque même un dégradation des performances, car il augmente l'overhead. Dans notre cas, où l'UC n'est pas saturée, nous n'observons pas de chute de performances, mais nous pouvons remarquer sur les figures 14 et 15 que le taux d'utilisation total de l'UC (en trait pointillé) augmente avec la taille du tampon et n'atteint pas de palier comme le taux de l'utilisation de l'UC sans overhead (en trait plein).

## 5 - CONCLUSION

Nous avons présenté un modèle global de système à mémoire virtuelle qui nous a permis de comprendre le fonctionnement de tels systèmes et en particulier l'apparition du phénomène d'écroulement. Ce modèle en dehors de toute hypothèse sur les distributions des temps de service aux différentes ressources fournit des relations simples, d'une part, entre les paramètres de l'architecture et ceux correspondant du comportement des programmes, et d'autre part, entre l'utilisation des différentes ressources du système et la qualité de service fournie mesurée par le débit du système. De tels résultats peuvent être exploités statiquement pour dimensionner une architecture en fonction d'une charge moyenne donnée ou dynamiquement pour maintenir, par un algorithme de contrôle, le système dans une zone de fonctionnement optimale. Ce dernier aspect a été développé dans [4, 5].

Si soigneusement qu'il soit construit, un modèle ne sera acceptable que s'il reflète, au moins en partie, une réalité connue et si son exploitation en est sûre et fiable. Dans cet article nous n'avons pas entrepris de validation systématique de notre modèle par rapport à un système réel, nous nous sommes contentés de retrouver des phénomènes connus et de prédire des performances cohérentes avec celles rapportées dans la littérature [2, 38, 41], mais de telles validations ont été effectuées pour le type de modèle, dit "à serveur central", que nous avons utilisé. La variété des systèmes réels modélisés [15, 35, 41] et les précisions obtenues [15, 16, 41] ne laissent aucun doute sur la réalité que de tels modèles permettent d'appréhender.
Du point de vue pratique, nous avons appliqué notre modèle
à des choix de paramètres d'architecture en indiquant, de plus, les relations
qu'il fallait respecter entre ces paramètres et une étude plus particulière a
été faite de l'influence du temps d'accès de la mémoire secondaire sur les
performances globales du système en montrant les limites d'une optimisation
par un tampon de pagination en mémoire.

Du point de vue méthodologique, la résolution du modèle
analytiquement et par simulation nous a permis d'évaluer sa robustesse, c'est-
à-dire les tolérences admissibles sur les paramètres d'entrée pour obtenir
un précision donnée sur les paramètres de sortie. Les paramètres importants
du modèle étant les moyennes des lois de distribution et non pas tellement
la forme de ces lois, d'où un choix possible d'une distribution arbitraire,
une solution analytique semble tout à fait justifiée par rapport à une
solution par simulation beaucoup plus coûteuse en temps de calcul et de
mise au point. Dans ce cas les résultats obtenus auront une précision relative
de 5 % à 15 % et fourniront toujours au moins un ordre de grandeur.
Notons, cependant, que certains mécanismes détaillés ne sont pas modélisables
analytiquement et demeurent l'apanage de la simulation, comme l'a montré
l'étude d'un tampon de pagination. C'est alors que la démarche adoptée, qui
consiste à valider mutuellement des modèles, peut être fructueuse par les
hypothèses simplificatrices qu'elle permet de dégager.
# ANNEXE I

## Théorèmes de CHANG et LAVENBERG [18]

Considérons un réseau de files d'attente fermé avec N clients et M stations de service. Un client achevant son service à la station i se dirige vers la station j avec la probabilité $p_{ij}^{-1}$. La matrice P = [p_{ij}] est irréductible. Les temps de service à la station i sont indépendants et identiquement distribués avec une moyenne $0 < \mu_i^{-1} < \infty$ et une distribution générale $F_i = F_i(t)$. La station i contient m_i serveurs, avec m_i ≥ 1, 1 ≤ i ≤ M. Les temps de service sont indépendants d'une station à l'autre et la règle de service est PAPS.

### Théorème

Soit $w_i(t)$ le service fourni par la station i durant l'intervalle de temps $[0, t]$, alors $U_i = \lim_{t \to \infty} \frac{w_i(t)}{t}$ existe avec probabilité un, et est indépendant de l'état du réseau à $t = 0$.

### Théorème

Soit $\Pi = (\Pi_1, \dots, \Pi_M)$ l'unique vecteur de probabilités satisfaisant $\Pi_P = \Pi$, alors, pour tout $(i,j)$

$$ \frac{U_i}{U_j} = \frac{\Pi_i \mu_i^{-1}}{\Pi_j \mu_j^{-1}} $$
# ANNEXE II

Considérons le réseau défini dans l'Annexe I, avec les hyptchèses supplémentaires que $m_i=1$, pour tout $i$, et que les distributions de temps de service sont exponentielles négatives, c'est-à-dire $F_i(t) = 1 - e^{-\mu_i t}$, et posons $\chi_i = \frac{\Pi_i}{\mu_i}$. D'après [14], la distribution d'équilibre du nombre de clients $n_i$ dans chaque station $i$ du réseau est donnée par

$$ (II.1) \qquad P(n_1, n_2, \dots, n_M) = \frac{1}{G(N)} \prod_{i=1}^{M} (\chi_i)^{n_i} $$

où $G(N)$ est une constante de normalisation définie de telle façon que $P(n_1, n_2, \dots, n_M)$ soit une distribution de probabilité. On a donc

$$ (II.2) \qquad G(N) = \sum_{S(N,M)} \prod_{i=1}^{M} (\chi_i)^{n_i} $$

où

$$ S(N,M) = \{(n_1, n_2, \dots, n_M) \mid \sum_{i=1}^{M} n_i \geq 0 \text{ pour tout } i\} $$

De (II.1) et (II.2) on déduit aisément

$$ (II.3) \qquad P[n_i \geq k] = (\chi_i)^k \frac{G(N-k)}{G(N)}, $$

$$ (II.4) \qquad E[n_i] = \sum_{k=1}^{N} (\chi_i)^k \frac{G(N-k)}{G(N)}, $$

et

$$ (II.5) \qquad A_i = P[n_i \geq 1] = \chi_i \frac{G(N-1)}{G(N)} $$

Les quantités $G(N)$ sont obtenues par un algorithme simple [14] sur les fonctions auxiliaires $g(n,m)$ définies comme suit

$$ (II.6) \qquad g(n,m) = \sum_{S(n,m)} \prod_{i=1}^{m} \chi_i^{n_i} $$
et, pour m > 1 et A > 0

$$
(\text{II.7}) \qquad g(n,m) = g(n,m-1) + \chi_m^\text{st} g(n-1,m),
$$

avec

$$
(\text{II.8}) \quad g(n,1) = (\chi_1)^n \quad \text{pour } n = 0, 1, \dots, N,
$$

et

$$
(\text{II.9}) \quad g(0,m) = 1 \quad \text{pour } m = 1, 2, \dots, M.
$$

La relation de récurrence (II.7) et les conditions initiales (II.8) et
(II.9) conduisent à $g(N,M)$ qui, par définition de $g(n,m)$, représente $G(N)$.

Remarquons que les $\chi_i$ sont définis à une constante multiplicative
près, et que, dans la pratique, on prendra $\chi_1 = 1$ pour simplifier les calculs.
Dans le cas du modèle étudié, nous aurons donc

$$
\chi_1 = 1,
$$

$$
\chi_2 = \frac{\sum_{e(1+\frac{c}{c}+\frac{e}{e}+\frac{r}{r}+\frac{q}{q})}^{T_{MS}}}{,}
$$

$$
\chi_3 = \frac{\sum_{r(1+\frac{c}{c}+\frac{e}{e}+\frac{r}{r}+\frac{q}{q})}^{T_{DF}}}{.}
$$
<figure><img src="image_4.png" /><figcaption>Figure 1</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 2</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 3
Overhead O en fonction du degré de multiprogrammation n</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 4
Utilisation UC programme maximum en fonction du degré de multiprogrammation</figcaption></figure>
<table><thead><tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><td>résultat analytique</td><td>.35</td><td>.43</td><td>.41</td><td>.34</td><td>.25</td><td>.20</td><td>.16</td><td>.13</td><td>.11</td><td>.09</td></tr><tr><td>simulation</td><td>.33</td><td>.43</td><td>.46</td><td>.34</td><td>.25</td><td>.18</td><td>.16</td><td>.13</td><td>.11</td><td>.09</td></tr><tr><td>erreur relative</td><td>.06</td><td>-</td><td>.12</td><td>-</td><td>-</td><td>.10</td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

$A_{UC}(n)$

Résultats analytiques : temps de service exponentiels à la MS et au DF

Résultats de simulation : temps de service constants à la MS exponentiels au DF

$$ \mathcal{O}_q = \mathcal{O}_c = \mathcal{O}_e = \mathcal{O}_r = 0 $$

(- signifie que l'erreur est inférieure à 5%)

Figure 5

<table><thead><tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><td>résultat analytique</td><td>.35</td><td>.43</td><td>.41</td><td>.34</td><td>.25</td><td>.20</td><td>.16</td><td>.13</td><td>.11</td><td>.09</td></tr><tr><td>simulation</td><td>.35</td><td>.45</td><td>.44</td><td>.35</td><td>.25</td><td>.20</td><td>.15</td><td>.13</td><td>.11</td><td>.09</td></tr><tr><td>erreur relative</td><td>-</td><td>-</td><td>.08</td><td>-</td><td>-</td><td>-</td><td>.06</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

$A_{UC}(n)$

Résultats analytiques : temps de service exponentiels à la MS et au DF

Résultats de simulation : temps de service constants à la MS et au DF

$$ \mathcal{O}_q = \mathcal{O}_c = \mathcal{O}_e = \mathcal{O}_r = 0 $$

(- signifie que l'erreur est inférieure à 5%)

Figure 6
<table><thead><tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><td>résultat analytique</td><td>.40</td><td>.56</td><td>.64</td><td>.65</td><td>.63</td><td>.60</td><td>.57</td><td>.54</td><td>.52</td><td>.50</td></tr><tr><td>simulation</td><td>.41</td><td>.56</td><td>.67</td><td>.69</td><td>.65</td><td>.61</td><td>.56</td><td>.54</td><td>.52</td><td>.50</td></tr><tr><td>erreur relative</td><td>-</td><td>-</td><td>-</td><td>.06</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

$A_{UC}(n)$ : comparaison des résultats analytiques et de simulation avec overheads

$$ \mathcal{O}_q = \mathcal{O}_c = 1 \text{ ms}, \mathcal{O}_e = \mathcal{O}_r = 2 \text{ ms}. $$

(- signifie que l'erreur est inférieure à 5 %)

<table><caption>Figure 7</caption><thead><tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><td>résultat analytique</td><td>.32</td><td>.37</td><td>.35</td><td>.29</td><td>.24</td><td>.19</td><td>.15</td><td>.13</td><td>.11</td><td>.09</td></tr><tr><td>simulation</td><td>.33</td><td>.38</td><td>.37</td><td>.31</td><td>.24</td><td>.19</td><td>.15</td><td>.13</td><td>.11</td><td>.09</td></tr><tr><td>erreur relative</td><td>-</td><td>-</td><td>-</td><td>.06</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

$A'_{UC}(n)$ : comparaison des résultats analytiques et de simulation avec overheads

$$ \mathcal{O}_q = \mathcal{O}_c = 1 \text{ ms}, \mathcal{O}_e = \mathcal{O}_r = 2 \text{ ms} $$

(signifie que l'erreur est inférieure à 5 %)

<caption>Figure 8</caption>
<figure><img src="image_8.png" /><figcaption>Figure 9</figcaption></figure>

D (n) et $A_{MS} (n)$ en fonction de n
($k = 1.5, 1.75, 2, 2.5, 3$)
<figure><img src="image_9.png" /><figcaption>Figure 10</figcaption></figure>

D (n) et A<sub>MS</sub> (n) en fonction de n
(r = 5, 10, 15, 25, 50 (millisecondes))
<figure><img src="image_10.png" /><figcaption>Figure 11</figcaption></figure>

$A_{DF} (n)$ en fonction de n
($r = 5, 10, 15, 20, 25, 50$ (millisecondes))
<figure><img src="image_11.png" /><figcaption>Figure 12</figcaption></figure>

D (n) et A<sub>MS</sub> (n) en fonction de n
(T<sub>MS</sub> = 5, 10, 20, 50 (millisecondes))
<figure><img src="image_12.png" /><figcaption>Figure 13</figcaption></figure>

$A_{MS}(n)$ pour n vérifiant

$$ \frac{|D(n) - D(n^*)|}{D(n^*)} < 0.05 $$
<figure><img src="image_13.png" /><figcaption>Taux d'utilisation UC</figcaption></figure>

Taille du tampon
alloué à chaque
programme en page

UC totale
UC sans overhead

Figure 14
<figure><img src="image_14.png" /><figcaption>Taux d'utilisation en %</figcaption></figure>

Taille du tampon global en pages

UC totale

UC avec overhead

Figure 15
REFERENCES

[ 1 ] ADAMS J.C. - "Architecture and performance evaluation of EMAS" - Séminaires de "Modélisation et évaluation des performances de systèmes informatiques" - IRIA-LABORIA - Octobre 1975.

[ 2 ] ADAMS J.C., MILLARD G.E. - "Performance measurements on the Edinburgh Multi Access System" - International Computing Symposium 75 - Antibes - Juin 1975.

[ 3 ] ADAIR R., BAYLES R.U., COMEAU L.W., CREASY R.J. - "A virtual machine system for the 360/40" - Cambridge Scientific Center Report n° G320-2007 - May 1966.

[ 4 ] BADEL M., GELENBE E., LEROUDIER J., POTIER D. - "Adaptive optimization of a time-sharing system's performance" - IEEE Proceedings on Interactive Computer Systems - June 1975.

[ 5 ] BADEL M., GELENBE E., LENFANT J., LEROUDIER J., POTIER D. - "Adaptive optimization of the performance of a virtual memory computer" - Proceedings of the workshop on computer architecture and networks - IRIA - Août 1974.

[ 6 ] BADEL M. - "Quelques problèmes liés à la simulation de modèles de systèmes informatiques" - Thèse de Docteur-Ingénieur - Université de Paris VI - Mai 1975.

[ 7 ] BARD Y. - "CP-67 Measurement and analysis : overhead and throughput" - ACM-SIGOPS - Workshop on System Performance Evaluation - Harvard - April 1971.

[ 8 ] BELADY L.A., KUEHNER C.J. - "Dynamic space-sharing in computer systems" - CACM Vol. 12, n° 5 - May 1969.

[ 9 ] BENSOUSSAN A., CLINGEN C.T., DALEY R.C. - "The MULTICS Virtual memory" - Proceedings of Second ACM Symposium on Operating Systems Principles - Princeton - October 1968.

[10] BORDSEN D.T. - "UNIVAC 1108 Hardware instrumentation system" - ACM-SIGOPS - Workshop on system performance evaluation - Harvard April 1971.

[11] BRAWN B.S., GUSTAVSON F.G. - "Program behaviour in a paging environment" - Fall Joint Computer Conference 1968.

[12] BUZEN J.P. - "Queueing network models of multiprogramming" - Ph. D. Thesis - Harvard University - 1971.

[13] BURGEVIN P., LEROUDIER J. - "Measurement analysis of program behaviour" - A paraître en Rapport LABORIA.

[14] BUZEN J.P. - "Computational algorithm for closed queueing networks with exponential servers" - CACM - Vol 16, n° 9 - September 1973.
[15] BUZEN J.P. - "Cost effective analytic tools for computer performance evaluation". Comp. Con. 75 - Washington D.C. - September 1975.

[16] BUZEN J.P., POTIER D. - "Accuracy of the exponential approximation in closed queueing systems" - A paraître en Rapport LABORIA.

[17] CHAMBERLIN D.D., FULLER S.H., LIU L.Y. - "A page allocation strategy for multiprogramming systems" - IBM Research - Report RC 3848 - May 1972.

[18] CHANG A., LAVENBERG S.S. - "Work-rates in closed queueing network model" - Operation Research 22 (1974).

[19] DENNING P.J. - "Virtual memory" - Computing Surveys - Vol. 2, n° 3 - September 1970.

[20] DENNING P.J. - "The working set model for program behaviour" - CACM - Vol. 11, n° 5 - May 1968.

[21] DENNING P.J. - "Thrashing : its causes and prevention" - Fall Joint Computer Conference - 1968.

[22] DENNING P.J., SCHWARTZ S.C. - "Properties of the working set model" - CACM - Vol. 15, n° 3 - Mars 1972.

[23] FERRARI D. - "Improving locality by critical working sets" - CACM - Vol. 17, n° 11 - Novembre 1974.

[24] GELENBE E. - "Modèles de comportement de systèmes informatiques" - Thèse d'Etat - Université de PARIS VI - Novembre 1973.

[25] GORDON W.J., NEWELL G.F. - "Closed queueing systems with exponential servers" - Operation Research - Avril 1967.

[26] GUIBOUD-RIBAUD S., BRIAT J. - "Espace d'adressage et espace d'exécution du système GEMAU" - Proceedings of International Symposium on Operating Systems - IRIA - Avril 1974 - (publiés par Springer-Verlag).

[27] IBM Corp. - "Virtual machine facility/370 - Planning guide" - IBM Corporation - Publication n° GC 20-1801-0 - 1972.

[28] JACKSON J.R. - "Jobshop-like queueing systems" - Management Science, 10, 1, Octobre 1963.

[29] JALICS P.J., LYNCH W.C. - "Selected measurement of the PDP-10 TOPS-10 time sharing operating system" - Proceedings of IFIP 74 Conference - Stockholm - Août 1974.

[30] KILBURN T., EDWARDS D.B.G., LANIGAN M.J., SUMMER F.H. - "One-level storage system" - IRE Trans. EC 11, 2 - Avril 1962.

[31] LENFANT J. - "Comportement des programmes dans leur espace d'adresse" - Application à la gestion des mémoires hiérarchisées" - Thèse d'Etat - Université de Rennes - Décembre 1974.

[32] LERODIER J., PARENT M. - "Quelques aspects de la modélisation par simulation à évènements discrets" - Rapport LABORIA n° 98 - Février 1975 et Revue Bleue de l'AFCET Janvier 1976.
[33] LERODIER J., POTIER D. - "A two level control scheme for multiprogrammed virtual memory computer systems" - Rapport LABORIA n° 141 - Novembre 1975.

[34] MEYER P.A., SEAWRIGHT L.H. - "A virtual machine time-sharing system" - IBM System Journal - Vol. 9, n° 3 - 1970.

[35] MOORE C.G. - "Network models for large scale time-sharing systems" - Ph. D. Thesis - University of Michigan - 1971.

[36] OPDERBECK H., CHU W. - "Performance of the page fault frequency replacement algorithm in a multiprogramming environment" - Proceedings of IFIP 74 Conference - Stockholm - août 1974.

[37] PINKERTON T.B. - "Program behaviour and control in virtual storage computer systems" - Report CONCOMP - University of Michigan - Avril 1968.

[38] RODRIGUEZ-ROSELL J., DUPUY J.P. - "The evaluation of a time-sharing page demand system" - Spring Joint Computer Conference - 1972.

[39] RODRIGUEZ-ROSELL J. - "Experimental data on low program behaviour effects the choice of scheduler parameters" - Third Symposium on Operating Systems - Stanford University - 1971.

[40] RODRIGUEZ-ROSELL J., DUPUY J.P. - "The design, implementation and evaluation of a working set dispatcher" - CACM - Vol. 16, n° 4 - Avril 1973.

[41] SEKINO A. - "Performance evaluation of multiprogrammed time-shared computer systems" - Ph.D. Thesis - Project MAC TR - 103 - MIT - Septembre 1972.

[42] UNIVERSITY OF MICHIGAN COMPUTER CENTER - "MTS : Michigan Terminal System" - Ann Arbor - University Press - 1970.