# L'acces aux informations dans le systeme multics

Jean-Serge Banino

► To cite this version:

Jean-Serge Banino. L'acces aux informations dans le systeme multics. [Rapport de recherche] IRIA-RR-217, IRIA. 1977, pp.70. hal-04716460

HAL Id: hal-04716460

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Dw-02845 RR 217

IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

L'ACCÈS
AUX INFORMATIONS
DANS LE
SYSTÈME MULTICS

Jean-Serge BANINO

Rapport de Recherche N° 217
Février 1977

70p.
L'ACCES AUX INFORMATIONS DANS LE SYSTEME MULTICS
ÉTUDE DE SYNTHESE

Jean-Serge Banino

Résumé :

Le système MULTICS, conçu et réalisé au MIT par l’équipe du projet MAC, les Laboratoires Bell et la Compagnie General Electric, constitue un exemple de projet de recherche important mené jusqu’au stade du développement industriel.

Cette étude tente, pour ce qui concerne l’accès aux informations, une synthèse des nombreuses publications faites au cours de la réalisation des versions successives du système.

Egalement sont énoncées un certain nombre de critiques issues d'études récentes qui ont pris «MULTICS» comme objet.

Abstract :

The Multics system was designed and implemented by MIT's project MAC, Bell Laboratories and the General Electric Company. It is an example of a large-scale research project carried through to the stage of industrial development.

This survey tries to synthesize the numerous papers published about successive releases of the
system.

Also a number of criticisms about Multics are extracted from recent studies.
Table des matières

1 Introduction : caractéristiques du système

2 Accès aux informations

2.1 Espace d'adressage d'un processus

2.2 Adresse segmentée

2.3 Gestion de la mémoire virtuelle

2.4 Accès à un segment

2.4.1 Initialisation

2.4.2 Connexion

2.5 Formation de l'adresse segmentée

2.5.1 Registres d'un processeur

2.5.2 Format des instructions

2.5.3 Formation de l'adresse segmentée

2.5.4 Adressage indirect

2.6 Accès aux informations

2.6.1 Les différentes classes d'information

2.6.2 Mécanismes d'accès

2.7 L'édition de liens

2.8 Communication entre procédures

2.8.1 Séquence d'appel

2.8.2 Séquence de sauvegarde

2.8.3 Séquence de retour

3 Influence des contrôles sur les mécanismes d'accès

3.1 Les contrôles d'accès

3.2 Pouvoir d'un processus

3.3 Implantation

3.3.1 Entrées du catalogue

3.3.2 Descripteurs et descriptif

3.3.3 Piles et segments de liaisons

3.3.4 Conclusion

4 Communications entre processus

4.1 Les processus

4.2 Synchronisation

4.3 Communication

4.4 Etablissement de la communication

4.5 Remarques
# 5 Le système de fichiers

## 5.1 Introduction

## 5.2 Organisation du catalogue

## 5.3 Les différents noms désignant un segment

## 5.4 Les modules du système de fichiers

## 5.5 Contrôle de l'accès au catalogue

## 5.6 Rôle du système de fichiers dans la traduction d'une référence symbolique

## 5.7 Formation des descripteurs par le module de contrôle des segments

## 5.8 Appels explicites au système de gestion des fichiers

# 6 Critiques

## 6.1 Insuffisances du principe des anneaux en ce qui concerne la protection

## 6.2 Influence du mécanisme de protection sur la taille et la complexité du noyau

### 6.2.1 Modification des différents espaces de noms

### 6.2.2 Eclatement de la fonction d'édition de liens

## 6.3 Conclusion

Bibliographie.

Glossaire.

<footnote>**Note** : Le glossaire contient les définitions des expressions qui apparaissent soulignées dans le texte.</footnote>
# 1. Introduction

## Caractéristiques du système

MULTICS (Multiplexed Information and Computing Service) est un système universel développé par le MIT (projet MAC) conjointement avec la société Honeywell et les laboratoires Bell. [1] Il présente une extension des concepts de base que l'on a rencontré dans les premiers systèmes à temps partagé. Il fut implanté d'abord sur les machines GE 645 (635 modifié) et est actuellement commercialisé sur Honeywell 6180.

Pour répondre à une généralité de besoins le système a été conçu sous forme modulaire et écrit en PL1 ; de ce fait, mises au point et extensions se font dynamiquement.

L'adressage, tant au niveau du système qu'au niveau des utilisateurs est virtuel : l'entité adressable est le segment, désignable par un nom (virtuel). Le système entier est décrit en terme de segments, si bien qu'il existe des mécanismes de désignation et d'accès identiques à tous les niveaux.

La structure d'exécution dans le système est le processus. Un processus est composé d'un ensemble de programmes et de données auquel peut être affecté un processeur. Chaque processus a son propre espace d'adressage à l'intérieur duquel il s'exécute. Par exemple tout utilisateur entrant dans le système se voit attribuer un processus. Pour s'adresser à un segment quelconque il lui suffit de pouvoir le désigner dans l'espace d'adressage de son processus.

De fait tout segment est potentiellement partageable. Il peut être désigné depuis plusieurs processus distincts.

Le partage est sélectif. Le principe du mécanisme de protection est de découper les espaces d'adressage en niveaux concentriques (anneaux) au pouvoir décroissant. Chaque opération sur un segment n'est possible que dans certains anneaux pré-définis. L'utilisateur qui travaille dans un tel anneau et qui possède le droit d'effectuer l'opération accède effectivement au segment. Un même segment peut donc être partagé par divers utilisateurs avec des droits différents.

Le principe de protection par anneaux et les règles de contrôle d'accès donnent la possibilité d'écrire des sous-systèmes et de les protéger. On peut même n'autoriser leur accès que par certains points d'entrée. Le
système peut ainsi croître dynamiquement par adjonction de modules aux fonctions bien définies.

Enfin toute désignation de segment à l'intérieur de l'espace d'adressage d'un processus peut se faire par référence virtuelle. Tout segment du système est conservé sur disque par le système de fichiers. Le couplage entre référence symbolique à un segment et sa représentation en mémoire est assuré de façon dynamique par l'éditeur de liens qui a pour charge d'identifier le segment désigné, éventuellement de provoquer son chargement en mémoire et enfin d'assurer la connexion entre ce segment et l'espace d'adressage du processus.
L'utilisateur peut donc travailler dans un espace virtuel illimité. Les liaisons sous-jacentes avec les représentations lui sont transparentes.
Nous nous intéresserons plus particulièrement dans cette étude à l'établissement des liens entre les objets du système au cours de son fonctionnement, tant du point de vue de la désignation des objets et des chemins d'accès que du contrôle de l'établissement de ces liens.

## 2. Accès aux informations

### 2.1 Espace d'adressage d'un processus

Chaque processus a son propre espace d'adressage, qui est un ensemble de segments [2]. Cet espace d'adressage est matérialisé par un ensemble de descripteurs de segments.

Un descripteur est un ensemble d'informations définissant le segment. Ces informations permettent au processus de localiser la représentation en mémoire du segment, et contiennent les attributs de protection du segment vis à vis du processus (longueur et droits d'accès).

Pour tenter un accès à un segment, le processus doit posséder un descripteur de ce segment. L'ensemble des descripteurs qu'il possède est groupé en une table de descripteurs (logée dans un segment) appelée le descriptif du processus [3]. On peut dire que le descriptif définit et matérialise l'espace d'adressage du processus.

Les segments adressables par le processus étant nécessairement représentés par une entrée du descriptif, la désignation de tout segment depuis le processus se fait par un index dans cette table.
Cette désignation est propre au processus : l'index dans le descrip-
tif constitue un _nom local_ pour le segment, et par exemple un segment partagé
par deux processus y est désigné par des noms locaux indépendants 1'un de
l'autre (figure 1).

<figure><img src="image_3.png" /><figcaption>Figure 1 : Le segment S a pour nom local s₁ dans P₁ et s₂ dans P₂.</figcaption></figure>

2.2 Adresse segmentée

Un mot d'un segment est désigné par le couple (nom local du segment,
déplacement dans le segment) (figure 2). Ce couple est appelé l'adresse segmen-
tée de cet élément d'information.

<figure><img src="image_4.png" /><figcaption>Figure 2 : Interprétation d'une adresse segmentée (s,d).</figcaption></figure>
## 2.3 Gestion de la mémoire virtuelle

Gérer la mémoire virtuelle consiste à réaliser les accès aux mots mots d'information désignés par des adresses segmentées.

La mémoire est gérée par pages. Un segment est réparti sur une ou plusieurs pages de 1024 mots chacune. La gestion des pages est invisible par l'utilisateur, qui ne connaît que des segments.

Le descripteur d'un segment contient l'adresse réelle de la table des pages du segment. Si cette table de pages n'est pas en mémoire, le descripteur contient une marque d'absence de segment. Dans ce cas un module du superviseur aura pour mission de charger cette table de pages, puis la page référencée. L'interprétation de l'adresse segmentée est visualisée par la figure 3.

<figure><img src="image_5.png" /><figcaption>Figure 3 : Dans l'adresse segmentée le déplacement (d) est interprétée en deux parties : numéro de page, déplacement d' dans la page.</figcaption></figure>

Une mémoire associative à 16 entrées accélère les accès.

Du point de vue du système un segment est dit actif si sa table de pages est en mémoire. Les tables de pages de tous les segments actifs à un instant donné sont groupées en une table des segments actifs.

C'est bien sûr une table propre au système.
Chaque entrée d'une table de pages est un descripteur de page contenant entre autre un bit de présence en mémoire. Si la page est absente, un module (de contrôle de pages) doit la charger en mémoire. Seule la page contenant le mot référencé est chargée, et non pas tout le segment.

## 2.4 Accès à un segment

L'optique générale choisie pour Multics en ce qui concerne les liaisons entre objets (segments) est de repousser l'établissement des liens au plus tard possible, lorsqu'ils sont vraiment indispensables. L'édition de liens se fait donc dynamiquement (nous en examinerons le fonctionnement par la suite), chaque référence à une donnée externe à un segment n'étant matérialisée qu'à l'exécution, au moment de l'accès effectif.

En particulier, la première référence à un segment ne se concrétise pas par un accès si le processus ne possède pas un descripteur de ce segment.

L'accès au segment s'établira en deux étapes :

- Initialisation du segment pour le processus,

- Formation d'un descripteur, ou connexion.

### 2.4.1 Initialisation

L'initialisation du segment (figure 4a) consiste à lui attribuer une entrée dans le descriptif, c'est-à-dire à lui donner un nom local au processus. Le processus connait alors le segment par ce nom. Au cours de l'initialisation une entrée de la table des segments connus du processus est allouée au segment. Y sont enregistrées des informations descriptives du segment, la plupart étant prises dans le catalogue général du système : par exemple nom symbolique par lequel se fait la référence, nom local qui vient d'être attribué, pointeur vers l'entrée du catalogue général, attributs de protection, identificateur unique du segment (nom d'horloge) etc...

Ces informations serviront à créer le descripteur lors de la deuxième étape de l'accès. Mais dès à présent toute référence au segment par son nom symbolique est traduite en son nom local par consultation de la table des segments connus.
<figure><img src="image_6.png" /><figcaption>(a) Segment initialisé (connu du processus Pᵢ)</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Segment connecté au processus Pᵢ et actif</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 4</figcaption></figure>
### 2.4.2 Connexion

Le segment initialisé, l'accès est tenté à nouveau. L'entrée du descriptif ayant été initialisé à des valeurs nulles, il y a déroutement et appel d'une procédure du superviseur qui provoquera la formation du descrip-teur au moyen des informations contenues par la table des segments connus. Quand le descripteur est créé, le segment est connecté au processus (figure 4b). L'instruction d'accès est reprise et si les droits sont adéquats l'accès est réalisé. (Ajoutons qu'à cet instant si le segment n'est pas actif il se produit un appel au module de contrôle de pages pour charger sa table de pages).

## 2.5 Formation de l'adresse segmentée

Chaque mot de l'espace adressable par le processus est accessible à partir de son adresse segmentée (nom local du segment, déplacement). Les méca-nismes d'initiation, de connexion et d'activation du segment provoquent le chargement en mémoire de l'information ainsi référencée.

