# Simulation de l'allocation de ressources dans un système à mémoire virtuelle paginée

Claude Bétourné, Sacha Krakowiak

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

## To cite this version:

Claude Bétourné, Sacha Krakowiak. Simulation de l'allocation de ressources dans un système à mémoire virtuelle paginée. [Rapport de recherche] IRIA-RR-012, IRIA. 1973, pp.18. hal-04715956

HAL Id: hal-04715956

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Env: 01/1971

RR12

RIA
laboria

laboratoire de recherche
en informatique
et automatique

Simulation de l'allocation
de ressources
dans un système
à mémoire virtuelle
paginée

18P

Claude Bétourné
Sacha Krakowiak

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n°12

mars 1973
SIMULATION DE L'ALLOCATION DE RESSOURCES
DANS UN SYSTEME CONVERSATIONNEL A MÉMOIRE VIRTUELLE PAGINÉE

C. Betourne, S. Krakowiak

ABSTRACT : Resource Management in a Virtual Memory Page-on-demand System :
A Simulation Study

This paper presents some simulation results obtained with a model of the time-sharing system ESOPE, implemented at IRIA on a CII 10070 computer. These experiments provided a quantitative assessment of the allocation strategies for CPU, central and secondary storage. The following points were investigated :

- disk transfer optimization,

- prevention of thrashing by a dynamic limitation of the multiprogramming degree.

- effect of information sharing.

- anticipation on disk transfers ("preloading" and "predumping").

- effect of program behaviour, using a constant reference probability model.

RÉSUMÉ : Simulation de l'allocation de ressources dans un Système conversationnel à mémoire virtuelle paginée*

Cet article présente des résultats de simulation obtenus sur un modèle du système en temps partagé ESOPE, réalisé à l'IRIA sur un calculateur CII 10070. L'objectif de cette étude est l'évaluation quantitative de diverses stratégies de gestion de l'ensemble de ressources constitué par l'unité centrale, la mémoire principale et la mémoire secondaire (disques à têtes fixes). L'expérimentation a porté sur les points suivants :

- optimisation des transferts entre mémoire centrale et disques,

- limitation dynamique du degré de multiprogrammation, dans le but de prévenir l'écroulement du système,

- influence du partage de l'information,

- exécution anticipée des transferts d'information (préchargement et prévidage),

- influence du comportement des programmes, en utilisant un modèle à probabilités de référence stationnaires.

<footnote>* Cet article a été présenté au Congrès AFCET sur les Techniques de l'Informatique (Grenoble, novembre 1972).</footnote>
# 1. Introduction

Cet article présente quelques résultats de simulation d'un système conversationnel à mémoire virtuelle paginée. Le modèle a été réalisé parallèlement à la construction du système ESOPE à l'IRIA, dans le but d'étudier les algorithmes fondamentaux du système avant leur mise en oeuvre effective. Il s'agissait moins de prévoir des performances en valeur absolue que de tester la validité de certaines hypothèses, de confirmer ou infirmer des conclusions fondées sur la seule intuition, d'évaluer quantitativement, au moins en valeur relative, les résultats de telle décision de conception.

L'expérimentation a été centrée sur les problèmes de gestion de l'ensemble processeur-mémoire centrale-mémoire secondaire, et, de façon plus précise, sur l'influence de la gestion des échanges de pages sur le temps de réponse moyen de travaux conversationnels. Les problèmes d'entrée-sortie ont été laissés de côté pour cette étude spécifique. De même, a été éliminé du modèle, pour des raisons de simplicité, le travail de fond, qui représente essentiellement une charge de l'unité centrale pendant les périodes laissées libres par les autres travaux, ainsi qu'un lentissement moyen du trafic de pages des autres travaux. La charge du système simulé comprend donc un ensemble d'usagers conversationnels ayant le même comportement statistique.

Par ailleurs, on ne s'est intéressé qu'au comportement du système en régime permanent, c'est-à-dire à nombre d'usagers constant. Il a été jugé que la simulation de l'arrivée et du départ d'usagers compliquerait le modèle sans apporter d'informations utiles.

# 2. Le système simulé

