IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

Dur = 02252

laboratoire de recherche
en informatique
et automatique

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

ADAPTATION AUTOMATIQUE
DES PROGRAMMES
AU MILIEU PAGINÉ

M. S. ACHARD
J. Y. BABONNEAU
G. MORISSET

Rapport de Recherche N° 196
Octobre 1976

S1P
ADAPTATION AUTOMATIQUE DES PROGRAMMES
AU MILIEU PAGINÉ

M.S. Achard, J.Y. Babonneau, G. Morisset

Résumé :

L'efficacité des algorithmes de pagination dans les systèmes à mémoire virtuelle dépend de l'existence dans un programme d'une localité des références aux informations. Cette localité peut être améliorée en restructurant dans l'espace virtuel les blocs qui constituent le programme. [HATFIELD & GERALD 71] [FERRARI 73] [MASUDA SHIOTA NOGUCHI & OHKI 74].

Nous proposons une solution générale et automatique en situant cette restructuration au niveau de l'édition de liens.

Cette solution s'est concrétisée sous forme d'un système auto-adaptatif. Une réduction de 40 % à 70 % du nombre de défauts de page a été obtenue.

Abstract :

The efficiency of replacement algorithms in paginated virtual storage memory depends upon the locality of memory references. Restructuring blocks which compose the program may improve this locality. [HATFIELD & GERALD 71] [FERRARI 73] [MASUDA SHIOTA NOGUCHI & OHKI 74].

In confining this restructuring to the linkage-editing, a general and automatic solution has been formulated. This solution is realised in the form of an adaptive system. A reduction of 40 to 70 % in the rate of page faults has been obtained.
ADAPTATION AUTOMATIQUE DES PROGRAMMES
AU MILIEU PAGINE

M.S. ACHARD, J.Y. BABONNEAU, G. MORISSET

Résumé :

L'efficacité des algorithmes de pagination dans les systèmes à mémoire virtuelle dépend de l'existence dans un programme d'une localité des références aux informations. Cette localité peut être améliorée en restructurant dans l'espace virtuel les blocs qui constituent le programme.

[HATFIELD & GERALD 71] [FERRARI 73] [MASUDA SHIOTA NOGUCHI & OHKI 74].

Nous proposons une solution générale et automatique en situant cette restructuration au niveau de l'édition de liens.

Cette solution s'est concrétisée sous forme d'un système autoadaptatif.

Une réduction de 40 à 70 % du nombre de défauts de page a été obtenue.

Abstract :

The efficiency of replacement algorithms in paginated virtual-storage
memory depends upon the locality of memory references. Restructuring
blocks which compose the program may improve this locality. [HATFIELD &
GERALD 71] [FERRARI 73] [MASUDA SHIOTA NOGUCHI & OHKI 74].

In confining this restructuring to the linkage-editing, a general and
automatic solution has been formulated. This solution is realised in the
form of an adaptive system. A reduction of 40 to 70 % in the rate of
page faults has been obtained.
# SOMMAIRE

## Introduction

## CHAPITRE 1 - SPECIFICATION DU PROBLEME .................................... 2

### 1.1 Gestion de la mémoire dans les systèmes.................................. 3

### 1.2 Limites de la pagination.................................................... 3

### 1.3 La restructuration............................................................ 5

### 1.4 Solution proposée : le RELIEUR ............................................ 7

## CHAPITRE II - LE RELIEUR OUTIL D'ADAPTATION AU MILIEU PAGINE ............ 10

### 2.1 Triangle d'auto-adaptation.................................................. 12

### 2.2 Structure du Module de Chargement ...................................... 15

### 2.3 Incorporation des "privés".................................................. 15

### 2.4 Module de mesure.............................................................. 16

#### 2.4.1 Le Surveillant............................................................ 18

#### 2.4.2 Le Gérant................................................................. 20

#### 2.4.3 Double fonction du module de mesure............................ 21

### 2.5 Module d'analyse.............................................................. 22

#### 2.5.1 Constitution des noyaux.................................................. 23

#### 2.5.2 Calcul de l'implantation............................................. 24

## CHAPITRE III - PRESENTATION DES RESULTATS ............................ 27

### 3.1 Examen de la matrice dynamique............................................ 29

### 3.2 Mesures faites sur le comportement du RELIEUR en milieu paginé.. 32

### 3.3 Calcul de la nouvelle implantation........................................ 35

### 3.4 Amélioration apportée par la restructuration............................ 35

## CONCLUSION .................................................................................. 44

## BIBLIOGRAPHIE ............................................................................ 46
## INTRODUCTION

Les systèmes d'exploitation paraissent adopter de plus en plus le concept de mémoire virtuelle. Ce concept part d'une hypothèse fondamentale : existence dans un programme d'une localité des références aux informations. Or il semble que cette localité soit souvent insuffisante provoquant, sinon un écoulement du système, tout au moins une nette détérioration de ses performances.

La solution consiste à améliorer cette localité en restructurant dans l'espace virtuel les blocs qui constituent le programme. Des expériences ont déjà été faites dans ce sens mais elles se situent au niveau de la compilation et semblent partiellement automatiques.

Nous proposons le RELIEUR, qui constitue l'élément central du projet OPALE mené au LABORIA, comme outil d'adaptation des programmes au milieu paginé. Ce processeur, dont la première fonction est l'édition de liens, est :

- d'une part, du fait de sa place dans la chaîne de traduction, indépendant des langages de programmation utilisés ; il a de plus une vision globale du programme,

- d'autre part, entièrement responsable de l'implantation des blocs qui sont pour lui les sections.

La restructuration des sections d'un programme se fait en deux étapes :

- à partir d'un examen statique du programme, ou d'une matrice dynamique représentant son comportement en milieu paginé, le RELIEUR le découpe en "segments" : ensemble de sections fortement liées.