Examinons quelle est la formation de cette adresse segmentée selon les types de références.

### 2.5.1 Registres d'un processeur

Un processeur dispose d'un certain nombre de registres [4] (figure 5) :

- un registre de base de descriptif

C'est le seul qui contienne une adresse physique. Il désigne la base du descriptif du processus.

- un registre pointeur de procédure, chargé avec le nom local de la procédure en cours d'exécution.

- un registre compteur d'instructions

- quatre double registres pointeurs qui contiennent chacun l'adresse segmentée d'un segment distinct du segment procédure en cours.

- huit registres d'index

- deux registres de travail.
<figure><img src="image_9.png" /><figcaption>Figure 5 : Registres d'un processeur.</figcaption></figure>

### 2.5.2 Format des instructions

Il existe deux types d'instructions, selon qu'elles commandent l'accès à un mot mémoire qui se trouve dans le segment procédure en cours d'exécution ou à l'extérieur (figure 6).
<figure><img src="image_10.png" /></figure>

instruction de type 1 (référence externe)

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

instruction de type 0 (référence interne)

Figure 6

### 2.5.3 Formation de l'adresse segmentée

- Adresse de l'instruction

Elle est formée par le contenu du registre pointeur de procédure et le contenu du registre compteur d'instructions (figure 7).

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

Figure 7

- Branchement

L'instruction de branchement est une instruction de type 0. L'adresse est formée au moyen du registre pointeur de procédure d'une part, du champ adresse de l'instruction et éventuelle d'un registre d'index de l'autre (figure 8).
<figure><img src="image_13.png" /><figcaption>Figure 8</figcaption></figure>

- Référence externe au segment procédure

Le segment externe est désigné par le champ "nom local" d'un des quatre registres pointeurs. Dans ce segment le déplacement est calculé à partir du champ adresse de l'instruction, du champ déplacement du registre pointeur et éventuellement d'un registre d'index (figure 9).

<figure><img src="image_14.png" /><figcaption>Figure 9</figcaption></figure>
### 2.5.4 Adressage indirect

En réalité le champ de l'instruction formé par les bits 30 à 35 fournit 3 bits servant à repérer l'un des 8 registres d'index, et les 2 autres bits spécifient le type d'adressage indirect éventuel.

Notons la forme d'indirection que nous rencontrerons lors de l'édition de liens : l'indirection à travers segment ("its"). C'est une façon d'adresser des informations indirectement à travers un ou plusieurs segments : l'instruction de type 1 contient une marque d'indirection ; l'adresse segmentée, formée de la façon décrite précédemment, est interprétée comme celle du premier d'une paire de mots mémoire consécutifs servant de relais à l'adressage (figure 10).

<figure><img src="image_15.png" /><figcaption>figure 10</figcaption></figure>

Le champ formé par les bits 30 à 35 du 1er mot contient la marque "its" signifiant que ce mot et son successeur sont à lire comme l'adresse segmentée terminale de la référence (comme indiqué sur la figure 10).

Le champ noté M sur la figure, comme le dernier champ d'une instruction, peut signaler une indexation sur l'adresse terminale. Il peut aussi indiquer un niveau supplémentaire d'indirection.

## 2.6 Accès aux informations

Tout accès à une information passe par une ou plusieurs adresses segmentées. Les mécanismes de formation d'adresse segmentée permettent d'accéder aux diverses classes d'informations existant pour un processus.
### 2.6.1 Les différentes classes d'informations

On distingue plusieurs classes d'informations relativement à la procédure en cours d'exécution et au processus [5] :

- Les informations internes à la procédure : étiquettes, locales, rémanentes. Elles ne sont accessibles que par la procédure. Les étiquettes sont des noms d'emplacement d'instructions (points de branchements).

Les informations locales sont propres à l'occurrence de la procédure. Elles disparaissent à la fin de l'exécution de cette procédure. Leurs valeurs initiales sont les mêmes à chaque appel de la procédure.

Les informations rémanentes sont relatives au couple procédure - processus. Initialisées au premier appel de la procédure dans le processus, leurs valeurs évoluent et se conservent d'un appel à l'autre de la procédure dans le processus.

- Les informations externes à la procédure :

Toute information accessible depuis la procédure : mot d'un segment de données ou point d'entrée d'une procédure. Mais ces informations ne sont pas propres à la procédure.

- Les paramètres

Ce sont des informations propres à l'occurrence de la procédure dont les valeurs sont des noms d'informations non internes à la procédure :

- internes de la procédure appelante

- externes de la procédure appelante

- paramètres de la procédure appelante

### 2.6.2 Mécanismes d'accès

- Etiquettes

L'instruction de branchement a été décrite au paragraphe 2.5.3.

- Informations locales à une procédure

Pour assurer le partage d'une procédure sans duplication de son segment de code, celui-ci doit être invariant.

Par conséquent, une zone de valeurs locales est attachée à chaque exécution de la procédure. Ces zones de valeurs locales sont gérées en pile dans un
segment particulier au processus, ce qui assure le fonctionnement des appels de procédure et la récursivité. L'accès à une valeur locale s' effectue par une instruction de type 1 utilisant le registre pointeur de pile qui a tout instant désigne le début de la section du segment pile attachée à l'occurrence de la procédure en cours (figure 11).

<figure><img src="image_16.png" /><figcaption>Figure 11 : Section de pile associée à une occurrence de procédure.</figcaption></figure>

L'en-tête de la section a un format standard (32 mots). Y sont rangés les informations de contexte pour permettre le fonctionnement des appels et retours de procédure. Les valeurs locales sont dans le corps de la section (de taille variable).
- Informations rémanentes

Elles doivent par définition être conservées dans une zone de données relative au couple processus - procédure.

Un segment spécial, nommé segment de liaison, est associé à chaque procédure dans un processus. Il est créé à la première occurrence de la procédure et les valeurs des informations rémanentes, initialisées à cette occasion, y sont disposées.

Le registre pointeur de liaison repère à tout instant le segment de liaison associé à la procédure en cours.

L'accès aux informations rémanentes est possible par une instruction de type 1 utilisant ce registre.

- Informations externes

Toute procédure, lorsqu'elle est écrite en langage source, désigne les informations externes par des noms symboliques.

A l'exécution ces références seront réalisées par des adresses segmentées. Mais le compilateur ne peut connaître les noms locaux des segments qui seront connectés au processus.

De plus les procédures, pour être partagées et n'exister qu'en un seul exemplaire, doivent être invariantes.

Pour ces raisons une référence à une information externe est complée en une référence indirecte à travers un segment propre au couple processus - procédure : le segment de liaison ( qui a été mentionné à propos des rémanents) car les adresses résolues d'externes sont des rémanents de la procédure (figure 12).

<figure><img src="image_17.png" /><figcaption>Figure 12</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>Figure 13 : Accès à une information externe</figcaption></figure>
L'indirection utilisée est du type défini au paragraphe 2.5.4.

Le double-mot d'indirection est appelé dans ce cas un lien. Le segment de liaison contient dans les liens les adresses segmentées des références externes.

Ainsi une référence externe est compilée en un déplacement dans le segment de liaison, ce qui assure l'invariance de la procédure.

Le segment de liaison est créé lors de la première exécution de la procédure, à partir d'une maquette située dans le segment objet lui-même.

Les adresses segmentées des références externes sont placées dynamiquement dans les liens du segment de liaison par l'éditeur de liens.

A tout instant le segment de liaison associé au couple processus - procédure est repéré par le registre pointeur de liaison.

L'accès aux informations externes est réalisé par les instructions de type 1 utilisant ce registre en mode indirect (figure 13).

## - Paramètres

La procédure appelante établit une liste de paramètres, en réalité une liste de pointeurs vers les informations paramètres.

Cette liste est placée dans la section de pile de la procédure appelante, à la suite de ses informations locales.

La structure de la liste de paramètres est la suivante (figure 14a) : une en-tête donnant le nombre de paramètres, et un corps (liste de n pointeurs vers les n paramètres).

<figure><img src="image_19.png" /><figcaption>Figure 14a :
Liste de paramètres stockée dans la pile</figcaption></figure>
<figure><img src="image_20.png" /></figure>

Figure 14b : La procédure p₁ appelle la procédure p₂ et lui passe en paramètre le nom d'un point d'entrée de la procédure p₃.

(l'indirection par le segment de liaison est justifiée au § 2.8.1.)
Chaque pointeur est un double mot - mémoire. Les accès aux paramètres se font par indirection à travers ces pointeurs qui eux-même grâce aux conventions sur l'adressage indirect, contiennent des adresses directes ou indirectes selon la classe des paramètres.
L'instruction d'accès est de type 1, utilisant le registre pointeur de paramètres qui repère la liste de paramètres.

On remarque que deux registres pointeurs (paramètres et pile) sont utilisés pour désigner la section de pile associée à la procédure appelante. Leur nécessité apparaîtra dans le paragraphe relatif aux contrôles d'accès.

Si le paramètre est une information locale à la procédure appelante, sa valeur figure dans la zone des locaux de l'appelante. Le pointeur de la liste de paramètres désigne cet emplacement. Si le paramètre est déjà un paramètre de l'appelante, le pointeur est obtenu par recopie d'une liste de paramètres à l'autre.

Si le paramètre est une information externe, le pointeur de la liste de paramètres est de type indirect. Il désigne (par une adresse segmentée selon les conventions de l'adressage indirect vues précédemment) un lien du segment de liaison de la procédure appelante. Ainsi l'adresse du paramètre est toujours valide : si le lien qu'elle désigne n'est pas résolu, il se produira, lors de l'accès indirect au paramètre, un appel à l'éditeur de liens.

Le passage en paramètre d'un nom de procédure se traduit par un pointeur désignant la procédure paramètre par indirection à travers la zone de locaux de la procédure appelante (figure 14b).

## 2.7 L'édition de liens

Le paragraphe 2.4.1 a montré que l'accès à un segment depuis un processus n'est pas immédiat. Un problème de désignation se pose puisque au moment de l'exécution un processus ne peut atteindre un segment que par un descripteur repéré dans le descriptif par un nom local.

Ce problème a été mis en évidence également au paragraphe 2.6.2 à propos de l'accès aux informations externes à la procédure en cours. Pour que les procédures puissent être compilées indépendamment du contexte d'exécution la notion de lien a été introduite, toute référence à une information externe se traduisant par une adresse indirecte. Le relais de cette indirection est un lien, c'est-à-dire un emplacement du segment de liaison propre au couple processus - procédure.
Le segment de liaison (cf figure 12) est créé à la première exécution de la procédure dans le processus, à partir d'une maquette contenue par le segment procédure lui-même. Les liens de ce segment ne sont pas résolus à cet instant, mais le sont de façon dynamique au moment des accès, comme nous allons le voir.

Dans les deux cas le problème principal se pose lors de la tentative d'accès à une information contenue dans un segment : identifier le segment et le faire entrer dans l'espace d'adressage du processus (liaison, puis connexion) : c'est le rôle de l'éditeur de liens.

L'instruction d'accès à une information externe est compilée en une instruction d'accès indirect via le segment de liaison. Le lien n'étant pas résolu, un déroutement se produit lors de la tentative d'accès et le module du superviseur nommé intercepteur d'erreurs donne le contrôle à une procédure appelée éditeur de liens. L'éditeur de liens doit identifier le segment contenant l'information référencée. Il a à sa disposition la table des définitions de liens, placée à la fin de la procédure en cours d'exécution, et le lien non résolu, dont l'emplacment à été mémorisé par l'intercepteur d'erreurs (figure 15).

La table des définitions de liens est créée par le compilateur. Le lien contient un indicateur de non résolution (NR sur la figure 15) et contient aussi un pointeur vers une définition de lien, c'est-à-dire une mémorisation de la référence symbolique (chaîne de caractères) que n'a pas pu traduire le compilateur.

L'éditeur de liens a donc la possibilité de récupérer cette référence symbolique (dans l'exemple TOTO, ALPHA).

Il appelle une procédure du système de fichiers, lui passe le nom symbolique du segment (TOTO). Cette procédure doit retourner un nom local pour le segment. Si le segment est déjà initialisé, elle trouve le nom local dans la table des segments connus du processus, sinon elle initialise le segment (paragraphe 2.4.1). Dans les deux cas un nom local est retourné à l'éditeur de liens.

Par ce nom local il atteint le segment cible (remarquons que si le segment vient juste d'être initialisé, son descripteur est vide, il se produit un nouveau déroutement et un nouvel appel à une procédure du système de fichiers qui va connecter le segment, c'est-à-dire remplir le descripteur à partir du contenu de la table des segments connus du processus).
<figure><img src="image_21.png" /><figcaption>Figure 15 : Résolution d'un lien</figcaption></figure>
<figure><img src="image_22.png" /></figure>

Registre pointeur
de pile

(A)

Registres pointeurs

(1)

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

Registre pointeur
de liaison

8

Registres d'index

Registres de travail

(A)

(2)

Segment de liaison

(S)
16

Pointeur vers la
section de l'appelante

(3)

(S)
18

Pointeur vers la
section de l'appelée

(4)

(A)
20

Adresse de retour

(5)

22

Pointeur vers les paramètres
effectifs de la procédure
courante

(S)
26

(6)

28

Figure 16 : Section de pile
associée à une procédure.

(A) : rempli par la séquence d'appel

(S) : rempli par la séquence de
sauvegarde

-> adresse segmentée

32

Informations locales

Liste d'arguments
Dans ce segment se trouve la table des symboles externes (cf. figure 15). Par consultation de cette table l'éditeur de liens obtient le déplacement associé à la référence symbolique (ALPHA dans l'exemple). Il connait donc le nom local du segment externe, et le déplacement dans ce segment. Il place cette adresse segmentée dans le lien dont il a gardé l'adresse, efface la marque de non résolution et rend le contrôle à l'intercepteur d'erreur. Ce module restaure les conditions machine et l'instruction d'accès indirect est re-exécutée.

