Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 4
Plus grand svp ! Organisation et gestion de la mémoire
Année 2002-2003

Suite N°2...

4.3 SEGMENTATION
                       Un rouleau de papyrus, de peau ou de papier.

La segmentation est apparue pour la première fois en 1965 dans le GE 645 par son système d'exploitation Multics.

Principe de la segmentation.

Déjà Howard Aiken avait imaginé que deux mémoires centrales distinctes, l'une pour les programmes, l'autre pour les données serait plus efficace qu'une seule. Si deux mémoires sont utiles, qu'en serait-il de plusieurs ou même d'autant que l'on peut souhaiter ? Mais de quelle mémoire s'agit-il ? Bien sur, la mémoire a une réalité en termes d'accès, d'impossibilité de faire deux accès simultanés sur le même banc, mais elle a aussi la propriété d'être un espace d'adressage linéaire commençant à zéro.

Après les réalisations à base de registre limite et registre de base, on a fait trois constatations.

• Un programme est une chose, sa pile d'exécution une autre, et ses données en sont une troisième. Pourrait-on charger le programme, sa pile, ses données etc. dans des entités repérées par le système au lieu de laisser le programmeur gérer lui-même l'espace qui lui est alloué ?
• Les compilateurs gèrent des volumes séparables par leurs contenus : le texte source, une ou plusieurs tables de symboles, les constantes, la pile des appels de procédures etc., autant de volumes que l'on ne doit pas mélanger.
• Des programmes différents peuvent cohabiter en mémoire, on voudrait gérer séparément leurs espaces d'implantation en considérant pour des raisons de facilité et d'homogénéité que chacun est dans une mémoire qui commence à zéro.

Les moyens de cette gestion sont à la fois du câblage et du système d'exploitation. On créera une table de segments ou encore un jeu de tables de segments, autant qu'il y a de processus chargés ou pouvant l'être sous le système. Ensuite, on vérifiera les adresses calculées par le filtre du registre de segment ou descripteur de segment, qui contiendra obligatoirement son adresse de début comme base. Au concepteur d'ajouter les drapeaux et les indicateurs utiles aux buts poursuivis.

Exemple tiré du circuit Z 8000

Le Z8000 de la société Zilog était le successeur du Z80, processeur le plus utilisé dans les dernières années des machines à 8 bits de données. Hélas, le Z8000 n'était pas compatible avec son prédécesseur non plus qu'avec la série 808X d'Intel. Il fut néanmoins choisi par exemple par Olivetti pour l'ordinateur M20 doté du système d'exploitation PCOS. Le succès du PC d'IBM fit abandonner cette réalisation.

Ce processeur a été choisi pour la simplicité du fonctionnement de sa segmentation comme on avait choisi le N32032 pour la pagination. Les adresses ont 24 bits, fournissant un espace adressable total de 16 Mo, l'unité de gestion de la mémoire (UGM) contient 64 registres descripteurs de segments. La taille de chaque segment peut aller de 256 à 64K octets par incrément de 256 octets. Cette allocation est modifiable dynamiquement par le système.

Le schéma suivant représente l'unité de segmentation Z8008 du Z8000.

Le numéro de segment occupe 6 bits.

La taille maximale d'un segment étant de 64 K, le déplacement, adresse dans le segment a 16 bits. Les tailles de segments allant par incréments de 256 octets, l'adresse de début d'un segment sur 24 bits a ses 8 bits de poids faibles à zéro. Les huit bits de poids fort du déplacement sont ajoutés aux bits 8 à 15 de l'adresse de début de segment.

Le schéma suivant présente les cheminements d'indirection pour le calcul des adresses :

L'UGM reçoit du Z8001, processeur du système Z8000, le n° de segment et le déplacement.
Le n° de segment sélectionne un des 64 registres descripteurs qui contiennent les adresses et huit indicateurs :
Ces attributs contiennent les renseignements suivants (avec quelques réserves) :
RED écriture autorisée ou interdite;
SYS attribution au système ou a un processus utilisateur;
CPUI inhibition de l'UC pour des données non exécutables;
EXC code exécutable uniquement;
DMAI inhibition ou non du canal d'accès direct à la mémoire;
DIRW segment déjà recopié;
CHG segment modifié par écriture;
REF segment présent ou absent dans la mémoire.La base sur 24 bits adresse virtuellement 16 Mo pour des segments de 64 Ko chacun au plus. Ceci ne fournit qu'un mécanisme de segmentation. Pour obtenir un système de mémoire virtuelle minimal, il faut disposer de tables.

Chaque tâche utilise deux tables résidentes en mémoire.

1) Une table globale qui contient les descripteurs communs accessibles par toutes les tâches.
2) Une table locale propre à la tâche.

L'accès à un segment par une tâche n'est possible que si la référence de ce segment figure dans sa table locale ou dans la table globale.

Chaque table locale ou globale peut contenir jusqu'à 8192 descripteurs.

REMARQUONS que l'adresse physique est un CALCUL sur deux adresses.