- en fonction de cette matrice dynamique, il définit une implantation des sections de chaque segment en minimisant les références interpages (création d'un noyau, diminution des chevauchements de sections sur des frontières de pages).

Dans ce rapport nous décrivons :

- l'outil d'évaluation du programme et sa mise en oeuvre par l'intermédiaire du RELIEUR,

- les résultats obtenus sous le système expérimental ESOPE qui nous ont amenés à poursuivre ces recherches sous SIRIS 8 paginé (système d'exploitation de l'IRIS 80 de CII-HB). Les expériences en cours sur ce dernier système et les résultats acquis seront publiés ultérieurement.
# CHAPITRE I

## SPECIFICATION DU PROBLEME
# 1.1 GESTION DE LA MEMOIRE DANS LES SYSTEMES

Les systèmes et leurs traducteurs sont responsables du passage d'un programme du milieu logique au milieu physique et de son exploitation dans ce milieu qui est transparent à l'utilisateur. La responsabilité de ce dernier se limite à construire des entités logiques en ayant à sa disposition des processeurs et des ressources virtuelles. C'est le système qui gère les besoins en processeurs, mémoire, périphériques, nécessaires à la transformation puis à l'exécution de ces entités logiques.

Un nombre de plus en plus important de systèmes offre en particulier à leurs usagers un espace adressable très grand, qui est la mémoire virtuelle.

L'implantation du programme en mémoire physique et la transformation adresse virtuelle - adresse physique est bien sûr une tâche du système. Cette mémoire virtuelle est découpée en blocs qui permettent au système de la gérer plus facilement.

Plusieurs méthodes sont utilisées : la pagination, la segmentation ou une combinaison des deux.

Ces méthodes sont particulièrement utiles dans les systèmes temps partagé. Un programme ne nécessitant pour s'exécuter en mémoire centrale qu'un espace, en général, très inférieur à sa taille, le système peut admettre plus d'usagers pour une même taille de mémoire centrale.

# 1.2 LIMITES DE LA PAGINATION

Une pagination nécessite en particulier un algorithme de remplacement de pages. C'est lui qui décide, lorsqu'une page référencée ne se trouve pas en mémoire centrale (défaut de page), quelle est la page qu'il faut ranger en mémoire secondaire pour faire une place à la page manquante. De nombreuses études ont été faites sur ces algorithmes pour minimiser le nombre de transferts de pages [DENNING 68]. En effet ces transferts coûtent chers : chacun d'eux nécessite deux accès au disque (un seul si la page à vider n'a pas été modifiée depuis son arrivée en mémoire centrale). L'algorithme optimal est celui qui connait la chaîne de références futures et n'est donc pas réalisable.
Les recherches entreprises sur les algorithmes réalisables ont montré qu'ils ne sont pas trop éloignés de l'algorithme optimal (figure 1).

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

En dépit de cela, il s'est avéré que les transferts de pages dans un système pouvaient devenir trop nombreux et provoquer l'écroulement du système ("thrashing"), ou du moins, une nette détérioration du temps de réponse. Nous l'avons nous-même observé sur le système ESOPE cons-truit à l'IRIA.

Ceci vient du fait de la superposition d'un milieu logique sur un milieu physique, sans que le premier milieu soit adapté au second. Le milieu physique est imposé par des contraintes de gestion de mémoire, sans aucun rapport avec la structure logique du programme.
## 1.3 LA RESTRUCTURATION

Il est donc nécessaire d'adapter les programmes au milieu paginé. Cette adaptation passe par l'augmentation de leur localité : [DENNING 68].

Il s'agit de déterminer une nouvelle implantation des informations dans les pages de l'espace virtuel pour diminuer les références interpages. Dans ce but, on essaye de grouper dans de mêmes pages des informations qui sont référencées dans un même intervalle de temps (pour le code comme pour les données). On pourrait envisager d'implanter "à côté" d'une instruction, les instructions et les données, qu'elle réfère le plus souvent.

L'énormité du problème, vu sous cet angle, interdit toute solution réalisable.

Par contre on peut suivre la même approche pour des ensembles de code ou de données que nous appellerons "blocs", à condition toutefois que ces ensembles aient une taille moyenne très inférieure à une page. Les corps des procédures et les zones de données, générées par beaucoup de traducteurs, forment de tels ensembles et peuvent être manipulés facilement.

Un exemple théorique montre bien l'amélioration que l'on peut espérer d'une réimplantation des blocs d'un programme (figure 2).

Le schéma (a) représente la fréquence d'utilisation des instructions d'un programme de sept blocs au cours d'une exécution. On voit que les six pages ont été référencées. Supposons que les blocs soient mis dans l'ordre 2-4-6-1-3-5-7, la même exécution ne référencera plus que trois pages (b). Si la fenêtre d'espace physique est de trois pages, nous voyons tout de suite le gain du nombre de défauts de page obtenu.

Une autre implantation (c), où le bloc ⁴ n'est plus à cheval sur une frontière de page, n'utilise toujours que trois pages d'espace virtuel et pourrait encore améliorer le nombre de défauts de pages.

Des recherches ont ainsi été effectuées depuis plusieurs années sur la réorganisation de l'espace virtuel des programmes en vue d'améliorer leur localité.

COMEAU pense que c'est au programmeur d'avoir une connaissance du milieu dans lequel sera traité son programme [COMEAU 67].

Des recherches sur des algorithmes de restructuration se sont développées et ont donné de bons résultats [HATFIELD & GERALD 71] [FERRARI 74] [MASUDA SHIOTA NOGUCHI & OHKI 74].

Cependant ces solutions sont partiellement automatiques puisque le réarrangement des blocs est manuel et que, de plus, l'existence des blocs est tributaire du langage dans lequel a été écrit le programme à restructurer.
<figure><img src="image_3.png" /></figure>

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

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

Exemple de restructuration

<caption>Figure 2</caption>
Il est donc souhaitable d'exhiber une solution générale, automatique et efficace. C'est ce que nous avons réalisé en utilisant le RELIEUR, dont la première fonction est l'édition de liens, comme outil d'adaptation au milieu paginé.

## 1.4 SOLUTION PROPOSEE : LE RELIEUR

Tous les traducteurs transforment un texte source en un Module Objet décrit dans un langage intermédiaire qui est le Langage Binaire Objet (LBO). Le RELIEUR reçoit en entrée l'ensemble des Modules Objets composant le programme pour en former un programme exécutable (*) (figure 3).

Il possède, en raison de sa place privilégiée dans la chaîne de traduction du système, plusieurs avantages :

- connaissance globale du programme,

- indépendance vis à vis des langages de programmation,

- il est entièrement responsable de l'implantation.

<footnote>(*) La place du RELIEUR n'est pas toujours celle qui vient d'être décrit-te. En effet l'édition de liens peut se faire à l'exécution : édition de liens dynamique réalisée par exemple sur des systèmes tels que Multics 645. On y définit des segments : entités logiques d'informations translatables, définies et nommées par le programmeur. Le lien entre les segments est réalisé à l'exécution avec possibilité de partage des segments, augmentation de leur taille... Ces systèmes très évolués, outre la complexité de l'implémentation hardware, grèvent considérablement le temps d'exécution.</footnote>
<figure><img src="image_6.png" /><figcaption>Schéma de la chaîne de traduction d'un programme constitué de trois modules écrits en FORTRAN, PL1, Langage d'assemblage.</figcaption></figure>

Chaîne de traduction

Figure 3
A son niveau le programme est constitué de blocs ou sections
bien adaptés à une restructuration. Il est en effet nécessaire que
ces blocs aient des tailles moyennes très inférieures à une page et
c'est ce que nous constatons dans la plupart des programmes. Mais,
une restructuration se fait en fonction de mesures prélevées sur le
programme qui peuvent être obtenues par le RELIEUR de deux façons :

- à l'édition de liens, il met en évidence les liens de section à section et les mémorise dans une matrice statique,

- à l'exécution, les références de section à section sont comptabilisées par un module incorporé au programme par le RELIEUR.

Nous mettrons ainsi en évidence le rôle fondamental que doit
jouer le RELIEUR dans la restructuration. Nous présenterons d'autre
part différents algorithmes mis en oeuvre dans un module qui analyse
les mesures afin de déterminer une nouvelle implantation :

- un algorithme qui, appliqué à une matrice statique ou
dynamique, met en évidence une structure du programme sous forme
de segments, un segment étant un ensemble de sections fortement
liées entre elles [ACHARD 75].

- constitution d'un noyau dans chaque segment. Ce noyau, déterminé à partir de la matrice dynamique, est composé des sections clés du segment.

- un algorithme d'implantation proprement dit : il minimise les chevauchements des sections sur les frontières de page.

La place centralisatrice du RELIEUR dans la chaîne de traduction d'un système, son indépendance vis à vis des langages de programmation, lui donnent de grandes responsabilités dans la gestion de l'information. Nous le proposons comme outil d'adaptation au milieu paginé.

<footnote>* Un Module Objet est constitué d'un nombre quelconque de sections. Une section est l'image d'un ensemble de mots contigus de la mémoire. Ces sections sont définies par le programmeur dans un langage d'assemblage ou par le compilateur dans un langage évolué.</footnote>
# CHAPITRE II

## LE RELIEUR OUTIL D'ADAPTATION

### AU MILIEU PAGINE
Un programme au niveau du RELIEUR est constitué par un ensemble de sections et c'est le RELIEUR qui est responsable de leur implantation. Nous avons vu d'autre part qu'une restructuration d'un programme en vue de son adaptation au milieu paginé, ne pouvait se faire que sur des blocs d'information ayant les propriétés suivantes :

- leur implantation dans l'espace virtuel peut être quelconque

- leur taille moyenne est très inférieure à une page.

C'est le cas des sections des modules objets d'un programme : leur taille moyenne se situe en effet entre 1/5 et 1/3 de la taille d'une page (512 mots).

Le RELIEUR peut donc être l'outil de l'adaptation des programmes au milieu paginé. De plus, sa place dans la chaîne de traduction lui donne une vision complète du programme et permet une restructuration indépendamment du ou des langages utilisés.

A partir des liens statiques qui existent entre les sections, il est déjà susceptible de mettre en évidence une structure du programme [ACHARD 75]. Ainsi l'élaboration d'une matrice statique Ms, représentant les liens de section à section, lui permet de grouper les sections fortement liées pour en constituer des segments. Cette matrice carrée de dimension n (n sections) est telle que $m_{ij}$ représente le nombre de références de la section i à la section j. Le découpage en segments, obtenu à partir d'un algorithme de reconnaissance des formes, reflète la logique du programme.

Mais une étude statique est insuffisante pour adapter les programmes au milieu paginé : la connaissance de leur logique ne saurait améliorer de façon satisfaisante un comportement qui est lié à l'environnement physique dans lequel il s'élaborate. C'est pourquoi il est nécessaire de prélever des mesures sur le comportement du programme pour, ensuite, l'adapter au milieu paginé. La solution de cette adaptation consiste à augmenter la localité en modifiant l'implantation des blocs d'informations constitués au niveau du RELIEUR par les sections.

Les mesures relatives au comportement du programme sont mémorisées dans la matrice dynamique Md : $m_{ij}$ représente le nombre de branchements de la section i à la section j ou le nombre de références de i vers j au cours de l'exécution. Md est identique à la matrice de HATFIELD et GERALD.

Dans ce chapitre nous allons montrer de quelle façon nous avons réalisé cette restructuration. Nous pouvons représenter les différentes étapes qui la constituent à l'aide d'un triangle que nous appelons triangle d'auto-adaptation.
Nous décrirons ensuite :

- comment le RELIEUR constitue le module de mesure :
  Incorporation des privés,

- le module de mesure,

- le module d'analyse.

## 2.1. TRIANGLE D'AUTO-ADAPTATION

Ce triangle représente l'ensemble des moyens mis en œuvre pour réaliser une restructuration (figure 1).

<figure><img src="image_7.png" /><figcaption>Triangle d'auto-adaptation
Figure 1</figcaption></figure>
Le point d'entrée dans ce triangle est le RELIEUR.

L'échange d'informations entre ces trois processeurs s'effectue par l'intermédiaire du Module de Chargement du programme étudié.

C'est dans ce fichier, crée par le RELIEUR, que sont rangées toutes les informations relatives à la restructuration et, en particulier, la matrice statique à la première édition de liens, dynamique après exécution.

Quels sont les cheminements possibles dans ce triangle ?

- A la première édition de liens, le RELIEUR, après avoir constitué la matrice statique, peut demander une segmentation au module d'analyse (liaison ①-③). Il en tient compte pour constituer le Module de Chargement du programme contenant le module de mesure.

- Le programme est ensuite surveillé au cours de l'exécution par ce module de mesure ② qui construit la matrice dynamique.

- Après cette première mesure, il est fait appel au module d'analyse qui en déduit une nouvelle implantation ③.

- Le RELIEUR restructure le programme en créant un nouveau Module de Chargement qui tient compte de cette implantation.

Une grande souplesse a été introduite dans ce schéma.

L'appel au module d'analyse pour obtenir une implantation peut se faire à partir du RELIEUR pendant la deuxième reliure. Il est possible de demander une segmentation à partir d'une matrice dynamique.

On peut enfin parcourir le cycle une deuxième fois, en surveillant le programme restructuré ou, avec le programme initial mais avec d'autres données. Dans le cas d'une deuxième surveillance, la matrice dynamique peut être remise à zéro au préalable ou cumuler les nouvelles références.

Il est alors possible de réaliser une deuxième restructuration et ainsi de suite.

On voit donc que l'on possède un ensemble d'outils assez souples pour restructurer un programme.

L'état actuel de nos recherches ne nous permet pas de dire s'il existe une meilleure façon de procéder, si oui quelle est-elle, vaut-il mieux faire une segmentation sur une matrice statique ou dynamique, faut-il faire des mesures pour un échantillon très large de données...

L'expérience nous le dira, mais nous possédons tous les outils pour agir de façon automatique, sur un programme quelconque, indépendamment du langage utilisé. Les premières expériences que nous détaillons plus loin donnent déjà de très bons résultats.
<figure><img src="image_8.png" /><figcaption>a Module de chargement</figcaption></figure>

Pointeurs vers les
lignes et les
colonnes de
MAT-ACCES

<figure><img src="image_9.png" /><figcaption>b MATRICE</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>c DESCRIPTION</figcaption></figure>

Pointeurs vers les
segmentations et les
implantations

Ensemble de
segmentations et
d'implantations

Structure du Module de Chargement

Figure 2
## 2.2. STRUCTURE DU MODULE DE CHARGEMENT

Nous avons vu le rôle de plaque tournante du Module de Chargement dans le triangle d'auto-adaptation. C'est lui qui représente le programme à chaque étape du cycle.

Citons brièvement ce qu'il contient (figure 2) :

a) les informations relatives au chargement du programme.

- une première page HEAD servant à décrire la structure du module, le point d'entrée, les protections des pages du programme.

- une table MAGMA contenant tous les externes de ce programme et leurs adresses.

- le programme lui-même, non translatable, prêt à être chargé en mémoire centrale.

b) les informations relatives à la restructuration.