L'avantage d'une édition de liens dynamique est double :

D'une part ne sont établis que les liens vers les segments auxquels on accède effectivement (ce qui permet, en particulier, à une procédure de référencer des segments qui n'existent pas).

D'autre part, la liaison ayant lieu à l'exécution, il est possible de substituer dynamiquement le segment référencé (ex : versions successives d'un traducteur).

## 2.8 Communications entre procédures

La communication entre procédures s'effectue de manière standard par des séquences d'instructions générées par le compilateur.

Ce sont les séquences d'appel, de sauvegarde et de retour.

Les instructions de ces séquences utilisent la pile du processus, décrite au paragraphe 2.6.2 (figure 11). La sécurité d'exécution dépend de la fiabilité du compilateur.

### 2.8.1 Séquence d'appel

L'appel d'une procédure s'effectue par la désignation d'un point d'entrée de la procédure d'une part, et d'une liste d'arguments d'autre part.

Au niveau du code est générée une séquence d'instructions qui a pour effet de :

a) ranger dans l'en tête de section de pile de la procédure appelante (figure 16) :

- les registres pointeurs (zone (1))

- les registres d'index et les registres de travail (2)

- l'adresse de retour dans la procédure appelante (5) (c'est-à-dire le registre pointeur de procédure et le compteur d'instructions).

b) charger le registre pointeur d'arguments avec un pointeur vers la liste des paramètres (qui se trouve à la suite de la zone des informations locales de l'appelante).

c) effectuer le transfert à la procédure appelée.
Le transfert à la procédure appelée présente une difficulté liée au hardware :
le registre pointeur de liaison n'est pas chargé implicitement lors du trans-
fert. En conséquence il l'est par des instructions de la séquence de sauvegarde.
A cette fin le transfert se fait de la façon suivante (figure 17) :

L'instruction de transfert est compilée comme toute référence exter-
ne en une instruction indirecte de type 1 à travers le segment de liaison de
l'appelante (P).

Si la procédure appelée (P') l'est pour la première fois, l'éditeur de liens est mis en oeuvre.

Il trouve dans la table des définitions de liens la référence symbolique qui
lui permet d'identifier P'. Dans la table des symboles externes de P' il
trouve le déplacement équivalent à cette référence symbolique, mais avec un
code spécial indiquant que ce déplacement est à prendre dans le segment de
liaison de P' et non dans P' elle-même.

Il établit le lien du segment de liaison de P avec l'adresse de l'entrée dans
le segment de liaison de P' (éventuellement c'est l'occasion de créer ce der-
nier segment de liaison).

Le lien créé, le contrôle est donné au segment de liaison de P'. On y trouve
une instruction de chargement du registre pointeur de liaison avec le contenu
du registre base de procédure (qui contient à cet instant le nom local du
segment de liaison de P'). Puis une instruction de transfert au point d'entrée
de P' indirectement à travers le double mot consécutif à cette instruction.
Ce double mot sert de lien. Il est initialisé par l'éditeur de lien qui y
trouve la référence symbolique du point d'entrée, qu'il retrouve dans la table
des définitions de liens avec un indicateur d'auto-référence. Il sait donc
que cet "externe" est d'un genre particulier, il prend le déplacement corres-
pondant dans cette définition du lien et initialise le lien du segment de
liaison de P'.

Désormais tout transfert de P à ce point d'entrée dans P' se fait par
l'intermédiaire des deux segments de liaison (figure 17) ce qui provoque à
chaque fois le chargement du registre pointeur de liaison à la valeur adéquate.

2.8.2 Séquence de sauvegarde

Cette suite d'instructions a pour objet de générer une nouvelle
section de pile associée à la procédure appelée et de placer les chaînages
vers la section de pile de la procédure "qui appelle" et vers celle de la
procédure "qu'on appelera".
<figure><img src="image_24.png" /><figcaption>Figure 17 : Transfert au point d'entrée de la procédure appelée.</figcaption></figure>
Une partie de ces instructions de sauvegarde, on l'a vu, se trouve
dans le segment de liaison de l'appelée. Elle assure le chargement du registre
pointeur de liaison. L'autre partie est au point d'entrée de l'appelée. Elle a
pour effet de :

a) créer la nouvelle section de pile, c'est-à-dire mettre en place les
pointeurs de chaînage (3) et (4) (la taille de la section est connue
en principe à la compilation).

b) ranger en zone (6) le pointeur d'arguments.

c) actualiser le registre pointeur de pile qui doit désigner la
section nouvelle.

Elle utilise à cette occasion le registre pointeur de base qui à la fin de la séquence repère le sommet de pile. (il faut toujours savoir où ranger le contexte machine en cas de panne).

Ce registre est utilisé d'autre part pour passer le nom d'une procédure en
paramètre.

2.8.3 Séquence de retour

Lors du retour de procédure elle provoque :

a) le chargement des registres pointeurs avec les valeurs sauvegardées
à l'occasion de l'appel dans la section de l'appelante.

b) la restauration des registres d'index, des registres de travail, du registre pointeur de procédure et du compteur ordinal.

A la fin de l'exécution de cette séquence la section de pile de la procédure appelée a disparu.

3. Influence des contrôles sur les mécanismes d'accès

3.1 Les contrôles d'accès

L'espace virtuel du système est un ensemble de segments. L'entité
logique repérable au niveau du système est le segment. C'est donc le segment qui
est introduit dans l'espace d'adressage d'un processus. Le partage se fait donc
nécessairement au même niveau et sa sélectivité est traduite par un contrôle
de l'accès au segment relatif à l'identité du processus, qui tente cet accès [6].
Les mécanismes de contrôle d'accès reposent sur le principe des anneaux de
protection :

Un niveau de pouvoir est associé à l'exécution de chaque processus. Il existe un certain nombre de niveaux ordonnés par pouvoir décroissant, le pouvoir d'un niveau étant un sous-ensemble du pouvoir du niveau supérieur. Cette relation d'ordre justifie le terme d'anneaux de protection.

On peut considérer ce principe comme une extension des modes d'exécution
(Maître/Esclave).
A tout segment est associé une protection : chaque opération n'est possible sur le segment que si le processus s'exécute dans certains anneaux. La protection est définie par la liste de contrôle d'accès associés au segment : c'est la liste des noms d'utilisateurs autorisés à accéder à ce segment et des droits qu'ils possèdent sur lui. Les droits sont représentés par les noms d'opérations possibles (lire, écrire, exécuter) et les numéros d'anneaux dans lesquels elles sont autorisées.

Cette liste de contrôle d'accès est rangée dans l'entrée du catalogue général du système associée au segment.

Lors de la formation d'un descripteur de segment pour un processus, le système va lire dans la liste de contrôle d'accès les droits que possède le processus sur ce segment et les inscrit dans le descripteur. Le contrôle est désormais effectué à chaque accès au segment par son descripteur.

Les droits sur un même segment pouvant être différents pour chaque utilisateur, on conçoit que les descripteurs qu'ils en possèdent soient différents. La sélectivité du partage des informations est ainsi assurée.

## 3.2 Pouvoir d'un processus

Le pouvoir d'un processus est maintenant précisé : le processus s'exécutant dans un anneau donné a le droit de faire un certain nombre d'opérations sur un certain nombre de segments. Le pouvoir est donc défini à partir de l'ensemble des listes de contrôle d'accès, de l'identité du processus et du niveau auquel il s'exécute.

En particulier un changement d'anneau d'exécution implique un changement de pouvoir.

Un processus est créé pour s'exécuter dans un anneau donné. Il peut éventuellement changer d'anneau d'exécution à l'appel d'une procédure qui ne peut pas s'exécuter dans l'anneau courant du processus. On distingue les appels avec augmentation de pouvoir ou avec diminution de pouvoir. Evidemment des contrôles sont opérés sur ces changements de pouvoir.

## 3.3 Implantation

L'étude détaillée du fonctionnement des mécanismes de protection n'est pas notre objectif. L'important est de noter les contraintes apportées par les contrôles dans les mécanismes d'accès aux informations.
Cette influence joue sur les supports même de ces mécanismes : descripteurs et descriptifs, registres, entrées du catalogue général, piles et segments de liaison.

### 3.3.1 Entrées du catalogue

L'entrée du catalogue associée à un segment contient une liste de contrôle d'accès.

Cette liste donne pour chaque utilisateur les opérations permises sur ce segment et pour chacune les numéros d'anneaux pour lesquels elle est autorisée. Comme en pratique une opération n'est autorisée que dans plusieurs anneaux consécutifs, on parle de parenthèse d'accès (figure 18).

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

Parenthèse d'écriture : 0 - 1

Parenthèse d'exécution : 4

Parenthèse de lecture : 0 - 1 - 2 - 3

Parenthèse d'appel : 5 - 6

<caption>Figure 18</caption>