Nous avons simulé le système ESOPE [1], réduit à la gestion des ressources principales. En fait le modèle peut s'appliquer à une classe de systèmes interactifs, utilisant une mémoire paginée chargée à la demande à partir d'une mémoire secondaire à accès direct. La mémoire secondaire est supposée "lente" en ce sens que le temps de chargement d'un programme est grand par rapport au temps d'unité centrale consommé (par exemple 300 ms contre 30 ms) ; il en résulte que le temps de réponse du système dépend dans ce cas essentiellement du trafic de pages.

Chaque programme, ou usager, possède sa propre mémoire virtuelle. Mis à part les phases d'entrée et de sortie du système, un usager conversationnel suit dans le système un chemin cyclique représenté ci-après.
<figure><img src="image_3.png" /><figcaption>Le cycle des usagers dans le système ESOPE</figcaption></figure>

L'usager est dit *oisif* lorsque le programmeur réfléchit, tape sa demande ou reçoit une réponse. Une fois la demande formulée, ce qui est signalé par le retour du chariot, l'usager devient *prêt* et attend d'entrer en mémoire principale.

L'admission en mémoire est contrôlée par un test dit de réservation et expliqué plus loin. L'usager admis est dit *courant* ; initialement il est éligible, c'est-à-dire candidat pour l'unité centrale. Les usagers éligibles sont servis à tour de rôle et reçoivent à chaque fois un quantum de temps. L'usager *élu* perd le contrôle lorsque le programme se termine, lorsqu'il épuise son quantum ou enfin lorsqu'il subit un défaut de page ; dans ce dernier cas, si la page ne se trouve pas déjà en mémoire, l'usager reste courant, mais dans l'état *suspendu* ; il attend le chargement de la page et redevient éligible dès l'achèvement du transfert.

Le programme une fois terminé, l'usager quitte la mémoire, c'est-à-dire qu'il libère toutes les pages qu'il a reçues et retombe à l'état *oisif*.

Précisons les points d'importance pour la simulation :

L'admission en mémoire repose sur une évaluation approchée de la taille du "working set" d'une interaction. Le moniteur estime, en se référant au passé, le nombre maximal de pages qui seront utilisées ; il assigne alors à l'usager une catégorie fonction du volume de mémoire calculé. Un usager n'entre en mémoire qu'à la condition que la mémoire puisse contenir l'ensemble des "working sets" des usagers courants. Si l'usager dépasse la limite estimée le moniteur peut, par exemple, l'éjecter de la mémoire et le remettre dans l'état prêt avec une catégorie supérieure.

L'allocation de page est dynamique et s'effectue lors d'un défaut de page. Le moniteur entretient deux files de pages allouables : les pages libres, dont le contenu peut être perdu car une image conforme existe en mémoire secondaire ; les pages quasi-libres qui contiennent des données à sauvegarder en mémoire secondaire avant d'y charger un nouveau contenu. L'allocateur distribue d'abord les pages libres, s'il y en a, sinon les pages quasi-libres. Les pages libres et quasi-libres sont les seules pages allouables ; remarquons qu'en raison de la politique de réservation il y a toujours des pages allouables.

Le contenu des pages allouables étant connu, lors d'un défaut de page le moniteur recherche d'abord si l'information demandée se trouve encore en mémoire ; en cas de succès la page est "récupérée", c'est-à-dire réallouée ; sinon le moniteur alloue une page et demande le chargement.
La récupération arrive fréquemment pour les pages de code réentrant, pages partageables entre les usagers.

Dans le système ESOPE la mémoire secondaire est constituée de disques RAD à têtes fixes ; la durée d'une révolution monte à 40 ms et le temps de transfert d'une page dure 15 ms. Les demandes de chargement et de vidage sont regroupées de façon à minimiser le temps total du transfert en évitant autant que possible les temps morts d'accès au pages.

## 3. Le modèle

### 3.1 Caractéristiques générales

Le simulateur peut se décomposer en trois parties logiquement distinctes :

- le moniteur, chargé de gérer les usagers et les ressources principales : mémoire centrale, mémoire secondaire, et unité centrale,

- la charge du système, constituée par un nombre réglable d'usagers travaillant en mode conversationnel à partir de terminaux,

- le programme de contrôle, chargé d'initialiser les simulations et de recueillir les statistiques.