- la matrice MAT-ACCES de liaison de section à section (statique ou dynamique).

- pour chaque section (SECT) : sa taille (TAILLE), sa protection (PROT), son adresse (ADR).

- les noms des Modules Objets constituant le programme (TABLE-ANAL).

- une ou plusieurs descriptions en segments suivant que le module d'analyse a été sollicité une ou plusieurs fois (SEG).

- une ou plusieurs implantations (IMP).

- des informations relatives à chaque implantation, représentant le nombre de défauts de pages en fonction de la fenêtre, permettant de faire des comparaisons sur ces implantations (RESULTATS).

- le module de mesure. Il est en effet incorporé au Module de Chargement.

## 2.3. INCORPORATION DES "PRIVES"

Sous ESOPE le module de mesure n'est pas indépendant : il est incorporé à chaque programme surveillé. Le RELIEUR reçoit donc en entrée deux ensembles de modules objets, les modules usagers et les modules dits "privés", en n'établissant aucun lien entre chacun des deux ensembles.

On peut ainsi avoir deux externes de même nom dans les deux ensembles. Les deux externes seront considérés comme des objets différents (figure 3).
<figure><img src="image_11.png" /><figcaption>Figure 3</figcaption></figure>

L'établissement des liens à l'intérieur de chaque ensemble se fait au cours de la même reliure.