La parenthèse d'appel est une extension de la parenthèse d'exécution. Elle indique les anneaux à partir desquels la procédure peut être appelée, sous contrôle (en passant par certains points d'entrée nommés guichets).

Les parenthèses d'accès à un segment sont définies conventionnellement par trois nombres r1, r2, r3 (figure 19).
<figure><img src="image_26.png" /><figcaption>Figure 19</figcaption></figure>

### 3.3.2 Descripteurs et descriptifs

Multics a été implanté en une première version sur GE 645. Les contraintes du hardware ont amené à dupliquer le descriptif d'un processus en autant d'exemplaires que d'anneaux. Ainsi la connection d'un segment au processus consistait à créer un descripteur dans le descriptif associé à l'anneau courant. Un accès tenté dans un autre anneau par le même nom local provoquait une nouvelle connection, c'est-à-dire la création d'un autre descripteur avec des droits différents. Les parenthèses d'accès (c'est-à-dire le triplet $(r_1, r_2, r_3)$ étaient dans la table des segments connus. Les descripteurs contenaient les droits (booléens) aux opérations.

L'implantation sur H6180 [7] évite cette duplication des descriptifs. Les descripteurs contiennent eux mêmes les parenthèses d'accès $(r_1, r_2, r_3)$ et éventuellement la liste des guichets (sous forme d'index, les points d'entrée étant placés par convention en tête des segments procédure). Tous les registres pointeurs ont un champ "numéro d'anneau", ainsi que les instructions et les liens d'indirection.

N'avoir qu'un descriptif par processus économise beaucoup de place en mémoire mais par contre fait perdre l'avantage du découpage en domaines de l'espace d'adressage du processus.

### 3.3.3 Piles et segments de liaison

Les procédures pouvant s'exécuter dans des anneaux différents, il existe, pour raison de protection évidente, une pile par anneau pour chaque processus. Lors d'un appel de procédure avec changement de pouvoir la commutation des piles est faite par une procédure du superviseur ("Gatekeeper").
Il tient en anneau 0 une table des piles du processus et assure pour permettre
le retour à la procédure appelante, la recopie de la zone du contexte d'appel
de la pile de l'appelante dans la pile de l'appelée.

Sur le H6180 au contraire, la transition entre la procédure appelante et la procédure appelée est faite sans appel au superviseur, uniquement par les séquences d'appel, de sauvegarde et de retour inhérentes à ces deux procédures.

Pour raison de protection également toute procédure est dotée d'un
segment de liaison dans chaque anneau où elle s'exécute. Ces copies de la
maquette contenue dans le segment procédure sont créées dynamiquement par
l'éditeur de liens.

### 3.3.4 Conclusion

Les contrôles d'accès aux informations sont effectués systématiquement au moyen des structures que l'on vient de décrire.

Le principe de la connection par descripteur d'un segment à un processus et le principe des anneaux de protection permettent de réaliser les accès et les liaisons de la même façon pour les segments du système et les segments des utilisateurs grâce à l'unicité des mécanismes d'adressage et de protection.

## 4. Communications entre processus

L'activité du système se traduit par le déroulement de processus co-existants. L'articulation des fonctionnements de tels processus nécessite l'existence de moyens de synchronisation et de communication [8].

### 4.1 Les processus

On peut distinguer trois sortes de processus co-existants :

- les processus apparemment indépendants.

Ils partagent néanmoins des ressources communes (processeurs, procédures du superviseur, tables etc...), ce qui nécessite des moyens de communication entre eux.

- les processus "utilisateurs" et les processus "système".

Un certain nombre de processus permanents du système sont au service de l'utilisateur. Celui-ci les appelle par le biais d'un appel de sous-programme de bibliothèque qui lui-même lance le processus système. Le processus utilisateur et le processus système s'exécutent alors en coopération.
- enfin certains processus sont explicitement coopérants (ex : calcul parallèle). Ils doivent bien sûr être synchronisés.

Dans tous les cas, la coopération entre processus implique une communication par l'utilisation de bases de données partagées spécialisées, ou par le partage de certains modules du superviseur et de tables du système.

## 4.2 Synchronisation

La gestion du parallélisme entre processus ne fait pas l'objet de cette étude. Schématiquement un sous-système du superviseur, le "Traffic Controller" assure de façon unitaire cette gestion pour tous les processus. Chaque processus se trouve dans l'un des états : en exécution, prêt, ou en attente.

Le "Traffic Controller" gère ces trois classes de processus, en entretenant la liste des processus actifs.

Un processus en attente d'un événement est forcé en anneau zéro par une interruption associée à l'arrivée de cet événement. Là il prend note de l'événement et appelle le Traffic Controller qui avertit les autres processus qui attendaient ce même événement. Chacun de ces processus passe alors éventuellement dans l'état prêt.

De plus, les processus ont à leur disposition les fonctions "bloquer" et "éveiller" exécutables dans tout anneau. Un processus peut donc se bloquer (en attente soit d'un événement au niveau du système, soit d'un événement au niveau d'un autre processus) et il peut aussi essayer de débloquer un autre processus.

## 4.3 Communication

Multics fournit un mécanisme général de communication de messages entre processus (l'"Interprocess communication facility") qui permet à un processus d'envoyer un message à un autre processus, quel que soit l'état de ce dernier. Les processus communiquent entre eux par des messages déposés dans des boîtes aux lettres. Un processus A voulant communiquer un message à un processus B dépose le message dans une boîte aux lettres de B et éveille le processus B.

Le message comprend, outre le texte lui-même, l'identificateur du processus expéditeur et celui du processus destinataire.

L'identificateur d'un processus est un nom d'horloge (chaîne de 36 bits) délivré par le système au moment de la création du processus.

Pour que soient respectées les contraintes de protection, tout processus peut avoir une (ou plusieurs) boîtes(s) aux lettres dans chaque anneau.
Une boîte aux lettres est repérée par un **identificateur** (chaîne de 72 bits) à 3 champs : un numéro d'anneau, une clef (date de création), un déplacement dans le segment (associé à cet anneau) où sont déposés les messages.

L'envoi d'un message s'effectue par un appel à une procédure du système (procédure "éveiller"). Sont passés en paramètres : l'identificateur du processus récepteur, l'identificateur de la boîte, le message et un code.

La procédure a pour action de vérifier l'identificateur du processus destinataire et de vérifier si ce processus est actif.

Ces vérifications faites, elle copie le message accompagné de son contexte dans une table du système (en anneau zéro). Enfin, elle réveille le processus destinataire qui devra extraire le message de cette table ("Interprocess Communication Table").

On peut remarquer que le message déposé dans la table de communication est accompagné de l'identificateur de l'expéditeur et du numéro d'anneau de départ.

Cette table est organisée en un ensemble de files de messages, une par processus.

Chaque processus de la table des processus actifs a un pointeur vers la file de messages qui lui est associée.

C'est le processus destinataire qui prend l'initiative de retirer de cette file les messages qui lui sont adressés.

Par exemple, l'attente d'un message se manifeste par l'appel d'une procédure (procédure "bloquer") qui va scruter les boîtes aux lettres du processus.

Comme cette procédure s'exécute dans l'anneau du processus destinataire, elle ne peut accéder à la table des communications. Elle fait donc elle-même appel à une procédure en anneau zéro qui transfère les messages valides de la table dans les boîtes aux lettres du destinataire. Seuls les messages placés dans les boîtes aux lettres situées dans les anneaux accessibles au destinataire sont effectivement consommés.

Si aucun message n'a été déposé dans une de ces boîtes aux lettres, le processus reste bloqué.

## 4.4 Etablissement de la communication

Le préalable pour que deux processus puissent communiquer est qu'ils connaissent chacun l'identificateur de l'autre ainsi que les identificateurs de ses boîtes aux lettres.
Un processus peut connaître son identificateur par une commande au système.
Les identificateurs de ses boîtes aux lettres lui ont été donnés par le
système lorsqu'il a demandé leur création.

L'établissement de la communication d'un processus A vers un
processus B suppose que les utilisateurs représentés par ces processus se soient
préalablement mis d'accord sur le choix d'un segment S qui leur soit commun.
Le processus destinataire B, dès qu'il est créé, dépose dans S son identificateur
et ceux de ses boîtes aux lettres. L'expéditeur, processus A, lit dans S ces
identificateurs et peut alors envoyer un message à B.

Par convention, le premier message envoyé à B contient l'identificateur de
l'expéditeur A et ceux de ses boîtes aux lettres, pour permettre les réponses
de B vers A.

On peut remarquer que le segment S partagé par les deux processus n'est
utilisé qu'à l'initialisation de la communication, pour transmettre à
l'expéditeur les "coordonnées" du destinataire.

Par la suite, toute communication passe par les boîtes aux lettres de l'un ou
de l'autre processus.

## 4.5 Remarques

On peut faire plusieurs remarques sur cette méthode de communication
entre processus. En premier lieu, tout processus crée pour lui-même les boîtes
aux lettres qu'il désire et en communique les identificateurs aux autres
processus de son choix. Il peut donc vouer lui-même chacune de ses boîtes aux
lettres à recevoir les messages de tel ou tel processus.

Ensuite, il n'a jamais un accès direct à ses propres boîtes aux lettres. C'est
lorsqu'il appelle la procédure de blocage qu'il transmet en paramètre la
désignation d'une ou plusieurs boîtes aux lettres et d'un emplacement mémoire.
La procédure videra les messages éventuels contenus par les boîtes dans cet
emplacement qui seul est accessible au processus.

Enfin l'obligation pour les messages d'être entreposés dans une table centrale
en anneau zéro apporte deux avantages :

- la synchronisation entre dépôt et retrait de messages est invisible par
les processus utilisateurs.

- un contrôle de validation des niveaux d'émission sélectionne parmi tous
les messages ceux qui peuvent être effectivement livrés au processus destinataire.
Une dernière remarque sur la désignation des boîtes aux lettres : comme les processus, elles sont repérées par des identificateurs délivrés par le système (noms d'horloge).

Elles ne sont captées ni dans l'espace d'adressage du processus auquel elles appartiennent ni dans celui des processus émetteurs de messages.

Seuls sont connus leurs identificateurs qui sont passés en paramètres à une procédure du système qui les interprète.

# 5. Le système de fichiers

## 5.1 Introduction

L'espace adressable du système est constitué d'un ensemble de segments. La conservation de ces segments en mémoire est à la charge du système de fichiers [9] (pour lequel segment et fichier sont des notions qui coïncident).

Chaque utilisateur se voit associer un processus et dispose d'un espace d'adressage virtuel propre. Le couplage entre cet espace et l'espace de conservation est transparent à l'utilisateur car il est à la charge du superviseur : lorsqu'une référence est émise à un segment hors de l'espace d'adressage du processus courant, un déroutement provoque l'appel de l'éditeur de liens, qui lui-même active le système de fichiers.

Ce dernier a pour charge de localiser le segment, de contrôler la validité de l'accès demandé, et d'inclure ce segment dans l'espace d'adressage du processus, ce qui autorise alors l'accès.

Outre ces appels implicites, le système de fichiers peut aussi être appelé explicitement par l'utilisateur qui désire créer un segment ou bien lire ou modifier des informations du catalogue.

## 5.2 Organisation du catalogue

### - les répertoires

Chaque segment conservé par le système de fichiers est décrit par une entrée dans le catalogue général du système. Ces entrées sont groupées en répertoires qui sont eux-mêmes des segments d'un type particulier et donc sont chacun décrits dans une entrée d'un autre répertoire.

Le catalogue est donc organisé selon une structure d'arbre (fig. 20) dont les "noeuds" sont des répertoires et les "feuilles" des segments non répertoires (code ou données). Une entrée de répertoire décrit un segment, c'est à dire détient une adresse physique, des noms désignant ce segment et une liste de contrôle d'accès.

Tout segment figurant dans l'espace de conservation est décrit par une telle entrée de répertoire.
Cette structure permet de regrouper de façon logique dans des réper-
toires les descriptions de certains segments.

Par exemple on trouve dans le catalogue un répertoire associé à chaque utili-
sateur contenant les descriptions de ses segments propres. Ces répertoires
utilisateurs sont décrits dans des répertoires par projets eux-mêmes décrits
dans un répertoire des répertoires utilisateurs. Existent aussi dans le
catalogue les répertoires des programmes bibliothèque, et un répertoire pour
chaque processus.

Les répertoires de processus ont la particularité de disparaître à la mort du
processus, ainsi que tous les segments qu'ils décrivaient.

<figure><img src="image_27.png" /><figcaption>Figure 20</figcaption></figure>
Ce n'est pas le cas du répertoire utilisateur qui permet à ce dernier de retrouver ses segments d'une session à l'autre.

Nous verrons à la fin de ce chapitre que l'utilisateur a le droit de créer des segments ou des répertoires (et par là de se constituer un sous-arbre).

Tous les objets du système sont donc répertoriés dans ce catalogue arborescent ce qui facilite considérablement les recherches du système de fichiers.

- Désignation dans le catalogue.

Chaque segment (répertoire ou non) du catalogue est décrit dans une entrée d'un répertoire de niveau supérieur, cette entrée contenant un nom symbo-lique désignant le segment. Ce nom (**nom d'entrée**) doit être unique dans le répertoire mais peut être utilisé dans d'autres répertoires. Le répertoire supérieur de l'arbre étant nommé RACINE, on peut désigner de façon non ambigüe tout segment figurant dans le catalogue par la concatenation des noms d'entrée de répertoires à parcourir depuis RACINE pour atteindre se description (fig. 21).

Cette concatenation de noms d'entrée est ce qu'on appelle le **nom d'arbre du segment**. Ce nom d'arbre peut être utilisé comme pointeur par l'utilisateur pour désigner un segment dans le catalogue.

Pour simplifier l'écriture, une convention autorise à décrire un segment par un nom d'arbre relatif.

Le principe est le même mais la formation du nom commence non pas à partir de RACINE mais à partir d'un répertoire situé plus bas dans l'arborescence : le répertoire de travail. C'est un répertoire du catalogue choisi par le système ou par l'utilisateur pour faciliter l'écriture des noms d'arbres (c'est souvent le répertoire de l'utilisateur) (fig. 21).
<figure><img src="image_28.png" /><figcaption>Figure 21</figcaption></figure>

Le même segment (17) a pour nom d'arbre
RACINE>B>H>C>F (par convention on peut omettre d'écrire RACINE)
et pour nom relatif C>F

Remarque : on peut référencer par des noms relatifs des segments n'appartenant
pas au sous-arbre du répertoire de travail :
le nom relatif <<A>F référence le segment (7)
(le symbole "<" ayant comme signification : "père de")
- Les liens

Une entrée de répertoire décrit un segment.

Elle contient l'adresse physique en mémoire secondaire des enregistrements constituant le segment et recèle d'autres renseignements, en particulier la liste des noms symboliques de référence utilisables pour désigner ce segment (liste des synónymes). Le nom d'entrée associé au segment fait partie des noms de référence.

Dans l'entrée de répertoire figurent aussi les attributs de protection du segment.

Il existe une autre sorte d'entrée dans les répertoires : les *liens*.
Un lien est une entrée de répertoire contenant seulement un nom d'arbre, c'est à dire un pointeur vers une entrée d'un autre répertoire (de type entrée ou lien). Les liens fournissent la possibilité d'associer à un même segment deux entrées dans des répertoires différents, ce qui n'est pas possible par l'utilisation des entrées de répertoire.

En établissant des liens l'utilisateur a le moyen de décrire dans le catalogue des structures autres qu'arborescentes.

Mais les liens sont de simples relais.

C'est toujours la liste de contrôle d'accès contenue dans l'entrée associée au segment qui détermine les droits des utilisateurs sur ce segment (contraintement à ce qui existe dans GEMAU [10], par exemple, où l'on peut obtenir par un lien un accès à un objet avec des droits différents de ceux dont on dispose lors d'un accès direct par l'entrée correspondante de l'annuaire). L'exemple de la figure 22 illustre que l'on peut avoir soit le même nom, soit des noms différents pour le lien et l'entrée qu'il réfère.

## 5.3 Les différents noms désignant un segment

- identificateur unique

Lors de sa création un segment reçoit l'attribution d'un identificateur unique (qui tient compte entre autres de la date de sa création et de la machine sur laquelle il est créé). Cet identificateur est unique et valide dans tout le système. Il sert en dernier recours au système à lever l'ambiguïté sur l'identité du segment.

L'identificateur unique est enregistré dans l'entrée du répertoire décrivant le segment. Quand le segment est connu d'un processus, l'identificateur unique figure dans la table des segments connus du processus.
<figure><img src="image_29.png" /><figcaption>Figure 22</figcaption></figure>

Le segment 7 est connu sous le nom d'entrée K dans les répertoires 2 et 5.

Le segment 13 est connu sous le nom d'entrée M dans le répertoire 8 et sous le nom d'entrée P dans le répertoire 9.

Les liens contiennent des noms d'arbre complets (>A>K dans le lien du répertoire 5, >B>G>M dans le lien du répertoire 9).

Mais les listes de contrôle d'accès de chacun de ces 2 segments sont dans les entrées qui les décrivent (respectivement dans 2 et dans 8).
- nom local à un processus*

C'est le numéro d'entrée dans le descriptif du processus. Ce nom est alloué lors de la reconnaissance du segment par le processus (qui lui attribue alors la première entrée libre dans le descriptif) et consigné dans l'entrée correspondante de la table des segments connus.

Le nom local n'est, bien sur, valide que pour le processus. Un segment partagé par deux processus a des noms locaux différents pour chacun d'eux.

- nom d'arbre

Il a été défini précédemment. Rappelons qu'un nom d'arbre désigne un segment dans le catalogue sans ambiguïté, mais que l'existence des liens permet à un segment d'être éventuellement désigné par des noms d'arbres distincts. Le nom d'arbre, valide pour tout le système, est le moyen le plus sûr, pour le système ou l'utilisateur, de désigner un segment. Le nom d'arbre complet d'un répertoire est consigné dans l'entrée de la table des segments qui est associé (ce n'est pas le cas pour un segment non répertoire).

- noms de référence

Ce sont les noms symboliques employés par l'utilisateur pour désigner un segment. Un nom symbolique a comme portée dans ce cas la région de l'espace d'adressage du processus associée au numéro de l'anneau dans lequel se fait la référence.

Conséquence : dans un processus un même nom symbolique peut désigner plusieurs segments différents selon l'anneau dans lequel se fait la référence.

Par contre, plusieurs noms de référence peuvent être utilisés pour désigner un même segment dans le même anneau.

La liste de ces synonymes figure dans l'entrée de répertoire associée à ce segment. (Le nom de l'entrée associée au segment dans le catalogue lors de sa création est lui-même un nom de référence). Lorsqu'un processus utilise des noms symboliques pour désigner un segment, ces noms sont enregistrés dynamiquement dans la table des segments connus, après identification du segment. Ils sont préfixés par le numéro d'anneau dans lequel s'est effectuée la référence. Ainsi se trouve résolu la question de l'ambiguïté d'un même nom symbolique désignant deux segments différents dans deux anneaux distincts.

<footnote>*On pourrait ajouter aussi le *nom procédural* : numéro de registre pointeur, d'éplacement dans le segment.</footnote>
## 5.4 Les modules du système de fichiers

Le système de fichiers est un ensemble de modules qui a pour vocation de :

- gérer les répertoires

- fournir les segments aux processus qui les demandent

- créer de nouveaux segments

- détruire des segments existants.

Deux modules essentiels du système de gestion de fichiers sont le module de contrôle de segments et le module de contrôle de répertoire.

Le module de contrôle de segments doit fournir le nom local d'un segment et certains droits d'accès lorsque l'utilisateur fait une référence symbolique. Il interprète cette référence et va chercher le segment dans l'espace d'adressage du processus ou, à défaut, dans l'espace de conservation. Il peut même éventuellement créer le segment désigné si nécessaire. C'est lui qui lève les ambiguïtés induites par les noms en utilisant les informations qu'il lit dans le processus (table des segments connus) ou dans le catalogue (répertoires).

Le module de contrôle de répertoire est le seul autorisé à lire et à modifier le contenu des répertoires.

## 5.5 Contrôle de l'accès au catalogue

Dans chaque entrée de répertoire décrivant un segment se trouve une liste de contrôle d'accès qui lui est associée, c'est à dire une suite de noms d'utilisateurs et des droits respectifs qu'ils possèdent sur ce segment (lecture, écriture, exécution).

(Le nom repérant l'utilisateur est formé de son nom propre et du nom du projet pour lequel il travaille). Les listes de contrôle d'accès sont construites, modifiées ou consultées au moyen de commandes. Mais ces opérations impliquent un contrôle de leur utilisation.

Aussi tout répertoire, comme tout autre segment, est protégé par une liste de contrôle d'accès située dans l'entrée de répertoire (immédiatement supérieur) qui le décrit. Les droits que l'on peut exercer sur un répertoire sont, par analogie avec les droits sur un segment (lire, écrire, exécuter) les droits de consulter, modifier le répertoire ou de lui ajouter une entrée.

Avec ce mécanisme on accède sélectivement aux régions du catalogue : l'utilisateur se voit attribuer un répertoire par son chef de projet qui, en créant la liste de contrôle d'accès pour ce répertoire, lui donne les droits nécessaires pour créer ses propres segments.
Le chef de projet lui-même tient ce droit de créer un répertoire
de par une liste de contrôle d'accès située dans un répertoire un niveau au
dessus, etc...

Les droits sur l'arborescence des répertoires sont distribués hiérarchiquement
à partir du répertoire RACINE dont la liste de contrôle d'accès n'autorise que
le responsable du système à modifier son contenu.

Pour éviter aux utilisateurs de décrire systématiquement les listes
de contrôle d'accès lorsqu'ils remplissent leurs répertoires, une liste de
contrôle d'accès est mise en place par défaut par le système pour toute
nouvelle entrée de répertoire (droits pour quiconque de lire et d'exécuter,
en ce qui concerne les segments, de consulter en ce qui concerne les
répertoires).

## 5.6 Rôle du système de fichiers dans la traduction d'une référence symbolique

Rappelons qu'un processus ne peut travailler que dans son espace
d'adressage, c'est à dire sur l'ensemble des segments dont il possède un
descripteur.

Ces descripteurs sont groupés en une table, le descriptif, et le nom local
d'un segment est le numéro de son descripteur dans cette table. (dans la
version implantée sur GE 645, le descriptif est "éclaté" en un descriptif par
anneau).

Parallèlement au descriptif existe au niveau du processus une table des
segments connus. Y sont consignées pour chaque segment de l'espace d'adressage
du processus des informations telles que : les noms de référence (symboliques)
sous lesquels le processus les connait - préfixés par le numéro d'anneau dans
lequel s'est faite la première référence par ce nom -, l'identificateur
unique du segment, un nom d'arbre (s'il s'agit d'un répertoire), le nom local,
les attributs de protection et un pointeur vers l'entrée de répertoire
décrivant ce segment (avec son nom local).

Lorsqu'une entrée est ouverte pour un segment dans la table des segments connus
du processus et qu'y sont enregistrées ces informations le concernant (en
particulier le nom local par lequel le processus le connaîtra) on dit que le
segment est connu du processus, ou initialisé.

Quand un processus désigne un segment par un nom symbolique, une
erreur est signalée, le module intercepteur d'erreurs identifie ce type
d'erreur et en conséquence appelle l'éditeur de liens. Ce dernier extrait de
la table des externes de la procédure en cours d'exécution le nom symbolique du
segment visé et le passe au module de contrôle des segments.

Le module de contrôle des segments doit, en retour, fournir un nom local pour ce segment.

Plusieurs cas peuvent se présenter :

a) Si le segment est connu du processus sous ce nom symbolique :
Le module de contrôle de segments, qui commence par rechercher de manière associative ce nom dans la table des segments connus, le trouve, vérifie que le numéro d'anneau qui le préfixe est bien celui de la référence actuelle, lit dans l'entrée de la table ainsi déterminée le nom local et le retourne à l'éditeur de liens.

b) Sinon, la recherche dans la table échoue, le module de contrôle de segments doit chercher le segment demandé dans le catalogue général.

Par l'intermédiaire du module de contrôle de répertoires il reconstitue le nom d'arbre (en observant des règles de recherche heuristiques dans l'arborescence des répertoires), et va lire dans l'entrée simple ainsi désignée l'identificateur unique (§5.3) du segment.

Au moyen de cet identificateur unique une deuxième recherche associative est entreprise dans la table des segments connus.

ba) Si la recherche est positive le segment est déjà connu mais sous un autre nom symbolique (ou sous plusieurs autres).

Le module de contrôle de segment ajoute le nouveau synonyme préfixé par le numéro d'anneau dans la liste des noms de références qui correspond à l'identificateur unique trouvé et retourne à l'éditeur de liens le nom local.

bb) Si la recherche est négative, le module de contrôle de segments ouvre une nouvelle entrée dans la table des segments connus. Il y consigne l'identificateur unique, le nom de référence préfixé par le numéro d'anneau, le nom d'arbre s'il s'agit d'un répertoire, le pointeur vers l'entrée du répertoire père, les attributs de protection, et le premier nom local disponible. L'entrée du descriptif correspondant à ce nom local est réservée et initialisée à des valeurs nulles.