Tout modèle représente un compromis entre la simplicité de réalisation et la fidélité au système représenté. On a essayé de représenter le plus fidèlement possible les mécanismes centraux d'allocation de ressources ; d'autres parties du système ont reçu un traitement plus global : ainsi il n'a pas été jugé utile, lors de la simulation des interactions avec les terminaux, de simuler l'entrée individuelle des caractères ; on s'est contenté de définir un comportement statistique de la longueur des messages, et d'imputer à l'unité centrale le temps de traitement correspondant. Plus généralement, une méthode simplificatrice a été utilisée à plusieurs reprises : elle consiste à isoler un sous-système ayant des relations bien définies avec le reste, à étudier expérimentalement son comportement moyen, et à remplacer dans le modèle général le sous-système par un modèle traduisant ce comportement. Cette méthode permet de réduire de façon notable le temps d'exécution de la simulation.

Le simulateur a été écrit dans le langage SIMULA 1.

### 3.2 Simulation du système

La gestion de la mémoire et de l'unité centrale sont fidèlement reproduites. Un processus (dans ce paragraphe, ce mot sera employé au sens du langage SIMULA) est chargé d'admettre les usagers en mémoire et de leur allouer l'unité centrale. L'accès en mémoire est régi par un test de réservation.

Le fonctionnement des disques à têtes fixes est simulé par un processus activé lors du lancement d'une requête ; le temps de transfert des pages est un facteur essentiel du temps de réponse des usagers et doit donc être déterminé avec précision. L'optimisation de l'exécution des requêtes, par modification de l'ordre des transferts, est simulée sans avoir à tenir compte des adresses individuelles des pages sur disque. On utilise pour cela des courbes déterminées par une simulation préliminaire et représentées approximativement par une formule algébrique. (figure 1)

On obtient ainsi une évaluation du temps moyen de transfert d'un groupe de pages en fonction du nombre de pages transférées. Les adresses de début de pages sont supposées réparties uniformément sur les disques hypothèse justifiée compte tenu du grand nombre de transferts. La figure 2 illustre l'influence globale de cette optimisation sur le temps de réponse moyen. Cette influence augmente nettement avec la charge.
### 3.3 Simulation de la charge du système

La charge du système est constituée d'un nombre variable de terminaux en interaction directe. Le comportement des usagers est cyclique. Le temps de réflexion est schématisé par une variable aléatoire de distribution uniforme, variant entre 2 et 20 secondes, ce temps comprenant l'entrée et la sortie de messages sur le terminal. Le temps de réponse d'une interaction est défini comme l'intervalle de temps compris entre la fin de l'entrée d'une demande et le début de la sortie de la réponse suivante. L'exécution d'un programme se représente par un processus générateur de tirages aléatoires de numéros de pages virtuelles ; si la page est reconnue manquante, un déroutement est simulé pour demander le chargement de cette page. Le temps de traitement moyen d'une interaction a été fixé à 30 ms.

Etant donné la mauvaise connaissance du comportement réel des programmes, on a choisi le modèle aussi simple que possible, avec toutefois la possibilité de simuler un comportement "local", et d'agir sur les paramètres de ce comportement.

Le modèle de programme choisi est un modèle à probabilité de référence stationnaire. La mémoire virtuelle du programme étant constituée de N pages, on attache à chacune d'elles un nombre $p_i$, qui mesure la probabilité pour la page n° i de faire l'objet d'une référence, à un instant quelconque.

$$ \text{On a } \sum_{i=1}^{N} p_i = 1. $$

Pour simuler le phénomène de comportement "local", on choisit un sous ensemble de P pages (ou "noyau"). La probabilité qu'une référence concerne une page du noyau est fixée à $p \ge \frac{1}{2}$ ; à l'intérieur du noyau, les pages ont la même probabilité de référence, de même qu'en dehors du noyau. On a donc

$$ P_i = \begin{cases} \frac{P}{P} & \text{pour les P pages du noyau} \\ \frac{1-P}{N-P} & \text{pour les N - P pages en dehors du noyau} \end{cases} $$

Par ailleurs, on admet qu'une référence sur deux est une écriture ; cette hypothèse est à peu près vérifiée dans la pratique.

On voit avec ce modèle que si on fait un nombre de références aux pages nettement supérieur à P, la plupart des pages du noyau seront référencées plusieurs fois si p est assez grand.

Ce modèle est certainement trop simpliste pour prétendre représenter fidèlement le comportement des programmes réels ; en particulier, le renouvellement des pages du "working set" d'un programme n'est pas simulé. Le rôle d'un tel modèle est de mettre en évidence l'influence d'un aspect du comportement des programmes sur les stratégies de gestion de la mémoire.