Le RELIEUR a ainsi la possibilité d'incorporer à un programme des modules de surveillance, de prélèvement de mesures, de statistique, de mise au point... Ces modules peuvent être conçus indépendamment du programme usager, sans avoir à prendre en compte les conflits de noms d'externes qui pourraient exister entre les deux ensembles.

## 2.4. MODULE DE MESURE

Nous avons vu la nécessité de réaliser une analyse du comportement du programme avant de le restructurer. La restructuration porte sur les sections. Il nous faut donc capter les références faites entre elles au cours de l'exécution.

Plusieurs solutions se présentent :

a) Interpréter le programme. Ce procédé se révèle particulièrement lourd

b) Surveillance de tous les branchements d'une section à une autre.
Le RELIEUR aurait pu générer à chaque branchement inter-section un dérou-
tement vers une séquence de mesure. Mais cette méthode, plus rapide, n'est
valable que pour les sections de code.

c) Utilisation du dispositif de violation de protection. Un dispositif hardware permet sur les machines 10070 et IRIS 80 CII-HB d'associer une protection à chaque page de la mémoire physique.

PROTECTION
{
  00 : Tout accès
  01 : Lecture Exécution
  10 : Lecture
  11 : Aucun Accès
}

La protection 11 interdit tout accès. Une tentative d'accès à une page en protection 11 provoque un "trap". Si ce trap est récupéré, il est alors possible d'exhiber un doublet d'adresses (ad1, ad2).

- ad1 est l'adresse de l'instruction qui a provoqué le trap,

- ad2 est l'adresse du mot référencé et qui est en protection 11.

Connaissant l'implantation des sections, on peut alors transformer
le doublet (ad1, ad2) en un doublet de sections (I, J). Si, au lieu de mémo-
riser les doublets (I, J) on les comptabilise dans une matrice de section à
section, on obtient alors une matrice dynamique Md.

C'est la solution qui a été adoptée.

Un module de prélèvement de mesures a été constitué sous le système ESOPE réalisant cette fonction. C'est un simulateur de pagination qui récu-père les défauts de pages par "TRAP" pour violation de protection et qui utilise le même algorithme de remplacement de pages que le système. Il est incorporé au Module de Chargement du programme à surveiller en tant que module privé et a été conçu de telle façon qu'il n'y a aucune modification à apporter au système. Pour le système il fait partie du programme usager.

Il se décompose en deux parties que nous allons détailler :
le Surveillant et le Gérant.
### 2.4.1. Le Surveillant

L'exécution du programme usager est précédée par une phase d'initialisation réalisée par le Surveillant. Il commence par armer le trap de violation de protection pour qu'il soit activé en cas de trap. Il initialise, sur demande, la matrice dynamique à 0. Ceci est nécessaire à la première surveillance. Ensuite, si la remise à zéro n'est pas demandée, les fréquences seront cumulées.

Le Surveillant différencie pages de code et pages de données pour voir l'influence des unes et des autres sur la pagination. C'est ainsi qu'il demande à l'usager le nombre de pages de code (NPC) et le nombre de pages de données (NPD) qu'il veut allouer à son programme (NPC et NPD ≥ 1). L'algorithme de remplacement de pages est appliqué séparément pour chacun des deux ensembles de pages.

Le Surveillant met d'abord toutes les pages de l'usager en protection "access interdit" et se branche à l'adresse de départ. A chaque accès à une page de données ou à une page de code protégée, le trap pour violation de protection est récupéré par le Surveillant qui exécute les phases suivantes :

2.4.1.1. Phase d'interprétation. Les valeurs de NPC et NPD peuvent descendre jusqu'à 1; beaucoup d'instructions peuvent nécessiter plus d'une page de code et plus d'une page de données. Par exemple un MBS(*) peut nécessiter au total trois pages. Autre exemple, l'instruction EXU(**) peut demander à la limite tout l'espace virtuel (EXU en chaîne).

Il est donc nécessaire d'interpréter l'instruction qui a provoqué le trap. Lors de l'interprétation, toutes les références qui auraient provoqué un défaut de page sont exhibées et comptabilisées, et ces pages sont mises en protection normale (celle demandée par l'usager), ce qui revient à les mettre momentanément dans la fenêtre, même si le nombre de pages de la fenêtre dépasse NPC ou NPD.

La figure 4 montre les différents états de la fenêtre au cours du traitement d'un trap provoqué par un chargement indirect avec NPC = 2 et NPD = 1 :

- AD1 est l'adresse de l'instruction de chargement

- AD2 est l'adresse du mot contenant l'adresse effective

- AD3 est l'adresse effective.

<footnote>(*) MOVE BYTE STRING</footnote>

<footnote>(**) EXU <ad> : Exécuter l'instruction qui se trouve à l'adresse <ad></footnote>
<figure><img src="image_12.png" /></figure>

Fenêtres successives au cours du traitement d'un trap

<caption>Figure 4</caption>

Les doublets d'adresses (ad1, ad2) (ad1 : adresse de l'instruction qui référence, ad2 : adresse du mot référencé) sont confiés au Gérant.