On peut faire quelques remarques sur le fonctionnement des modules du système de fichiers.

1) Tout d'abord, il faut noter que lorsque le module de contrôle des répertoires parcourt le catalogue il le fait pour le compte du segment procédure en cours d'exécution. En conséquence, il ne consulte un répertoire que si le nom de l'utilisateur est compris dans la liste de contrôle d'accès associée à ce répertoire et que si cet utilisateur a le droit de consultation.
Si ces deux conditions ne sont pas respectées, le répertoire est sauté dans
la recherche.

2) La reconstitution d'un nom d'arbre à partir d'un nom symbolique revient à chercher ce nom symbolique dans certains répertoires pris successivement. Le module de contrôle de répertoires fouille un ensemble prédéterminé de répertoires dans un ordre fixé à l'avance : répertoire père du segment en cours d'exécution, puis répertoire de travail, puis bibliothèques du système, enfin le répertoire du processus. Le premier segment trouvé est considéré comme le bon. Par contre si le nom symbolique cherché n'est pas trouvé dans cet ensemble de répertoires, un signal d'erreur est retourné par le module de contrôle de segments à l'éditeur de liens et l'intercepteur d'erreurs envoie un message à la console de l'utilisateur.

La suite des répertoires à fouiller successivement est définie arbitrairement.
Cette convention est importante puisque d'elle dépend l'interprétation des
noms symboliques.

