3. Mise en œuvre dans GORDO

3.1 Introduction à GORDO

GORDO est un système à temps partagé mis en œuvre sur SDS Sigma 7. Nous exposons ci-dessous quelques-unes des caractéristiques pertinentes pour notre document.

3.1.1 Système de fichiers de GORDO

Le système de fichiers est orienté page. Il est composé de fichiers et de répertoires. Un fichier se compose d'un en-tête et d'un certain nombre de pages qui constituent le corps du fichier. Un répertoire se compose d'un certain nombre d'entrées qui pointent vers des fichiers ou d'autres répertoires.

3.1.2 Processus GORDO

• Un processus est un programme (procédures et données) plus son environnement logique. En d'autres termes, un processus est un programme connu et contrôlé par l'ordonnanceur de GORDO.
• Un utilisateur (une tâche) peut avoir plusieurs processus aussi différents que compilateur, chargeur, éditeur, programme d'application, etc. Un processus est créé au moyen d'un appel système (FORK).
• L'espace auquel un processus peut se référer est l'espace virtuel de 128k mots. Une partie (8k) est réservée au système d'exploitation, l'autre partie (120k) est directement accessible par l'utilisateur. Ce dernier peut remplir ou modifier sa partie de l'espace virtuel lors du 'couplage'. (Voir ci-dessous : appels de service) de pages prises dans différents fichiers. La figure 3 illustre ce couplage.
• Un processus peut demander des services au moyen d'appels système. Les appels système pertinents pour notre document sont :

WAKE pour réveiller (rendre actif) un processus endormi SLEEP pour endormir un autre processus (ou lui-même) COUPLE pour coupler une page de l'espace de fichiers à l'espace virtuel.

• Un processus s'exécute ordinairement en mode esclave. Toutefois, s'il est configuré comme processus E/S, il peut accéder à des instructions privilégiées.
• Les processus peuvent partager des données par l'intermédiaire de fichiers rattachés à des répertoires "boîte aux lettres".

Remarque : tout au long de cette note, les mots processus et programme sont utilisés de manière interchangeable.

[Figure 3 - Espace virtuel et couplage - voir le fichier PDF]

3.2 Aperçu de l'organisation logicielle

La figure 4 illustre l'organisation d'ensemble.

Le système est fondé sur deux programmes principaux : le "Réseau" et le "Handler".

Le Handler est une routine d'interruption E/S étroitement liée à l'interface matérielle IMP-HOST. Il sert le processus Réseau pour transmettre et recevoir des messages du réseau.

Le processus Réseau effectue la majeure partie du travail.

Sa fonction principale est de satisfaire les demandes des utilisateurs d'ouverture/fermeture de connexions et de transmission/réception de messages du réseau. Pour ce faire,