2.4.1.2. Après l'interprétation, il exécute l'instruction par un EXU (sauf pour les branchements, auquel cas il modifie simplement l'adresse de retour dans le programme usager qui, autrement, est égale à l'adresse de l'instruction qui a provoqué le trap + 1). L'EXU doit s'exécuter sans provoquer de défauts de pages, toutes les pages nécessaires à son exécution ayant été introduites dans la fenêtre.

2.4.1.3. Il retire ensuite de la fenêtre, suivant l'algorithme de remplacement, une ou plusieurs pages pour n'avoir que NPC pages de code et NPD pages de données.

Enfin, après restauration des registres il retourne au programme usager.
### 2.4.2. Le Gérant

Il reçoit du Surveillant, comme nous l'avons vu, un doublet d'adresses (ad1, ad2) qu'il doit transformer en un doublet de sections (I, J) pour incrémenter le compteur de l'élément de la matrice dynamique Md (I, J). Pour établir la correspondance adresse → numéro de section, deux tables ont été introduites dans le Module de Chargement du programme surveillé : ADR et SECT (figure 2). Elles donnent l'implantation des sections non vides du programme de l'usager :

- SECT contient les numéros de sections dans leur ordre d'implantation.

- ADR (i) contient l'adresse du début de la section SECT (i).

Par un simple parcours de table on peut donc trouver à quelle section appartient le mot d'adresse adi.

La matrice statique, qui est essentiellement une matrice creuse, constituée par le RELIEUR, est implantée dans le Module de Chargement sous forme de listes de cellules croisées [ACHARD 75]. Nous avons choisi d'utiliser la même structure pour la matrice dynamique que pour la matrice statique. Il n'est pas gênant de perdre cette matrice statique à partir du moment où la segmentation a été effectuée à partir de cette matrice, et que la description correspondante a été incorporée au Module de Chargement.

Des liens entre sections peuvent ne pas exister dans la matrice statique et apparaître à l'exécution. C'est le cas par exemple des branchements retours d'une procédure et des sections "à cheval" sur une frontière de page qui créent des cellules Md(I, I).

C'est pour éviter une forte augmentation du nombre des cellules de la matrice que nous avons fait le choix décrit par l'ordinogramme de la figure 5: nous avons introduit, pour chaque cellule, un flag de symétrie FLAGSYM initialisé à zéro.

Le temps passé dans le gérant s'étant avéré assez important deux optimisations ont été réalisées :

- introduction de tables permettant une traduction adresse → numéro de section plus rapide,

- création de cellules "haute fréquence" examinées avant tout parcours de listes de la matrice.

Une amélioration de 80 % du temps d'exécution du gérant a ainsi été obtenue.
<figure><img src="image_13.png" /><figcaption>Figure 5</figcaption></figure>

### 2.4.3. Double fonction du module de mesure

Nous avons vu que les valeurs de NPC et NPD, nombre de pages de code et de données allouées à la fenêtre d'exécution, pouvaient être quelconques.

Pour restructurer un programme, il est nécessaire de connaître toutes les références faites d'une section à une autre; c'est le cas lorsqu'on demande NPC = 1 et NPD = 1. Nous obtenons alors la matrice dynamique complète.
En fait nous avons supposé de façon implicite qu'il y avait au plus une section par page. Hors, pour de gros programmes, ceci n'est pas réalisable. Dans ces conditions on ne récupère pas toutes les références : une référence d'une section i à une section j situées dans la même page ne sera pas prise en compte.

Mais cet inconvénient peut disparaître en cumulant les nombres de références après plusieurs surveillances. En effet après la première surveillance le module d'analyse implantera fort probablement les sections i et j dans deux pages différentes, étant donné qu'elles n'auront aucun lien apparent dans la matrice dynamique. Une deuxième surveillance détectera alors les références entre les sections i et j. La matrice dynamique deviendra alors plus complète.

Pour comparer un programme avant et après restructuration il faut connaître le nombre de défauts de pages enregistrés pour différentes valeurs de NPC et NPD. Le Surveillant nous donne ces nombres de défauts de pages.

Le module de mesure nous permet donc de réaliser deux fonctions :
a) obtenir la matrice dynamique des références de section à section avec
NPC = NPD = 1.

b) faire des mesures sur le comportement du programme dans l'environnement d'un système paginé avec des valeurs variables de NPC et NPD. Les pages de code et les pages de données étant dissociées, il permet en outre d'étudier l'influence relative de chacun des deux ensembles. De plus tous les doublets d'adresses (ad1, ad2) tels que ad1 a provoqué un défaut de page en réfençant ad2 sont, sur option, mémorisés dans un fichier.

Nous avons donc, avec ce module de mesure, un outil de recherche sur la pagination. Nous allons maintenant voir de quelle façon nous exploitons la matrice dynamique obtenue avec ce module.

## 2.5. MODULE D'ANALYSE

Ce module constitue avec le RELIEUR et le module de mesure le troisième élément du triangle d'auto-adaptation.

Comme nous l'avons vu il peut intervenir à deux moments :
a) pendant la première reliure; lorsque la matrice statique est constituée pour réaliser une segmentation.

b) lorsque le programme a été surveillé et qu'une matrice dynamique a été constituée. A ce stade, trois actions sont possibles :

- réaliser une implantation avec les segments obtenus à l'aide de la matrice statique.
- refaire une segmentation à partir de la matrice dynamique avant de
réaliser une implantation avec les nouveaux segments.

- tenir compte des deux matrices.

Le module d'analyse se décompose donc en deux procédures :
a) une procédure de segmentation qui, à partir d'une matrice découpe le programme en segments. Ces segments forment une partition de l'ensemble des sections du programme et sont tels que :

- les sections appartenant à un même segment sont fortement liées entre elles.

- les segments sont peu liés entre eux.

C'est un algorithme de reconnaissance des formes qui effectue ce
découpage [DIDAY 73]. La description des segments est rangée dans le Module
de Chargement (figure 2).

b) une procédure d'implantation. Elle effectue l'adaptation du milieu logique au milieu physique. Il s'agit d'implanter des segments qui sont des entités logiques dans une mémoire physique constituée de pages d'une certaine taille et auxquelles sont affectées une protection.

Un premier travail consiste à extraire de chaque segment un noyau constitué par les sections les plus "importantes" de ce segment. Nous entendons par "importantes", les sections qui sont les plus référencées et qui référencent le plus d'autres sections. Ce n'est qu'après la constitution de ces noyaux que l'implantation est effectivement calculée. Nous allons maintenant décrire ces deux phases : la constitution des noyaux et le calcul des implantations.

2.5.1. Constitution des noyaux

Deux raisons nous incitent à constituer des noyaux :
1) minimiser le nombre de défauts de pages en implantant les sections d'un noyau dans un minimum de pages.

2) autoriser le préchargement car chacun d'eux peut constituer un ensemble préchargeable.

Nous allons voir comment est choisi un noyau à l'intérieur d'un
segment.

Soit $G(X, \Gamma)$ le graphe pondéré de liaison entre sections du programme

$$ \begin{cases} X : \text{ensemble des sections} \\ \Gamma : \text{application interne à X telle que } i \Gamma j \text{ si } Md(i,j) \neq 0 \end{cases} $$

avec $\delta(i,j) = Md(i,j)$
Soit $G_α$ ($X_α$, $Γ_α$) le sous graphe du segment $S_α$

$\{ X_α : \text{ensemble des sections du segment } S_α \}$

$\{ \Gamma_α : \text{application interne à } X_α \text{ telle que } i\Gamma_α j \text{ si } i\Gamma_α j \text{ avec } \delta_α(i,j)=\delta(i,j) \}$

Pour chaque section $i$ du segment $S_α$ on affecte un poids $P(i)$ qui traduira l'importance de cette section dans le segment :

$$P(i) = \sum_{k \in S_\alpha} \delta_{\alpha}(k, i) + \delta_{\alpha}(i, k)$$

Ce poids tient compte :

- d'une part du nombre de références des autres sections du segment à la section $i$.

- d'autre part du nombre de références de la section $i$ aux autres sections du segment.