Le système est conçu pour qu'éventuellement l'utilisateur puisse imposer ses
propres règles de recherches (par exemple intercaler des répertoires dans la
succession des répertoires fouillés).

3) Lorsque la recherche est fructueuse, le segment visé est initialisé par le
processus et en particulier les droits d'accès à ce segment, quels qu'ils
soient, sont enregistrés dans la table des segments connus.
Ce n'est qu'à l'occasion de l'accès effectif, c'est à dire au moment où le
descripteur sera créé, que les droits seront contrôlés et l'accès autorisé
ou refusé.

4) Pour qu'un segment soit initialisé par un processus tous les répertoires
qui sont fouillés pendant la recherche doivent eux aussi être initialisés par
le processus.

Des entrées leur sont donc allouées dans la table des segments connus et comme
elles sont chaînées entre elles on retrouve dans cette table un sous-arbre du
catalogue général.

5) Une aide supplémentaire permet de lever les ambiguïtés sur les noms de
référence : les noms symboliques qui sont enregistrés dans la table des
segments connus sont préfixés non seulement par un numéro d'anneau, mais aussi
par l'identificateur unique du répertoire père du segment ainsi désigné (ce
qui permet de le retrouver facilement dans cette table).
## 5.7 Formation des descripteurs par le module de contrôle des segments

Par définition, un segment est dit initialisé pour un processus lorsqu'une entrée dans la table des segments connus lui a été attribuée (§2.4.1). Il est dit actif (notion relative au système) lorsque sa table de pages est en mémoire. Il est dit connecté à un processus lorsqu'un descripteur existe pointant vers la table des pages (§2.4.2).

L'accès effectif au contenu d'un segment suppose que le segment soit initialisé, connecté et actif.

L'initialisation et la connection sont à la charge du module de contrôle de segments, l'activation est réalisée par le module de contrôle de pages.

Nous avons décrit l'initialisation d'un segment. Après cette opération, le segment est connu du processus par un nom local et par une entrée dans la table des segments connus contenant les informations qui le décrivent.

Le descripteur associé à ce nom local (ou les descripteurs pour chaque anneau) est initialisé à une valeur nulle.

Lorsque l'instruction d'accès est réexécutée le contenu du descripteur sélectionné est interprété par l'intercepteur d'erreurs comme une marque d'absence de segment. Il appelle le module de contrôle de segments pour fabriquer le contenu du descripteur.

Celui-ci travaille à partir du numéro d'anneau dans lequel s'effectue la référence, du contenu de l'entrée de la table des segments connus, de la table des segments actifs, et de l'entrée de répertoire associée au segment.

Le résultat est un descripteur contenant entre autres, un champ "droits".

Le module de contrôle de segments retourne le contrôle à la procédure initiale pour tenter l'accès effectif par ce descripteur.

Si la référence se fait sans augmentation ni diminution de pouvoir, le module de contrôle de segments a initialisé le champ "droits" du descripteur de façon adéquate et éventuellement provoqué la création d'une table de pages pour le segment.

Dans ces conditions, l'accès se réalise effectivement. Si par contre, la référence nécessite un changement de pouvoir, le module de contrôle de segments a déposé dans le champ "droits" du descripteur un code reconnu par l'intercepteur d'erreur comme un appel au module portier ("Gatekeeper").

Il se produit donc un nouveau déroutement et le portier ou bien assure le déroulement de l'accès avec les changements de pouvoir nécessaires, ou bien signifie à l'utilisateur le refus d'accès.
Remarquons que dans le premier cas il peut arriver qu'après avoir effectué le changement d'anneau, le portier retourne le contrôle à la procédure initiale parce que le segment cible n'a jamais été désigné dans cet anneau et que le descripteur figurant dans le descriptif associé à cet anneau est initialisé à des valeurs nulles.

Il faut donc tenter à nouveau l'accès pour provoquer dans cet anneau la formation du descripteur par le module de contrôle de segment et ensuite réaliser l'accès.

## 5.8 Appels explicites au système de gestion des fichiers

L'utilisateur dispose de commandes qui font appel directement au système de gestion des fichiers (en réalité au module de contrôle de segments). Grâce à ces commandes il peut créer ou modifier des segments (ou des répertoires), consulter des répertoires, établir des liens, changer de répertoire de travail (c'est à dire changer la convention sur les noms de référence) etc...

Ces actions sont accomplies sous réserve que le contrôle d'accès les autorise.

Illustrons par un exemple les possibilités offertes par ces appels explicites aux modules du système de fichiers (l'exemple est tiré du "Multics Programmers' Manual" [11]).

Nous partons d'une configuration simplifiée du catalogue représentée par la figure 23. ROOT est le répertoire racine, UDD (pour "user-directory-directory") le répertoire des répertoires utilisateurs.

Le système associe à tout utilisateur entamant une session un répertoire de travail.

Supposons qu'il s'agisse de l'utilisateur Jones et du répertoire désigné par le nom d'arbre `ROOT>UDD>JONES` (ou en abrégé par convention `UDD>JONES`).

Le dialogue entre JONES et le système s'instaure (figure 24). (Les instructions tapées par Jones sont marquées par un "*").
<figure><img src="image_30.png" /><figcaption>Figure 23</figcaption></figure>
1* print_wdir
2 >udd>Jones
3 r 1210 .137 .812 27
4
5* list
6
7 Segments = 2, Records = 4.
8
9 r w 1 lp.pl1
10 re 3 x
11
12 r 1212 .216 1.762 33
13
14* create foo
15 r 1213 .320 3.728 77
16
17* list
18
19 Segments = 3, Records = 4.
20
21 r w 0 foo
22 r w 1 lp.pl1
23 re 3 x
24
25 r 1215 .202 1.856 49,
26
27* createdir mypoems
28 r 1216 .151 1.482 0
29
30* change_wdir mypoems
31 r 1218 .089 .306 17
32
33* print_wdir
34 >udd>Jones>mypoems
35 r 1219 .119 .056 14
36
37* list
38 directory empty
39 r 1219 .147 1.406 42
40
41* copy >udd>Smith>poem limerick
42 r 1220 .311 1.732 53
43
44* list
45 Segments = 1, Records = 1.
46
47 r w 1 limerick
48
49 r 1220 .219 2.162 41
50
51* change_wdir >udd
52 r 1221 .067 .646 30
53

<caption>Figure 24 : Dialogue entre l'utilisateur JONES (instructions précédées par *) et le système.</caption>
54* list -a
55
56 segments = 0
57
58 links = 0
59
60 Directories = 2, Records = 2.
61
62 s 1 Smith
63 sma 1 Jones
64
65 r 1222 .077 .304 9
66
67* cwd Smith>old_dir
68 r 1222 .136 1.406 42
69
70* status x
71
72 names: x
73 type: segment
74 date used: 11/29/70 1657.6 est Sun
75 date modified: 11/23/70 2104.5 est Mon
76 branch modified: 11/2/70 2104.5 est Mon
77 bit count 1596
78 records used 1
79 mode rw
80
81 r 1223 .439 3.402 62
82
83* change_wdir
84 r 1224 .111 1.110 41
85
86* link >udd>Smith>old_dir>x Smithx
87 r 1225 .178 1.788 41
88
89* listnames -a
90
91 Segments = 3, Records = 4.
92
93 foo
94 lp.pl1
95 x
96
97 Directories = 1, Records = 1.
98
99 mypoems
100
101 Links = 1.
102
103 Smithx
104
105 r 1227 .626 2.154 43
106
ligne 1 : l'utilisateur demande quel est le répertoire de travail.
La réponse (ligne 2) est donnée par un nom d'arbre.

ligne 3 : le système est prêt. Il donne quelques renseignements
(date, etc...).

ligne 5 : ordre d'imprimer le contenu du répertoire de travail.

ligne 7 : nombre de segments et d'enregistrements occupés (unités
d'espace mémoire, un enregistrement = 4 096 caractères
imprimés soit 1024 mots mémoire).

ligne 9 et 10 : le contenu du répertoire, c'est-à-dire droits, nombre
d'enregistrements, nom pour chaque entrée.

ligne 14 : l'utilisateur crée un segment.

ligne 17 : il demande à nouveau à consulter le répertoire de travail.
Le nouveau segment y figure.

ligne 27 : l'utilisateur commence la construction d'un sous-arbre
en créant un répertoire.

ligne 30 : il en fait le répertoire de travail.

ligne 33 : il vérifie l'identité du répertoire de travail.

ligne 37 et 38 : ce répertoire vient d'être créé, il est vide.

ligne 41 : cette commande a pour effet de
- localiser le segment de nom >UDD>SMITH>POEM
- créer le segment de nom LIMERICK
(interprété par rapport au répertoire de travail,
c'est-à-dire désigné dans le catalogue par le nom
d'arbre ROOT>UDD>JONES>MYPOEMS>LIMERICK)
- copier le contenu du premier segment dans le second.

ligne 44 : l'utilisateur fait imprimer le contenu du répertoire
de travail et y trouve la description du segment qu'il
vient de créer.

ligne 51 : changement de répertoire de travail.

ligne 54 : consultation du répertoire de travail (1'instruction list-a
(pour list all) provoque l'impression de toutes les
entrées du répertoire alors que list n'imprime que les
entrées associées à des segments).

ligne 56 - 63 : on constate que JONES a plus de droits sur son répertoire
(s, m, a = search, modify, append) que sur celui de Smith.
Si SMITH faisant la même demande on obtiendrait une
configuration différente des droits.

ligne 67 : JONES change le répertoire de travail.

ligne 70 : il demande tous les renseignements possible sur le
segment X
<figure><img src="image_31.png" /><figcaption>Figure 25</figcaption></figure>
ligne 83 : la commande "change-wdir" sans argument provoque le retour au répertoire de travail initial.

ligne 86 : l'utilisateur place un lien dans son répertoire vers le segment `ROOT>UDD>SMITH>OLD-DIR>X`.

ligne 89 : il fait imprimer les noms figurant dans son répertoire.

La configuration du catalogue à ce moment est donnée par la figure 25.

En plus des aides offertes par le système telles qu'elles apparaissent dans cet exemple on peut citer quelques possibilités supplémentaires d'appel explicite au système de fichiers.

L'utilisateur peut déclarer un synonyme pour un segment déjà existant. Ce synonyme est alors mémorisé dans l'entrée de la table des segments connus du processus à la suite du nom initial du segment. Le synonyme aura donc la durée de vie du processus.

L'utilisateur peut initialiser un segment, c'est à dire lui faire allouer par le module de contrôle de segment une entrée dans la table des segments connus.

D'autres commandes permettent d'obtenir un nom d'arbre à partir d'un nom de référence, un nom d'arbre à partir d'un nom local, ou d'ôter un segment de la table des segments connus du processus (opération inverse de l'initialisation) etc...
## 6. Critiques

