Fonctionnement d'un ordinateur/La mémoire virtuelle

Un programme peut être exécuté sur des ordinateurs ayant des capacités mémoires diverses et variées et dans des conditions très différentes. Et il faut faire en sorte qu'un programme fonctionne sur des ordinateur ayant peu de mémoire sans poser problème. Après tout, quand on conçoit un programme, on ne sait pas toujours quelle sera la quantité mémoire que notre ordinateur contiendra, et encore moins comment celle-ci sera partagée entre nos différentes programmes en cours d’exécution : s'affranchir de limitations sur la quantité de mémoire disponible est un plus vraiment appréciable. Ce besoin est appelé l'abstraction matérielle de la mémoire.

Enfin, plusieurs programmes sont présents en même temps dans notre ordinateur, et doivent se partager la mémoire physique. Si un programme pouvait modifier les données d'un autre programme, on se retrouverait rapidement avec une situation non prévue par le programmeur. Cela a des conséquences qui vont de comiques à catastrophiques, et cela fini très souvent par un joli plantage. Il faut donc introduire des mécanismes de protection mémoire. Pour éviter cela, chaque programme a accès à des portions de la mémoire dans laquelle lui seul peut écrire ou lire. Le reste de la mémoire est inaccessible en lecture et en écriture, à part pour la mémoire partagée entre différents programmes. Toute tentative d'accès à une partie de la mémoire non autorisée déclenchera une exception matérielle (rappelez-vous le chapitre sur les interruptions) qui devra être traitée par une routine du système d'exploitation. Généralement, le programme fautif est sauvagement arrêté et un message d'erreur est affiché à l'écran.

Ces détails concernant l'organisation et la gestion de la mémoire sont assez compliqués à gérer, et faire en sorte que les programmes applicatifs n'aient pas à s'en soucier est un plus vraiment appréciable. Ce genre de problèmes a eu des solutions purement logicielles, mais quelques techniques règlent ces problèmes directement au niveau du matériel : on parle de mémoire virtuelle. Avec la mémoire virtuelle, tout se passe comme si notre programme était seul au monde et pouvait lire et écrire à toutes les adresses disponibles à partir de l'adresse zéro. Chaque programme a accès à autant d'adresses que ce que le processeur peut adresser : on se moque du fait que des adresses soient réservées aux périphériques, de la quantité de mémoire réellement installée sur l'ordinateur, ou de la mémoire prise par d'autres programmes en cours d’exécution. Pour éviter que ce surplus de fausse mémoire pose problème, on utilise une partie des mémoires de masse (disques durs) d'un ordinateur en remplacement de la mémoire physique manquante.

Mémoire virtuelle
Les périphériques peuvent eux aussi utiliser la mémoire virtuelle. Dans ce cas, ceux-ci intègrent une MMU dans leurs circuits. Ces MMU, aussi appelées IOMMU, sont séparées de la MMU du processeur.

Bien sûr, les adresses de la fausse mémoire vue par le programme sont des adresses fictives, qui devront être traduites en adresses mémoires réelles pour être utilisées. Les fausses adresses sont ce qu'on appelle des adresses logiques, alors que les adresses réelles sont appelées adresses physiques. Pour implémenter cette technique, il faut rajouter un circuit qui traduit les adresses logiques en adresses physiques : ce circuit est appelé la memory management unit. Il faut préciser qu'il existe différentes méthodes pour gérer ces adresses logiques et les transformer en adresses physiques : les principales sont la segmentation et la pagination. La suite du chapitre va détailler ces deux techniques.

Le bank switchingModifier

 
Exemple de Bank switching.

Le bank switching, aussi appelé commutation de banque, permet d'utiliser un bus d'adresse plus grand que les adresses du processeur. L'adresse réelle est plus grande que l'adresse utilisée par le processeur, les bits manquants étant fournit par un registre configurable du processeur : le registre de banque. L'espace mémoire du processeur est présent en plusieurs exemplaires, sélectionnés par la valeur du registre de banque. Chaque exemplaire de l'ensemble des adresses du processeur s'appelle une banque. On peut changer de banque en changeant le contenu de ce registre : le processeur dispose souvent d'instructions spécialisées qui en sont capables.

En répartissant les données utiles dans différentes banques, le processeur peut donc adresser beaucoup plus de mémoire. De plus, cette technique se marie assez bien avec les entrées-sorties mappées en mémoire. Par exemple, supposons que j'ai besoin d'adresser une mémoire ROM de 4 kibioctets, une RAM de 8 kibioctets, et divers périphériques. Le processeur a un bus d'adresse de 12 bits, ce qui limite à 4kibioctets. Dans ce cas, je peux réserver 4 banques : une pour la ROM, une pour les périphériques, et deux banques qui contiennent chacune la moitié de la RAM. La simplicité et l'efficacité de cette technique font qu'elle est beaucoup utilisée dans l'informatique embarquée.

   

La segmentationModifier

 
Segments typiques des programmes sur OS modernes.

