Chapitre 4 Mémoire

4.1 Les problèmes à résoudre

La mémoire, terme d'un anthropomorphisme abusif hérité des « cerveaux artificiels » et auquel les Anglo-Saxons ont raison de souvent préférer storage, est un élément essentiel de l'architecture de von Neumann. Lorsqu'un calcul est effectué par un ordinateur, ses phases successives sont représentées par différents états de la mémoire, ce qui est la réalisation technique du ruban de la machine de Turing. Dès que le calcul se complique, l'organisation de la mémoire joue un rôle important dans l'efficacité et l'intelligibilité du programme.

En outre, dès qu'un système d'exploitation permet la présence simultanée en mémoire (et l'exécution « pseudo--simultanée ») de plusieurs programmes il faut partager entre eux la mémoire disponible et veiller à éviter que l'un n'empiète sur la zone réservée à l'autre. Les systèmes modernes permettent également d'allouer dynamiquement des zones mémoires pour y représenter des objets temporaires qui seront supprimés avant la fin du programme, ce qui permettra de rendre disponible la zone mémoire correspondante.

Enfin, encore aujourd'hui la mémoire rapide est une ressource coûteuse, aussi les ordinateurs modernes sont-ils dotés non pas d'une mémoire homogène d'un seul tenant, mais d'une hiérarchie de mémoires, en commençant par une toute petite mémoire très rapide pratiquement incorporée au circuit du processeur, puis des mémoires de plus en plus grandes et de plus en plus lentes, pour finir par un espace sur disque magnétique où sont recopiées les zones mémoire provisoirement inutilisées. La petite mémoire très rapide contient des données en cours de traitement, les grandes mémoire lentes (et bon marché) contiennent des données en attente.

Toutes ces questions, regroupées sous le titre de « gestion de la mémoire », sont l'objet des soins attentifs des architectes de processeurs et des écrivains de systèmes d'exploitation, parce que leur solution plus ou moins heureuse jouera un rôle primordial pour l'efficacité plus ou moins grande du couple processeur--système, et que la conception du matériel et celle du logiciel sont ici très étroitement intriquées. Un système de mémoire raté lors de la conception initiale d'une architecture est un des rares défauts non rattrapables.

4.2 La mémoire du programme

Nous avons dit que les états successifs de la mémoire représentent les étapes successives d'un calcul. La théorie de cette représentation, telle qu'illustrée à la grande époque des systèmes formels par Kurt Gödel, Alan Turing et Alonzo Church, conduit à des notations d'une rigueur implacable mais d'un maniement délicat, qui réserverait la programmation des ordinateurs à une élite triée sur le volet de la mathématique. L'histoire des langages de programmation est marquée par une évolution vers l'expressivité, destinée à faciliter l'écriture comme la compréhension des programmes.

4.2.1 Les mots de mémoire

Dès von Neumann la mémoire est structurée, nous l'avons vu, en mots qui regroupent un certain nombre de bits. Un détail à ne pas oublier : tous les mots ont la même taille constante. Si l'on considère chaque bit comme un chiffre binaire et un mot de taille n comme un nombre binaire de n chiffres, nous avons l'élément de base d'une arithmétique. L'annexe A donne quelques détails sur sa réalisation concrète.

Nous avons vu que nous devons aussi représenter en mémoire bien d'autres choses que des nombres. D'abord et malgré qu'en aient les physiciens et les numériciens, toutes les données ne sont pas des nombres, il y a aussi des chaînes de caractères, du texte, des images et des sons représentés de façon codée. Et nous avons vu qu'il fallait aussi stocker les instructions, qui souvent occupent chacune un mot¹.

4.2.2 Les adresses

Il faut allouer à chacun de ces objets un ou plusieurs mots de mémoire, et ensuite pouvoir les y retrouver. Ceci suppose un système d'identification et de repérage des mots individuels, un système d'adresses. Beaucoup de solutions ont été essayées, mais aujourd'hui tous les concepteurs se sont ralliés à la plus simple : les mots de la mémoire centrale sont numérotés du premier au dernier et chaque mot est identifié par son numéro d'ordre qui est son adresse. Enfin, à un facteur près : pour des raisons de commodité l'unité adressable de mémoire est le plus souvent aujourd'hui un octet de 8 bits, le mot comportera quatre ou huit octets et les adresses de mots seront des multiples de 4 ou de 8.

Ceci semble anodin et simple, et il s'agit pourtant d'un choix technique absolument crucial. L'adresse est un numéro, donc un nombre, un nombre binaire, on l'aura deviné. Les adresses, nous l'avons vu en ??, sont manipulées par les instructions, c'est-à-dire qu'elles doivent tenir dans les registres². La taille d'un registre en bits est la borne supérieure du nombre de chiffres binaires d'une adresse. Si le registre a n bits, la plus grande adresse vaudra 2ⁿ-1, et donc aucun ordinateur conforme à cette architecture ne pourra avoir une capacité mémoire supérieure à 2ⁿ octets. Cette valeur de n intervient partout dans l'architecture et dans les programmes, si on l'a prévue trop petite au départ c'est irréparable.

L'architecture 360 conçue au début des années 1960 comportait des mots, et donc des registres, de 32 bits, ce qui permettait une taille mémoire maximum de 2³² octets, un peu plus de 4 milliards. À l'époque cette valeur semblait énorme, et les ingénieurs limitèrent la taille des adresses à 24 bits donnant accès à une mémoire de 16 millions d'octets. En effet chaque bit d'adresse supplémentaire coûte très cher : les adresses sont transmises entre le processeur, la mémoire et les périphériques par des bus spéciaux (les bus d'adresse) qui comportent un fil par bit. La largeur du bus d'adresse pèse lourd dans le budget du processeur en termes de surface, de consommation électrique, de complexité des dispositifs, sans parler de la taille accrue des circuits logiques de toutes les instructions qui doivent manipuler des adresses.

Les concepteurs du matériel mirent en garde les concepteurs de logiciels : interdiction d'utiliser les huit bits vides qui restaient dans les mots de mémoire ou les registres qui contenaient des adresses, ils seraient précieux pour une extension ultérieure de l'architecture ! Mais à une époque où chaque bit de mémoire était utilisé avec parcimonie et à bon escient c'était un supplice de Tantale. Lorsqu'à la fin des années 1970 la limite de 16 millions d'octets se révéla une contrainte insupportable, les systèmes d'exploitation développés par IBM soi-même pour l'architecture 360 utilisaient régulièrement les huit bits de poids fort des mots d'adresse pour toutes sortes d'usages, et la conversion à l'architecture XA (pour Extended addressing, passage aux adresses sur 32 bits) imposa un remaniement complet de milliers de modules de logiciel, au prix d'années de travail et de millions de dollars³. Cette imprévoyance eut de fait des conséquences bien plus lourdes même si bien moins médiatiques que le soi-disant « bug de l'an 2000 ».

4.2.3 Noms et variables

L'adresse, que nous venons de décrire, a deux fonctions bien différentes : elle repère la position physique d'un emplacement en mémoire, et elle permet à un programme en langage machine (ou en assembleur) d'en désigner le contenu. Dans ce dernier rôle l'adresse exerce la fonction de nom : un élément de langage (un lexème) qui désigne est un nom.

En langage machine ou assembleur les noms sont des adresses, mais dans des langages de plus haut niveau les noms sont des lexèmes plus abstraits, en fait plus similaires à ce que nous appelons nom dans la grammaire des langages humains. De tels noms seront généralement appelés des identifiants. Mais pour être exécuté le programme en langage de haut niveau sera traduit en langage assembleur, puis en langage machine, et ses noms (ses identifiants) se résoudront en adresses qui permettront d'accéder physiquement à la donnée.

En langage machine ou assembleur même, la donnée traitée n'est pas toujours désignée directement par une adresse simple. Un mot peut contenir l'adresse d'un autre mot qui, lui, contient l'adresse de la donnée, c'est l'adressage indirect. Il peut aussi être commode de traiter de façon itérative une série de mots adjacents comme un tableau : un registre R1 contiendra l'adresse du premier mot, et un registre R2 contiendra le rang du mot courant dans la série, éventuellement multipliée par la taille du mot en octets : ainsi l'adresse réelle du mot à traiter sera R1 + R2. R1 sera appelé registre de base et R2 registre index du tableau. L'art de la programmation en assembleur consiste à utiliser judicieusement les possibilités d'adressage indirect et indexé.

Dans un langage évolué, en général, on a envie de conserver des résultats intermédiaires, ou des valeurs significatives d'un calcul ou d'un traitement de quelque sorte. Ces valeurs, de quelque type (nombre, texte, image), occupent un ou plusieurs mots qui constituent un objet élémentaire. Bref, on souhaite pouvoir retrouver, à la demande, la valeur d'un objet du langage. La solution retenue consiste souvent à associer à la valeur un nom (un identifiant) de telle sorte que l'évocation ultérieure de ce nom procure un accès à la valeur. L'identifiant sera le nom de l'objet.

L'objet le plus habituel des langages de programmation évolués est la variable. La variable, nous l'avons vu à la section ??, est un objet doté des propriétés suivantes (que nous enrichissons ici) :

posséder un nom ;
posséder une valeur ;
le langage permet, par le nom, de connaître la valeur de la variable ;
une variable a une durée de vie (une persistance), qui est souvent égale à la durée pendant laquelle le programme s'exécute, mais qui peut être plus courte (variable locale à un sous-programme) et que l'on peut souhaiter plus longue (les moyens de satisfaire ce souhait feront l'objet du chapitre suivant) ;
une variable a une visibilité, qui peut s'étendre à l'ensemble du programme, mais qui peut être limitée par exemple à un sous-programme ;
il est possible par le langage de modifier la valeur de la variable. L'opération de modification de la valeur d'une variable s'appelle l'affectation (notons que certains langages de haut niveau tels que ML et Haskell n'autorisent pas cette opération d'affectation).

Ne perdons pas de vue qu'en dernier recours ce que nous appelons valeur sera une configuration de bits contenue dans un ou plusieurs mots de mémoire. La valeur a donc une existence physique, elle est un élément de l'état de la mémoire.

Le nom sera en dernière analyse traduit en une adresse, l'adresse du premier mot de la région de mémoire où est stockée la valeur. Le nom n'est qu'un objet du langage, un objet symbolique destiné à disparaître au cours du processus de traduction de langage évolué en langage machine. Nous avons ainsi une chaîne de noms, depuis l'identifiant du langage évolué jusqu'à l'adresse mémoire physique en passant par d'éventuelles adresses indirectes (des noms de noms) ou indexées, qui tous mènent à la même donnée. Cette chaîne parcourt en fait les différents niveaux d'abstraction qui mènent de la description formelle d'un traitement par le texte d'un programme jusqu'à son exécution par un ordinateur matériel.

Revenons un instant sur l'affectation, qui est la propriété numéro 6 de ce que nous avons appelé variable. Si nous en étions restés aux trois propriétés précédentes, ce que nous appelons variable serait grosso modo la même chose que ce que les mathématiciens appellent variable. Mais l'affectation opère une rupture radicale entre vision mathématique et vision informatique du calcul, elle y introduit un aspect dynamique, actif et concret qui est étranger aux mathématiciens.

Or cette rupture, si elle est radicale, n'est susceptible ni de suture ni de réduction. L'affectation est vraiment au coeur de la problématique informatique, c'est elle qui permet de modéliser un calcul par des états de mémoire successifs, bref c'est elle qui permet de réaliser des machines de Turing.

4.2.4 Protection de la mémoire

Dès que les systèmes se compliquèrent, et surtout dès qu'il y eut plusieurs programmes en mémoire, des accidents arrivèrent. Si l'on a en mémoire le petit programme en langage machine de la section ??, il est clair qu'une erreur de programmation très banale peut envoyer une donnée à une mauvaise adresse, et écraser une donnée ou une instruction qui ne devrait pas l'être, ce qui perturbera radicalement les traitements ultérieurs. Si encore le programme erroné détruit ses propres données ou son propre texte, l'auteur n'a qu'à s'en prendre à lui-même, mais s'il s'agit de celui d'un collègue innocent c'est trop injuste. Et si ce sont les données ou le texte du système, alors la catastrophe est générale.

Les premiers systèmes de multiprogrammation abordaient ce problème par le côté du matériel. L'architecture 360 découpe (elle existe encore...) la mémoire en groupes de 2 048 octets qui constituent l'unité non partageable (le quantum) d'allocation à un processus donné. Chacun de ces groupes possède une clé physique de quatre chiffres binaires pouvant donc prendre 16 valeurs. Par ailleurs le PSW comporte un champ de quatre bits qui contient la clé attribuée à son démarrage au processus courant. Lors de tout accès mémoire, le processeur vérifie que la clé de la zone concernée est bien égale à la clé du processus courant, sinon le processeur provoque une erreur fatale et le processus concerné est interrompu. Bien sûr le système d'exploitation qui s'exécute en mode privilégié bénéficie d'une clé particulière, la clé zéro, qui lui donne accès à toute la mémoire.

Ce système est un peu rudimentaire : il n'autorise que quinze processus concomitants et le système. Le développement des systèmes à mémoire virtuelle permettra des dispositifs bien plus raffinés.

4.3 Partage de mémoire en multiprogrammation

Les sections 3.2 et 3.8 ont décrit les principes de la multiprogrammation et ses conséquences dans le domaine de la mémoire ; il faut maintenant préciser comment se fait l'attribution de la mémoire à chacun des programmes concomitants pseudo-simultanés.

4.3.1 Exemple : l'OS/360

Les premiers systèmes d'exploitation destinés à l'architecture IBM 360, au milieu des années 1960, procédaient de façon statique : une zone fixe en mémoire était attribuée à chaque programme à son démarrage et il la gardait jusqu'à la fin de son exécution. Il existait deux variantes :

Avec l'OS/MFT (Multiprogramming with a fixed number of tasks), la mémoire était découpée en partitions fixes au démarrage du système. Il appartenait à l'administrateur du système de fixer judicieusement le nombre de partitions et la taille de chacune d'entre elles. Les travaux étaient répartis en classes (en fait des files d'attente) et chaque classe était éligible pour une ou plusieurs partitions, principalement en fonction de la taille mémoire nécessaire à l'exécution des travaux de la classe. On pouvait ainsi prévoir plusieurs petites partitions pour petits travaux et une grande partition pour les gros. Le modèle de file d'attente pour l'exécution des travaux est laissé en exercice au lecteur.

L'inconvénient de ce système est facile à imaginer : les partitions sont des lits de Procuste. Leur taille est toujours plus ou moins arbitraire et tous les programmes ne peuvent pas s'y adapter exactement. De surcroît les files d'attente de certaines classes peuvent être vides alors que d'autres peuvent être embouteillées. Tout ceci entraîne un risque de mauvaise utilisation de la mémoire.
La version plus perfectionnée, OS/MVT (Multiprogramming with a variable number of tasks), abolit le découpage rigide de la mémoire. Chaque programme annonce la taille de la région de mémoire nécessaire à son exécution et dès qu'elle est disponible elle lui est attribuée, toujours une fois pour toutes et jusqu'à la fin de son exécution. Détail important : la région de mémoire ainsi allouée est contiguë.

OS/MVT est beaucoup plus complexe mais beaucoup plus satisfaisant qu'OS/MFT. Néanmoins on voit bien que ce n'est pas vraiment satisfaisant : les programmes ont des tailles et des durées d'exécution arbitraires. Lorsqu'un programme se termine il libère une région de mémoire qui laisse un trou à une adresse arbitraire au milieu de la mémoire. Rien n'assure que parmi les programmes en file d'attente il y en aura un qui logera dans ce trou. Il peut ainsi se créer un effet « fromage de gruyère », où plusieurs trous de mémoire atteignent taille cumulée suffisante pour les travaux en attente, mais comme chacun est trop petit, la file d'attente est bloquée.

Ce défaut de la gestion de mémoire de l'OS/360 sera corrigé par l'introduction de la mémoire virtuelle que nous étudierons à la section suivante, mais auparavant il nous faut compléter ce qui vient d'être dit en expliquant la translation des programmes, sans quoi nous ne pourrions avoir plusieurs programmes en mémoire simultanément.

4.3.2 Translation des programmes

Oui il s'agit bien de translation, puisqu'aujourd'hui il faut préciser en employant ce mot que l'on n'est pas en train de faire une erreur de traduction (justement) de l'anglais translation qui signifie traduction en français⁴. Nous avons donc parlé plus haut de la traduction des programmes, ici c'est de leur translation qu'il s'agit.

Le lecteur vigilant, à la lecture des alinéas précédents, aura dû se demander comment il est possible de charger des programmes en mémoire à des adresses somme toute imprévisibles sans en perturber la fonctionnement ? Lors de nos essais en langage machine nos programmes comportaient des adresses qui désignaient sans ambiguïté un mot de mémoire bien déterminé où devait se trouver une instruction ou une donnée indispensable au bon déroulement des opérations. Locus regit actum...

Si maintenant on nous dit que le programme va être chargé à une adresse qui ne sera plus l'adresse 0, mais une position quelconque et imprévue en plein milieu de la mémoire, tout le texte va être décalé, et chaque objet désigné par le programme aura une adresse qui ne sera plus l'adresse absolue à partir de 0 que nous avions écrite, mais cette adresse additionnée de l'adresse de chargement du programme. Comment est-ce possible ? Nous avons déjà abordé cette question à la section ??, nous allons y revenir ici.

Lorsqu'on programme en assembleur, on écrit rarement des adresses absolues. Les assembleurs allègent la tâche du programmeur en lui permettant de désigner la position d'un octet dans le texte du programme par un nom symbolique, que l'assembleur se chargera de traduire en adresse. Nous avons vu un exemple d'usage de nom symbolique dans le programme assembleur de la section ??, avec le traitement de l'étiquette FIN, qui désignait l'instruction située à l'adresse absolue 5. Un tel symbole peut de la même façon désigner le premier octet d'une zone de mémoire qui contient une donnée.

Nous voulons maintenant que ce symbole ne désigne plus l'adresse absolue 5, mais une adresse relative par rapport au début du programme, lequel ne serait plus nécessairement à l'adresse 0. Pour ce faire, notre assembleur devra opérer une traduction un peu plus complexe ; chaque symbole sera traduit en adresse selon le schéma suivant : l'adresse sera exprimée comme la somme de deux termes :

un déplacement par rapport au début du programme, égal à l'adresse que nous avions écrite de façon absolue ;
une valeur dite de base, qui correspondra à l'adresse de chargement du programme, et sera contenue dans un registre, dit registre de base.

Pendant l'assemblage proprement dit, le registre de base recevra la valeur 0. Au moment de l'exécution, il recevra l'adresse du point de chargement du programme en mémoire, et ainsi nos adresses exprimées sous la forme base + déplacement seront juste. Le mécanisme qui place dans le registre de base l'adresse de début du programme varie selon les systèmes, il est parfois à la charge du système d'exploitation, d'autres réalisations laissent cette action à la charge du programmeur qui dispose d'instructions capables de l'effectuer (c'est le cas de l'OS/360). Enfin, n'oublions pas que lorsque que nous disons programmeur il faut la plupart du temps entendre compilateur, parce que c'est lui qui va traduire en assembleur les programmes écrits en langage évolué par des humains qui n'auront pas eu à se soucier de ces contingences techniques pourtant passionnantes.

Ce perfectionnement de l'assembleur n'est pas très spectaculaire, mais sans lui la multiprogrammation serait plus complexe à réaliser. Les programmes assemblés selon ce principe avec des adresses sous forme de base + déplacement sont appelés des programmes translatables. La translation des programmes est parfois aussi nommée réimplantation . Nous retrouverons un autre usage de cette propriété lorsque nous parlerons de l'édition de liens, qui permet de réunir plusieurs modules de programmes compilés indépendamment (c'est-à-dire éventuellement écrits dans des langages différents) pour constituer un seul programme.

2mm

4.4 Mémoire virtuelle

4.4.1 Insuffisance de la mémoire statique

Nous avons vu ci-dessus que l'allocation à un programme de la zone mémoire dont il avait besoin, de façon fixe une fois pour toutes au début de son exécution, avait un inconvénient qui était la fragmentation de la mémoire au fur et à mesure du lancement à des instants aléatoires de programmes de tailles hétérogènes. Ainsi peut être libre une zone de mémoire de taille suffisante pour lancer un programme sans que le lancement soit possible, parce que cette zone libre est constituée de fragments disjoints.

Certains systèmes des années 1960 (Univac, Control Data) palliaient cette inefficacité en réorganisant périodiquement la mémoire pour « tasser » les zones utilisées les unes contre les autres. Mais une solution bien plus radicale allait advenir : la mémoire virtuelle. La voici.

3mm

4.4.2 Organisation générale

L'organisation de mémoire virtuelle que nous allons décrire est inspirée de celle des systèmes IBM 370 et suivants, mais les autres réalisations sont assez comparables. Il y a eu des organisations différentes, mais celle-ci, qui est la plus simple, s'est aussi révélée la plus efficace, ce qui a assuré son succès général.

Il existe dans cette organisation trois états de la mémoire : virtuelle, réelle, auxiliaire. La mémoire virtuelle est celle que les programmes utilisent, mais elle n'existe pas vraiment. Un emplacement de la mémoire virtuelle peut avoir ou ne pas avoir de contenu ; s'il n'a pas de contenu il est simplement virtuel et le restera jusqu'à ce que le programme décide d'y placer un contenu ; s'il a un contenu il faut bien que celui-ci existe quelque part, et ce quelque part sera soit la mémoire réelle, soit une zone tampon sur disque appelée mémoire auxiliaire.

La mémoire virtuelle répond à deux préoccupations. La première vise à éviter le gaspillage de fragments de mémoire en permettant à la mémoire linéaire vue par le programme d'être physiquement constituée de fragments disjoints, ce qui supprime l'inconvénient de la fragmentation de la mémoire, au prix d'un mécanisme que nous allons étudier pour rétablir la fiction de la linéarité⁵.

Localité des traitements

La seconde préoccupation répond à un phénomène appelé localité des traitements. Si nous observons, cycle par cycle, le déroulement d'un programme dont la taille mémoire est par exemple de un million d'octets, nous constaterons que pendant une tranche de temps donnée, brève par rapport au temps d'exécution total, il ne fait référence qu'à un petit nombre d'adresses proches les unes des autres. Ceci veut dire qu'à chaque instant le programme a besoin de beaucoup moins de mémoire qu'il ne lui en faut au total, et que le contenu de la mémoire inutile à un instant donné pourrait être stocké provisoirement dans un endroit moins coûteux, par exemple sur disque.

Lorsque le système d'exploitation lance l'exécution d'un programme, il lui alloue un espace de mémoire virtuelle. Comme cette mémoire est virtuelle, donc gratuite ou presque, l'espace alloué est aussi vaste que l'on veut, dans les limites de l'adressage possible avec la taille de mot disponible.

Cet espace de mémoire virtuelle est découpé en pages de taille fixe (souvent 2¹² = 4 096 octets, pour fixer les idées) et décrit par une table des pages. En fait, pour éviter d'avoir une seule grande table incommode à manipuler on aura généralement une table à plusieurs niveaux, avec une table de segments au niveau le plus élevé, un segment comprenant par exemple 32 pages et chaque segment ayant une petite table de pages, mais l'idée est la même.

Les emplacements en mémoire virtuelle sont désignés par des adresses virtuelles, qui ressemblent comme des soeurs aux adresses réelles que nous avons vues jusqu'alors. Les adresses multiples de 4 096 (selon notre exemple) sont des frontières de pages, et les multiples de 32 * 4 096 = 131 072 des frontières de segments, mais cela ne change pas grand-chose. La table des pages aura une entrée par page, indexée par l'adresse virtuelle de la page, qui sera le numéro d'ordre de l'octet frontière de page dans l'espace virtuel, soit un multiple de 4 096, c'est-à-dire un nombre binaire se terminant par douze 0.

4.4.3 Pagination

Que dit la table des pages ? D'abord, pour chaque page virtuelle elle indique où elle se trouve réellement. Selon les trois états de mémoire évoqués ci-dessus, il y a trois situations possibles pour une page virtuelle :

elle peut avoir une incarnation en mémoire réelle, physique, et la table indique alors l'adresse réelle de cette incarnation ; la zone de mémoire réelle qui accueille une page de mémoire virtuelle est appelée cadre de page (page frame) ;
si elle correspond à une adresse qui n'a encore jamais été invoquée par le programme, elle reste purement virtuelle et elle n'existe physiquement nulle part, son existence est limitée à une entrée vierge dans la table des pages ;
si cette page a été utilisée à un moment donné mais que l'exécution du programme ne nécessitait pas son usage à cet instant et qu'il n'y avait pas assez de place en mémoire centrale, elle peut avoir été placée sur disque dans ce que l'on appellera mémoire auxiliaire de pages, et la table indiquera son emplacement dans cette mémoire auxiliaire.

MMU (Memory Management Unit)

Comment fonctionne la mémoire virtuelle ? Les programmes ne connaissent que la mémoire virtuelle, et des adresses virtuelles. Chaque fois qu'une instruction fait référence à une donnée, cette référence est une adresse virtuelle. Il faut donc traduire à la volée l'adresse virtuelle en adresse réelle : l'obtention d'une vitesse raisonnable impose un circuit logique particulier à cet effet, appelé DAT (Dynamic Address Translation). Avec les autres fonctions de gestion de la mémoire virtuelle que nous allons décrire il constitue la MMU (Memory Management Unit).

Le DAT fonctionne de la façon suivante, illustrée par la figure 4.1. L'adresse (24 bits dans notre exemple) est découpée en trois parties : les 12 derniers bits (si nous poursuivons notre exemple avec des pages de taille 2¹²), dits bits de poids faible, sont considérés comme une adresse relative par rapport à la frontière de page précédente, soit un déplacement dans la page. Les 5 bits de poids le plus fort sont un numéro de segment, index dans la table de segments du processus, qui permet de trouver la table des pages du segment. Les 7 bits de poids intermédiaire sont un numéro de page, index dans la table des pages qui permet de trouver la page concernée. La partition des 12 bits de poids fort en numéro de segment et numéro de page n'est qu'un artifice pour hiérarchiser la table des pages, ils peuvent être considérés globalement comme le numéro de page.

Le DAT consulte la table des pages pour y chercher l'entrée correspondant au numéro de page virtuelle voulu. Selon les trois cas énumérés ci-dessus trois situations peuvent se présenter :

Dans le cas 1 de la liste ci-dessus la page existe et possède une incarnation en mémoire réelle. Le circuit de traduction d'adresse trouve dans la table des pages l'adresse du cadre de page qui contient la page virtuelle. Cette adresse est additionnée au déplacement dans la page, ce qui donne l'adresse réelle à laquelle le programme doit accéder.
Voyons ensuite le cas 2 : l'adresse évoquée par le programme n'a encore fait l'objet d'aucune référence, non plus qu'aucune adresse de la même page. Cette situation peut se produire au lancement d'un programme, ou après l'allocation d'une zone de mémoire dynamique vierge, par exemple. Il va falloir obtenir du système une page réelle « neuve » et placer son adresse dans la table des pages, ainsi nous serons ramenés au problème précédent, après la consommation d'un nombre non négligeable de cycles de processeur. La MMU génère une exception dite de défaut de page (la section 3.12.2 donne la définition des exceptions), et le gestionnaire de défaut de page va être chargé d'obtenir une page réelle neuve.

-6mm

Figure 4.1 : Pagination : cas où la page demandée n'est plus en mémoire réelle (exemple de l'OS/370)