Au terme de cette étude on peut relever un certain nombre de critiques sur la conception et le fonctionnement du système tant pour l'adressage que pour le contrôle de l'accès aux informations.

Le contrôle d'accès fondé sur un système d'inclusion de pouvoir implique certaines conséquences contraignantes. D'abord, le principe des anneaux tend à cloisonner l'espace adressable du système, ce qui est bon du point de vue de la protection, mais introduit une dissymétrie dans cette protection. Ensuite, les concepteurs ont été amenés à placer dans l'anneau le plus protégé les fonctions vitales du système, ce qui a conduit à un noyau de grande taille et très complexe.

### 6.1 Insuffisances du principe des anneaux en ce qui concerne la protection

a) L'imbrication des anneaux ne permet pas d'assurer la méfiance mutuelle [12] de deux sous-systèmes devant coopérer. En effet, le sous-système qui évolue dans l'anneau de pouvoir le plus faible n'est pas sûr que son intégrité soit respectée par l'autre sous-système.

D'une façon générale le franchissement d'une frontière inter-anneaux pose un problème de contrôle qui est différent selon le sens du franchissement.

Par exemple, le cas d'un appel de procédure avec changement d'anneau est résolu dans un sens (augmentation de pouvoir) par la mise en place de guichets de contrôle d'accès à la procédure appelée, mais dans l'autre sens (appel avec diminution de pouvoir) se pose la question de la confiance dans les résultats reçus en retour.

b) Sur le plan de protection on remarque aussi [13] que l'espace d'exécution de chaque processus peut s'étager sur plusieurs anneaux, et qu'il comporte des structures d'adressage qui, pour le même processus, sont communes à des procédures s'exécutant dans le même anneau (piles, segments de liaison, cf. §3). La protection des informations placées dans ces structures communes à plusieurs procédures repose sur la bonne utilisation des registres pointeurs par le compilateur.

c) On peut remarquer enfin que la structure du catalogue de Multics n'autorise pour tout segment qu'une entrée dans le catalogue (où sont enregistrés tous les attributs du segment, en particulier sa liste de contrôle d'accès).
Cette contrainte devrait logiquement impliquer une dépendance entre la liste de contrôle d'accès à un segment et la liste de contrôle d'accès au répertoire père de ce segment : un utilisateur ayant accès au segment devrait nécessairement avoir accès au répertoire contenant sa description.

En réalité la contradiction est permise car la consultation des répertoires est confiée à une procédure du noyau qui agit indistinctement, quels que soient sur ces répertoires les droits du processus qui l'a appelée.

## 6.2 Influence du mécanisme de protection sur la taille et la complexité du noyau

On appelle noyau l'ensemble des fonctions du système qui doivent être absolument sûres et par conséquent rigoureusement protégées du reste du système. Ces fonctions de base assurent le bon fonctionnement de l'ensemble et en particulier les contrôles d'accès aux informations.

Dans Multics, elles sont regroupées dans l'anneau le plus protégé, c'est à dire l'anneau zéro.

Le noyau présente alors une taille importante (150 000 instructions en langage machine) et une grande complexité.

Deux études ont été menées pour réduire cette taille et cette complexité et restructurer le noyau afin qu'il soit plus facile d'en prouver et d'en assurer le bon fonctionnement.

Elles ont fait apparaître que certaines fonctions peuvent être assurées dans des anneaux plus externes. Le résultat en est un allègement et un meilleur découpage du noyau.

L'une de ces études [14] a proposé une modification des espaces de noms dans le but de minimiser le nombre de fonctions d'adressage à protéger.

L'autre étude [15] a montré comment assurer une partie de la fonction d'édition de liens hors du noyau.

### 6.2.1 Modification des différents espaces de noms

R.G. Bratt [14] a étudié la portée des différents espaces de noms qui existent dans Multics ainsi que les liaisons entre eux.

En établissant un modèle général de système il a dégagé trois espaces de noms :
<figure><img src="image_32.png" /></figure>

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

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

D'après ce modèle général, l'identificateur unique de l'objet, fourni par le noyau, est associé une fois pour toutes à l'objet, en une relation biunivoque, et a une portée globale au système. La liaison entre cet identificateur et l'objet (accompagné de sa liste de contrôle d'accès) doit être établie par le noyau et ensuite rester protégée pour que l'intégrité de l'identification des objets soit assurée.

Le nom d'arbre a aussi une portée globale. Il est partageable par les utilisateurs. Il est lié à la structure du catalogue. Sa correspondance avec l'identificateur unique est obligatoirement protégée, elle aussi, contre toute modification de la part d'un utilisateur.