Soit $N_α$ le noyau du segment $S_α$.

Par définition $N_α$ est le plus grand sous-ensemble de $S_α$ qui satisfait les deux conditions suivantes :

$$- \text{Vi} \in N_α, \text{Vj} \in S_α, \notin N_α \quad P(i) > P(j)$$

$$- \sum_{i \in N_\alpha} P(i) < a \sum_{j \in S_\alpha} P(j), a < 1$$

De la détermination de $a$ fixé à priori, nous déterminons l'ensemble des sections du noyau. Dans les résultats présentés ici, nous l'avons choisi égal à 5/6.

Le poids associé à une section pourra être modulé en fonction de sa taille, de façon à avantager les plus petites.

Le noyau de chaque segment étant constitué, il ne reste plus qu'à implanter l'ensemble des sections.

### 2.5.2. Calcul de l'implantation

L'implantation des sections nécessite la connaissance des caractéristiques physiques de chaque section :

- sa taille

- sa protection.

C'est dans ce but que ces renseignements ont été incorporés au Module de Chargement (figure 2).

L'implantation du programme a été ramenée à l'implantation d'ensembles de sections, chaque ensemble étant implanté dans un nombre entier de pages. Si on appelle "reste" d'un segment les sections de ce segment qui n'appartient pas à son noyau, on peut classer ces ensembles en deux parties :
- ceux formés pour chaque protection et pour chaque segment par les sections des noyaux.

- ceux formés pour chaque protection et pour chaque segment par les sections des restes.

La figure 6 représente l'ordre dans lequel nous avons choisi d'implanter ces ensembles.

<figure><img src="image_14.png" /><figcaption>Figure 6</figcaption></figure>

Les sections d'un noyau sont contigues dans l'espace virtuel et rangées suivant leur protection. Ainsi dans le cas d'un préchargement, un seul accès au disque amène toutes les pages du noyau en mémoire centrale.

Mais ceci entraîne de nombreux sous-ensembles qui, étant chacun implan-
té dans un nombre entier de pages, provoquent une perte de place à la fin de
la dernière page allouée à chacun de ces sous-ensembles (en moyenne une
demie page). Pour limiter cette perte de place, nous complétons la dernière
page du noyau de chaque segment par des sections du reste, ceci pour chaque
protection.

Une procédure d'alignements (CARNAC) en est responsable et veille à ce que toute section dont la taille est inférieure à une page soit toute entière contenue dans une page. Plus généralement que toute section de taille t telle que

$$n 1 < t \le (n + 1) 1$$

1 étant la taille d'une page', soit contenue dans n+1 pages. Ainsi tout chevauchement inutile d'une section sur une frontière de page est éliminé.
Ceci est très important dans le cas des sections comportant des boucles qui
pourraient se trouver "à cheval" sur une frontière de page.

Cette procédure calcule d'abord les tailles des sections modulo 1,
qui seules ici nous intéressent. En effet passer de la taille réelle à la
taille modulo 1 n'engendre dans l'espace virtuel qu'une translation d'un
nombre entier de pages ce qui ne change rien au problème de chevauchement.

L'algorithme utilisé assure l'élimination de tout chevauchement
inutile mais n'assure pas l'encombrement minimum. Ceci a peu d'importance,
car l'expérience a montré que les pertes de place en fin de page sont
minimes.

Principe de l'algorithme.

Chaque page est remplie de la façon suivante :

Si r est l'espace libre restant dans une page (initialisé à 1)

① on cherche la section, qui a la plus grande taille t module 1 parmi celles qui restent à implanter, telle que $t \le r$.

② si elle existe on l'implante, on fait $r := r-t$ et on va en ①

③ s'il n'y a plus de sections à implanter c'est terminé, sinon on remplit une autre page.

Pour chaque segment on commence par implanter les ensembles de sections du noyau de façon à pouvoir compléter les pages partiellement remplies par des sections du reste.

Les résultats de ce calcul d'implantation est rangé dans le Module de Chargement. Ils se résument en une suite ordonnée de numéros de sections qui représente l'ordre dans lequel elles devront être implantées avec, pour certaines d'entre elles, l'obligation d'être implantées au début d'une page.
# CHAPITRE III

## PRESENTATION DES RESULTATS
Nous nous proposons de présenter ici les principaux résultats obtenus sous le système ESOPE.

Une étude plus complète de l'influence relative de chacun des algorithmes et de l'influence du type de programme est en cours de réalisation sous SIRIS 8 paginé en collaboration avec une équipe système CII.

D'ores et déjà :

- d'une part la structure permettant de mettre en oeuvre cette étude est en place. La modularité qui a guidé la réalisation offre la possibilité d'améliorer ou même de remplacer aisément ces algorithmes.

- d'autre part, les résultats déjà obtenus sont très satis-faisants et nous ont confirmé l'intérêt porté à cette recherche.

Les résultats décrits dans ce chapitre concernent la restructura-tion du RELIEUR lui-même. C'est un programme de 50 sections non vides réparties comme suit :

- en protection 1, 26 sections implantées dans 16 pages (dont une section de 8 pages 1/2).

- en protection 0, 24 sections implantées dans 75 pages (dont 10 sections dans 71 pages).

Si on ne tient pas compte des sections très importantes la taille des autres est en moyenne de 1/3 de page.

Diverses catégories de résultats sont à examiner :

- les résultats révélés par l'examen de la matrice dynamique du programme,

- les mesures faites sur son comportement en milieu paginé,

- le calcul de la nouvelle implantation,

- les mesures faites après restructuration.
## 3.1 EXAMEN DE LA MATRICE DYNAMIQUE

Cette matrice a été obtenue pendant une surveillance du RELIEUR avec NPC = NPD = 1, fenêtre correspondant à une page de code et une page de données (figure 1).

La première constatation que nous ferons est que la matrice dynamique est bien plus creuse que la matrice statique malgré les 707 000 défauts de pages qui ont été enregistrés (figure 2 : matrice statique correspondante). D'une part, un grand nombre de liens statiques ont disparu d'autre part les valeurs des poids qui, pour la matrice statique, variaient entre 1 et 10 environ peuvent se diviser pour la matrice dynamique en trois groupes :

- celles qui restent de quelques unités (Symbole |).

- celles qui montent à quelques centaines (Symbole +).

- enfin quelques uns qui atteignent quelques centaines de milliers de références (Symbole *).

La très grande différence entre ces deux matrices montre bien la difficulté de prévoir le comportement d'un programme à partir d'un examen statique, sans faire ce genre de mesures.

L'exécution sous contrôle a duré 40 minutes au lieu de 6 secondes en temps normal. Un rapide calcul nous montre qu'un défaut de page a été enregistré toutes les 5 à 8 instructions en moyenne.