Sur les vieux systèmes d'exploitation, chaque programme recevait un bloc de RAM pour lui tout seul, une partition mémoire. La segmentation est une amélioration de cette technique, qui affecte une ou plusieurs partitions par programme. Cela permet à un seul processus d'avoir plusieurs espaces d'adressages, plusieurs mémoires virtuelles à lui tout seul. L'utilité est qu'un programme est rarement un tout unique, mais peut souvent être décomposé en plusieurs ensembles de données/instructions séparés, qui peuvent grossir ou se réduire suivant les circonstances. Par exemple, la pile a une taille qui varie beaucoup, tandis que le code du programme ne change pas. La segmentation permet de découper la mémoire virtuelle d'un processus en sous-partitions de taille variable qu'on appelle improprement des segments. Ainsi, un programme peut utiliser des segments différents pour la pile, le tas, le programme lui-même, et les variables globales. Chaque segment pourra grandir ou diminuer à sa guise, suivant les besoins, ce qui serait beaucoup plus difficile avec une seule partition mémoire.

La relocation avec la segmentationModifier

Chaque segment peut être placé n'importe où en mémoire physique par l'OS, ce qui fait qu'il n'a pas d'adresse fixée en mémoire physique et peut être déplacé comme bon nous semble. C'est le système d'exploitation qui gère le placement des partitions/segments dans la mémoire physique. Ainsi, les adresses de destination des branchements et les adresses des données ne sont jamais les mêmes. Il faut donc trouver un moyen pour que les programmes fonctionnent avec des adresses qui changent d'une exécution à l'autre. Ce besoin est appelé la relocalisation. Pour résoudre ce problème, le compilateur considère que le programme commence à l'adresse zéro et laisse l'OS corriger les adresses du programme. Cette correction d'adresse demande simplement d'ajouter un décalage, égal à la première adresse de la partition mémoire. Cette correction peut se faire de deux manières : soit l'OS corrige chaque adresse lors du lancement du programme, soit le processeur s'en charge à chaque accès mémoire. Nous allons étudier le cas où le processeur s'en charge de lui-même, en étant aidé par le système d'exploitation.

 
Segmentation et relocation.

Pour gérer correctement la relocation, le système d'exploitation doit mémoriser l'adresse de base pour chaque segment. Pour cela, l'OS associe chaque segment à son adresse de base dans une table de correspondance, appelée la table des segments. Elle est unique pour chaque programme : la même adresse logique ne donnera pas la même adresse physique selon le programme. La table des segments est un tableau, indexé par un indice, un numéro qui donne la position du segment dans le tableau. C'est en quelque sorte le numéro du segment dans la table des segments.

L'adresse manipulée par le processeur est découpée en deux partie : un sélecteur de segment qui identifie le segment voulu par son indice dans la table des segments, et un décalage (offset) qui donne la position de la donnée dans ce segment. La relocalisation se fait de la même manière pour un segment que pour une partition mémoire. La traduction de l'adresse demande d'accéder à la table des segments, pour récupérer l'adresse de base, avant d'additionner l'offset. Pour cela, le processeur prend le sélecteur de segment, l'utilise pour calculer l'adresse adéquate dans la table des segment, lit l'adresse de base, et fait l'addition. Le tout est représenté dans le schéma ci-dessous.

 
Traduction d'adresse.

Pour rappel, la table des segments est censée être en mémoire RAM. Ce qui fait qu'accéder à la table des segments pour chaque accès mémoire est lent : chaque accès mémoire demande d'en faire deux : un pour lire la table des segments, l'autre pour l'accès lui-même. Pour éviter cela, diverses techniques ont été inventées. Une première solution consiste à charger la table de correspondance complète dans un banc de registre dédié. Elle marche très bien si le nombre de segments est limité et que le processeur gère quelques dizaines ou centaines de segments tout au plus. Autant dire qu'elle est peut utilisée.

 
Table des segments dans un banc de registres.

Une autre solution permet au programmeur de préciser quel est le segment en cours d'utilisation. En clair, le système d'exploitation ou le programmeur précise au processeur qu'il est en train d’accéder uniquement à ce segment, et tous les futurs accès mémoire se feront à celui-ci. En clair, cette solution utilise un registre de base, mis à jour automatiquement lors de chaque changement de programme. Il est possible de changer de segment à tout instant, en utilisant une instruction processeur dédiée. En faisant cela, on peut mémoriser dans un registre l'adresse de base du segment en cours d'utilisation. La table des segments est stockée en mémoire RAM, mais le processeur ne contient qu'un registre de base, rien de plus. Le programmeur ou le système d'exploitation se chargent de mettre à jour ce registre à chaque changement de segment. Typiquement, le registre de segment est adressé implicitement et le processeur dispose d'une instruction dédié pour changer de segment. Si ce n'est pas le cas, il est possible d'écrire dans ce registre de segment, qui est alors adressable.

 
Registre de base de segment.