Comment obtient-on une page réelle neuve ? Le système gère une table des cadres de pages en mémoire réelle, cette table garde pour chaque cadre de page un certain nombre d'informations, et notamment s'il est libre. Deux cas peuvent se présenter :
1. Si le parcours de la table des cadres de pages révèle un cadre libre il est alloué à la page vierge, son adresse est placée dans la table des pages et le programme peut poursuivre son exécution.
2. S'il n'y a aucun cadre de page libre, il faut en libérer un. En première approximation nous dirons que le système d'exploitation procède ainsi (nous verrons plus tard quelques raffinements techniques qui améliorent les performances sans bouleverser le schéma de principe) : chaque entrée dans la table des cadres de pages comporte une estampille qui indique la date du dernier accès d'un programme à une adresse comprise dans la page qui réside dans ce cadre. L'estampille de plus faible valeur désigne le cadre de la page la moins récemment utilisée. Cette page est donc candidate à l'éviction : son contenu est recopié en mémoire auxiliaire de pages, son cadre libéré et alloué à notre page vierge. La table des pages est mise à jour et le programme continue comme dans le cas précédent.
  
  Cet algorithme qui consiste à évincer la page la moins récemment utilisée est appelé LRU (Least recently used) et nous le retrouverons pour d'autres usages.