### 3.4 Exploitation du modèle

#### 3.41 Remarques générales

Avant de réaliser les expériences proprement dites, il est nécessaire de vérifier la validité du simulateur, d'évaluer la précision de ses résultats, et de figer un certain nombre de paramètres ; il n'est pas possible en effet, ne serait-ce qu'en raison du temps élevé de la simulation, de faire évoluer tous les paramètres. Parmi les nombreux paramètres du modèle, un certain nombre peuvent être fixés une fois pour toutes, si l'on estime que la variation de ces paramètres dans un certain domaine n'a pas
d'influence sur les résultats, ou a une influence entièrement prévisible. C'est ainsi que le temps moyen de changement d'usager a été fixé à 3 ms et la durée moyenne d'une interaction à 30 ms.

Tous les résultats obtenus sont de nature statistique, et il est donc important d'avoir une idée de leur précision et de leur stabilité. Une expérience de simulation comprend l'échange d'un certain nombre de messages par terminal, nombre qui détermine la durée de l'expérience. Le tableau I montre l'influence de ce paramètre sur le temps de réponse et l'écart-type mesuré, les autres paramètres étant maintenus constants.

<table><thead><tr><td>Nombre de messages</td><td>Temps de réponse moyen (s.)</td><td>Ecart-type</td></tr></thead><tbody><tr><td>40</td><td>1.81</td><td>1.01</td></tr><tr><td>100</td><td>1.87</td><td>1.12</td></tr><tr><td>200</td><td>1.78</td><td>1.07</td></tr><tr><td>400</td><td>1.78</td><td>1.08</td></tr><tr><td>800</td><td>1.90</td><td>1.05</td></tr></tbody></table>

## Tableau I

Pour les expériences dont il est rendu compte ici, la durée moyenne des essais a été fixée à 200 messages, ce qui semble correspondre à une erreur de 5 à 10 % environ sur le temps de réponse moyen.

## 3.42 Utilisation du modèle

Une expérience consiste à exécuter une série de simulations, en faisant varier un et parfois deux paramètres, et en modifiant une stratégie donnée du moniteur. Les paramètres fondamentaux sont : le nombre d'usagers en activité, la taille de la mémoire allouable, les paramètres définissant le comportement des programmes.

Comme il vient d'être indiqué, une simulation se termine lorsque 200 messages ont été échangés (ce qui correspond à environ 3 minutes de fonctionnement du système réel sous une charge constante de 20 usagers).

Les principales variables mesurées sont les suivantes :

- répartition de l'activité de l'unité centrale : en attente d'usagers, en attente de page, exécution de programmes du moniteur, exécution de programmes d'usagers.

- activité des disques : facteur d'utilisation, nombre de pages transférées dans les deux sens, taille moyenne des requêtes.

- statistiques sur les pages physiques : pages chargées, vidées, récupérées, partagées.

- temps de réponse (moyenne, écart-type).

- longueur moyenne des files d'usagers prêts et courants.

## 3.43 Notations

On utilisera dans les tableaux et figures les abréviations suivantes :

### Paramètres du système

NUS : nombre d'usagers conversationnels présents dans le système

NPP : taille de la mémoire principale, exprimée en nombre de pages (1 page = 512 mots)
## Modèle de programme

<table><tr><td>N</td><td>: taille de la mémoire virtuelle du programme</td></tr><tr><td>NWS</td><td>: taille du noyau simulant un "working set"</td></tr><tr><td>PWS</td><td>: probabilité pour qu'une référence à une page concerne une page du noyau</td></tr></table>

## Paramètres des simulations

<table><tr><td>NREF</td><td>: nombre de tirages aléatoire de pages virtuelles (par usager)</td></tr><tr><td>NPV</td><td>: nombre de pages prévidées (lorsque le prévidage est prati-qué)</td></tr></table>

## Grandeur mesurées

<table><tr><td>TRM</td><td>: temps de réponse moyen (en secondes)</td></tr></table>

# 4. Analyse des résultats

## 4.1 Gestion de la mémoire physique