Plusieurs sections pouvant se trouver dans une même page, toutes les références n'ont donc pas été détectées et la restructuration a néanmoins été très efficace. Ainsi il ne semble pas que ceci ait une grande importance. De toutes façons, comme nous l'avons vu, il est toujours possible après la restructuration de compléter la matrice en faisant une deuxième surveillance qui cumule les fréquences, afin d'obtenir une meilleure restructuration ; la matrice dynamique se rapproche alors plus de la réalité. Dans une deuxième surveillance nous avons réinitialisé les poids à zéro pour comparer les deux matrices dynamiques : le nombre total de défauts de pages a été équivalent (684 000) et quelques nouveaux liens sont apparus alors que d'autres ont disparu. La somme de ces deux matrices aurait ainsi donné une matrice dynamique plus complète.
<figure><img src="image_15.png" /><figcaption>Matrice statique
Figure 2</figcaption></figure>
## 3.2 MESURES FAITES SUR LE COMPORTEMENT DU RELIEUR EN MILIEU PAGINE

La méthode de surveillance nous a permis de construire les courbes représentant le nombre de défauts de pages en fonction du nombre de pages de code et du nombre de pages de données allouées à la fenêtre.

Deux séries de courbes ont été construites :

- les courbes $y = f_{NPC}(NPD)$ représentant le nombre de défauts de pages en fonction de NPD pour NPC constant (figure 3).

- les courbes $y = f_{NPD}(NPC)$ représentant le nombre de défauts de pages en fonction de NPC pour NPD constant (figure 4).

Nous avons d'abord constaté que l'espace virtuel référencé au cours de l'exécution était de 34 pages (sur les 91 pages que comporte le RELIEUR) réparties en :

- 14 pages en protection 1 (sur les 16).

- 20 pages en protection 0 (sur les 75).

On remarque que presque toutes les pages de code ont été référencées alors que le quart seulement des pages de données l'a été.

Les courbes décrivant le nombre de défauts de pages en fonction de NPD, pour NPC constant, ressemblent tout à fait aux courbes du même genre que l'on trouve dans la littérature (Nombre de défauts de pages $= f(Taille totale de la fenêtre)$). Par contre l'autre série de courbes (NPD constant) présente un palier situé entre 5 et 10 pages qui peut s'expliquer par la présence d'une boucle nécessitant une dizaine de pages.

Nous avons aussi construit la matrice représentant les liens de section à section détectés pour des couples (NPC, NPD) égaux à (2,2) et (3,3). Les matrices obtenues sont très proches de la matrice dynamique du point de vue ensemble de cellules non vides. Seuls les poids de ces cellules sont sensiblement différents.
<figure><img src="image_16.png" /><figcaption>Nombre de défauts de pages = f(NPD)
pour NPC Constant</figcaption></figure>

Figure 3
<figure><img src="image_17.png" /><figcaption>Figure 4</figcaption></figure>
Les temps de surveillance étant proportionnels au nombre de défauts de pages et relativement élevés, le nombre de défauts de pages décroissant rapidement avec des fenêtres supérieures à (1,1), il devient alors possible et intéressant d'obtenir une bonne approximation de la matrice dynamique à moindres frais. Le nombre de défauts de pages qui est de 707 000 pour (1,1) descend en effet à 418 000 pour (2,2) et 271 000 pour (3,3).

### 3.3 CALCUL DE LA NOUVELLE IMPLANTATION

Nous avons considéré, pour la restructuration que nous avons faite, que le programme ne comportait qu'un seul segment. Pour la constitution du noyau de ce segment nous avons constaté que beaucoup de sections avaient des poids nuls ou très faibles (sections correspondant à des procédures d'erreurs ou de traitement particulier), ce qui nous a permis de constituer un noyau composé de la moitié des sections et englobant la quasi totalité des poids. Ce qui tendrait à prouver que le facteur a(§3-5-1) pourrait être plus proche de 1 que 5/6.

Pour l'alignement à des frontières de pages, nous n'avons pas perdu de page en protection 1 et une seule en protection 0 (sur les 75 pages en protection 0).

L'algorithme choisi semble donc satisfaisant pour ce problème. La présence de petites sections entraîne une perte de place vraiment minime : la première page de l'espace virtuel a été remplie à 100%.

### 3.4 AMÉLIORATION APPORTEE PAR LA RESTRUCTURATION

Cette nouvelle implantation étant calculée nous avons à nouveau relié le programme en tenant compte de cette nouvelle implantation des sections et le module de chargement ainsi créé, a été mesuré avec les mêmes données qu'en 3.2.

Les résultats ont fait apparaître une diminution considérable du nombre de défauts de pages. Cette diminution est comparable aux résultats exposés dans le chapitre III et obtenus par FERRARI, HATFIELD et GERALD et l'équipe des japonais.
<figure><img src="image_18.png" /><figcaption>Figure 5</figcaption></figure>
Défauts de pages = f(NPC)
pour NPD constant
Après Restructuration

<figure><img src="image_19.png" /><figcaption>y = f(NPD (NPC)) Après restructuration</figcaption></figure>

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

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

Comparaisons, à NPC constant, AVANT et APRES Restructuration

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

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

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

Comparaisons, à NPD constant, AVANT et APRES Restructuration

<figure><img src="image_26.png" /><figcaption>Figure 7</figcaption></figure>
Les séries de courbes de la figure 5 et de la figure 6 sont celles
du RELIEUR restructuré. Les courbes de la figure 7 montrent la diffé-
rence avant et après restructuration. On remarque que :

- l'espace virtuel référencé par la reliure surveillée qui
'était de 34 pages n'est plus que de 31 pages.

- sur les courbes à NPC constant le pourcentage du gain du nombre de défauts de pages est important ( > 50 %) lorsque NPD est supérieur à 5, mais ce pourcentage diminue lorsque NPD est en dessous de 5.

- par contre sur les courbes à NPD constant, c'est pour des valeurs de NPC inférieures à 10 que le pourcentage est très important, surtout lorsque NPC est inférieur à 5 pages.

On voit donc que c'est la restructuration du code qui parait la plus efficace et que l'on gagne plus difficilement des défauts de pages par restructuration des données. Cela s'explique par l'existence de beaucoup de tables de taille supérieure à une page et par le fait que, même si ces tables sont très peu remplies, une suite de références à n de ces tables provoque des références à autant de pages. La localité des références aux données parait donc très faible.

C'est pour cette raison qu'une procédure de gestion dynamique et auto-adaptative des tables du RELIEUR est actuellement en cours d'élaboration pour le RELIEUR.

Cependant les résultats restent très satisfaisants. La courbe
de la figure 8 montre le pourcentage du gain du nombre de défauts de
pages en fonction de la fenêtre allouée au programme (NPC+NPD). L'espace
virtuel référencé étant ramené de 34 à 31 pages le gain est évidemment
de 100 % entre 31 et 34 pages, mais on remarque qu'il en reste très
proche jusqu'à 20 pages. Il baisse ensuite au fur et à mesure que la
fenêtre diminue jusqu'à devenir négligeable (680 000 au lieu de
707 000) pour une fenêtre de deux pages (une page de code et une page
de données). Ce qui démontre que peu de références nous échappent avec
ce mode de prélèvement de mesures. On s'aperçoit que pour 7 pages,
<figure><img src="image_27.png" /><figcaption>Pourcentage du gain obtenu en fonction de la fenêtre d'exécution
Figure 8</figcaption></figure>
<figure><img src="image_28.png" /></figure>