Voyons enfin le cas 3 : la page a été utilisée, elle a un contenu, mais elle ne réside plus en mémoire réelle, elle a été déplacée sur disque en mémoire auxiliaire de page. Cette condition déclenche comme la précédente une exception de défaut de page et le transfert du contrôle au gestionnaire de défaut de page. Il faut pour pouvoir utiliser la page la ramener en mémoire réelle, et pour cela il faut qu'un cadre de page soit libre, ou en libérer un : ceci est fait selon le même mécanisme qu'à l'alinéa ci-dessus. Une fois le cadre de page obtenu, le contenu de la page virtuelle qui était en mémoire auxiliaire est recopié dans ce cadre, la table des pages est mise à jour et l'exécution du programme peut continuer. C'est le mécanisme illustré par la figure 4.1.

Une vision de la pagination

La technique de pagination a suscité une floraison de métaphores explicatives, qui aident à comprendre la question. Celle que je cite ici m'a été fournie par mon collègue Henri Leridon :

« Finalement, tout ça me semble relever du problème du garçon de plage sur la Côte d'Azur au mois d'aout. Je m'explique. Le plagiste doit gérer -- au mieux -- un espace limité, avec des clients qui vont et viennent en exprimant des besoins (de surface au sol : on les laisse se débrouiller dans l'eau) variés. On peut compliquer un peu en supposant que les premiers arrivés d'une même famille ne savent pas à l'avance combien ils seront au total, ni à quelle heure arrivera le reste de la famille, mais qu'ils voudront être tous ensemble. On pourrait aussi admettre qu'il y a deux plagistes, situés chacun à une extrémité de la plage et gérant plus ou moins le même espace. Et pourquoi ne pas admettre que les clients seraient en droit de changer de place (pour se rapprocher du bar, par exemple), les plagistes devant alors s'évertuer à conserver leur adresse ? »