L'étude de la gestion de la mémoire physique a été centrée sur la mise en évidence, l'explication et la prévention du phénomène d'écroulement [2]. Ce phénomène, qui se manifeste sur les systèmes paginés utilisant la politique de la page à la demande, se traduit par une chute brutale des performances du système, liée à un accroissement des échanges de pages et à un taux d'oisiveté élevé de l'unité centrale. Le phénomène d'écroulement est lié aux caractéristiques de comportement de programmes et à la stratégie d'allocation de la mémoire : on étudiera donc l'influence de ces deux facteurs.

## 4.11 Influence du comportement des programmes

Une première série d'expériences a été faite en supprimant la réservation de mémoire à l'entrée des usagers dans l'état courant. L'état "prêt" disparaît : un usager débloqué passe aussitôt à l'état courant. En conséquence, un défaut de page peut se produire alors qu'il n'y a pas de page libre : on remplace dans ce cas au hasard une page déjà allouée. Pour mettre en évidence l'influence du comportement local, on a comparé un modèle de programme à références uniformes (NREF = 25) avec un modèle comportant un noyau (NREF = 40). La figure 3 représente la variation du temps de réponse moyen en fonction du nombre de pages physiques allouables. En normalisant les courbes à un même nombre de références, on constate que les performances du programme avec noyau deviennent rapidement meilleures lorsque la taille de la mémoire augmente.

Dans un programme avec noyau, les pages du noyau sont référencées plusieurs fois, d'où un gain en nombre de transferts de page par rapport au programme à références uniformes ; mais à mesures que la taille de la mémoire diminue, la probabilité de pouvoir réutiliser une page de noyau sans avoir à la recharger décroît, si bien que le nombre de défauts de page tend, pour les deux comportements de programme, à rejoindre le nombre de tirages de pages.

En conséquence, en l'absence de réservation de mémoire, on voit que les programmes à comportement local sont favorisés lorsqu'il y a peu de remplacements, c'est-à-dire quand la taille de mémoire disponible est
grande ; en revanche, en mémoire restreinte, la dégradation des performances de ces programmes est plus rapide.

## 4.12 Influence de la politique de réservation de mémoire

On s'intéresse maintenant au comportement du système en fonction de la charge. En l'absence de mécanisme limitant le degré de multiprogrammation, l'écroulement est prévisible lorsque la taille de mémoire disponible est insuffisante pour contenir l'ensemble des "working sets" des usagers courants.

Ce phénomène d'écroulement est clairement visible sur la figure 4 représentant le temps de réponse moyen en fonction de la charge. Pour une taille de mémoire allouable de 70 pages, la charge étant constituée de programmes comportant un noyau de 10 pages, on constate une discontinuité du temps de réponse lorsque la charge dépasse 25 usagers. L'écroulement se manifeste en outre par :

- une dispersion beaucoup plus grande du temps de réponse autour de sa valeur moyenne (voir figure 4)

- une croissance très forte du nombre de remplacements de pages.

Le paramètre NPP représente le nombre moyen d'usagers courants au-dessus duquel l'écroulement se produit ; dans les conditions de l'expérience, ce paramètre vaut 7. On constate en effet que le taux d'occurence d'un nombre d'usagers courants supérieur ou égal à 7 croît brutalement au-dessus de 25 usagers. Le tableau II représente la variation des principaux paramètres énumérés :