• il établit, identifie et rompt les liaisons en utilisant les tables d'allocation (HOST, CONNECT, INPUT LINK ; voir 3.3.1.1)
• il prend connaissance de la présence de nouveaux utilisateurs en explorant le répertoire boîte aux lettres du Réseau ;
• il communique avec les utilisateurs actifs au moyen de pages partagées par lesquelles des messages et des demandes sont échangés (pages partagées de connexion) ;
• il met en forme les messages entrants/sortants dans une page de travail. Cette page de travail possède une extension (anneau d'urgence) ;
• il communique avec le Handler au moyen d'une page partagée (page de communication E/S) qui contient les tampons de communication E/S.

[Figure 4 - Aperçu de l'organisation logicielle - voir le fichier PDF]

3.3 Description du logiciel

3.3.1 Structures de données

3.3.1.1 Tables d'allocation : HOST, CONNECT, INPUT LINK

Le programme Réseau établit, identifie et rompt les liaisons et les connexions en utilisant 3 tables :

Une table triée par numéro d'hôte distant.

Une table triée par numéro de connexion.

Une table triée par numéro de liaison d'entrée.

(a) table HOST (voir figure 5)

C'est une table de bits indiquant les liaisons sortantes libres. Elle présente les caractéristiques suivantes :

• Emplacement : résident sur disque
• Couplage : couplée à l'espace virtuel du processus Réseau.
• Taille : autant d'emplacements que de HOST[s] distants.
• Structure d'emplacement : autant de bits que de liaisons sortantes possibles vers un hôte distant, c'est-à-dire 256.
• Accès : indexation. Chaque emplacement est accédé au moyen d'un numéro d'hôte distant.
• Particularité : dans toute la table, pas plus de 64 bits ne peuvent être activés. Ce chiffre correspond au nombre maximal de liaisons sortantes pouvant être activées simultanément (quel que soit le nombre de HOST[s] distants).

(b) table CONNECT

Cette table garde la trace de l'environnement de toutes les connexions.

Elle présente les caractéristiques suivantes :

• Emplacement : résident sur disque
• Couplage : couplée à l'espace virtuel du processus Réseau
• Taille : autant d'emplacements que de connexions en service.
• Structure d'emplacement : voir figure 6. Chaque emplacement a une longueur de 2 mots
• Accès : indexation. Chaque emplacement est accédé au moyen d'un numéro de connexion. Voir 3.4 la manière dont elle est gérée.
• Particularité 1 : la structure d'emplacement correspondant à une connexion primaire n'est pas identique à celle d'une connexion auxiliaire (voir figure 7). Cela parce que les identifications et les demandes des utilisateurs se font par l'intermédiaire des pages partagées primaires.
• Particularité 2 : cette table est gérée parallèlement aux pages de connexion (voir 3.3.2 (b))
• Particularité 3 : cette table est principalement utilisée pour transmettre des messages. (Pour chaque connexion, elle contient le numéro de la liaison sortante et le numéro de l'hôte distant, c'est-à-dire toutes les informations requises pour transmettre un message.)

(c) table INPUT LINK

Cette table garde la trace de toutes les liaisons entrantes (d'entrée) et est donc étroitement liée à la table CONNECT.

[Figure 5 - table HOST - voir le fichier PDF]

[Figure 6 - table CONNECT : structure d'emplacement - voir le fichier PDF]

[Figure 7 - table INSERT LINK : structure d'emplacement - voir le fichier PDF]

Elle présente les caractéristiques suivantes :

• Emplacement : résident sur disque.
• Couplage : couplée à l'espace virtuel du processus Réseau.
• Taille : autant d'emplacements que de liaisons entrantes, c'est-à-dire que de connexions
• Structure d'emplacement : voir figure 7. Chaque emplacement a une longueur de 1 mot
• Accès : hachage. La valeur de clé hachée est principalement fondée sur le numéro de la liaison entrante et le numéro de l'hôte distant.
• Particularité 1 : cette table est également utilisée pour mémoriser momentanément le numéro de connexion pendant l'établissement de la connexion suivante. Voir 3.4 la manière dont elle est gérée.
• Particularité 2 : cette table est principalement utilisée à la réception des messages. (Pour chaque liaison entrante, elle contient le numéro de connexion correspondant, c'est-à-dire indirectement l'identification de l'utilisateur auquel le message doit être transmis)

3.3.1.2 Pages tampons

Toutes les pages qui vont maintenant être décrites contiennent deux tampons (entrée et sortie). Ces tampons servent soit à faire passer, soit à traiter les messages.

La taille de chacun de ces tampons devrait être au moins égale à celle d'un message, c'est-à-dire 8095 bits. Nous avons choisi une taille de tampon de 253 mots (8096 bits) afin que les deux tampons soient inclus dans une seule page (512 mots). Les 6 mots restants de la page sont généralement utilisés pour le contrôle.

Une structure de page tampon typique est identifiée sur la figure 8.

(a) Page de communication E/S

Voir figure 9.

Cette page de communication E/S est utilisée comme interface entre le Handler et le programme Réseau.

Dans les tampons de cette page, les messages sont assemblés (entrée) ou désassemblés (sortie) mot par mot par le Handler ; par exemple, un message "prêt à partir", rangé par le programme Réseau dans le tampon de sortie, est expédié mot par mot par le Handler.

Caractéristiques principales :

• Emplacement : résident en mémoire : page verrouillée
• Couplage : couplée à l'espace virtuel du processus Réseau
• Contenu : * tampon d'entrée (253 mots) pour les messages entrants tampon de sortie (253 mots) pour les messages sortants
  • zone de contrôle d'entrée (6 demi-mots)
  • zone de contrôle de sortie (6 demi-mots)
• Structure : voir figure 9.
• Particularité : * le tampon d'entrée est rempli par le Handler (lu depuis le matériel) et vidé par le programme Réseau
  • Inversement pour le tampon de sortie

(b) Pages partagées de connexion (zone partagée utilisateur-Réseau)

Caractéristiques générales :

• Il y a autant de pages partagées que de connexions.
• Ces pages partagées entre le Réseau et les processus utilisateur constituent une zone de communication pour (1) faire passer les messages dans les deux sens, et (2) échanger des informations de contrôle, par exemple une demande d'établissement de nouvelles connexions.

Caractéristiques principales :

• Emplacement : résident sur disque
• Couplage : couplée à la fois à l'espace virtuel d'un processus utilisateur et à l'espace virtuel du processus Réseau.
• Contenu : - tampon d'entrée (253 mots) pour les messages entrants
  • tampon de sortie (253 mots) pour les messages sortants
  • zone de contrôle d'entrée (6 demi-mots)
  • zone de contrôle de sortie (6 demi-mots)
• Structure : voir figure 10.
• Particularité 1 : - le tampon d'entrée est rempli par le Réseau et vidé par l'utilisateur.
  • Inversement pour le tampon de sortie.
• Particularité 2 : la zone de contrôle correspondant à une page partagée de connexion primaire diffère de celle d'une connexion auxiliaire. Cela parce que c'est par l'intermédiaire d'une "zone de contrôle de connexion primaire" que les demandes d'établissement de connexions auxiliaires sont transmises au processus Réseau.

(c) Page de travail

Caractéristique générale :

• Cette page permet aux programmes Réseau et Handler de travailler indépendamment sur des messages différents et contribue ainsi à un recouvrement. Par exemple, lorsque le Handler est occupé à transmettre un message au matériel, le programme Réseau peut mettre en forme (en-tête, marquage, etc.) le message suivant à expédier, de sorte qu'il puisse relancer le Handler dès que celui-ci est libre.

Caractéristiques principales :

• Emplacement : résident sur disque
• Couplage : couplée à l'espace virtuel du processus Réseau
• Contenu : - tampon d'entrée (253 mots) pour les messages entrants
  • tampon de sortie (253 mots) pour les messages sortants

Remarque :

Pendant la réception, il peut arriver qu'un programme utilisateur ne soit pas prêt à accepter un nouveau message. Dans ce cas, pour éviter d'engorger le système, le Réseau stocke momentanément le message entrant dans l'un des tampons de l'anneau d'urgence. (Si cet anneau est plein, une routine d'aide sera invoquée.)

Pendant l'émission, toutes les opérations sont synchronisées avec les RFNM ; de telles procédures n'ont donc pas besoin d'être prévues. (Le programme Réseau n'autorise un utilisateur à réémettre qu'après avoir reçu le RFNM du message précédemment transmis.)

[Figure 8 - Page tampon typique - voir le fichier PDF]

[Figure 9 - Structure de la page de communication E/S - voir le fichier PDF]

[Figure 10 - Structure de la page partagée de connexion - voir le fichier PDF]

3.3.2 Programmes

3.3.2.1 Programme Handler

Caractéristiques générales :

C'est une routine d'interruption E/S qui pilote l'interface matérielle IMP/HOST afin de transmettre ou de recevoir des messages. La transmission et la réception sont effectuées en mode duplex intégral.

Caractéristiques principales :

• Emplacement : résident en mémoire. Le Handler se trouve dans la même zone mémoire que le système d'exploitation et peut être considéré comme faisant partie de celui-ci.
• Déclenchement : par l'interruption matérielle IMP-HOST. Cette interruption est déclenchée soit :
• pendant la transmission, lorsqu'un mot du message est complètement envoyé à l'IMP
• pendant la réception, lorsqu'un mot du message a été complètement reçu de l'IMP
• pendant les temps d'inactivité, lorsque le matériel a reçu un ordre 'start input' ou 'start output' du CPU du Sigma 7. Ces ordres sont émis par le programme Réseau pour provoquer des interruptions en retour (et par conséquent pour déclencher indirectement le Handler).
• Fonctions principales : * vide le tampon de sortie en transmettant son contenu (message sortant vers l'IMP. Cette opération est effectuée mot par mot (32 bits) et utilise des ordres "Write" pour piloter le matériel HOST-IMP.
• remplit le tampon d'entrée avec les données reçues du matériel HOST-IMP (message entrant). Cette opération est également effectuée mot par mot et utilise des ordres "Read" pour piloter le matériel HOST-IMP.
• réveille le programme Réseau lorsque l'une des opérations précédentes est terminée.

3.3.2.2 Programme Réseau

Caractéristiques générales :

Ce programme sert l'utilisateur pour ouvrir/fermer des connexions et transmettre/recevoir des messages. Il utilise le Handler comme auxiliaire pour l'interfaçage avec le matériel.

Du point de vue de GORDO, c'est un processus ordinaire et il est traité comme tel.

Caractéristiques principales :

• Emplacement : résident sur disque. Plus précisément, il est sur disque lorsqu'il est endormi et appelé en mémoire lorsqu'il est réveillé par un programme.
• Déclenchement : il est déclenché par des appels de service 'WAKE' émis soit par un processus utilisateur, soit par le Handler.
• Fonctions principales : * établit/supprime les connexions sortantes sur demande des utilisateurs. Pour ce faire, il envoie des messages de contrôle (voir 2.4.2) aux HOST[s] distants afin d'obtenir l'établissement/la libération des liaisons ; il notifie ensuite les utilisateurs en retour.
  • assure le traitement des messages de contrôle entrants (transmis sur les liaisons de contrôle), par exemple pour contribuer aux établissements/suppressions de connexions (ceux demandés par les hôtes distants).
• prépare la transmission des messages sortants. Il prélève les messages texte dans les pages partagées (les messages y sont stockés par les utilisateurs), les met en forme (ajoute l'en-tête, le marquage, la somme de contrôle..), et les transmet au Handler pour la transmission.
• assure la distribution des messages entrants. C'est l'opération inverse de la précédente. Les utilisateurs auxquels les messages doivent être distribués sont identifiés au moyen des en-têtes.
• Configuration de l'espace virtuel : voir figure 11.
• Particularité : il est intégré comme processus E/S, de sorte qu'il peut accéder à des instructions privilégiées (RD/WD pour déclencher indirectement le Handler).

[Figure 11 - Espace virtuel du processus Réseau - voir le fichier PDF]

3.4 Procédures logicielles

Les procédures logicielles détaillées sont données dans les organigrammes joints à l'annexe A.

Toutefois, pour permettre une compréhension rapide de la mise en œuvre, nous énumérons ci-dessous quelques procédures logicielles typiques.

3.4.1 Description de quelques séquences typiques

Considérons quelques-unes des transactions à la disposition de l'utilisateur (voir 2.4) et indiquons les procédures logicielles de base qu'elles impliquent. Pour chaque cas, nous décrirons (i) ce que fait le programme utilisateur et (ii) ce que fait le programme Réseau.

(a) Ouvrir une liaison primaire (voir aussi 2.4.2)

(i) Ce que fait le programme utilisateur[1] :

• il stocke dans le répertoire boîte aux lettres du Réseau le nom d'un fichier, par exemple DATA ;
• il couple la première page de ce fichier à son espace virtuel ;
• il stocke des informations dans cette page (son numéro de tâche/processus, le numéro de l'hôte distant, par exemple (i)) ;
• il réveille le processus Réseau ;
• il s'endort.

(ii) Ce que fait le programme Réseau :

• il explore le répertoire boîte aux lettres du Réseau et accède au fichier DATA ;
• il couple la première page de ce fichier à son espace virtuel (zone partagée, voir 3.3.1.2). Supposons que cette page soit la k-ième dans la zone partagée ; k est le numéro de connexion interne ;
• il explore le i-ième emplacement de la nouvelle table HOST (voir 3.3.1.1 (a)) et sélectionne le premier bit = 0, par exemple le (alpha)-ième bit ; alpha correspond au numéro de la liaison sortante ;
• il stocke des informations (numéro de tâche/processus, numéro de l'hôte distant (i), numéro de la liaison sortante (alpha)) dans le k-ième emplacement de la table CONNECT (voir 3.3.1.2).
• il stocke momentanément le numéro de connexion (k) dans la table INPUT LINK. Ceci est effectué en créant une entrée dans cette table (hachage de la valeur de clé : "numéro de la liaison sortante (alpha) + numéro de l'hôte distant (i) + indicateur sortant".) ;
• il prépare le texte du message ENQ PRIM 0 0 a et met en forme un message complet en ajoutant l'en-tête, le marquage, la somme de contrôle, etc. ;
• il vérifie l'état du Handler (bit dans la page verrouillée E/S). Si le Handler est libre, il stocke le message de contrôle 'prêt à partir' dans le tampon de sortie de la page verrouillée E/S, déclenche le Handler et s'endort. Sinon, il s'endort.

Au bout d'un moment, le Handler réveille le processus Réseau parce qu'il a reçu un message complet. Nous supposons que ce message soit le message de contrôle envoyé par l'hôte distant pour acquitter l'établissement de la connexion. Le texte du message devrait être :

ACK ENQ PRIM 0 0 alpha 0 0 beta

où beta est le numéro de la liaison entrante. (Voir 2.4.2)

Voyons maintenant ce que fait le programme Réseau à la réception du message de contrôle ci-dessus :

• il récupère le numéro de connexion précédemment stocké dans la table INPUT LINK en re-hachant la même valeur de clé (voir ci-dessus). Il supprime également cette entrée ;
• il crée une entrée dans la table INPUT LINK pour la liaison entrante. Pour ce faire, il hache la valeur de clé : "numéro de la liaison entrante (beta]) + numéro de l'hôte distant (i) + "indicateur entrant". Dans cette entrée, il stocke le numéro de l'hôte (i), le numéro de la liaison entrante (beta) et le numéro de connexion (k) ;
• il met à jour le k-ième emplacement de la table CONNECT en y stockant le numéro de la liaison entrante (beta) ;
• il active le bit 'net-user' dans la k-ième page partagée (page correspondant à la connexion primaire qui vient d'être ouverte) et réveille le processus utilisateur ;
• il s'endort.

(b) Transmettre un message sur la liaison primaire

(i) Ce que fait le programme utilisateur[1].

• il stocke le texte du message dans le tampon de sortie de la page partagée de la connexion primaire (voir 3.3.1.2) ;
• il active le bit 'user-net' de cette page et réveille le processus Réseau ;
• il s'endort.

(ii) Ce que fait le programme Réseau :

• il recherche une demande d'utilisateur, c'est-à-dire qu'il explore en séquence les pages partagées de connexion et sélectionne celle dont le bit 'user-net' est activé. Supposons que k soit le numéro de la page sélectionnée dans la liste partagée, K est le numéro de connexion ;
• il détermine le type de demande en testant les 'bits de demande' de la page partagée k. Il constate qu'il s'agit d'une demande de transmission d'un message.
• il prélève le texte du message dans le tampon de sortie de la page partagée k, le met en forme en un message complet et le transmet au Handler d'une manière très semblable à ce qui précède (voir Ouvrir une liaison primaire).
• il s'endort.

[1] Remarque : dans une première phase, l'utilisateur écrira directement les fonctions réseau dans son programme. Par la suite, des sous-programmes seront mis à sa disposition. Ces sous-programmes seront très proches de ceux décrits en 2.4.