4.4.4 Espaces adresse

Les premiers systèmes à mémoire virtuelle (chez IBM par exemple OS/VS1 et VS2 en 1972) allouaient pour l'ensemble du système un espace unique de mémoire virtuelle dont la taille était fixée par la valeur maximum d'une adresse. Cet espace virtuel était partagé entre les programmes selon les mêmes principes que dans les anciens systèmes sans mémoire virtuelle, tels que nous les avons exposés au début de ce chapitre. Ceci présentait l'avantage que l'adjonction de la mémoire virtuelle modifiait assez peu le système d'exploitation.

Cependant le caractère virtuel de la mémoire allouée permet d'imaginer d'autres solutions, notamment allouer à chaque programme un espace de mémoire virtuelle entier. Pour réaliser un tel système il faut donner à chaque programme une table des pages particulière, qui décrit tout l'espace adressable. Quand le système d'exploitation donnera la main à un autre programme il changera également de table des pages. Ce sera chez IBM le système MVS (Multiple Virtual Storage) en 1974, chez Digital Equipment VMS en 1978, chez Data General AOS/VS... Une mémoire virtuelle à espaces adresse multiples est illustrée par la figure 4.2.

Il ne devrait pas échapper au lecteur attentif une conséquence importante de cette multiplication des espaces de mémoire virtuelle (ou espaces adresse) : une adresse virtuelle donnée est désormais traduite dans le contexte d'exécution d'un programme donné, la même adresse dans le contexte d'un autre programme est traduite à partir d'une autre table des pages, et correspond donc à une autre adresse réelle. Il est de ce fait impossible à un programme de faire référence à une adresse qui appartient à une page de mémoire virtuelle d'un autre programme. La mémoire virtuelle à espaces adresse multiples améliore la sécurité des données.

Autre conséquence : dans les systèmes à espace adresse unique (virtuel ou non) l'adresse de chargement d'un programme dépend de l'emplacement de la zone de mémoire libre que le système a pu lui allouer, elle est donc variable, d'où les techniques de translation exposées à la section 4.3.2. Maintenant que chaque programme a son espace privé, rien n'interdit de le charger toujours à la même adresse, et d'avoir une carte de la mémoire identique d'une exécution à l'autre. Cela dit les techniques de translation conservent leur utilité pour pouvoir lier ensemble des programmes écrits séparément, elles ont même trouvé un surcroît d'utilité avec les techniques de processus légers connus sous le nom d'activités (threads) : la multi-activité (multithreading) consiste à faire exécuter plusieurs parties de programmes en pseudo--simultanéité dans le même espace adresse (voir section 10.2). L'instabilité notoire de certains programmes qui reposent sur cette technique, au premier rang desquels les navigateurs du WWW, découle peut-être de cette promiscuité en mémoire, qui a par ailleurs des avantages : il est commode de pouvoir afficher plusieurs fenêtres du navigateur à l'écran, et de consulter une page dans une fenêtre cependant qu'une autre se charge dans une fenêtre différente et qu'un transfert de fichier a lieu dans une troisième. Vous ne le saviez peut-être pas mais c'est de la multi-activité.

Que chaque programme s'exécute dans son espace privé inaccessible aux autres parce que tout simplement aucun nom n'est disponible pour en désigner les emplacements, très bien, mais il y a quand même des choses à partager. Notamment le système d'exploitation, qui après tout est lui aussi un programme, avec des sous-programmes qui doivent pouvoir être appelés par les programmes ordinaires. Le système d'exploitation comporte aussi de nombreuses tables qui contiennent des informations relatives à l'état de l'ordinateur et du système, comme par exemple le fuseau horaire de référence, des moyens d'accès aux données sur disque ou au réseau, etc. Comment y accéder ?