Améliorations du nombre de défauts de pages (DP) en fonction du nombre de pages de code (NPC) et de pages de données (NPD) allouées au programme.

<caption>Figure 9</caption>
c'est-à-dire environ 1/5 de l'espace virtuel référencé, le gain est supérieur à 45 % ce qui, pour cette fenêtre, fait passer le nombre de défauts de pages de 138 000 à 74 000. De 7 à 20 pages le gain augmente de façon à peu près linéaire de 45 à 90 %.

Enfin la figure 9 nous montre globalement le gain obtenu par la restructuration. La coupe a été représentée pour NPD = 5 et NPC = 3.

Tous ces résultats ont été obtenus dès la première restructuration sur un système expérimental.

Nous poursuivons nos travaux sur le système d'exploitation SIRIS 8 version C10 de CII-HB afin de confirmer ces résultats et de valider ainsi cette recherche.
Les récents projets sur les mémoires hiérarchisées montrent
bien l'importance de plus en plus grande de la pagination dans les
systèmes d'exploitation. Certains pensent que c'est au programmeur
de construire son programme en fonction du milieu paginé pour qu'il
soit mieux adapté à ce milieu.

Nous avons la conviction que, même si la connaissance par
le programmeur du milieu dans lequel son programme va s'exécuter est
nécessaire, elle n'est certes pas suffisante. Une solution manuelle
ne peut être envisagée comme seule susceptible de résoudre de façon
efficace un problème d'une telle complexité.

D'autant plus qu'une restructuration automatique donne,
comme cette étude l'a montré, une très nette amélioration du compor-
tement des programmes en milieu paginé.

La solution que nous avons adoptée et qui consiste à proposer
le RELIEUR, dont la première fonction est l'édition de liens, comme
outil d'adaptation des programmes au milieu paginé possède une grande
généralité du fait de sa place dans la chaîne de traduction : cette
solution est en effet indépendante du langage de programmation et son
automatisme décharge complètement le programmeur du souci d'adaptation.

En outre le RELIEUR possède une vision suffisamment globale
pour que le problème soit moins complexe, en raison du nombre limité
d'entités à manipuler, et cependant assez fine pour que les algorithmes
de restructuration soient efficaces.
Des études plus complètes, sur un plus grand nombre de traducteurs, de l'influence relative de chacun des algorithmes, en particulier un algorithme de reconnaissance des formes [DIDAY 72] sont poursuivies sous SIRIS 8 paginé.

Mais, d'ores et déjà, le module de prélèvement de mesures qui dissocie page de code et page de données nous a permis de constater que la restructuration du code est plus efficace que la restructuration des données.

D'autre part nous avons prouvé que des algorithmes simples pouvaient donner de très bons résultats et améliorer considérablement le comportement des programmes en milieu paginé.

En particulier on peut espérer que la restructuration du système lui-même améliorera de façon très nette ses performances.
[ACHARD BABONNEAU MORISSET 75]

"Segmentation automatique des programmes indépendamment des langages de programmation" Mai 1975

M.S. ACHARD : Thèse 3ème Cycle. Université PARIS VI, Avril 1975

[BELADY 66]

"A study of replacement algorithms for virtual storage computers"

IBM Systems J ; pages 78-101, 1966

[BELADY KUEHNER 69]

"Dynamic espace sharing in computer systems"

Communication ACM pages 282-288, Mai 1969

[BETOURNE BOULENGER FERRIE KAISER KRAKOWIAK MOSSIERE 70]

"Process management and resource sharing in the multi access system ESOPE"

Comm. ACM, 13, 12, pages 727-733, Décembre 1970

[BRAWN GUSTAVSON 68]

"Program behavior in a paging environment"

Proc. AFIPS, Fall Joint Computer Conf. Vol 33, pages 1019-1032, 1968

[CHRETIENNE 74]

"Gestion de la mémoire des ordinateurs"

Thèse de 3ème cycle. Institut de programmation de Paris, n° IP 74-8, Mai 1974

[COFFMAN RYAN 72]

"A study of storage partitionning using à mathematical model of locality"

Comm. ACM ; 15, 3, pages 185-190, Mars 1972

[COFFMAN VARIAN 68]

"Further experimental data on the behavior of program in a paging environment"

Comm. ACM, 11, 7, pages 471-474, Juillet 1968

[COMEAU 67]

"A study of the effect of user program optimization in a paging system"

ACM Symp. on operating systems principles, Gatlinbourg, Tennessee,
1-4 Octobre 1967
[CORBATO 68]

"A paging experiment with the MULTICS system"
Rep. MAC-M-383, MIT project MAC Cambridge, Mai 1968.

[DALEY DENNIS 68]

"Virtual memory, processes and sharing in MULTICS"
Comm. ACM, 11, 5, pages 306-312, Mai 1968

[DENNING 68]

"The working-set model for program behavior"
Comm. ACM, 11, 5, pages 323-333.

[DENNING 68]

"Resource allocation in multiprocess computer systems"
Tech. Rep. MAC-TR-50, MIT project MAC, Cambridge, 1968

[DENNING 68]

"Thrashing : its causes and prevention"
Proc. AFIPS 1968, Fall Joint Computer Conf., Vol 33, pages 915-922

[DENNING CHEN SHEDLER 68]

"A model for program behavior under demand paging"
Rep. R.C. 2301 IBM T J Watson Research Center, Yorktown Heights, N.Y.,
Septembre 1968.

[DENNING SCHWARTZ 72]

"Properties of the working-set model".
Comm. ACM, 15, 3, pages 191-198, Mars 1972

[DIDAY 71]

"Une nouvelle méthode en classification automatique et reconnaissance des formes : la méthode des nuées dynamiques".
Revue de statistiques appliquées, vol XIX n° 2, 1971

[DIDAY 72]

"Optimisation en classification automatique et reconnaissance des formes"
Bulletin de l'IRIA n° 12, Mai-Juin 1972
[FERRARI 73]

"A tool for automatic program restructuring"
ACM National Conference, Atlanta, Georgia, Août 1973

[FERRARI 74]

"Improving program locality by strategy-oriented restructuring"
Information processing 1974, North Holland publishing Company

[FINE JACKSON ISAAC 66]

"Dynamic program behavior under paging"
ACM Pub. P66, pages 223-228, 1966.

[GELENBE TIBERIO 73]

"Page size in demand paging systems"
ACM-SIGME First Symp. on Measurement and Evaluation, Palo Alto, Février 1973

[HATFIELD 72]

"Experiments with page size, program access pattern and virtual memory performance"
IBM Journal of research and development, 16, 1, pages 58-66, 1972

[HATFIELD GERALD 71]

"Program restructuring for virtual memory"
IBM Syst. J. n° 3, 1971

[MASUDA SHIOTA NOGUCHI OHKI 74]

"Optimization of program organisation by cluster analysis"
IFIP 1974

[MORISSET 75]

"Adaptation automatique des programmes au milieu paginé"
Thèse 3ème Cycle Juin 75. Université PARIS VI.

[PRESSER WHITE 72]

"Linkers and loaders"
Computing Surveys, Vol. 4, n° 3, Septembre 1972