<table><thead><tr><th>NUS</th><th>Nb observations<br>≥ 7 usagers courants</th><th>Nb<br>remplacements</th><th>Nb<br>{echange de<br>pages</th><th>Ecart-type<br>temps de<br>réponse(s)</th></tr></thead><tbody><tr><td>22</td><td>6</td><td>13</td><td>3520</td><td>0.9</td></tr><tr><td>24</td><td>4</td><td>9</td><td>3600</td><td>0.8</td></tr><tr><td>25</td><td>135</td><td>3930</td><td>8180</td><td>8.4</td></tr><tr><td>26</td><td>122</td><td>3900</td><td>8160</td><td>9.5</td></tr><tr><td>28</td><td>153</td><td>5230</td><td>9740</td><td>9.5</td></tr></tbody></table>

### Tableau II

On constate (figure 4) que l'introduction de la politique de réservation de mémoire permet de supprimer l'écroulement à 25 usagers. (pour des raisons techniques, la simulation n'a pu être poursuivie au-delà de 30 usagers). Par ailleurs, on a également représenté sur la figure la courbe de temps de réponse obtenue pour une taille de mémoire de 100 pages, sans réservation. Le seuil d'écroulement est reporté au-delà de 30 usagers et n'a pu être observé.

## 4.2 Etude des échanges de pages

Un objectif important de la politique d'allocation de ressources est la réduction des échanges de pages entre mémoire et disque. On a déjà examiné (§3.2) la réduction du temps d'exécution des requêtes. Un second mode d'optimisation consiste à anticiper sur les transferts prévisibles ou probables. Suivant le sens du transfert, on parlera de préchargement ou de prévidage.

## 4.21 Préchargement

Le principe du préchargement consiste à charger en mémoire centrale,
lors du passage d'un usager à l'état courant, des pages dont la probabilité estimée d'utilisation par cet usager est élevée. Les avantages attendus du préchargement sont les suivants :

- réduction du temps consacré à la gestion du système (grâce à la diminution du nombre de défauts de page,

- optimisation du transfert par allongement de la taille moyenne des requêtes, à nombre de pages transférées constant.

Cette technique implique toutefois le risque de charger des pages qui ne seront pas utilisées ; l'intérêt du préchargement est donc directement lié à l'évaluation de la probabilité d'utilisation des pages.

L'expérience faite en simulation a consisté à évaluer les avantages du préchargement dans le cas où cette probabilité d'utilisation est continue. Le modèle de programme utilisé comportant un noyau, seules les pages de ce noyau ont été préchargées. Les résultats de l'expérience, avec et sans préchargement, sont résumés dans le tableau III ; on s'est d'abord placé dans le cas où le noyau est "dur", cas où le préchargement des pages du noyau doit donner des résultats favorables.

<table><caption>Tableau III
Effet du préchargement</caption><thead><tr><th></th><th>Nombre d'usagers</th><th>sans préchargement</th><th>avec préchargement</th></tr></thead><tbody><tr><td rowspan="3">Taille moyenne des requêtes (pages)</td><td>10</td><td>1.5</td><td>2.5</td></tr><tr><td>20</td><td>2.9</td><td>5.5</td></tr><tr><td>30</td><td>5.0</td><td>9.0</td></tr><tr><td rowspan="3">Nomre de requêtes</td><td>10</td><td>2470</td><td>1470</td></tr><tr><td>20</td><td>1710</td><td>910</td></tr><tr><td>30</td><td>960</td><td>560</td></tr><tr><td rowspan="3">Taux d'oisiveté des disques</td><td>10</td><td>0.55</td><td>0.63</td></tr><tr><td>20</td><td>0.16</td><td>0.33</td></tr><tr><td>30</td><td>0.07</td><td>0.15</td></tr><tr><td rowspan="3">Fraction de temps passé à la gestion du système</td><td>10</td><td>0.07</td><td>0.04</td></tr><tr><td>20</td><td>0.13</td><td>0.06</td></tr><tr><td>30</td><td>0.16</td><td>0.07</td></tr><tr><td rowspan="3">Fraction d'unité centrale disponible</td><td>10</td><td>0.91</td><td>0.94</td></tr><tr><td>20</td><td>0.84</td><td>0.91</td></tr><tr><td>30</td><td>0.79</td><td>0.88</td></tr><tr><td rowspan="3">Temps de réponse moyen (s)</td><td>10</td><td>1.10</td><td>0.98</td></tr><tr><td>20</td><td>3.19</td><td>2.49</td></tr><tr><td>30</td><td>8.41</td><td>7.33</td></tr></tbody></table>

<table><tr><td>Paramètres : NPP = 100</td><td>Pas de pages partagées</td></tr><tr><td rowspan="3">Programme avec noyau</td><td>N = 50</td></tr><tr><td>NWS = 10</td></tr><tr><td>PWS = 0.80</td></tr></table>

Ces résultats donnent lieu aux remarques suivantes :

- avec le préchargement, la taille moyenne des requêtes est augmentée, et leur nombre diminué, le nombre total de pages transférées restant sensiblement constant (il est légèrement supérieur avec préchargement, en
raison de l'incertitude sur l'utilisation des pages préchargées). L'al-
longement des requêtes a pour effet d'augmenter le taux d'oisiveté des
disques.

- La fraction du temps de processeur consacrée à la gestion du système est réduite, ce qui semble devoir être attribué au nombre moindre de défauts de page ; le taux d'oisiveté de l'unité centrale est corrélativement augmenté.

- Les facteurs précédents donnent lieu à une légère amélioration du temps de réponse moyen.

En fait, dans les conditions habituelles d'utilisation d'un système d'exploitation, il est souvent difficile d'estimer a priori avec précision la probabilité d'utilisation des pages. Il était donc intéressant d'examiner l'influence comparée du préchargement pour plusieurs types de comportement. On a fait varier la taille du noyau entre 0.33 et 1 fois la taille du programme ; le dernier cas correspond à une ignorance complète du programme. Les résultats sont résumés, en ce qui concerne le temps de réponse moyen, dans le tableau IV.

<table><caption>Tableau IV</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="2">Temps de réponse moyen</th></tr><tr><th>sans préchargement</th><th>avec préchargement</th></tr></thead><tbody><tr><td rowspan="3">taille relative du noyau NWS / N</td><td>1/3</td><td>2.21</td><td>1.65</td></tr><tr><td>1/2</td><td>5.42</td><td>5.09</td></tr><tr><td>1</td><td>9.80</td><td>10.5</td></tr></tbody></table>

On constate que l'influence favorable du préchargement diminue, et tend même à s'inverser lorsque la qualité de la prévision des pages à précharger diminue.

## 4.22 Prévidage

Le principe du prévidage consiste à utiliser le temps d'oisiveté du canal de communication entre mémoire centrale et disques pour transférer vers ceux-ci des pages quasi-libres. Le but recherché est d'augmenter le nombre de pages libres directement réutilisables, et donc de réduire le temps moyen d'allocation des pages. Un risque possible est que l'exécution des requêtes de prévidage retarde la prise en compte de requêtes pour le compte des usagers. En conséquence, le prévidage n'est lancé que si la file des usagers courants est vide.

On a d'abord examiné l'influence d'une limitation du nombre de pages prévidées. On obtient des courbes ayant l'allure de celle représentée sur la figure 5 ; on voit, dans les conditions de l'expérience, que l'on a intérêt à prévoir toutes les pages quasi-libres. On observe une amélioration de l'ordre de 30 % ; ce chiffre s'explique par le fait qu'environ un tiers des échanges entre mémoire et disque sont des vidages, une page sur deux étant écrite.

On a représenté sur la figure 6 la variation du temps de réponse moyen en fonction de la charge avec et sans prévidage. On constate que l'efficacité du prévidage est maximale à charge moyenne ; à charge faible, l'avantage est négligeable ; à charge élevée, le prévidage tend à avoir un effet défavorable sur le temps de réponse.
Essayons d'expliquer ce comportement : à faible charge, la réserve de pages libres suffit en grande partie à satisfaire les demandes de pages ; son extension par le prévidage ne procure donc qu'un avantage réduit. A charge très élevée, l'activité du canal des disques est grande, et le probabilité d'interférence des requêtes de prévidage avec les autres requêtes augmente. Cela entraîne un retard moyen qui se traduit par l'accroissement du temps de réponse.

## 4.3 Partage de l'information

Dans le système ESOPE, les programmes communs à plusieurs usagers sont écrits de façon réentrante, ce qui permet de partager les pages contenant leur code et leurs données invariantes. Ce partage réduit le nombre de chargements de pages, et la place occupée en mémoire. On étudie ici les problèmes de gestion des pages partagées, et les actions qui tendent, au niveau de la gestion des usagers, à créer des conditions favorables au partage.

## 4.31 Gestion des pages partagées

La figure 7 montre l'effet global du partage sur le temps de réponse, effet net mais non spectaculaire ; il faut de plus noter que la préférence d'un noyau unique dans le programme crée des conditions particulièrement favorables au partage.

Ces conditions seraient moins favorables avec un modèle à localité variable représentant plus fidèlement la réalité.

On a également porté sur la sur même figure la variation du nombre de pages récupérées, avec et sans partage ; comme on peut s'y attendre, le partage d'information augmente le nombre de pages récupérées ; on peut également noter la croissance, avec la charge, du nombre de pages partagées effectivement réutilisées.

Lorsqu'on applique la politique de réservation de mémoire indiquée au §3.2, l'utilisation de fichiers partagés pose le problème de la réservation de place pour ces fichiers. Si on réserve une place égale à la taille totale du fichier, on risque une sous-utilisation de la mémoire. On diminue ce risque en réservant un nombre de pages égal à la taille estimée du noyau, et en atténuant le caractère strict de cette réservation (les dépassements sont autorisés dans la limite des pages disponibles). La figure 8 représente les résultats d'une expérience où on a réservé soit la taille totale soit la taille du noyau avec possibilité de débordement. On constate, dans les conditions de cette expérience que la différence des performances est faible.

## 4.32 Regroupement des usagers

Le partage de pages augmente d'autant plus l'efficacité du système que les usagers utilisant simultanément les informations partagées sont plus nombreux. Aussi est-il naturel de chercher à contrôler le cycle des usagers et la gestion des fichiers partagés de façon à créer des conditions favorables au partage.

L'idée du regroupement des usagers prêts consiste à rassembler, dans la file P, ceux des usagers partageant un même fichier. On y parvient simplement en donnant une priorité supérieure aux usagers partageant un fichier avec d'autres. On augmente ainsi les chances de ces usagers de se retrouver ensemble dans l'état courant. En fait, l'expérience montre que l'effet du regroupement ne se fait sentir qu'à charge élevée. Cet effet est évidemment fonction de la fraction de la population totale participant au partage. Les résultats représentés sur la figure 9 montrent que, dans les conditions de l'expérience, l'effet global du regroupement est
nul ou même négatif : le temps de réponse est amélioré pour les usagers participant au partage, mais détérioré pour les autres.

Une autre façon de favoriser le partage d'information est de maintenir les fichiers partagés en mémoire aussi longtemps que possible, ou plus exactement, tant qu'ils ont une certaine probabilité d'être utilisés. La difficulté réside dans l'estimation de cette probabilité. On utilise dans ESOPE un compteur pour chaque fichier partagé indiquant le nombre d'usagers *courants* ayant *ouvert* ce fichier ; le fichier reste en mémoire tant que ce compteur est positif.

Une variante de cet algorithme consiste à faire enregistrer par ce compteur le nombre d'usagers *courants ou prêts* utilisant le fichier. On constate que cette modification n'améliore pas le temps de réponse de façon visible, mais au contraire défavorise les usagers qui ne participent pas au partage.

Tenant compte du fait que le modèle à noyau unique tend plutôt à favoriser le partage, on peut conclure en définitive au peu d'intérêt des modifications de la stratégie d'allocation tendant à favoriser le partage.

## 5. Conclusion

Cette série de simulations a permis de mettre en évidence le bienfondé de plusieurs des stratégies d'allocation de ressources utilisées dans le système ESOPE. L'étude sur un modèle permet de dépasser l'intuition qualitative et de se faire une idée, au moins approchée, du comportement quantitatif d'un système. C'est ainsi qu'on a pu constater l'influence bénéfique, sous certaines conditions, de la politique de réservation de mémoire, de l'optimisation du transfert mémoire-disque, du partage des pages. Dans de nombreux cas, en revanche, la comparaison de deux politiques ne permet pas de conclure nettement, les résultats étant équivalents dans l'environnement étudié. Par ailleurs, la simulation permet de détecter les "fausses améliorations" : une modification locale d'une stratégie peut qualitativement apparaître comme un progrès ; elle ne sera en fait bénéfique qu'à la double condition de servir suffisamment souvent et de ne pas entraîner par ailleurs de conséquences négatives imprévues.

## Références

[1] C. BETOURNE, J. BOULENGER, J. FERRIE, C. KAISER, S. KRAKOWIAK, J. MOSSIERE.
Le Système ESOPE.
Congrès d'Informatique AFCET, Paris 1970.

[2] P.J. DENNING. Thrashing, its causes and prevention.
Proc. AFIPS FJCC, 1968.
<figure><img src="image_4.png" /><figcaption>Figure 1 : Temps d'exécution des transferts mémoire-disque</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 2 : Effet global de l'optimisation des transferts</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 3 : Effet du comportement des programmes</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 4 : Ecroulement</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 5 : Efficacité du prévidage</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 6 : Effet de la charge sur l'efficacité du prévidage</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 7 : Effet du partage d'information</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Figure 8 : Réservation des fichiers partagés</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 9 : Effet du regroupement des utilisateurs d'un fichier partagé</figcaption></figure>