Figure 4.2 : Mémoire virtuelle à espaces adresse multiples

La solution imaginée par les auteurs de VMS est la suivante : les adresses sont sur 32 bits, ce qui autorise des espaces adresse de 2³² octets, soit plus de quatre milliards (4 294 967 296). Les 2³¹ octets qui constituent la première moitié de cet espace (avec des adresses dont le bit de poids le plus fort est 0) sont dévolus au programme et à ses données. Les 2³¹ octets suivants (avec des adresses dont le bit de poids le plus fort est 1) sont dévolus au système d'exploitation, c'est-à-dire que ces pages sont décrites par la table des pages du système. Naturellement pour tous les programmes la table des pages du système est la même, c'est-à-dire que tous les programmes voient le même système d'exploitation avec les mêmes adresses virtuelles, et n'y ont bien sûr droit qu'à un accès en lecture mais pas en modification. On dit que le système d'exploitation est mappé (de l'anglais mapped) dans l'espace adresse du programme, les adresses virtuelles des pages du système sont superposées à des adresses virtuelles de l'espace de chaque programme.

Les auteurs de Unix 4.4 BSD ont recours à un découpage analogue, mais ils sont moins généreux pour le système d'exploitation (le noyau) et le programme reçoit la plus grande part de l'espace adresse. Il est vrai que 4.4 BSD est moins volumineux que VMS.

Après cet éloge des systèmes à espaces adresse multiples, il convient de signaler que les processeurs 64 bits semblent remettre à la mode l'espace adresse unique. En effet l'espace offert par une telle taille d'adresse est suffisant pour les usages actuels, et la conception du système s'en trouverait simplifiée. L'architecture IA-64 (Itanium) prévoit le support des deux types de gestion de mémoire virtuelle, et les manuels Intel présentent l'espace adresse unique comme la voie de l'avenir...

3mm

4.4.5 Registres associatifs (Translation Lookaside Buffer, TLB)

Tout ceci fonctionne, mais il est difficile de ne pas se poser la question suivante : si chaque accès à la mémoire entraîne une traduction d'adresse, et que celle-ci entraîne la consultation d'une table des pages, cela risque de consommer un temps considérable, même avec une table hiérarchisée et un circuit spécial. Un espace adresse de 2³² octets (adresses sur 32 bits) découpé en pages de 4 096 octets aura une table des pages avec un million d'entrées, alors ne parlons pas d'adresses sur 64 bits qui nous entraîneraient vers une table à 2⁵² entrées...

En fait, un système de mémoire tel que celui décrit jusqu'ici serait d'une lenteur exécrable. Pour en accroître la vitesse les MMU réelles ont recours à un dispositif qui ne change rien aux grands principes de fonctionnement mais qui procure une accélération spectaculaire : le tampon de traduction anticipée (Translation Lookaside Buffer, TLB).

L'idée est de tirer parti une seconde fois de la localité des traitements (cf. section 4.4.2). Puisqu'un programme à un moment donné ne fait référence qu'à un petit nombre d'adresses proches les unes des autres (c'est un fait d'observation générale), c'est qu'il utilise (pendant ce laps de temps) toujours les mêmes pages. Il serait donc judicieux de garder sous la main, c'est-à-dire dans quelques registres implantés sur le circuit du processeur, et de ce fait d'un accès beaucoup plus rapide que la mémoire, le résultat des traductions les plus récentes, soit une table de correspondance numéro de page virtuelle -- numéro de cadre de page pour ces quelques pages utilisées.

Comment déterminer les pages privilégiées dont le cadre de page de résidence figurera dans le TLB ? Ce seront les pages les plus récemment utilisées. À chaque référence à la mémoire, le MMU déclenche en parallèle deux méthodes de traduction d'adresse : consulter le TLB pour voir si la page cherchée n'y figure pas, activer le DAT pour parcourir la table des pages. Si la consultation du TLB réussit, le DAT beaucoup plus lent est arrêté. Si elle échoue le DAT poursuit la traduction jusqu'à son terme et en place le résultat dans le TLB pour la prochaine fois.

Où le DAT va-t-il placer le résultat de la traduction qu'il vient d'effectuer ? À la place d'une autre entrée.

Pour être efficace, le TLB n'a pas besoin d'être très grand : en fait, une taille étonnamment petite suffit, en général 64 entrées. Généralement, les systèmes à espaces adresse multiples évoqués à la section précédent 4.4.4 mettent le TLB en échec, et chaque commutation de contexte, qui entraîne un changement d'espace adresse, nécessite la remise à zéro du TLB. Le plus surprenant est que le TLB reste néanmoins efficace. Signalons que certains processeurs, tel le MIPS R4000, utilisent un TLB étiqueté (tagged TLB), c'est-à-dire que chaque entrée de TLB comporte l'identifiant de l'espace adresse auquel elle appartient, ce qui évite la pénalité que nous venons d'évoquer.

Ce dispositif est si efficace et résout une si grande proportion des traductions d'adresses (plus de 99% !) que certains concepteurs se sont dit que le DAT servait très rarement et qu'il suffisait de le réaliser en logiciel, ce qui est beaucoup plus lent mais plus simple et moins coûteux, et libère des nanomètres--carrés précieux sur le circuit. Les premiers architectes à risquer cette audace furent ceux des processeurs MIPS, et comme les résultats furent excellents ceux des SPARC, des Alpha et des HP PA leur emboîtèrent le pas. Sur ces processeurs le seul matériel spécialisé pour la mémoire virtuelle est le TLB et sa logique de consultation.

Nous retrouverons d'autres dispositifs d'optimisation bâtis sur le même principe : un dispositif rapide (et donc cher) pour traiter une petite quantité de cas très fréquents, un dispositif plus lent pour traiter la grande masse des cas à faible occurrence. C'est notamment sur ce principe que reposent les dispositifs de cache, qui constituent la hiérarchie de mémoire, et que nous verrons bientôt. Ce qui est frustrant, c'est qu'aucune modélisation mathématique ne rend compte à ce jour des optimisations considérables qu'ils procurent.

4.4.6 Tables de pages inverses

Nous venons de voir qu'avec l'avènement des adresses sur 64 bits, et donc des espaces adresse de 2⁶⁴ octets, il nous faudrait des tables de pages avec 2⁵² entrées, soit, avec huit octets par entrée, 30 millions de gibioctets⁶. C'est impossible aujourd'hui et pour encore pas mal de temps. Une solution, retenue sur les premières versions de l'Alpha et de l'Itanium, est de réduire arbitrairement mais radicalement la taille mémoire adressable en limitant le nombre de lignes du bus d'adresses, mais ce n'est guère satisfaisant.

Une solution à ce problème, dite des tables inverses, est la suivante : au lieu d'avoir une table des pages avec une entrée par page virtuelle, on a juste une table des cadres de page qui contient pour chaque cadre la référence de la page virtuelle qu'il contient, cette référence comportant le numéro de page virtuelle et l'identifiant du programme propriétaire de l'espace adresse. L'avantage de la table des cadres de pages, c'est qu'elle est beaucoup plus petite, et par définition dans un rapport de taille avec la mémoire réelle de l'ordre de un pour mille.

L'on a ainsi une table qui donne la correspondance cadre de page physique -- page de mémoire virtuelle, mais en général on cherche à faire la conversion en sens inverse, et avec une telle table cela risque d'être très laborieux : la seule solution consiste à examiner une par une en séquence les entrées de la table, en espérant trouver notre page plutôt vers le début. Cela semble désespérant, mais nous allons être sauvés. Par quoi ? par le TLB, pardi. N'avons-nous pas vu, à la section 4.4.5 il y a un instant, qu'il fournissait des traductions virtuel -- réel avec une efficacité étonnante et sans table des pages ? Alors voilà...