Ces manipulations de segments sont le fonctionnement courant de la mémoire.
Le chargement d'un nouveau programme consiste à lui allouer des segments en nombre suffisant.
 

La segmentation gère les CONTENUS de l'espace de mémoire selon leurs natures et chacun dans un espace de mémoire CONNEXE commençant à 0.

Protocoles d'allocation

Nous mentionnons ici les protocoles d'allocation de mémoire pour la segmentation seule. La présence quasi universelle de la pagination qui prend en charge cette allocation les a rendus inutiles, leur importance est donc des plus réduites. Ils étaient analogues à ceux de la multiprogrammation pure. Les algorithmes correspondants sont toujours largement présentés dans les cours et ouvrages sur les systèmes d'exploitation, en général sous le nom de politique et même de stratégie (sic!) d'allocation.

L'allocation d'un espace libre peut être faite selon trois procédures :

• le premier ajustement (first fit), on prend le premier bloc, premier dans le parcours des disponibilités, suffisant pour contenir le segment dans la liste des emplacements libres, cette stratégie a été reconnue comme la meilleure par de nombreuses simulations;
• le meilleur ajustement (best fit), on cherche l'emplacement disponible le plus petit qui puisse contenir le segment;
• le pire ajustement (worst fit), on prend systématiquement le plus grand emplacement libre, on en réserve la quantité nécessaire et le reste est remis comme emplacement libre dans la liste.

Les modèles de mémoire.

La pagination et la segmentation peuvent sont des modèles de mémoire comme déjà dit.

2.5.9. DANS LE DÉSORDRE, AVANTAGES, INCONVÉNIENTS ET PARAMÈTRES

Le premier aspect intéressant de la pagination est la possibilité pour le système de changer l'emplacement physique des pages, même en cours d'exécution du processus. Ceci est fait par la simple mise à jour des tables, laissant bien sûr inchangée l'adresse inscrite dans le programme.

Les avantages de la segmentation tiennent d'abord au groupement des informations en sous ensembles cohérents : programme, données, pile, entrées et sorties. Ils tiennent ensuite dans les formes normales de segmentation, que chaque segment est pour l'occupant un espace d'adressage commençant à zéro. On peut voir la segmentation comme une généralisation dee l'architecture de Harvard.

L'inconvénient de la segmentation seule est la fragmentation progressive de l'espace de mémoire. En effet les segments de tailles très variables restitués en fin d'exécution par les processus qui les occupaient deviennent des trous et ne sont pas toujours réutilisables par d'autres processus. Il faut donc que le système contienne une tâche de compactage ou ramasse miettes, qui sera lancée sur un critère à définir et sera coûteuse en temps d'exécution.

La pagination n'a pas cet inconvénient puisque les pages sont toutes de même taille et sont allouées de façon atomique. La translation dynamique est par contre indispensable pour maintenir la connexité logique des pages non contiguës.

Les références de la page courante ou des dernières pages, du segment courant ou des segments du processus courant sont normalement placés dans des registres. Toutefois, même si l'on dispose de plusieurs registres, on n'évite pas l'accès à des tables normalement en mémoire. Le temps total d'accès aux données est plus que multiplié par deux.
La seule solution est d'utiliser des caches à raison :

• d'un cache des descripteurs de segments des derniers (ou autres) processus;
• d'un cache des tables relatives aux pages les plus fréquemment utilisées (ou les dernières utilisées).

Un premier bit: présence indique la présence ou l'absence de la page en mémoire. Il y en a un par entrée de la table des pages. Il est mis à jour par le système et utilisé par le câblage pour déterminer s'il y a lieu de charger ou non la page.

Un deuxième bit: modifiée, est attaché à chaque entrée, pour signifier si la page a été modifiée ou non. Il sert à indiquer au système la liste des pages non modifiées qui n'ont pas à être réécrites sur disque.

Un troisième bit: accédé indique au système si la page a fait l'objet d'un accès dans un intervalle de temps fixé au préalable. Il est périodiquement mis à 0 pour cela. Plusieurs architectures n'utilisent pas un tel bit, c'est le cas des VAX conçus pour VMS qui met en œuvre un algorithme de remplacement qui n'en a pas besoin. Unix sur Vax doit en faire une émulation.

Observations sur la taille des pages

Dans un système paginé, la taille des pages peut avoir été choisie par le concepteur du matériel, mais elle peut aussi être un paramètre libre du système d'exploitation ou être modifiée par lui. Les tailles les plus courantes sont de 512 octets à 4 ko.

Le choix de la taille répond aux mêmes critères que le choix de la granulation d'un disque. On observe très simplement qu'en moyenne la moitié d'une page est inoccupée si l'on fait l'hypothèse réaliste d'une distribution uniforme des restes de la division de la taille des unités à charger par la taille de la page.

• Si la taille de la page (du granule) est grande, la perte unitaire est grande.
• Si la taille est petite, la perte unitaire est faible, mais alors le nombre des transferts augmente et la table des pages est plus grande et donc le cache employé.