La protection mémoire avec la segmentationModifier

Un programme ne doit avoir accès qu'à la partition qui lui est dédiée et pas aux autres, sauf dans quelques rares exceptions. Toute tentative d'accès à une autre partition doit déclencher une exception matérielle, qui entraîne souvent l'apparition d'un message d'erreur. Tout cela est pris en charge par le système d'exploitation, par l'intermédiaire de mécanismes de protection mémoire, que nous allons maintenant aborder.

Pour commencer, le processeur (ou l'OS) doivent détecter les accès hors-partition, à savoir un programme qui lit/écrit de la mémoire au-delà de la partition qui lui réservée. La solution est de mémoriser les limites du segment dans la page des segments et de vérifier que les accès mémoire ne se font pas au-delà de cette limite. L'adresse de fin de segment est mémorisée dans la table des segments et est récupérée lors de chaque accès. Le processeur vérifie si l'accès se fait dans les clou, en comparant l'adresse accédée avec l'adresse limite. Une autre solution consiste à mémoriser non pas l'adresse, mais l'offset maximal possible dans le segment en cours. Cela économise quelques bits par entrée dans la table des tables. Voici comment se passe la traduction d'une adresse avec la segmentation, en tenant compte de la vérification des accès hors-segment.

 
Traduction d'adresse avec vérification des accès hors-segment.

Vient ensuite la gestion des droits d'accès : chaque partition/segment se voit attribuer un certain nombre d'autorisations d'accès qui indiquent si l'on peut lire ou écrire dedans, si celui-ci contient un programme exécutable, etc. Par exemple, il est possible d'interdire d'exécuter quoique ce soit de localisé dans certains segments, ce qui fournit une protection contre certaines failles de sécurité ou certains virus. Lorsqu'on exécute une opération interdite, le processeur lève une exception matérielle, à charge du système d'exploitation de gérer la situation. L'OS ou la MMU mémorisent les autorisations pour chaque segment, qui sont rassemblées avec d'autres informations (registre de base et limite) dans un descripteur de segment. Pour se simplifier la tache, les concepteurs de processeurs et de systèmes d'exploitation ont décidé de regrouper ces descripteurs dans une portion de la mémoire, spécialement réservée pour l'occasion : la table des descripteurs de segment. Pour des raisons de performance, le processeur utilise un registre pour mémoriser le descripteur de segment du segment en cours d'utilisation. Quand on accède à un segment, son descripteur est chargé dans des registres du processeur, l'ancien est effacé.

 
Schéma d'un descripteur de segment sur une architecture x86.

Le partage de segmentsModifier

Il faut préciser qu'il est possible de partager des segments entre applications. Il suffit de configurer les tables de segment convenablement. Cela peut servir quand plusieurs instances d'une même applications sont lancés simultanément : le code n'ayant pas de raison de changer, celui-ci est partagé entre toutes les instance.

 
Illustration du partage d'un segment entre deux applications.

Il est aussi possible de faire en sorte que deux segments se recouvrent l'un autre, à savoir que les deux segments partagent la même mémoire physique. Cela peut servir à partager de la mémoire entre plusieurs applications qui doivent communiquer entre elles.

 
Recouvrement de segments.

L'implémentation de la segmentation sur les processeurs x86Modifier

La première implémentation de la segmentation été celle de l'Intel 8086, un des tout premiers processeurs 16 bits. Il s'agissait d'une forme très simple de segmentation, sans aucune forme de protection mémoire. Elle avait pour but de permettre d'utiliser plus de 64 kibioctets de mémoire, ce qui était la limite maximale sur les processeurs 16 bits de l'époque. L'Intel 8086 ajouta la segmentation de manière à adresser 1 mébioctet de RAM, ce qui donne des adresses de 20 bits. On peut voir cette méthode comme du bank switching amélioré. Par la suite, la segmentation s'améliora et ajouta un support complet de la mémoire virtuelle et de la protection mémoire. L'ancienne forme de segmentation fut alors appelé le mode réel, et la nouvelle forme de segmentation fut appelée le mode protégé.

Le mode réelModifier

Les processeurs 8086 utilisaient des registres de segment, pour mémoriser la base du segment, les adresses calculées par l'ALU étant des offsets. Il y a en tout quatre registres de segment : un pour le code, un autre pour les données, et un pour la pile, le quatrième étant un registre facultatif laissé à l'appréciation du programmeur. Ils sont nommés CS (code segment), DS (data segment), SS (Stack segment), et ES (Extra segment). Ce sont tous des registres de 16 bits. Vous pouvez vous demandez comment on peut obtenir des adresses de 20 bits alors que les registres de segments font tous les deux 16 bits. Cela tient à la manière dont sont calculées les adresses physiques. Le registre de segment n'est pas additionné tel quel avec l'offset : à la place, le registre de segment est décalé de 4 rangs vers la gauche.

  0000 0110 1110 11110000 Registre de segment - 16 bits, décalé de 4 bits vers la gauche
+      0001 0010 0011 0100 Offset 16 bits
  0000 1000 0001 0010 0100 Adresse finale 20 bits

Le décalage de 4 rangs vers la gauche fait que chaque segment a une adresse qui est multiple de 16. Le fait que l'offset soit de 16 bits fait que les segments ont une taille de 64 kibioctets. Ces deux caractéristiques font que deux segments peuvent se recouvrir partiellement. On peut par exemple prendre l'exemple de deux segments adjacents, séparés par 16 octets : ils partageront la plupart de leurs adresses (toutes, sauf 16). Et c'est là un problème avec cette méthode : une adresse physique peut correspondre à plusieurs couples (segment-offset), si les segments se recouvrent. Cela facilite le partage de segments entre deux applications ou à l'intérieur d'une application, mais cela pose des problèmes vu que la protection mémoire est inexistante.

La MMU des processeurs en mode réel était très simple. Elle consistait en un simple additionneur, couplé à un petit banc de registres pour les registres de segment. Sur le 80186, la MMU est fusionnée avec les circuits de gestion du program counter. Au lieu d'utiliser un additionneur séparé pour le program counter et un autre pour le calcul de l'adresse physique, un seul additionneur est utilisé pour les deux. Les registres de segment sont regroupés avec le program counter dans un même banc de registres. Les registres sont reliés au chemin de données, afin de gérer les branchements indirects, mais aussi afin de pouvoir altérer les registres de segment (pour changer de segment, par exemple). Notons que le tout est aussi fusionné avec les circuits de préchargement, que nous avions vu dans le chapitre sur l'unité de contrôle. En somme, il n'y a pas vraiment de MMU dédiée, mais un super-circuit en charge du Fetch et de la mémoire virtuelle, ainsi que du préchargement des instructions.

 
Architecture du 8086, du 80186 et de ses variantes.

Le mode protégéModifier

L'Intel 80286, aussi appelé 286, ajouta un second mode de segmentation, qui ajoute une protection mémoire à la segmentation, ce qui lui vaut le nom de mode protégé. Dans ce mode, les adresses physiques passent à 24 bits. Par contre, le calcul de l'adresse se fait autrement que sur le 8086. Cette fois-ci, on n'a pas un registre de base dont le contenu est décalé. A la place, les registres de segment mémorisent un pointeur vers la table des segments, qui pointe sur le descripteur de segment adéquat.

Le 286 était pensé pour être rétrocompatible au maximum avec le 80186. Par exemple, le 286 bootait en mode réel, puis le système d'exploitation devait faire quelques manipulations pour passer en mode protégé. Mais les choses n'étaient pas parfaites. Les différences entre le 286 et le 8086 étaient majeures au point que les applications devaient être réécrites intégralement pour profiter du mode protégé. Le mode de compatibilité permettait aux applications destinées au 8086 de fonctionner, avec même de meilleures performances. Aussi, le mode protégé resta inutilisé sur la plupart des applications exécutée sur le 286.

Le mode réel du 8086 avait une particularité : les adresses calculées ne dépassaient pas 20 bits. Si l'addition de la base du segment et de l'offset déborde, alors les bits au-delà du vingtième sont perdus. Dit autrement, le calcul de l'adresse physique utilise l'arithmétique modulaire sur le 8086. Mais le 80286 gère des adresses de 24 bits ! L'additionneur du 80286 ne gère pas les débordements comme un 8086 et calcule les bits en trop, au-delà du 20ème. En conséquence, les applications peuvent utiliser plus d'un mébioctet de RAM, mais au prix d'une rétrocompatibilité imparfaite. Pour résoudre ce problème, certains fabricants de carte mère mettaient à 0 le 20ème fil du bus d'adresse, quand le programmeur leur demandait. La carte mère avait un petit interrupteur qui pouvait être activé de manière à activer ou non la mise à 0 du 20ème bit d'adresse.

Vint ensuite le processeur 80386, renommé en 386 quelques années plus tard. Sur ce processeur, le mode protégé est conservé tel quel, à une différence près : toutes les adresses passent à 32 bits, qu'il s'agisse de l'adresse physique, de l'adresse de base du segment ou des offsets. De plus, le 80386 ajouta deux registres de segment, les registres FS et GS. De plus, un autre mode est ajouté : le mode virtual 8086. Il permet d’exécuter des programmes en mode réel, pendant que le système d'exploitation s’exécute en mode protégé. c'est une technique de virtualisation matérielle qui permet d'émuler un 8086 sur un 386. L'avantage est que la compatibilité avec les programmes anciens écrits pour le 8086 est conservée, tout en profitant de la protection mémoire. De plus, le 386 ajouta le support d'une autre technologie de mémoire virtuelle, en plus de la segmentation : la pagination. Nous allons voir celle-ci dans la section suivante.

La paginationModifier

De nos jours, la segmentation est obsolète et n'est plus utilisée : à la place, les OS et processeurs utilisent la pagination. Avec la pagination, la mémoire virtuelle et la mémoire physique sont découpées en blocs de taille fixe, appelés des pages mémoires. La différence avec les segments est que les segments sont de taille variable, alors que les pages sont de taille fixe. La taille des pages varie suivant le processeur et le système d'exploitation et tourne souvent autour de 4 kibioctets. Le contenu d'une page en mémoire fictive est rigoureusement le même que le contenu de la page correspondante en mémoire physique. Cependant, le nombre total de pages en mémoire virtuelle dépasse celui de la mémoire physique.

 
Principe de la pagination.

Le surnombre est simplement placé sur le disque dur, dans un fichier appelé le fichier d'échange. Les pages virtuelles vont ainsi faire référence soit à une page en mémoire physique, soit à une page sur le disque dur. Tout accès à une page sur le disque dur va charger celle-ci dans la mémoire RAM, dans une page vide. Les pages font ainsi une sorte de va et vient entre le fichier d'échange et la RAM, suivant les besoins.

 
Mémoire virtuelle paginée et fichier d'échange.
Pour information, le tout premier processeur avec un système de mémoire virtuelle était le super-ordinateur Atlas. Il utilisait la pagination, et non la segmentation. Mais il fallu du temps avant que la méthode de la pagination prenne son essor dans les processeurs commerciaux.

La traduction d'adresse avec la paginationModifier

La mémoire est donc découpée en pages de taille fixes, ce qui fait que la mémoire est découpée en un certain nombre de pages en mémoire. Il se trouve que les pages sont numérotées, de 0 à une valeur maximale, afin de les identifier. Le numéro en question est appelé le numéro de page. Il est utilisé pour dire au processeur : je veux lire une donnée dans la page numéro 20, la page numéro 90, etc. Une fois qu'on a le numéro de page, on doit alors préciser la position de la donnée dans la page, appelé le décalage, ou encore l'offset.

Le numéro de page et le décalage se déduisent à partir de l'adresse, en divisant l'adresse par la taille de la page. Le quotient obtenu donne le numéro de la page, alors que le reste est le décalage. Les processeurs actuels utilisent tous des pages dont la taille est une puissance de deux, ce qui fait que ce calcul est fortement simplifié. En effet, rappelons qu'une division par   est un simple décalage, alors que le reste de la division correspond au   bits de poids faible. Sous cette condition, le numéro de page correspond aux bits de poids fort de l'adresse, alors que le décalage est dans les bits de poids faible. La démarcation entre les deux est claire, et sa place varie suivant la taille de la mémoire virtuelle et de la taille des pages.

Le numéro de page existe en deux versions : un numéro de page physique, qui identifie une page en mémoire physique, et un numéro de page logique, qui identifie une page dans la mémoire virtuelle. Traduire l'adresse logique en adresse physique demande de remplacer le numéro de la page logique en un numéro de page physique.

 
Traduction d'adresse avec la pagination.

Pour faire cette traduction, il faut se souvenir des correspondances entre numéro de page et adresse de la page en mémoire fictive. Elles sont stockées dans une sorte de table, nommée la table des pages. Celle-ci contient aussi, pour chaque page, des bits qui encodent des informations sur la dite page. Ce peut être des bits pour gérer la protection mémoire, pour savoir si une page est swappée sur le disque dur ou si elle est présente en RAM, ou bien d'autres. La table des pages est généralement organisée en une suite consécutives d'entrées de la table des pages, chaque entrée mémorisant toute information/correspondance liée à une page (correspondances numéro de page - adresse et bits d'information annexes).

 
Table des pages.

La table des pages est unique pour chaque programme, vu que les correspondances entre adresses physiques et logiques ne sont pas les mêmes. Chaque programme lancé sur l'ordinateur dispose de son propre espace d'adressage, ce qui fait qu'il a sa propre table des page dédiée. Il y a une table des page par processus/programme lancé sur l'ordinateur, une table des pages unique par espace d'adressage. Bien sûr, il est possible que de la mémoire soit partagée entre plusieurs processus, ce qui implique des interactions entre tables des pages, mais pas de partage des tables en elles-mêmes.

 
Tables des pages de plusieurs processus.

Les tables des pages simplesModifier

Dans le cas le plus simple, il n'y a qu'une seule table des pages par programme, qui est adressée par les numéros de page logique. La table des pages est un vulgaire tableau d'adresses physiques, placées les unes à la suite des autres. Avec cette méthode, la table des pages a autant d'entrée qu'il y a de pages logiques en mémoire virtuelle. Accéder à la mémoire nécessite donc d’accéder d'abord à la table des pages en mémoire, de calculer l'adresse de l'entrée voulue, et d’y accéder. La table des pages est souvent stockée dans la mémoire RAM, son adresse est connue du processeur, mémorisée dans un registre spécialisé du processeur. Le processeur effectue automatiquement le calcul d'adresse à partir de l'adresse de base et du numéro de page logique.

 
Table des pages.

Les tables des pages inverséesModifier

Sur certains systèmes, la taille d'une table des pages serait beaucoup trop grande en utilisant les techniques vues au-dessus. C'est notamment le cas sur les architectures 64 bits ou plus, pour lesquelles le nombre de pages total est très important. Sur les ordinateurs x86 récents, les adresses sont en pratique de 48 bits, les bits de poids fort étant ignorés en pratique, ce qui fait en tout 68 719 476 736 pages. Chaque entrée de la table des pages fait au minimum 48 bits, mais fait plus en pratique : partons sur 64 bits par entrée, soit 8 octets. Cela fait 549 755 813 888 octets pour la table des pages, soit plusieurs centaines de gibioctets ! Une table des pages normale serait tout simplement impraticable.

Pour résoudre ce problème, on a inventé les tables des pages inversées. L'idée derrière celles-ci est l'inverse de la méthode précédente. La méthode précédente stocke, pour chaque page logique, son numéro de page physique. Les tables des pages inversées font l'inverse : elles stockent, pour chaque numéro de page physique, la page logique qui correspond. Avec cette méthode table des pages contient ainsi autant d'entrées qu'il y a de pages physiques. Elle est donc plus petite qu'avant, vu que la mémoire physique est plus petite que la mémoire virtuelle.

Quand le processeur veut convertir une adresse virtuelle en adresse physique, la MMU recherche le numéro de page de l'adresse virtuelle dans la table des pages. Le numéro de l'entrée à laquelle se trouve ce morceau d'adresse virtuelle est le morceau de l'adresse physique. Pour faciliter le processus de recherche dans la page, les concepteurs de systèmes d'exploitation peuvent stocker celle-ci avec ce que l'on appelle une table de hachage.

 
Table des pages inversée.

Les tables des pages multiples par espace d'adressageModifier

Dans les deux cas précédents, il y a une table des page par processus/programme lancé sur l'ordinateur, une table des pages unique par espace d'adressage. Cependant, les concepteurs de processeurs et de systèmes d'exploitation ont remarqué que les adresses les plus hautes et/ou les plus basses sont les plus utilisées, alors que les adresses situées au milieu de l'espace d'adressage sont peu utilisées en raison du fonctionnement de la pile et du tas. Il y a donc une partie de la table des pages qui ne sert à rien et est utilisé pour des adresses inutilisées. C'est une source d'économie d'autant plus importante que les tables des pages sont de plus en plus grosses. Pour profiter de cette observation, les concepteurs d'OS ont décidé de découper l'espace d'adressage en plusieurs sous-espaces d'adressage de taille identique : certains localisés dans les adresses basses, d'autres au milieu, d'autres tout en haut, etc. Et vu que l'espace d'adressage est scindé en plusieurs parties, la table des pages l'est aussi, ele est découpée en plusieurs sous-tables. Si un sous-espace d'adressage n'est pas utilisé, il n'y a pas besoin d'utiliser de la mémoire pour stocker la table des pages associée. On ne stocke que les tables des pages pour les espaces d'adressage utilisés, ceux qui contiennent au moins une donnée.

L'utilisation de plusieurs tables des page ne fonctionne que si le système d'exploitation connaît l'adresse de chaque table des pages (celle de la première entrée). Pour cela, le système d'exploitation utilise une super-table des pages, qui stocke les adresses de début des sous-tables de chaque sous-espace. En clair, la table des page est organisé en deux niveaux, la super-table étant le premier niveau et les sous-tables étant le second niveau. L'adresse est structurée de manière à tirer profit de cette organisation. Les bits de poids fort de l'adresse sélectionnent quelle table de second niveau utiliser, les bits du milieu de l'adresse sélectionne la page dans la table de second niveau et le reste est interprété comme un offset. Un accès à la table des pages se fait comme suit. Les bits de poids fort de l'adresse sont envoyé à la table de premier niveau, et sont utilisés pour récupérer l'adresse de la table de second niveau adéquate. Les bits au milieu de l'adresse sont envoyés à la table de second niveau, pour récupérer le numéro de page physique. Le tout est combiné avec l'offset pour obtenir l'adresse physique finale.

 
Table des pages hiérarchique.

On peut aussi aller plus loin et découper la table des pages de manière hiérarchique, chaque sous-espace d'adressage étant lui aussi découpé en sous-espaces d'adressages. On a alors une table de premier niveau, plusieurs tables de second niveau, encore plus de tables de troisième niveau, et ainsi de suite. Cela peut aller jusqu'à 5 niveaux sur les processeurs x86 64 bits modernes. Dans ce cours, la table des page désigne l'ensemble des différents niveaux de cette organisation, toute les tables inclues. Seules les tables du dernier niveau mémorisent des numéros de page physiques, les autres tables mémorisant des pointeurs, des adresses vers le début des tables de niveau inférieur. Un exemple sera donné plus bas, dans la section suivante.

L'exemple des processeurs x86Modifier

Pour rendre les explications précédentes plus concrètes, nous allons prendre l'exemple des processeur x86 anciens, de type 32 bits. Les processeurs de ce type utilisaient deux types de tables des pages : une table des page unique et une table des page hiérarchique. Les deux étaient utilisées dans cas séparés. La table des page unique était utilisée pour les pages larges et encore seulement en l'absence de la technologie physical adress extension, dont on parlera plus bas. Les autres cas utilisaient une table des page hiérarchique, à deux niveaux, trois niveaux, voire plus.

Une table des pages unique était utilisée pour les pages larges (de 2 mébioctets et plus). Pour les pages de 4 mébioctets, il y avait une unique table des pages, adressée par les 10 bits de poids fort de l'adresse, les bits restants servant comme offset. La table des pages contenait 1024 entrées de 4 octets chacune, ce qui fait en tout 4 kibioctet pour la table des pages. La table des page était alignée en mémoire sur un bloc de 4 kibioctet (sa taille).

 
X86 Paging 4M

Pour les pages de 4 kibioctets, les processeurs x86-32 bits utilisaient une table des page hiérarchique à deux niveaux. Les 10 bits de poids fort l'adresse adressaient la table des page maitre, appelée le directoire des pages (page directory), les 10 bits précédents servaient de numéro de page logique, et les 12 bits restants servaient à indiquer la position de l'octet dans la table des pages. Les entrées de chaque table des pages, mineure ou majeure, faisaient 32 bits, soit 4 octets. Vous remarquerez que la table des page majeure a la même taille que la table des page unique obtenue avec des pages larges (de 4 mébioctets).

 
X86 Paging 4K

La technique du physical adress extension (PAE), utilisée depuis le Pentium Pro, permettait aux processeurs x86 32 bits d'adresser plus de 4 gibioctets de mémoire, en utilisant des adresses physiques de 64 bits. Les adresses virtuelles de 32 bits étaient traduites en adresses physiques de 64 bits grâce à une table des pages adaptée. Cette technologie permettait d'adresser plus de 4 gibioctets de mémoire au total, mais avec quelques limitations. Notamment, chaque programme ne pouvait utiliser que 4 gibioctets de mémoire RAM pour lui seul. Mais en lançant plusieurs programmes, on pouvait dépasser les 4 gibioctets au total. Pour cela, les entrées de la table des pages passaient à 64 bits au lieu de 32 auparavant.

La table des pages gardait 2 niveaux pour les pages larges en PAE.

 
X86 Paging PAE 2M

Par contre, pour les pages de 4 kibioctets en PAE, elle était modifiée de manière à ajouter un niveau de hiérarchie, passant de deux niveaux à trois.

 
X86 Paging PAE 4K

En 64 bits, la table des pages est une table des page hiérarchique avec 5 niveaux. Seuls les 48 bits de poids faible des adresses sont utilisés, les 16 restants étant ignorés.

 
X86 Paging 64bit

Le remplacement des pages mémoiresModifier

La mémoire physique contient moins de pages que la mémoire virtuelle et il faut trouver un moyen pour que cela ne pose pas de problème. La solution consiste à utiliser des mémoires de stockage comme mémoire d'appoint : si on a besoin de plus de pages mémoires que la mémoire physique n'en contient, certaines pages mémoires vont être déplacées sur le disque dur pour faire de la place. Les pages sur le disque dur doivent être chargées en RAM, avant d'être utilisables. Lorsque l'on veut traduire l'adresse logique d'une page mémoire déplacée sur le disque dur, la MMU ne va pas pouvoir associer l'adresse logique à une adresse en mémoire RAM. Elle va alors lever une exception matérielle dont la routine rapatriera la page en mémoire RAM.

Charger une page en RAM ne pose aucun problème tant qu'il existe des pages inoccupée en RAM. Mais si toute la RAM est pleine, il faut déplacer une page mémoire en RAM sur le disque dur pour faire de la place. Tout cela est effectué par le système d'exploitation dont j'ai parlé plus haut. Notons que si on supprime une donnée dont on aura besoin dans le futur, il faudra recharger celle-ci, ce qui prend du temps. Le choix de la page doit être fait avec le plus grand soin et il existe différents algorithmes qui permettent de décider quelle page supprimer de la RAM. Les plus simples sont les suivants.

  • Aléatoire : on choisit la page au hasard.
  • FIFO : on supprime la donnée qui a été chargée dans la mémoire avant toutes les autres.
  • LRU : on supprime la donnée qui été lue ou écrite pour la dernière fois avant toutes les autres.
  • LFU : on vire la page qui est lue ou écrite le moins souvent comparée aux autres.
  • etc.

Ces algorithmes ont chacun deux variantes : une locale, et une globale. Avec la version locale, la page qui va être rapatriée sur le disque dur est une page réservée au programme qui est la cause du page miss. Avec la version globale, le système d'exploitation va choisir la page à virer parmi toutes les pages présentes en mémoire vive.

Sur la majorité des systèmes d'exploitation, il est possible d'interdire le déplacement de certaines pages sur le disque dur. Ces pages restent alors en mémoire RAM durant un temps plus ou moins long, parfois en permanence. Cette possibilité simplifie la vie des programmeurs qui conçoivent des systèmes d'exploitation : essayez d'exécuter une interruption de gestion de page miss alors que la page contenant le code de l'interruption est placée sur le disque dur.

La protection mémoire avec la paginationModifier

La protection mémoire est garantie avec des clés de protection, un nombre unique à chaque programme. Le processeur mémorise, pour chaque page, la clé de protection du programme qui a réservé la page. À chaque accès mémoire, le processeur compare la clé de protection du programme en cours d’exécution, et celle de la page adressée. Si les deux clés sont différentes, alors un programme a effectué un accès hors des clous et il se fait sauvagement arrêter.

Comme avec la segmentation, chaque page a des droits d'accès précis, qui permettent d'autoriser ou interdire les accès en lecture, écriture, exécution, etc. La table des pages mémorise les autorisations pour chaque page. Ces autorisations/interdictions sont mémorisés sous la forme d'une suite de bits, chaque bit autorisant/interdisant une opération bien précise. Le format exact de la suite de bits a cependant changé dans le temps sur les processeurs x86 modernes. Par exemple, c'est lors du passage au 64 bits que l'interdiction d’exécution a été ajouté au jeu d’instruction. Avant, les CPU et OS ne pouvaient pas marquer une page mémoire comme non-exécutable. C'est seulement avec le passage au 64 bits qu'à été ajouté un bit pour interdire l'exécution de code depuis une page. Ce bit, nommé bit NX, est à 0 si la page n'est pas exécutable et à 1 sinon. De plus, diverses techniques intégrées aux processeur permettent de gérer celui-ci facilement. Notamment, le processeur vérifie à chaque chargement d'instruction si le bit NX de page lue est à 1. Sinon, il lève une exception matérielle et laisse la main à l'OS.

La taille des pagesModifier

La taille des pages varie suivant le processeur et le système d'exploitation et tourne souvent autour de 4 kibioctets. Les processeurs actuels gèrent plusieurs tailles différentes pour les pages : 4 kibioctets par défaut, 2 mébioctets, voire 1 à 4 gibioctets pour les pages les plus larges. Les pages de 4 kibioctets sont les pages par défaut, les autres tailles de page sont appelées des pages larges. La taille optimale pour les pages dépend de nombreux paramètres et il n'y a pas de taille qui convienne à tout le monde. Certaines applications vont bénéficier à utiliser des pages larges, d'autres vont au contraire perdre drastiquement en performance en les utilisant.

La désavantage principal des pages larges est qu'elles favorisent la fragmentation mémoire. Si un programme veut réserver une portion de mémoire, pour une structure de donnée quelconque, il doit réserver une portion dont la taille est multiple de la taille d'une page. Par exemple, un programme ayant besoin de 110 kibioctets allouera 28 pages de 4 kibioctets, soit 120 kibioctets : 2 kibioctets seront perdus. Par contre, avec des pages larges de 2 mébioctets, on aura une perte de 2048 - 110 = 1938 kibioctets. En somme, des morceaux de mémoire seront perdus car les pages sont trop grandes pour les données qu'on veut y mettre. Le résultat est que le programme qui utilise les pages larges utilisent plus de mémoire, et ce d'autant plus qu'il utilise des données de petite taille. Un autre désavantage est qu'elles se marient mal avec certaines techniques d'optimisations de type copy-on-write.

Mais l'avantage est que la traduction des adresses est plus performante. Une taille des pages plus élevée signifie moins de pages, donc des tables des pages plus petites. Et des pages des tables plus petites n'ont pas besoin de beaucoup de niveaux de hiérarchie, voire peuvent se limiter à des tables des pages simples, ce qui rend la traduction d'adresse plus simple et plus rapide. De plus, les programmes ont une certain localité spatiale, qui font qu'ils accèdent souvent à des données proches. La traduction d'adresse peut alors profiter de systèmes de mise en cache dont nous parlerons dans le prochain chapitre, et ces systèmes de cache marchent nettement mieux avec des pages larges.

Il faut noter que la taille des pages est presque toujours une puissance de deux. Cela a de nombreux avantages, mais n'est pas une nécessité. Par exemple, le tout premier processeur avec de la pagination, le super-ordinateur Atlas, avait des pages de 3 kibioctets. L'avantage principal est que la traduction de l'adresse physique en adresse logique est trivial avec une puissance de deux. Cela garantit que l'on peut diviser l'adresse en un numéro de page et un offset : la traduction demande juste de remplacer les bits de poids forts par le numéro de page voulu. Sans cela, la traduction d'adresse implique des divisions et des multiplications, qui sont des opérations assez couteuses.