Reste les cas résiduels des références non résolues par le TLB : leur traitement doit être traité par le logiciel (système d'exploitation). Des méthodes telles que les tables associatives (hash tables) sont de nature à diminuer la pénalité qui en résulte.

4.4.7 Mémoire virtuelle segmentée

Les systèmes de mémoire virtuelle que nous avons décrits jusqu'ici utilisent des espaces adresse uniformes, c'est-à-dire découpés en pages de tailles identiques, elles-mêmes regoupées par simple raison de commodité de manipulation en segments de tailles identiques. Certaines régions de la mémoire virtuelle pourront être dévolues à un usage particulier, mais ceci ne se reflète pas dans la structure de l'espace adresse, qui reste uniforme, et plus précisément linéaire : les adresses se succèdent comme la suite des nombres entiers, avec des frontières de page tous les 4 096 octets et des frontières de segment tous les 32 * 4 096 = 131 072 octets, par exemple.

D'autres architectures de mémoire virtuelle ont été imaginées, avec des segments de tailles variables, adaptés à des régions particulières du programme, par exemple un segment pour le code du programme, un segment pour les données initialisées au lancement du programme, un segment pour les données non initialisées, un segment de données non modifiables, un segment pour les structures de données créées par le système pour ce processus, etc. De tels systèmes conservent en général une taille de page fixe, mais le nombre de pages d'un segment est arbitraire. La gestion est plus complexe, puisque les tables de pages deviennent elles aussi de taille arbitraire.

L'archétype de ces systèmes à mémoire virtuelle segmentée est Multics (voir chapitre 8). Les Unix modernes tels que Linux recourent à la notion de segment, mais elle est alors orthogonale à la notion de page : l'espace adresse d'un processus est partagé en segments (un pour le code du noyau, un pour les données du noyau, un pour le code utilisateur, un pour les données utilisateur, un segment d'état de tâche par processus (TSS, Task State Segment), un segment pour la table de descripteurs de segments). Par ailleurs ces segments sont paginés ; l'impression est qu'ils ne servent pas à grand'chose.

4.4.8 Petite chronologie de la mémoire virtuelle

La première réalisation de mémoire virtuelle avec pagination date de 1961 et figure à l'actif de l'Université de Manchester, qui développait en collaboration avec le constructeur le système de l'ordinateur ATLAS de Ferranti. Le système de l'ATLAS était précurseur dans bien des domaines et surtout il fut l'objet de publications très complètes.

En 1962 Burroughs (devenu depuis sa fusion avec Univac Unisys) lançait son modèle B 5000, qui apportait les innovations suivantes :

utilisation de piles pour gérer les données locales des processus ; l'architecture de la machine comportait des instructions de gestion de pile ;
mémoire virtuelle segmentée ;
allocation dynamique de mémoire par demande de segment ;
système écrit en langage évolué (Algol 60).

1961 vit les débuts du projet MAC dirigé par Fernando Corbató au MIT, et dans ce cadre la réalisation du système CTSS (Compatible Time Sharing System), ancêtre de Multics, sur ordinateur IBM 709 puis 7094 . CTSS comportait un système de swap, qui recopiait sur mémoire auxiliaire les programmes mis en attente par le système au profit de programmes réactivés et rechargés depuis la mémoire auxiliaire vers la mémoire vive. Ce système de swap, qui peut être considéré comme la mémoire virtuelle du pauvre, se retrouve sur le PDP-1 de Digital mis au point en 1962 pour BBN (Bolt, Baranek & Newman), un nom que nous retouverons au chapitre consacré aux réseaux, puis sur beaucoup de machines de la gamme PDP.

En 1963 la société française SEA dirigée par F.H. Raymond réalisait pour sa machine CAB 1500 un système qui reposait sur des principes différents, les noms généralisés.

En 1967 IBM réalise le modèle 360/67, qui était un 360/65 doté des dispositifs de mémoire virtuelle que nous avons décrits plus haut, avec des pages de 4 096 octets et en outre un dispositif logiciel que l'on pourrait appeler hyperviseur, CP/67, que nous évoquerons au chapitre 10, qui permettait de simuler le fonctionnement de plusieurs ordinateurs virtuels dotés chacun de son système.

En 1972 IBM généralise la mémoire virtuelle sur sa gamme 370.

4.5 Hiérarchie de mémoire

4.5.1 Position du problème

La recherche d'informations dans des espaces de mémoire très vastes nous a amenés à poser des questions de performance : parcourir séquentiellement une table pour y chercher une information quelconque demande l'exécution d'un nombre d'instructions proportionnel à la longueur de la table. Dès que cette table devient longue il faut trouver une solution plus subtile. C'est un problème très fréquent en programmation.

Un schéma très général de solution possible, inspiré d'ailleurs des méthodes exposées ci-dessus, est le suivant : si dans cette table figurent d'une part une petite minorité d'informations très souvent utilisées et de l'autre une majorité d'informations rarement utilisées, et que nous disposions d'un moyen d'identifier la petite minorité active de notre stock d'information (le « working set »), il serait alors possible de réaliser deux versions de la table : une petite table pour le working set, d'accès rapide parce que petite, et la grande table complète, peu rapide d'accès mais rarement utilisée. Lors d'une recherche on lancera simultanément la consultation dans les deux tables, et que le meilleur gagne : si l'information cherchée est dans la petite table, c'est elle qui « gagnera » (sauf si le résultat est au début de la grande table), sinon on fera la recherche longue dans la grande table. C'est l'idée de la hiérarchie de mémoires, une mémoire petite et rapide en avant--plan d'une mémoire vaste, plus lente mais complète.

Notre problème est un peu plus complexe : la composition du working set varie dans le temps, une information très utile à un instant va devenir inutile quelques microsecondes plus tard, cependant que d'autres informations vont sortir de l'ombre pour occuper le devant de la scène. Il nous faudra disposer d'un algorithme de remplacement des informations vieillies par de nouvelles vedettes. Remarquons que cette idée de working set se marie bien avec la constatation notée plus haut de la localité des traitements.

Le chapitre 2 nous a déjà procuré un tel exemple, un peu particulier, de hiérarchie de mémoire : les registres du processeur ne sont rien d'autre que des cases de mémoire incorporées à l'unité centrale pour pouvoir être atteintes et modifiées plus rapidement. Les sections précédentes nous ont permis d'en voir deux autres exemples :

l'organisation de la mémoire virtuelle vise à ne maintenir en mémoire réelle que les pages actives à un instant donné, (le working set) et à reléguer en mémoire auxiliaire les pages inactives ;
le TLB conserve dans une toute petite table les traductions des adresses en cours d'usage, ce qui satisfait plus de 99% des demandes de traduction.

Le cas du TLB est spectaculaire parce que le rapport entre le nombre d'adresses virtuelles possibles et le nombre de celles qu'il conserve est énorme : pour un processeur 32 bits (quasiment une antiquité...) chaque espace adresse comporte 2²⁰ pages de 4 096 octets et le TLB en indexe 64 = 2⁶, soit si nous avons à un instant donné 20 espaces adresse actifs (valeur très modeste) une sur 20 × 16 384 = 327 680, et il résout néanmoins plus de 99% des défauts de pages.

4.6 La technique du cache

Le mot cache, curieux retour au français d'un emprunt anglais, suggère ici l'idée de cacher dans un coin pour avoir sous la main une chose que l'on ne veut pas avoir à aller chercher à la cave ou au grenier, pour gagner du temps. À moins qu'il ne s'agisse de l'image de la chose, au premier plan d'une scène, qui cache la chose elle-même, à l'arrière-plan.

4.6.1 Cache mémoire

Les processeurs modernes utilisent la technique du cache pour les accès à la mémoire. De quoi s'agit-il ?

Figure 4.3 : Hiérarchie de mémoire d'Itanium