Le nom local, utilisé par la machine pour tous les accès, a une portée qui résulte d'un compromis entre d'une part l'efficacité de son interprétation et d'autre part la facilité de communication entre les domaines de protection parcourus par le processus.
(Dans Multics le domaine serait l'intersection de l'espace d'adressage du processus et d'un anneau de protection, et le nom local est local au processus, mais commun aux domaines qu'il parcourt).

Le nom local doit être en correspondance avec l'identificateur unique de l'objet et aussi avec l'objet et sa liste de contrôle d'accès. Ces correspondances ne doivent pas être modifiées par les utilisateurs.

Les accès sont accélérés au moyen de descripteurs. Dans le modèle il y a deux descripteurs : l'un fournit l'adresse de l'objet ; il est local au processus. L'autre permet le contrôle d'accès ; il est local au domaine. Ces descripteurs assurent matériellement la correspondance entre d'une part nom local et moyen d'accès et d'autre part nom local et moyen de contrôle.

Ces correspondances, comme celle entre descripteur d'adresse et objet, sont protégés contre toute transformation une fois qu'elles sont établies.
(Dans Multics, les deux descripteurs en fait n'en forment qu'un).

Enfin les noms de référence sont ceux qui sont employés par l'utilisateur pour désigner un autre programme que le sien. En leur donnant une interprétation locale au domaine, c'est dans ce dernier qu'on assure leur transformation en noms d'arbre. Il y a dans ce cas étanchéité entre les espaces de noms de référence de chaque domaine. Si leur interprétation est la même dans plusieurs domaines de protection, elle doit être contrôlée par le noyau, pour éviter les conflits de noms d'arbre.

En résumé le modèle fait apparaître que l'établissement des correspondances entre les espaces de noms doit être protégé. La seule façon d'établir une désignation en dehors du noyau est d'utiliser des noms de référence locaux aux domaines de protection.

La comparaison du modèle à Multics montre la différence essentielle : dans Multics l'espace des noms de référence associé à un processus recouvre plusieurs domaines. Ceci implique que l'interprétation de ces noms de référence se fasse dans le noyau.

En conséquence, Bratt a proposé pour Multics de réduire la portée des noms de référence au domaine, et d'en faire assurer l'interprétation dans ce même domaine.

Cette modification soulève cependant une difficulté : les fonctions de gestion des noms, ainsi que les fonctions de gestion de l'espace d'adressage se trouvent dans le noyau. Les premières (formant le module de gestion des noms) assurent les correspondances entre classes de noms, les autres, constituant le module de gestion de l'espace d'adressage, assurent l'initialisation des segments,
l'opération inverse notée "terminaison", et la création des descripteurs.
Ces deux modules se partagent une base de données dans le processus : la table
des segments connus. Faire assurer la gestion des noms de référence dans le
domaine courant revient à sortir du noyau les fonctions de gestion des noms.
Mais dans certains cas - que nous détaillerons plus loin - le module de
gestion de l'espace d'adressage fait appel au module de gestion des noms.
Comme il n'est pas possible, pour raison de protection, que des procédures
du noyau utilisent des procédures qui peuvent s'exécuter en tout anneau, il
faut dissocier complètement la gestion des noms de la gestion de l'espace
d'adressage.

Le module de gestion de l'espace d'adressage fait appel au module
de gestion des noms dans le cas où l'initialisation d'un répertoire est néces-
saire. En effet, on sait que l'initialisation d'un segment dans l'espace
d'adressage d'un processus suppose l'initialisation préalable de tous les
répertoirs "ascendants" de ce segment.

Or, un répertoire n'est désigné que par un nom d'arbre. Pour initialiser ce
répertoire le module de gestion d'espace d'adressage utilise de façon récursive
une procédure "find" qui transforme en nom local le nom d'arbre. Cette
procédure appelle elle-même le module de gestion des noms pour lui passer le
nom d'arbre interprété comme un nom de référence, et obtenir le nom local.
Si ce nom d'arbre est inconnu comme nom de référence, "find" s'appelle
elle-même pour se procurer le nom local du répertoire père, et à partir de ce
dernier essayer d'initialiser le répertoire cible.

En fin de recherche, le module de gestion des noms sera appelé pour associer le
nom local trouvé au nom d'arbre du répertoire.

On voit donc que le module de gestion d'espace d'adressage dépend,
par la procédure "find", du module de gestion des noms.

Il faut donc sortir du noyau ce dernier module et cette fonction
particulière.

En conséquence les répertoirs peuvent être initialisés dans le domaine
courant.

La version courante de Multics impose que cette opération s'effectue
exclusivement en anneau zéro. De cette façon un processus ne peut soupçonner
l'existence de répertoirs sur lesquels il n'a aucun droit mais qui sont
initialisés en tant qu'"ascendants" du segment cible.
De plus, c'est une façon de ne faire intervenir pour déterminer les droits sur un segment que la liste de contrôle d'accès qui lui est associée et non celle des répertoires ascendants.

La modification proposée implique que les répertoires soient initialisés dans le domaine de l'utilisateur. Le droit d'initialiser tout répertoire, qu'il existe ou non, est accordé à tout processus. Un répertoire est détectable pour le processus si ce dernier a au moins un droit sur lui, ou si son père ou un de ses descendants est détectable. Ainsi le processus ne voit pas de différence lorsqu'il initialise un répertoire qui n'existe pas ou un répertoire qui existe mais sur lequel il n'a aucun droit. En dernier ressort l'initialisation du segment sera refusée si ce dernier n'existe pas ou si le processus n'a aucun droit sur lui.

Les répertoires se voient donc attribuer des noms locaux (s'ils sont initialisés deux fois par un processus ils auront deux noms locaux différents).

Grâce à ces précautions le processus ne peut pas obtenir d'information sur la structure du catalogue au cours de l'initialisation des répertoires.

En résumé :

- l'interface du noyau accepte des noms locaux pour désigner les répertoires

- le module de gestion des noms et la procédure "find" sont sortis du noyau.

- Lors d'une tentative d'initialisation d'un segment, les répertoires ascendants sont initialisés systématiquement, si bien que le processus ne peut tirer aucun renseignement significatif de cette tentative dans le cas où elle échoue.

- La table des segments connus du processus ne contient plus les noms de référence ni les noms d'arbre des segments. Ceux-ci figurent dans des bases de données propres aux domaines. La table des segments connus tient à jour dans chaque entrée un bit par anneau qui indique si le segment a été initialisé dans cet anneau par le processus. Quand les 8 bits sont à zéro, on peut libérer cette entrée de la table. L'entrée associée à un répertoire contient de plus la parenthèse de "détectabilité" du répertoire.

Ces modifications ont été réalisées, ce qui a impliqué une diminution de 77 % de la taille du module de gestion de l'espace d'adressage et de 2,5 % de la taille du noyau. Pour ce dernier le principal apport est une réduction importante
de sa complexité. Sur le plan des performances une amélioration de 8% est obtenue pour l'initialisation d'un objet ou l'opération inverse.

### 6.2.2 Éclatement de la fonction d'édition de liens

P. A. Janson [15], dans le même but de réorganisation et de simplification du noyau, a montré comment assurer une partie de la fonction d'édition de liens hors de l'anneau zéro.

Il a utilisé un modèle du même type que dans l'étude précédente : un processus parcourt des domaines de protection, les noms des segments sont locaux aux processus et communs aux domaines parcourus par le processus, les noms de référence sont locaux au domaine.

L'environnement d'exécution est le suivant :
une pile par domaine, un segment de liaison par domaine.

Janson étudie sur ce modèle quelles sont les différentes fonctions réalisées à l'édition de liens, et détermine lesquelles peuvent être sorties du noyau :

Supposant qu'une procédure P, s'exécutant dans un domaine D, appelle une procédure P' qui s'exécutera dans un domaine D', l'édition de liens consiste, de façon générale, à :

- identifier la procédure appelée et établir la liaison avec elle,

- initialiser son environnement d'exécution, c'est à dire charger les registres pointant vers la section de pile et vers la section de segment de liaison adéquates.

On peut décomposer ces opérations de la façon suivante :

A l'appel de P' sous un nom symbolique, l'intercepteur d'erreur donne le contrôle à l'éditeur de liens dans le domaine D de l'appelante.

Le nom symbolique étant local à D, l'éditeur de liens traduit le nom symbolique de P' en un nom d'arbre. Ensuite il appelle une primitive du noyau (le gérant de l'espace d'adressage) pour obtenir le nom local (numéro de segment) de P' à partir de son nom d'arbre. A cette occasion un descripteur est alloué à P'.
Enfin, l'éditeur de liens place ce nom local dans le lien de P vers P'.

On peut remarquer que seules l'attribution du nom local et la formation du descripteur de P' se font dans le noyau. L'établissement du lien s'effectue dans le domaine D de la procédure appelante.

Le lien mis en place, les registres pointeurs de domaine et de procédure sont chargés (séquence d'appel standard). Il reste à faire l'initialisation de l'environnement d'exécution.

Le chargement du registre de pile repose sur la convention qu'il existe un nombre N, fini et connu, de domaines. Alors dans l'espace d'adressage de
chaque processus sont réservées systématiquement N entrées pour les piles
associées aux N domaines (qu'ils soient utilisés ou non).

Le nom local au processus du segment pile concerné est donc connu.

De plus dans chaque pile le premier mot désigne le début de la zone libre ;
la section courante est donc facile à repérer. Le registre pointeur de pile
est chargé automatiquement par la séquence d'entrée dans la procédure P'.

L'initialisation du segment de liaison associé à P' est plus difficile.

Elle ne peut être confiée aux séquences d'appel et d'entrée de procédure
puisque la section de liaison d'une procédure n'est initialisée qu'une fois,
au premier appel de la procédure.

La version courante de Multics confie cette tâche à l'éditeur de liens. Il
charge le registre pointeur vers le segment de liaison de P' en même temps qu'il
établit le lien vers P', ce qui l'oblige à travailler dans le noyau puisqu'il
a en même temps connaissance du segment de liaison de l'appelante et de celui
de l'appelée.

Ce mode de fonctionnement de l'éditeur de liens appelle deux remarques :

- il suffit de faire référence à une procédure pour déclencher l'initialisation
de son segment de liaison,

- une procédure peut, par un appel au noyau, se procurer un nom local d'une
autre procédure et l'appeler directement par ce nom.

La procédure appelée commence alors son exécution sans que son segment de
liaison ait été initialisé.

La solution proposée par Janson ressemble à celle qu'il adopte pour l'initiali-
sation des segments piles : Par convention N noms locaux sont réservés dans le
processus pour les N segments de liaison des N domaines du processus. La
séquence d'appel dépose ce nom local dans le registre pointeur du segment de
liaison et un descripteur est créé automatiquement par le noyau quand ce segment
de liaison est référencé pour la première fois.

Le segment de liaison a ses K premiers mots réservés (K étant le nombre maximum
de segments pouvant figurer dans l'espace d'adressage d'un processus).

Le $n^{\text{ième}}$ de ces mots désigne l'emplacement, dans ce même segment, de la section associée au $n^{\text{ième}}$ segment de l'espace d'adressage.

Le $(K+1)^{\text{ième}}$ mot du segment de liaison désigne le début de sa zone libre.

Ainsi, s'il s'agit d'un appel de P' (dont nous supposons que le nom local est
m) qui n'est pas le premier appel, le $m^{\text{ième}}$ mot du segment de liaison indique la
section de liaison associée à P'.
Si c'est le premier appel, ce mot est vide, il se produit un déroutement.

L'intercepteur d'erreur passe le contrôle à une procédure du domaine D', qui a pour tâche d'initialiser la nouvelle section de liaison, de placer dans le mot du segment de liaison un pointeur vers cette section, et de mettre à jour le mot (K+1) pointeur du début de la zone libre.

Ce travail ne nécessite des accès qu'à P' et à son segment de liaison. Il peut donc s'exécuter dans D', domaine de l'appelée.

En résumé, Janson a montré dans son modèle que l'édition de liens dynamique et l'initialisation de l'environnement comporte cinq étapes :

- établissement des liens par l'édition de liens

- chargement des registres à l'appel de procédure (procédure appelée, domaine nouveau, pile associée).

Ce chargement est l'oeuvre de l'opération (câblée) d'appel.

- Création et initialisation de la pile si c'est la première entrée dans le domaine.

- Localisation de la section de pile associée à la procédure. (Travail effectué par la séquence d'entrée de la procédure).

- Initialisation de la section du segment de liaison si c'est le premier appel de la procédure.

Parmi ces cinq étapes, trois sont réalisées par des programmes, et ces programmes s'exécutent dans des domaines différents :

L'édition des liens se réalise dans le domaine D de la procédure appelante.

L'initialisation de la section de segment de liaison peut se faire dans D', domaine de la procédure appelée.

L'initialisation de la pile doit s'effectuer dans le noyau puisqu'on ne peut travailler dans un domaine sans pile.

Janson a réalisé dans Multics l'implantation de la fonction d'édition de liens sous cette forme. Le résultat est une réduction d'environ 10% de la taille du noyau et de la taille de son interface, à performances sensiblement égales.

## 6.3 Conclusion

L'inclusion des anneaux de protection implique un découpage hiérarchisé des espaces d'adressage tant au niveau de l'utilisateur qu'au niveau global du système. En conséquence, une centralisation excessive est apparue, en particulier une grande taille et une grande complexité du noyau de protection (environ 150 000 instructions en langage machine). Les études critiques et les modifications que nous avons mentionnées tendent à décentraliser certaines fonctions pour simplifier le noyau.
En outre, comme un processus s'exécute dans plusieurs domaines qui conservent toujours la relation d'inclusion, la structuration du système à l'exécution ne peut être que hiérarchique, ce qui interdit l'utilisation de procédés de regroupement fonctionnels tels que moniteurs [16] ou modules [17,18,19].

Néanmoins Multics a élevé au niveau de principe la nécessité de construire des espaces de noms distincts et protégés permettant à différents utilisateurs de partager des objets sans interaction logique.

L'étape suivante des architecture à mémoire commune est la généralisation de l'emploi de descripteurs et l'apparition de structures non hiérarchisées de systèmes [20, 21, 22, 23].
[1] Corbato F.J., Vyssotsky V.A : "Introduction and overview of the Multics System". AFIPS Conf. Proc. 27 (1965 FJCC), Spartan Books, Washington D.C., 1965, pp.185-196.

[2] Bensoussan A., Clingen C.T., Daley R.C. : "The Multics virtual memory". ACM Second Symposium on operating systems principles (October 20-22, 1969), Princeton University, pp. 30-42.

[3] Crocus (nom collectif) : "Systèmes d'exploitation des ordinateurs. Principes de conception". Dunod Université. 1975.

[4] Daley R.C., Dennis J.B. : "Virtual memory, processes, and sharing in Multics". Comm. ACM 11,5 (May, 1968) pp.306-312.

[5] E.I. Organick : "The Multics System : an examination of its structure" MIT Press, Cambridge, Mass., 1972.

[6] Graham R.M. "Protection in an information processing utility" comm. ACM 11,5 (May 1968), pp. 365-369.

[7] Schroeder M.D., Saltzer J.H. : "A hardware architecture for implementing protection rings" comm. ACM 15,3 (March 1972) pp. 157-170.

[8] Spier M.J., Organick E.I. : "The Multics Interprocess communication facility" ACM Second Symposium on operating system principles (October 20-22, 1969), Princeton University, pp. 83-91.

[9] Daley R.C., Neumann P.G. : "A general-purpose file system for secondary storage". Proc. AFIPS 1965 FJCC (27,1), Sparton Books, New-York, pp.213-229.

[10] S. Guiboud-Ribaud, C. Otrage : "Architecture de calculateurs orientés vers les systèmes. 2ème partie : Structure d'accès aux objets du système GEMAU". RAIRO série bleue. Vol 10 n° 1. Janvier 1976
[11] MIT, Project MAC : "The Multiplexed Information and Computing Services : Programmers' Manual. Part I : Introduction to Multics" 1973.

[12] Schroeder M.D. : "Cooperation of mutually suspicious subsystems in a computer utility". Ph.D. Thesis, MAC Tr-104, MIT 1972.

[13] Ferrié J. : "Contrôle de l'accès aux objets dans les systèmes informatiques" Thèse de doctorat d'état. Université de Paris VI, Septembre 1975.

[14] Bratt R.G. : "Minimizing the naming facilities requiring protection in a computing utility" MIT, Project MAC, rapport TR-156 - September 1975.

[15] Janson P.A. : "Dynamic linking and environment initialization in a multi-domain process" MIT, Project MAC, rapport TR-132 - 1974.

[16] C.A.R. Hoare : "Monitors : An operating system structuring concept". Comm. ACM 17,10 (October 1974) pp. 549-557.

[17] D.L. Parnas : "A technique for software module specification with example". Comm. ACM 15,5 (May 1972) pp. 330-336.

[18] J.L. Cheval, F. Cristian, S. Krakowiak, M. Lucas, J. Montuelle et J. Mossière : "Un système d'aide à l'écriture des systèmes d'exploitation". Congrès AFCET Informatique. Novembre 1976.

[19] N. Wirth : "Modula : A language for modular multiprogramming". Berichte des Instituts für Informatik nr 18. Eidgenössische Technische Hochschule. Zürich.

[20] Fabry R.S. : "Capability - Based Addressing" comm. ACM 17,7 (July 1974), pp. 403-411.

[21] England D.M. : "Capability concept mechanisms and structure in system 250". RAIRO série bleue. 9ème année. Septembre 1975.
[22] Needham R.M., Walker R.D.H. : "Protection and Process Management in the CAP computer". International workshop on Protection in Operating System. IRIA, August 1974.

[23] J. Ferrié, C. Kaiser, D. Lanciaux, B. Martin : "An extensible structure for protected systems design".
The Computer Journal. November 1976.
(La référence renvoie au paragraphe du texte où
apparaît la définition de l'expression)

**adresse segmentée** : couple (nom local du segment, déplacement dans le segment)
(§ 2.2).

**connexion d'un segment** : création d'un descripteur pour le segment (§ 2.4.2).

**identificateur d'un processus** : chaîne de 36 bits délivré par le système au moment
de la création du processus (§ 4.3).

**identificateur d'une boîte aux lettres** : chaîne de 72 bits délivrée par le système
quand le processus demande la création
d'une boîte aux lettres (§ 4.3).

**identificateur unique d'un segment** : chaîne de bits associé à un segment lors de
sa création. (dépend de la date de création
et de la machine sur laquelle le segment est
créé) (§ 5.3.).

**initialisation d'un segment** : attribution d'un nom local au segment (§ 2.4.1).

**lien** : entrée d'un répertoire du catalogue contenant un pointeur (nom d'arbre)
vers une entrée d'un autre répertoire (§ 5.2).

**liste des processus actifs** : liste des processus utilisée par un module du
système pour assurer la gestion du parallélisme
(§ 4.2).

**nom d'arbre d'un segment** : concatenation des noms de répertoires à parcourir
depuis la racine du catalogue pour atteindre l'entrée
associée au segment (§ 5.2).

**nom d'entrée d'un segment** : nom contenu dans l'entrée de répertoire associée au
segment et désignant ce segment (§ 5.2).
**nom de référence** d'un segment : nom symbolique employé par l'utilisateur pour désigner le segment (§ 5.3).

**nom local** d'un segment : numéro d'entrée dans le descriptif du processus (§ 5.3).

**nom procédural** d'un segment : couple (numéro de registre pointeur, déplacement dans le segment) (§ 5.3).

**référence symbolique** : équivalent du "nom de référence" (§ 2.7).