Supposons que l'accès du processeur à la mémoire par le bus système se fasse en un temps t. Une petite quantité de mémoire très rapide va être implantée sur le processeur proprement dit, ce sera le cache de premier niveau (L1, pour Level 1) qui aura un temps d'accès de t/40 (habituellement un ou deux cycles de processeur, soit de l'ordre de la nano-seconde). Puis une quantité un peu moins petite de mémoire un peu moins rapide va être connectée au bus interne du processeur, avec un temps d'accès, par exemple, de t/10. Ce sera le cache de niveau 2, L2, avec un débit d'accès de quelques milliards d'octets par seconde. Les ratios de temps d'accès indiqués ici sont des ordres de grandeur, mais vraisemblables à la fin de l'an 2002.

Le cache L1 d'Itanium, représenté par la figure 4.3, contient 32K de mémoire (16K pour les données, 16K pour les instructions) avec un délai d'accès (temps de latence) de 2 cycles, son cache L2, qui est sur le même circuit (la même puce) que le processeur, 92K avec un accès en 6 cycles, et il a un cache externe L3 de 4 mébioctets avec un accès en 21 cycles.

L'accès à la mémoire principale se fait à un débit de de 2,1 gibioctets⁷ par seconde par un bus à 133 Mhz.

4.6.2 Mise en oeuvre du cache

Comment seront utilisés ces caches ? Leur utilité repose sur la localité des traitements : on a observé qu'à une échelle de temps petite pour l'observateur mais grande par rapport à la vitesse du processeur, disons pendant l'exécution d'un sous--programme moyen, le processeur accède toujours à peu près aux mêmes zones de la mémoire. Donc si on charge ces zones dans le cache on va accélérer les traitements.

L'algorithme de gestion du cache consiste à y charger toute zone de mémoire demandée par le processeur à la place de la zone la moins récemment utilisée de celles qui étaient déjà là, en spéculant sur le fait que si cette zone est demandée maintenant elle va l'être souvent (des milliers de fois) dans les instants qui suivent (quelques milli-secondes). La partie plus compliquée de l'algorithme consiste à maintenir la cohérence entre les caches et la mémoire principale par la réécriture des zones modifiées dans le cache. Le lecteur trouvera dans le livre de Hennessy et Patterson [28] toutes informations souhaitables sur ce mécanisme de hiérarchisation de la mémoire. S'il est soucieux de se tenir au courant des derniers développements techniques il devra s'abonner à l'excellente revue Microprocessor Report [46]. Deux choses importantes doivent être retenues à propos de la technique du cache : elle procure des augmentations de performances très spectaculaires, et aucun modèle général satisfaisant de son fonctionnement n'a pu être proposé à ce jour.

4.7 Langage et mémoire

Le système d'exploitation alloue à chaque programme l'espace de mémoire nécessaire à son exécution. Comment se présente cet espace, du point de vue du programme ? Cela dépend du programme, et singulièrement du langage de programmation utilisé, ou plus exactement du traducteur. Mais auparavant il n'aura sans doute pas été inutile de se remémorer les développements page ?? sur la notion de sous-programme, qui permet de découper un grand programme en entités plus maniables.

4.7.1 Langages à mémoire statique

Le cas le plus simple est celui des langages à gestion de mémoire statique comme Fortran (nous parlons du Fortran IV traditionnel ou de son successeur Fortran 77, pas du langage au baroquisme ébouriffant qui porte aujourd'hui ce nom), pour les programmes desquels la mémoire est allouée une fois pour toutes au lancement du programme. Le texte du programme en langage machine et les variables sont à des emplacements fixes et ne sont pas extensibles, c'est-à-dire que tous les noms présents dans le programme sont associés (liés) à des emplacements de mémoire lors de la compilation. Le compilateur construit l'image binaire du programme traduit et de ses zones de données, l'éditeur de liens assemble les différents sous-programmes sans oublier les sous-programmes de bibliothèque en effectuant les translations appropriées (voir à la page ??), et le résultat est un fichier binaire exécutable prêt à être chargé en mémoire pour s'exécuter.

De cette politique d'allocation de mémoire il résulte que les variables locales d'un sous-programme sont au même endroit à chaque activation du sous-programme.

Cette technique d'allocation a trois inconvénients :

la taille de chaque structure de donnée doit être connue une fois pour toutes à la compilation et elle ne pourra plus varier pendant l'exécution ;
les sous-programmes ne peuvent pas s'appeler eux-mêmes (ce que l'on appelle récursion) parce que les objets locaux pour chaque activation partageraient les mêmes emplacements de mémoire ;
il n'est pas possible de créer des objets dynamiquement à l'exécution.

et elle a deux avantages :

les programmes écrits dans des langages statiques peuvent être rapides, parce qu'ils ne nécessitent pas de création de structures de données pendant l'exécution, et parce que l'emplacement fixe des objets permet l'usage de l'adressage direct, plus efficace que l'adressage indirect ;
un programme à mémoire statique est par construction à l'abri de l'échec par pénurie de mémoire en cours d'exécution.

4.7.2 Vecteur d'état d'un programme

Tout sous-programme s'exécute dans un contexte⁸ qui comporte au moins les informations que nous avons mentionnées ci-dessus à la page ?? : l'adresse de la liste (éventuellement vide) des arguments que lui aura transmis le programme appelant, l'adresse de retour à laquelle il devra effectuer un branchement quand il se sera terminé, l'adresse où déposer le résultat de son exécution. Il faut y ajouter les variables internes (locales) au sous-programme. Ces éléments de contexte constituent ce que nous appellerons vecteur d'état du (sous-)programme, et il s'agit donc d'une (petite) collection de mots.

4.7.3 Langages à mémoire dynamique

Tous les langages ne sont pas, tel Fortran IV, confinés à une mémoire statique. Les systèmes d'exploitation proposent depuis des lustres des mécanismes et des appels système qui permettent à un processus d'acquérir une zone de mémoire supplémentaire, et les langages en font usage pour surmonter les limitations mentionnées à la section 4.7.1.

Il y a deux grandes catégories de méthodes pour allouer de la mémoire supplémentaire dynamiquement à un programme lors de son exécution : sur la pile et dans le tas. La plupart des langages modernes utilisent les deux :

on utilise généralement la pile pour les données qui tiennent dans un mot (nombre, adresse, pointeur...) ou peu de mots, doivent être traitées rapidement (liste d'arguments d'un sous-programme), et qui en outre ne doivent pas avoir une durée de vie qui excède la terminaison de l'exécution courante du sous-programme ;
le tas est utilisé pour les données de taille quelconque et éventuellement variable (tableau, chaîne de caractères, liste...), ainsi que pour les données qui doivent survivre au sous-programme courant.

Nous allons examiner ces deux techniques. Mais ne perdons pas de vue qu'il s'agit toujours d'allouer de la mémoire disponible dans l'espace adresse du processus : quand cet espace-adresse sera saturé, les tentatives d'allocation déclencheront des erreurs.

Allocation de mémoire sur la pile

Dans un langage à gestion de mémoire dynamique, le système, pour chaque appel de sous-programme, crée un vecteur d'état (activation record, ou activation frame en anglais ; il contient, rappelons-le, les arguments passés par le programme appelant, l'adresse de retour, l'adresse du résultat éventuel, et les variables locales), et le détruit lorsque la procédure se termine.

Pour réaliser cela le compilateur utilise une structure de données appelée pile (en anglais stack) : les vecteurs d'état successifs, au fur et à mesure de leur création, vont être empilés comme des assiettes, puis dépilés au fur et à mesure de la terminaison des sous-programmes correspondants. À chaque instant un pointeur permet de connaître le sommet de la pile, qui correspond au sous-programme actif à cet instant.

Pour empiler un vecteur c'est simple : on place les mots de mémoire qui le constituent dans la zone qui commence à l'adresse immédiatement supérieure à la valeur courante du pointeur de pile, puis on additionne à celui-ci la taille du nouveau contexte afin qu'il pointe bien sur le sommet de la pile.

Pour dépiler un vecteur c'est encore plus simple, il suffit de soustraire du pointeur de pile la taille du vecteur à supprimer. En général, le résultat renvoyé par un sous-programme qui se termine aura été placé dans la pile, à un endroit convenu du vecteur d'état du programme appelant, c'est-à-dire « en dessous » du vecteur courant.

Pourquoi se compliquer la vie à faire tout cela, qui prend du temps, diront les adeptes de Fortran, les physiciens ? Pour avoir une organisation plus fine et plus sûre de l'information, pour faciliter le travail du programmeur et lui éviter des risques d'erreur, notamment par les traits suivants :

Différentes activations d'un sous-programme peuvent coexister, avec chacune son vecteur d'état distinct, ce qui permet notamment à un sous-programme d'être récursif, c'est-à-dire de s'appeler lui-même.
La taille d'une structure de données locale peut dépendre des arguments passés au sous-programme.
Les valeurs, associées aux noms locaux, contenues dans le vecteur d'état stocké sur la pile, sont détruites à la fin de l'activation, ce qui élimine une cause d'erreur de programmation.
Le vecteur d'état d'un sous-programme appelé ne peut plus exister après la terminaison de l'appelant.

Allocation de mémoire sur le tas

La plupart des systèmes offrent un appel système pour obtenir une allocation de mémoire, d'une taille quelconque déterminée par le programme à l'exécution, prise parmi les pages disponibles de l'espace adresse du processus. Pour l'OS 360 il s'agit de GETMAIN, pour UNIX de brk(), plus connu sous son habillage grand public malloc(). La mémoire demandée est prise dans une zone de l'espace adresse du processus appelée le tas(heap), par opposition à la pile et le système renvoie au programme un pointeur sur la zone allouée, qui, lui, réside généralement dans la pile.

L'assembleur et les langages de bas niveau comme C et C++ utilisent des fonctions explicites comme malloc() pour obtenir de la mémoire dans le tas et lui faire correspondre les structures de données que le programmeur veut y placer, cependant que des langages dotés d'un plus haut niveau d'abstraction font ce travail en coulisse à l'insu du programmeur. Les cadres de pages ne sont effectivement affectés au processus que lorsque celui-ci génère une exception en essayant d'accéder à l'une de leurs adresses virtuelles.

Si l'allocation est explicite, la libération doit l'être aussi : imaginons un sous-programme appelé dans une boucle et qui à chacune de ses exécutions demande une allocation de mémoire dans le tas ; le pointeur qui permet d'y accéder est sur la pile et il sera donc libéré à chaque terminaison, mais il n'en va pas de même pour la mémoire obtenue sur le tas, dont rien ne permet de justifier la libération si le programme ne fait pas appel explicitement à la fonction free(), qui remet le pointeur de début de la mémoire libre à sa valeur antérieure. Et il est parfois difficile de savoir s'il est légitime de le faire.

En effet dans un programme complexe plusieurs sous-programmes peuvent faire référence à la même zone de mémoire allouée. Imaginons un sous-programme qui obtient une zone de mémoire, y place des données et renvoie comme résultat à l'appelant, en se terminant, la valeur du pointeur sur cette zone : le pointeur sur la zone obtenu initialement était sur la pile et disparaît avec le sous-programme, mais l'appelant en a récupéré la valeur, qu'il peut alors passer en argument à de nombreux autres sous-programmes, ce qui fait qu'à un instant donné un nombre indéterminé de sous-programmes possèdent dans leur vecteur d'état un pointeur sur cette zone dynamique. Quand pourra-t-on la libérer ? Quand plus aucun pointeur actif n'y fera référence. Comment le saura-t-on ? C'est un problème difficile, dépourvu de solution simple, pour lequel existent plusieurs algorithmes heuristiques.

Gestion de la mémoire dynamique

Les langages évolués contemporains peuvent au bout du compte être classés en deux catégories : les langages à gestion de mémoire explicite comme C, C++, Pascal, où le programmeur est responsable de l'allocation et de la libération des zones de mémoire obtenues dynamiquement sur le tas, et les langages à gestion de mémoire automatique, comme Lisp, Smalltalk, Scheme, Caml ou Java, où la mémoire est allouée implicitement quand la création d'un objet le nécessite. Les langages de la seconde catégorie mettent en oeuvre un algorithme heuristique de libération des zones de mémoire allouées et devenues inutiles ; ces algorithmes sont connus sous le nom de ramasse-miettes, ou glaneur de cellules (garbage collector), en abrégé GC ; ils s'exécutent périodiquement, de manière asynchrone par rapport au programme lui-même. Il existe une réalisation de Scheme pour Macintosh, MacGambit, qui offre au programmeur une présentation visuelle très suggestive du déclenchement et de l'exécution du GC.

Signalons le cas intéressant du langage Ada, dont toute la logique interne suggère la présence d'un GC, prévu d'ailleurs par les concepteurs, mais le langage a trouvé son public dans la communauté du temps réel, c'est-à-dire des ingénieurs qui écrivent des systèmes pour piloter Ariane V ; les auteurs de tels systèmes sont très rétifs à l'idée du déclenchement asynchrone du GC, par exemple au moment de la mise à feu du second étage de la fusée lanceuse. Cette réticence a toujours retenu les auteurs et réalisateurs d'Ada, qui n'a jamais eu de GC mais à la place la procédure générique UNCHECKED_DEALLOCATION, ce qui veut tout dire.

Les langages à gestion de mémoire explicite (C, C++) sont des langages de bas niveau, qui donnent au programmeur le contrôle d'objets très proches du matériel, en l'occurrence des pointeurs qui sont en fait des adresses mémoire. Ce contrôle est indispensable pour écrire des systèmes d'exploitation, des pilotes de périphérique, des programmes très dépendants du matériel. Mais pour écrire des programmes de résolution de systèmes d'équations, de comparaison de séquences d'ADN ou de construction d'arbres généalogiques, cela ne se situe pas au niveau d'abstraction approprié et oblige le programmeur (qui est peut-être un mathématicien, un biologiste ou un généalogiste) à acquérir des compétences dont un langage mieux adapté devrait le dispenser, d'autant plus que l'expérience tend à montrer que ces compétences sont acquises incomplètement et que la maîtrise des programmes qui en résulte est approximative.

Les langages à GC comme Scheme ou Java sont des langages plus abstraits (par rapport au réel, l'ordinateur) et de ce fait plus expressifs et plus utilisables pour des tâches moins tournées vers le système d'exploitation. L'argument de la performance est régulièrement avancé en faveur des langages à gestion de mémoire explicite : outre que cet argument est loin d'être prouvé, il apparaît que les deux langages qui ont eu, et de loin, le plus de succès au cours des cinq dernières années du second millénaire sont Java et Perl, deux langages connus pour leur grande lenteur, ce qui montre que la rapidité n'a, la plupart du temps, aucune importance avec les processeurs actuels.

1: Les instructions des processeurs RISC de l'an 2002 sont de longueur fixe et occupent chacune un mot, ce qui simplifie la conception de beaucoup de composants du processeur et du système. Les grands systèmes IBM (l'architecture 360 et sa postérité) ont des instructions sur un demi-mot, un mot ou un mot et demi. Sur le processeur Itanium (architecture IA-64) trois instructions de 41 bits et un masque de 5 bits se partagent un double mot. Voir le chapitre 9 pour plus de détails.
2: Notre programme d'exemple avait un jeu d'instructions autorisant la présence d'adresses directement dans les instructions, ce qui n'est plus le cas des architectures récentes, où les adresses sont manipulées dans les registres.
3: En réalité XA est un adressage sur 31 bits ; pour éviter les conflits trop graves avec les anciens programmes, on conserve les adresses traditionnelles sur 24 bits et on dégage 2³¹ octets adressables nouveaux en utilisant des adresses « négatives » (voir l'annexe A pour la représentation des nombres binaires négatifs, qui explique cet artifice).
4: Je voudrais en profiter pour réhabiliter aussi consistant, qui n'est pas la traduction française de consistent, laquelle est « cohérent ». L'inconvénient de ces confusions est la perte de signifiés. La consistance et la translation sont des concepts intéressants et utiles, menacés de disparition par extinction (usurpation ?) de leurs signifiants. Si aujourd'hui dans un milieu mathématique vous vous risquez à ne pas employer consistant où il faudrait cohérent, au mieux vous ne vous ferez pas comprendre, et vous serez soupçonné de ne pas être un habitué des conférences anglo-saxonnes.
5: Malgré les avantages qu'elle apporte, la mémoire virtuelle n'a pas eu que des afficionados. Seymour Cray, qui fut le concepteur des ordinateurs les plus puissants du XXe siècle, de 1957 à 1972 pour Control Data Corporation , puis jusqu'à sa mort en 1996 pour Cray Research, a dit : « La mémoire, c'est comme le sexe : c'est meilleur quand c'est réel. »
6: La taille de la mémoire, principale ou auxiliaire, est exprimée en multiples de 1 024 octets naguère nommés k, pour kilo-octet, avec des multiples comme le méga-octet, le giga-octet, etc. Cette dénomination avait l'inconvénient de créer une confusion avec les multiples de 1 000 utilisés dans le cadre du Système International. Une norme internationale promulguée par la Commission Internationale d'Électrotechnique (IEC) y a mis bon ordre en décembre 1998. Désormais k désigne 10³ tandis que Ki (le « kibi ») désigne 2¹⁰=1 024, Mi (le mébi) désigne 2²⁰=1 048 576, Gi (le gibi) 2³⁰=1 073 741 824. Si l'on compte en bits on aura un kibibit (1 024 bits, 1 Kib), un mébibit (1 Mib) (1 048 576 bits). Ces préfixes s'appliquent aux octets, soit en anglais où octet se dit byte et où un mebibyte (1 MiB) vaut 1 048 576 octets, soit en français où un gibioctet (1 Gio) vaut 1 073 741 824 octets. Ces nombres bizarres sont des puissances de 2. On consultera avec profit à ce sujet le site http://physics.nist.gov/cuu/Units/binary.html.
7: Voir note 4.4.6.
8: Le contexte que nous envisageons ici est celui du programme vu comme la description d'un traitement. Il est distinct du contexte du programme vu comme processus que nous avons évoqué aux section 3.11.1 et 3.11.2. Le contexte du programme est créé et utilisé selon la logique du déroulement du traitement, dans l'espace adresse de l'utilisateur, cependant que le processus peut être interrompu à tout moment par un événement extérieur, asynchrone et sans respect pour le traitement en cours. La restauration du contexte du processus, qui comporte notamment les contenus du PSW et des registres, permet évidemment de retrouver le contexte du programme qui réside dans son espace adresse.