Fonctionnement d'un ordinateur/L'abstraction mémoire et la mémoire virtuelle

Pour introduire ce chapitre, nous devons faire un rappel sur le concept d'espace d'adressage. Pour rappel, un espace d'adressage correspond à l'ensemble des adresses utilisables par le processeur. Par exemple, si je prends un processeur 16 bits, il peut adresser en tout 2^16 = 65536 adresses, l'ensemble de ces adresses forme son espace d'adressage.

L'espace d'adressage est un ensemble d'adresses géré par le processeur, et on s'attend à ce qu'il y ait correspondance avec les adresses envoyées à la mémoire RAM. J'entends par là que l'adresse 1209 de l'espace d'adressage correspond à l'adresse 1209 en mémoire RAM. C'est là une hypothèse parfaitement raisonnable et on voit mal comment ce pourrait ne pas être le cas. Mais sachez qu'il existe des techniques d'abstraction mémoire qui font que ce n'est pas le cas. Avec ces techniques, l'adresse 1209 de l'espace d'adressage correspond en réalité à l'adresse 9999 en mémoire RAM, voire n'est pas en RAM.

L'abstraction mémoire fait que les adresses de l'espace d'adressage sont des adresses fictives, qui doivent être traduites en adresses mémoires réelles pour être utilisées. Les adresses de l'espace d'adressage portent le nom d'adresses logiques, alors que les adresses de la mémoire RAM sont appelées adresses physiques.

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.

Pour implémenter l'abstraction mémoire, il faut rajouter un circuit qui traduit les adresses logiques en adresses physiques. Ce circuit est placé dans le processeur et est appelé la Memory Management Unit (MMU). Si le processeur contient une MMU, les périphériques qui accèdent à la mémoire RAM peuvent disposer d'une MMU intégrée, qui s'appelle une IOMMU.

L'abstraction mémoire implémente de nombreuses fonctionnalités complémentaires modifier

Leur utilité n'est pas évidente, mais sachez que l'abstraction matérielle est très utile et que tous les processeurs modernes la prennent en charge. Elles servent à implémenter la relocation directement dans le processeur, à implémenter l'abstraction matérielle des processus. Elle sert aussi pour les fonctionnalités de mémoire virtuelle, dont vous avez peut-être entendu parler, mais que nous aborderons plus bas. Nous allons voir toutes ces fonctionnalités dans ce qui suit.

La plupart de ces fonctionnalités manipulent la relation entre adresses logiques et physique. Dans le cas le plus simple, une adresse logique correspond à une seule adresse physique. Mais l'abstraction mémoire et le partage de mémoire entre programmes ne respectent pas cette règle.

L'abstraction matérielle des processus modifier

Dans le chapitre précédent, nous avions vu l'abstraction matérielle des processus, une technique qui fait que chaque programme a son propre espace d'adressage. Chaque programme a l'impression d'avoir accès à tout l'espace d'adressage, de l'adresse 0 à l'adresse maximale gérée par le processeur. Évidemment, il s'agit d'une illusion maintenue justement grâce à la traduction d'adresse. Les espaces d'adressage contiennent des adresses logiques, les adresses de la RAM sont des adresses physiques, la nécessité de l'abstraction mémoire est évidente.

Implémenter l'abstraction mémoire peut se faire de plusieurs manières. Mais dans tous les cas, il faut que la correspondance adresse logique - physique change d'un programme à l'autre. Ce qui est normal, vu que les deux processus sont placés à des endroits différents en RAM physique. La conséquence est qu'avec l'abstraction mémoire, une adresse logique correspond à plusieurs adresses physiques. Une même adresse logique dans deux processus différents correspond à deux adresses phsiques différentes, une par processus. Une adresse logique dans un processus correspondra à l'adresse physique X, la même adresse dans un autre processus correspondra à l'adresse Y.

Les adresses physiques qui partagent la même adresse logique sont alors appelées des adresses homonymes. Le choix de la bonne adresse étant réalisé par un mécanisme matériel et dépend du programme en cours. Le mécanisme pour choisir la bonne adresse dépend du processeur, mais il y en a deux grands types :

  • La première consiste à utiliser l'identifiant de processus CPU, vu au chapitre précédent. C'est, pour rappel, un numéro attribué à chaque processus par le processeur. L'identifiant du processus en cours d'exécution est mémorisé dans un registre du processeur. La traduction d'adresse utilise cet identifiant, en plus de l'adresse logique, pour déterminer l'adresse physique.
  • La seconde solution mémorise les correspondances adresses logiques-physique dans des tables en mémoire RAM, qui sont différentes pour chaque programme. Les tables sont accédées à chaque accès mémoire, afin de déterminer l'adresse physique.

Le partage de la mémoire entre programmes modifier

Dans le chapitre précédent, nous avions vu qu'il est possible de lancer plusieurs programmes en même temps, mais que ceux-ci doivent se partager la mémoire RAM. Toutefois, cela amène un paquet de problèmes qu'il faut résoudre au mieux. Le problème principal est que les programmes ne doivent pas lire ou écrire dans les données d'un autre, sans quoi on se retrouverait rapidement avec des problèmes. Il faut donc introduire des mécanismes de protection mémoire, pour isoler les programmes les uns des autres.

Il faut cependant que la protection mémoire permette à deux programmes de partager des morceaux de mémoire, ce qui est nécessaire pour implémenter les mécanismes de communication inter-processus des systèmes d'exploitation modernes. Ce partage de mémoire est rendu très compliqué par l'abstraction mémoire, mais est parfaitement possible.

Avec le partage de mémoire, plusieurs adresses logiques correspondent à la même adresse physique. Les adresses logiques sont alors appelées des adresses synonymes. Lorsque deux processus partagent une même zone de mémoire, la zone sera mappées à des adresses logiques différentes. Tel processus verra la zone de mémoire partagée à l'adresse X, l'autre la verra à l'adresse Y. Mais il s'agira de la même portion de mémoire physique, avec une seule adresse physique.

La mémoire virtuelle : quand l'espace d'adressage est plus grand que la mémoire modifier

Toutes les adresses ne sont pas forcément occupées par de la mémoire RAM, s'il n'y a pas assez de RAM installée. Par exemple, un processeur 32 bits peut adresser 4 gibioctets de RAM, même si seulement 3 gibioctets sont installés dans l'ordinateur. L'espace d'adressage contient donc 1 gigas d'adresses inutilisées, et il faut éviter ce surplus d'adresses pose problème.

Sans mémoire virtuelle, seule la mémoire réellement installée est utilisable. Si un programme utilise trop de mémoire, il est censé se rendre compte qu'il n'a pas accès à tout l'espace d'adressage. Quand il demandera au système d'exploitation de lui réserver de la mémoire, le système d'exploitation le préviendra qu'il n'y a plus de mémoire libre. Par exemple, si un programme tente d'utiliser 4 gibioctets sur un ordinateur avec 3 gibioctets de mémoire, il ne pourra pas. Pareil s'il veut utiliser 2 gibioctets de mémoire sur un ordinateur avec 4 gibioctets, mais dont 3 gibioctets sont déjà utilisés par d'autres programmes. Dans les deux cas, l'illusion tombe à plat.

Les techniques de mémoire virtuelle font que l'espace d'adressage est utilisable au complet, même s'il n'y a pas assez de mémoire installée dans l'ordinateur ou que d'autres programmes utilisent de la RAM. Par exemple, sur un processeur 32 bits, le programme aura accès à 4 gibioctets de RAM, même si d'autres programmes utilisent la RAM, même s'il n'y a que 2 gibioctets de RAM d'installés dans l'ordinateur.

Pour cela, on utilise une partie des mémoires de masse (disques durs) d'un ordinateur en remplacement de la mémoire physique manquante. Le système d'exploitation crée sur le disque dur un fichier, appelé le swapfile ou fichier de swap, qui est utilisé comme mémoire RAM supplémentaire. Il mémorise le surplus de données et de programmes qui ne peut pas être mis en mémoire RAM.

 
Mémoire virtuelle et fichier de Swap.

Une technique naïve de mémoire virtuelle serait la suivante. Avant de l'aborder, précisons qu'il s'agit d'une technique abordée à but pédagogique, mais qui n'est implémentée nulle part tellement elle est lente et inefficace. L'espace d'adressage est partiellement occupé par des périphériques ou des adresses mémoires, mettons qu'on a 3 gigas d'occupés sur seulement 4, ce qui fait 1 giga d'adresses inutilisées. Les accès mémoire aux 3 gigas installés dans l'ordinateur se font normalement, mais l'accès aux adresses inutilisées lève une exception matérielle "Memory Unavailable". La routine d'interruption accède alors au swapfile et récupère les données associées à cette adresse. La mémoire virtuelle est alors émulée par le système d'exploitation. Le défaut de cette méthode est la performance des accès mémoire. Les accès aux trois premiers gigas sont très rapides, car ils accèdent à la RAM, mais l'accès au giga manquant est très lent, parce qu'il se fait depuis le disque dur. D'autres techniques de mémoire virtuelle font beaucoup mieux, mais nous allons les passer sous silence.

On peut faire mieux, avec l'aide du matériel. L'idée est de charger les données dont le programme a besoin dans la RAM, et de déplacer les autres sur le disque dur. Du fait de la localité temporelle, le programme ne va pas accéder à des données dispersées dans la RAM, mais il accède à un bloc de mémoire contiguë et l'utilise durant un bon moment avant de passer au suivant. La RAM est alors utilisée comme une sorte de cache alors que les données sont placées dans une mémoire fictive représentée par l'espace d'adressage et qui correspond au disque dur.

Par exemple, imaginons la situation suivante : un programme a besoin de 4 gigas de mémoire, mais ne dispose que de 2 gigas de mémoire installée. On peut imaginer découper l'espace d'adressage en 2 blocs de 2 gigas, qui sont chargés à la demande. Si le programme accède aux adresses basses, on charge les 2 gigas d'adresse basse en RAM. S'il accède aux adresses hautes, on charge les 2 gigas d'adresse haute dans la RAM après avoir copié les adresses basses sur le swarpfile. On perd du temps dans les copies de données entre RAM et swapfile, mais on gagne en performance vu que tous les accès mémoire se font en RAM.

Mais avec cette technique, la correspondance entre adresses du programme et adresses de la RAM change au cours du temps. Les adresses de la RAM correspondent d'abord aux adresses basses, puis aux adresses hautes, et ainsi de suite. On a donc besoin d'abstraction mémoire. Les correspondances entre adresse logique et physique peuvent varier avec le temps, ce qui permet de déplacer des données de la RAM vers le disque dur ou inversement. Une adresse logique peut correspondre à une adresse physique, ou bien à une donnée swappée sur le disque dur. C'est l'unité de traduction d'adresse qui se charge de faire la différence. Si une correspondance entre adresse logique et physique est trouvée, elle l'utilise pour traduire les adresses. Si aucune correspondance n'est trouvée, alors elle laisse la main au système d'exploitation pour charger la donnée en RAM. Une fois la donnée chargée en RAM, les correspondances entre adresse logique et physiques sont modifiées de manière à ce que l'adresse logique pointe vers la donnée chargée.

L'extension d'adressage modifier

Une autre fonctionnalité rendue possible par l'abstraction mémoire est l'extension d'adressage. Elle permet d'utiliser plus de mémoire que l'espace d'adressage ne le permet. Par exemple, utiliser 7 gigas de RAM sur un processeur 32 bits, dont l'espace d'adressage ne gère que 4 gigas. L'extension d'adresse est l'exact inverse de la mémoire virtuelle. La mémoire virtuelle sert quand on a moins de mémoire que d'adresses, l'extension d'adresse sert quand on a plus de mémoire que d'adresses.

Dans le chapitre précédent, nous avions vu que c'est possible via la commutation de banques. Mais l'abstraction mémoire est une méthode alternative. Que ce soit avec la commutation de banques ou avec l'abstraction mémoire, les adresses envoyées à la mémoire doivent être plus longues que les adresses gérées par le processeur. La différence est que l'abstraction mémoire étend les adresses d'une manière différente.

Une implémentation possible de l'extension d'adressage fait usage de l'abstraction matérielle des processus. Chaque processus a son propre espace d'adressage, mais ceux-ci sont placés à des endroits différents dans la mémoire physique. Par exemple, sur un ordinateur avec 16 gigas de RAM, mais un espace d'adressage de 2 gigas, on peut remplir la RAM en lançant 8 processus différents et chaque processus aura accès à un bloc de 2 gigas de RAM, pas plus, il ne peut pas dépasser cette limite. Ainsi, chaque processus est limité par son espace d'adressage, mais on remplit la mémoire avec plusieurs processus, ce qui compense. Il s'agit là de l'implémentation la plus simple, qui a en plus l'avantage d'avoir la meilleure compatibilité logicielle. De simples changements dans le système d'exploitation suffisent à l'implémenter.

 
Extension de l'espace d'adressage

Un autre implémentation donne plusieurs espaces d'adressage différents à chaque processus, et a donc accès à autant de mémoire que permis par la somme de ces espaces d'adressage. Par exemple, sur un ordinateur avec 16 gigas de RAM et un espace d'adressage de 4 gigas, un programme peut utiliser toute la RAM en utilisant 4 espaces d'adressage distincts. On passe d'un espace d'adressage à l'autre en changeant la correspondance adresse logique-physique. L'inconvénient est que la compatibilité logicielle est assez mauvaise. Modifier l'OS ne suffit pas, les programmeurs doivent impérativement concevoir leurs programmes pour qu'ils utilisent explicitement plusieurs espaces d'adressage.

Les deux implémentations font usage des adresses logiques homonymes, mais à l'intérieur d'un même processus. Pour rappel, cela veut dire qu'une adresse logique correspond à des adresses physiques différentes. Rien d'étonnant vu qu'on utilise plusieurs espaces d'adressage, comme pour l'abstraction des processus, sauf que cette fois-ci, on a plusieurs espaces d'adressage par processus. Prenons l'exemple où on a 8 gigas de RAM sur un processeur 32 bits, dont l'espace d'adressage ne gère que 4 gigas. L'idée est qu'une adresse correspondra à une adresse dans les premiers 4 gigas, ou dans les seconds 4 gigas. L'adresse logique X correspondra d'abord à une adresse physique dans les premiers 4 gigas, puis à une adresse physique dans les seconds 4 gigas.

Les liens entre ces différentes techniques modifier

Pour résumer, l'abstraction mémoire permet de gérer : la relocation, la protection mémoire, l'isolation des processus, la mémoire virtuelle, l'extension de l'espace d'adressage, le partage de mémoire, etc. Elles sont souvent implémentées en même temps. Ce qui fait qu'elles sont souvent confondues, alors que ce sont des concepts sont différents.

Par exemple, la multiprogrammation et la mémoire virtuelle sont deux choses différentes, mais complémentaires. Il est parfaitement possible d'avoir de la mémoire virtuelle avec un système d'exploitation mono-programmé, qui n'exécute qu'un seul programme sur l'ordinateur.

Comme autre exemple, la mémoire virtuelle et l'abstraction matérielle des processus sont souvent confondus. Avoir un espace d'adressage par programme, comme vu dans le chapitre précédent, est la norme sur les systèmes d'exploitation moderne. Et son implémentation se base justement sur la mémoire virtuelle. Pourtant, il existe des architectures qui ne respectent pas cette complémentarité :

  • La relocation matérielle, qu'on verra plus bas, gère l'abstraction mémoire, mais pas la mémoire virtuelle.
  • Il existe des architectures où il n'y a qu'un seul espace d'adressage partagé entre tous les programmes, donc sans abstraction matérielle des processus, mais avec mémoire virtuelle. C'est le cas sur les architectures à capacité que nous verrons dans quelques chapitres. L'espace d'adressage est unique et tous les programmes doivent se le partager, mais ca reste un espace d'adressage virtuel remplit d'adresses logiques.

Le partage de mémoire entre processus dépend fortement de la protection mémoire, et est rendue plus compliquée par l'abstraction matérielle des processus.

L'abstraction matérielle des processus et l'extension de l'espace d'adressage font usage de plusieurs espaces d'adressages, mais avec une différence importante. Avec la première, on a un espace d'adressage par processus, la seconde en donne soit un, soit plusieurs par processus. Les autres méthodes fonctionnent soit avec un seul espace d'adressage, soit de concert avec l'abstraction matérielle et/ou l'extension de l'espace d'adressage.

La relocation matérielle modifier

Pour rappel, les systèmes d'exploitation moderne permettent de lancer plusieurs programmes en même temps et les laissent se partager la mémoire. Dans le cas le plus simple, qui n'est pas celui des OS modernes, le système d'exploitation découpe la mémoire en blocs d'adresses contiguës qui sont appelés des segments, ou encore des partitions mémoire. Les segments correspondent à un bloc de mémoire RAM. C'est-à-dire qu'un segment de 259 mébioctets sera un segment continu de 259 mébioctets dans la mémoire physique comme dans la mémoire logique. Dans ce qui suit, un segment contient un programme en cours d'exécution, comme illustré ci-dessous.

 
Espace d'adressage segmenté.

Le système d'exploitation mémorise la position de chaque segment en mémoire, ainsi que d'autres informations annexes. Le tout est regroupé dans la table de segment, un tableau dont chaque case est attribuée à un programme/segment. La table des segments est un tableau numéroté, chaque segment ayant un numéro qui précise sa position dans le tableau. Chaque case, chaque entrée, contient un descripteur de segment qui regroupe plusieurs informations sur le segment : son adresse de base, sa taille, diverses informations.

Un segment peut être placé n'importe où en RAM physique et sa position en RAM change à chaque exécution. Le programme est chargé à une adresse, celle du début du segment, qui change à chaque chargement du programme. Et toutes les adresses utilisées par le programme doivent être corrigées lors du chargement du programme, généralement par l'OS. Cette correction s'appelle la relocation, et elle consiste à ajouter l'adresse de début du segment à chaque adresse manipulée par le programme.

 
Relocation.

La relocation matérielle va de pair avec les segments, mais la relocation est faite par le processeur. La relocation matérielle traduit les adresses logiques en adresses physiques, directement en matériel. La méthode de relocation matérielle associée s'appelle la segmentation simple. Peut-être avez-vous entendu dire qu'il s'agit d'une technique de mémoire virtuelle. Et ce n'est pas faux ! En fait, il existe plusieurs versions de la segmentation, certaines plus puissantes que les autres. Les plus simples se contentent de découper la RAM en segments et de faire la relocation en matériel, mais ne gèrent pas la mémoire virtuelle. Les versions élaborées incorporent de la protection mémoire et/ou la mémoire virtuelle.

La relocation avec la relocation matérielle : le registre de base modifier

La relocation est intégrée dans le processeur par l'intégration d'un registre : le registre de base, aussi appelé registre de relocation. Il mémorise l'adresse à laquelle commence le segment, la première adresse du programme. Pour effectuer la relocation, le processeur ajoute automatiquement l'adresse de base à chaque accès mémoire, en allant la chercher dans le registre de relocation.

 
Registre de base de segment.

Le processeur s'occupe de la relocation des segments et le programme compilé n'en voit rien. Pour le dire autrement, les programmes manipulent des adresses logiques, qui sont traduites par le processeur en adresses physiques. La traduction se fait en ajoutant le contenu du registre de relocation à l'adresse logique. De plus, cette méthode fait que chaque programme a son propre espace d'adressage.

 
Traduction d'adresse avec la relocation matérielle.

Le système d'exploitation mémorise les adresses de base pour chaque programme, dans la table des segments. Le registre de base est mis à jour automatiquement lors de chaque changement de segment. Pour cela, le registre de base est accessible via certaines instructions, accessibles en espace noyau, plus rarement en espace utilisateur. Le registre de segment est censé être adressé implicitement, vu qu'il est unique. Si ce n'est pas le cas, il est possible d'écrire dans ce registre de segment, qui est alors adressable.

La protection mémoire avec la relocation matérielle : le registre limite modifier

Sans restrictions supplémentaires, la taille maximale d'un segment est égale à la taille complète de l'espace d'adressage. Sur les processeurs 32 bits, un segment a une taille maximale de 2^32 octets, soit 4 gibioctets. Mais il est possible de limiter la taille du segment à 2 gibioctets, 1 gibioctet, 64 Kibioctets, ou toute autre taille. La limite est définie lors de la création du segment, mais elle peut cependant évoluer au cours de l'exécution du programme, grâce à l'allocation mémoire. Le processeur vérifie à chaque accès mémoire que celui-ci se fait bien dans le segment, en comparant l'adresse accédée à l'adresse de base et l'adresse maximale, l'adresse limite.

Limiter la taille d'un segment demande soit de mémoriser sa taille, soit de mémoriser l'adresse limite (l'adresse de fin de segment, l'adresse limite à ne pas dépasser). Les deux sont possibles et marchent parfaitement, le choix entre les deux solutions est une pure question de préférence. A la rigueur, la vérification des débordements est légèrement plus rapide si on utilise l'adresse de fin du segment. Précisons que l'adresse limite est une adresse logique, le segment commence toujours à l'adresse logique zéro.

Pour cela, la table des segments doit être modifiée. Au lieu de ne contenir que l'adresse de base, elle contient soit l'adresse maximale du segment, soit la taille du segment. En clair, le descripteur de segment est enrichi avec l'adresse limite. D'autres informations peuvent être ajoutées, comme on le verra plus tard, mais cela complexifie la table des segments.

De plus, le processeur se voit ajouter un registre limite, qui mémorise soit la taille du segment, soit l'adresse limite. Les deux registres, base et limite, sont utilisés pour vérifier si un programme qui lit/écrit de la mémoire en-dehors de son segment attitré : au-delà pour le registre limite, en-deça pour le registre de base. Le processeur vérifie pour chaque accès mémoire ne déborde pas au-delà du segment qui lui est allouée, ce qui n'arrive que si l'adresse d'accès dépasse la valeur du registre limite. Pour les accès en-dessous du segment, il suffit de vérifier si l'addition de relocation déborde, tout débordement signifiant erreur de protection mémoire.

Techniquement, il y a une petite différence de vitesse entre utiliser la taille et l'adresse maximale. Vérifier les débordements avec la taille demande juste de comparer la taille avec l'adresse logique, avant relocation, ce qui peut être fait en parallèle de la relocation. Par contre, l'adresse limite est comparée à une adresse physique, ce qui demande de faire la relocation avant la vérification, ce qui prend un peu plus de temps. Mais l'impact sur les performances est des plus mineurs.

 
Registre limite

Les registres de base et limite sont altérés uniquement par le système d'exploitation et ne sont accessibles qu'en espace noyau. Lorsque le système d'exploitation charge un programme, ou reprend son exécution, il charge les adresses de début/fin du segment dans ces registres. D'ailleurs, ces deux registres doivent être sauvegardés et restaurés lors de chaque interruption. Par contre, et c'est assez évident, ils ne le sont pas lors d'un appel de fonction. Cela fait une différence de plus entre interruption et appels de fonctions.

Il faut noter que le registre limite et le registre de base sont parfois fusionnés en un seul registre, qui contient un descripteur de segment tout entier.

La mémoire virtuelle avec la relocation matérielle modifier

Il est possible d'implémenter la mémoire virtuelle avec la relocation matérielle. Pour cela, il faut swapper des segments entiers sur le disque dur. Les segments sont placés en mémoire RAM et leur taille évolue au fur et à mesure que les programmes demandent du rab de mémoire RAM. Lorsque la mémoire est pleine, ou qu'un programme demande plus de mémoire que disponible, des segments entiers sont sauvegardés dans le swapfile, pour faire de la place.

Faire ainsi de demande juste de mémoriser si un segment est en mémoire RAM ou non, ainsi que la position des segments swappés dans le swapfile. Pour cela, il faut modifier la table des segments, afin d'ajouter un bit de swap qui précise si le segment en question est swappé ou non. Lorsque le système d'exploitation veut swapper un segment, il le copie dans le swapfile et met ce bit à 1. Lorsque l'OS recharge ce segment en RAM, il remet ce bit à 0. La gestion de la position des segments dans le swapfile est le fait d'une structure de données séparée de la table des segments.

L'OS exécute chaque programme l'un après l'autre, à tour de rôle. Lorsque le tour d'un programme arrive, il consulte la table des segments pour récupérer les adresses de base et limite, mais il vérifie aussi le bit de swap. Si le bit de swap est à 0, alors l'OS se contente de charger les adresses de base et limite dans les registres adéquats. Mais sinon, il démarre une routine d'interruption qui charge le segment voulu en RAM, depuis le swapfile. C'est seulement une fois le segment chargé que l'on connait son adresse de base/limite et que le chargement des registres de relocation peut se faire.

Un défaut évident de cette méthode est que l'on swappe des programmes entiers, qui sont généralement assez imposants. Les segments font généralement plusieurs centaines de mébioctets, pour ne pas dire plusieurs gibioctets, à l'époque actuelle. Ils étaient plus petits dans l'ancien temps, mais la mémoire était alors plus lente. Toujours est-il que la copie sur le disque dur des segments est donc longue, lente, et pas vraiment compatible avec le fait que les programmes s'exécutent à tour de rôle. Et ca explique pourquoi la relocation matérielle n'est presque jamais utilisée avec de la mémoire virtuelle.

L'extension d'adressage avec la relocation matérielle modifier

Passons maintenant à la dernière fonctionnalité implémentable avec la traduction d'adresse : l'extension d'adressage. Elle permet d'utiliser plus de mémoire que ne le permet l'espace d'adressage. Par exemple, utiliser plus de 64 kibioctets de mémoire sur un processeur 16 bits. Pour cela, les adresses envoyées à la mémoire doivent être plus longues que les adresses gérées par le processeur.

L'extension des adresses se fait assez simplement avec la relocation matérielle : il suffit que le registre de base soit plus long. Prenons l'exemple d'un processeur aux adresses de 16 bits, mais qui est reliée à un bus d'adresse de 24 bits. L'espace d'adressage fait juste 64 kibioctets, mais le bus d'adresse gère 16 mébioctets de RAM. On peut utiliser les 16 mébioctets de RAM à une condition : que le registre de base fasse 24 bits, pas 16.

Un défaut de cette approche est qu'un programme ne peut pas utiliser plus de mémoire que ce que permet l'espace d'adressage. Mais par contre, on peut placer chaque programme dans des portions différentes de mémoire. Imaginons par exemple que l'on ait un processeur 16 bits, mais un bus d'adresse de 20 bits. Il est alors possible de découper la mémoire en 16 blocs de 64 kibioctets, chacun attribué à un segment/programme, qu'on sélectionne avec les 4 bits de poids fort de l'adresse. Il suffit de faire démarrer les segments au bon endroit en RAM, et cela demande juste que le registre de base le permette. C'est une sorte d'émulation de la commutation de banques.

Le partage de segments avec la relocation matérielle modifier

Deux programmes peuvent partager une même zone de mémoire, mais sous des conditions très restrictives. L'idée est que deux segments consécutifs se recouvrent l'un autre, à savoir que les deux segments contiennent une même région de mémoire physique. C'est possible, car une adresse physique peut correspondre à plusieurs couples (segment-offset). Il suffit alors de configurer correctement les adresses de base/limite.

 
Recouvrement de segments.

Il faut avouer que le partage de la mémoire n'est pas pratique avec la relocation matérielle, ce qui fait qu'il est rarement utilisé.

La segmentation modifier

La segmentation est une amélioration de la technique de a relocation matérielle vue dans la section précédente. Elle est apparue sur des processeurs assez anciens, le tout premier étant le Burrough 5000. Elle a ensuite été utilisée sur d'autres architectures, avant de faire son apparition sur les processeurs x86 de nos PC. La segmentation regroupe un ensemble de techniques très différentes. les plus simples se passent de mémoire virtuelle et même de protection mémoire, mais les plus élaborées implémentent les deux.

La mémoire virtuelle avec la segmentation : la relation avec l'overlaying modifier

Là où les autres techniques d'abstraction mémoire offrent à chaque programme un seul segment, la segmentation leur attribue plusieurs ! L'utilité d'avoir plusieurs segments par programme n'est pas évidente, mais elle devient évidente quand on se plonge dans le passé. Dans le passé, les programmeurs devaient faire avec une quantité de mémoire limitée et il n'était pas rare que certains programmes utilisent plus de mémoire que disponible sur la machine. Mais les programmeurs concevaient leurs programmes en fonction.

L'idée était d'implémenter un système de mémoire virtuelle, mais émulé en logiciel, appelé l'overlaying. Le programme était découpé en plusieurs morceaux, appelés des overlays. Certains blocs overlays en permanence en RAM, mais d'autres étaient soit chargés en RAM, soit stockés sur le disque dur. Le chargement des overlays ou leur sauvegarde sur le disque dur était réalisé en logiciel, par le programme lui-même. Le matériel n'intervenait pas, comme c'est le cas avec la mémoire virtuelle.

 
Overlay Programming

Avec la segmentation, un programme peut utiliser la technique des overlays, mais avec l'aide du matériel. Il suffit de mettre chaque overlay dans son propre segment, et laisser la segmentation faire. Les segments sont swappés en tout ou rien : on doit swapper tout un segment en entier. L'intérêt est que la gestion du swapping est grandement facilitée, vu que c'est le système d'exploitation qui s'occupe de swapper les segments sur le disque dur ou de charger des segments en RAM. Pas besoin pour le programmeur de coder quoique ce soit.

L'implémentation de la mémoire virtuelle est aussi beaucoup plus simple avec la segmentation, comparé à la relocation matérielle. Avce la relocation matérielle, on devait swapper des programmes entiers, alors que la segmentation swappe des morceaux de programmes plus petits. La mémoire virtuelle est donc beaucoup plus pratique avec la segmentation, et est une fonctionnalité souvent implémentée sur les processeurs qui gérent la segmentation, alors que les processeurs avec relocation matérielle s'en passaient.

Par contre, cela demande l'intervention du programmeur, qui doit découpe le programme en segments/overlays de lui-même. Sans cela, la segmentation n'est pas très utile. Il est possible d'utiliser un seul segment par programme, mais cela réduit grandement l'intérêt de la segmentation, surtout comparé à la pagination. Au minimum, la segmentation sépare la pile, le tas, le code machine et les données constantes dans quatre segments distincts. D'ailleurs, la segmentation des processeurs x86 était prévue pour ça. Les premiers processeurs x86 avaient 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).

La segmentation sur les processeurs x86 modifier

 
Typical computer data memory arrangement

Un découpage possible se fait en utilisant ce qu'on appris au chapitre précédent. Pour rappel, un programme est souvent découpé en quatre portions :

  • Le segment text, qui contient le code machine du programme, de taille fixe.
  • Le segment data contient des données de taille fixe qui occupent de la mémoire de façon permanente, des constantes, des variables globales, etc.
  • Le segment pour la pile, de taille variable.
  • le reste est appelé le tas, de taille variable.

En général, les autres portions ont chacune leur propre segment. c'est le cas notamment sur les premiers processeurs x86. Sur les suivants, il était possible de découper le segment data en plusieurs segments. Il n'était pas rare que le code machine du programme, le segment text, soit découpé en plusieurs morceaux indépendants, chargés selon les besoins. Cela complexifiait les branchements qui sautaient d'un overlay à l'autre, mais les programmeurs s'assuraient que ceux-ci étaient rares. Dans d'autres, c'était le tas était découpé en plusieurs overlays. La gestion du tas était plus complexe que pour le code machine pour une raison simple : le code machine est généralement de taille fixe et en lecture seule, pas le tas. Autant on doit sauvegarder sur le disque dur les modifications réalisées dans le tas, autant ces modifications n'existent pas pour le code machine.

La relocation avec la segmentation modifier

Avec la segmentation, la table des segments est fortement modifiée et doit respecter plusieurs contraintes. Premièrement, il y a plusieurs segments pas programmes. Deuxièmement, le nombre de segments est variable : certains programmes se contenteront d'un seul segment, d'autres en utiliseront moins d'une dizaine, d'autres en utiliseront un grand nombre. La seule solution praticable est d'utiliser une table de segment par processus/programme.

Et cela complique quelque peu la relocation matérielle, à savoir la traduction d'adresse. Le principe reste le même : additionner l'adresse de base du segment à chaque accès mémoire. Sauf que la présence de plusieurs segments change la donne. On n'a plus une adresse de base, mais plusieurs : une par segment associé au programme. Il faut donc sélectionner le segment voulu, récupérer l'adresse de base associée, puis faire l'addition.

La relocation avec plusieurs registres de base modifier

L'adresse manipulée par le processeur se déduit à partir de deux informations : un sélecteur de segment qui sélectionne le segment voulu, et un décalage (offset) qui donne la position de la donnée dans ce segment. Le sélecteur de segment se comprend simplement : les segments sont numérotés, le sélecteur est le numéro.

La solution la plus simple pour implémenter la relocation est d'utiliser plusieurs registres de base, un par segment. Il suffit alors de sélectionner le registre de base voulu avec le sélecteur de segment. Mais cette solution ne marche que si le nombre de segments par programme est limité, à une dizaine de segments tout au plus. Les processeurs x86 utilisaient cette méthode, et n'associaient que 4 à 6 registres de segments par programme.

 
Table des segments dans un banc de registres.

Une autre option utilise des registres de base, dont certains sont adressés implicitement. Un exemple est celui des processeurs x86, où on a un segment pour la pile, un autre pour le code machine, et deux autres. Les instructions de la pile manipulent le segment associé à la pile, le chargement des isntructions se fait dans le segment de code. Pour cela, les registres de base sont aussi spécialisés, avec un registre SS dédié à la pile, un registre CS pour le segment de code, etc. Et les instructions de la pile utilisent le registre SS, le chargement se fait en combinant le program counter et le registre CS, etc.

La relocation avec une table de segment en RAM modifier

Sur les processeurs Burrough 5000, et quelques autres ordinateurs de ce genre, le nombre de segments par programme était beaucoup plus élévé. La conséquence est que la table des segments ne tenait pas dans les registres du processeur et devait être placée en mémoire RAM. La traduction de l'adresse demande d'accéder à la table des segments en RAM, pour récupérer l'adresse de base. La conséquence est que 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. Et il faut dire que les performances s'en ressentent.

 
Traduction d'adresse avec une table des segments.

Pour accéder à la table des segments, le processeur doit contenir un registre supplémentaire, qui contient l'adresse de la table de segment, afin de la localiser en mémoire RAM. Nous appellerons ce registre le pointeur de table. Le pointeur de table est combiné avec le sélecteur de segment pour adresser le descripteur de segment adéquat.

 
Traduction d'adresse avec une table des segments, ici appelée table globale des de"scripteurs (terminologie des processeurs Intel x86).

La protection mémoire : les accès hors-segments modifier

Comme avec la relocation matérielle, le processeur utilise l'adresse ou la taille limite pour vérifier si l'accès mémoire ne déborde pas en-dehors du segment en cours. Pour cela, le processeur compare l'adresse logique accédée avec l'adresse limite/l'offset maximal. Soit cette information est lue depuis la table des segments à chaque accès, soit elle est chargée dans un registre limite à chaque changement de segment. 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.

Par contre, une nouveauté fait son apparition avec la segmentation : la gestion des droits d'accès. Chaque 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. Les autorisations pour chaque segment sont placées dans le descripteur de segment. Elles se résument généralement à trois bits, qui indiquent si le segment est accesible en lecture/écriture ou exécutable. Par exemple, il est possible d'interdire d'exécuter le contenu d'un segment, 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'exemple des descripteurs de segment des processeurs x86 modifier

Pour donner un exemple, prenons celui des processeurs x86 32 bits. Sur ces derniers, un descripteur de segment est organisé comme suit, pour les architectures 32 bits. On y trouve l'adresse de base et la taille limite, ainsi que de nombreux bits de contrôle.

Le premier groupe de bits de contrôle est l'octet en bleu à droite. Il contient :

  • le bit P qui indique que l'entrée contient un descripteur valide, qu'elle n'est pas vide ;
  • deux bits DPL qui indiquent le niveau de privilège du segment (noyau, utilisateur, les deux intermédiaires spécifiques au x86) ;
  • un bit S qui précise si le segment est de type système (utiles pour l'OS) ou un segment de code/données.
  • un champ Type qui contient les bits suivants : un bit E qui indique si le segment contient du code exécutable ou non, le bit RW qui indique s'il est en lecture seule ou non, les bits A et DC assez spécifiques.

En haut à gauche, en bleu, on trouve deux bits :

  • Le bit G indique comment interpréter la taille contenue dans le descripteur : 0 si la taille est exprimée en octets, 1 si la taille est un nombre de pages de 4 kibioctets. Ce bit précise si on utilise la segmentation seule, ou combinée avec la pagination.
  • Le bit DB précise si l'on utilise des segments en mode de compatibilité 16 bits ou des segments 32 bits.
 
Segment Descriptor

Le partage de segments modifier

Comme pour la relocation matérielle, deux segments consécutifs peuvent se recouvrir partiellement, la fin d'un segment faisant partie du début du suivant. Mais il est aussi possible de partager un segment entre plusieurs applications. Il suffit de configurer les tables de segment convenablement.

Cela peut servir quand plusieurs instances d'une même application sont lancés simultanément : le code n'ayant pas de raison de changer, celui-ci est partagé entre toutes les instances. Mais ce n'est là qu'un exemple.

 
Illustration du partage d'un segment entre deux applications.

C'est beaucoup pratique que ce qu'on avait avec la relocation matérielle. Et cela se marie aussi très bien avec la protection mémoire. Le même segment peut avoir des droits d'accès différents selon les processus. Les adresses de base/limite sont identiques, mais les tables des segments ont alors des droits d'accès différents.

L'extension d'adresse avec la segmentation modifier

L'extension d'adresse est possible avec la segmentation, de la même manière qu'avec la relocation matérielle. Il suffit juste que les registres de base contiennent des adresses plus grandes que les autres, aussi grandes que le bus d'adresse. Mais il y a une différence avec la relocation matérielle : un même programme peut utiliser plus de mémoire qu'il n'y en a dans l'espace d'adressage. La raison est simple : il y a un espace d'adressage par segment, plusieurs segments par programme.

Pour donner un exemple, prenons un processeur 16 bits, qui peut adresser 64 kibioctets, associé à une mémoire de 4 mébioctets. Il est possible de placer le code machine dans les premiers 64k de la mémoire, la pile du programme dans les 64k suivants, le tas dans les 64k encore après, et ainsi de suite. Le programme dépasse donc les 64k de mémoire de l'espace d'adressage. Ce genre de chose est impossible avec la relocation, où un programme est limité par l'espace d'adressage.

L'exemple de la segmentation sur les processeurs x86 modifier

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, ni même de mémoire virtuelle. 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. 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éel modifier

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). Les registres de segment sont utilisés implicitement. Par exemple, toutes les instructions sont chargées depuis le segment pointé par CS, les instructions de gestion de la pile (PUSH et POP) utilisent le segment pointé par SS. Ce sont tous des registres de 16 bits.

L'Intel 8086 utilisait la segmentation pour adresser 1 mébioctet de RAM, ce qui donne des adresses de 20 bits. Vous pouvez vous demander 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 le décalage : à la place, le registre de segment est décalé de 4 rangs vers la gauche. Le fait que le décalage soit de 16 bits fait que les segments ont une taille de 64 kibioctets. Le décalage de 4 rangs vers la gauche fait que chaque segment a une adresse qui est multiple de 16.

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

Le mode protégé de l'Intel 80286 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é et on accède à la table des segments en mémoire RAM.

 
Traduction d'adresse suyr le 80286.

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.

Le mode protégé de l'Intel 80386 et supérieurs modifier

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. AU total, ces processeurs possédaient six registres de base : CS, DS, SS, ES, FS et GS.

Les programmeurs n'hésitaient pas à découper le code machine en plusieurs overlays placés dans des segments séparés. Intel avait d'ailleurs prévu le coup, et avait conçu l'instruction CALL pour ça. L'instruction CALL gérait plusieurs types de branchements, dont les deux plus connus sont les near call et les far call. Le premier est un branchement qui reste dans le segment en cours, à savoir que le branchement et l'instruction de destination sont toutes deux dans le même segment. Avec le second, les deux sont dans des segments différents. Les premiers étaient plus rapides, car on n'avait pas à changer de segment et mettre à jour l'état du processeur.

Un autre mode de segmentation 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 de la pagination en plus de la segmentation.

Les processeurs x86 64 bits désactivent la segmentation en mode 64 bits.

La pagination modifier

Avec la pagination, la mémoire est découpée en blocs de taille fixe, appelés des pages mémoires. La taille des pages varie suivant le processeur et le système d'exploitation et tourne souvent autour de 4 kibioctets. Mais elles sont de taille fixe : on ne peut pas en changer la taille. C'est la différence avec les segments, qui sont de taille variable. 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.

L'espace d'adressage est découpé en pages logiques, alors que la mémoire physique est découpée en pages physique de même taille. Les pages logiques correspondent soit à une page physique, soit à une page swappée sur le disque dur. Quand une page logique est associée à une page physique, les deux ont le même contenu, mais pas les mêmes adresses. Les pages logiques sont numérotées, en partant de 0, afin de pouvoir les identifier/sélectionner. Même chose pour les pages physiques, qui sont elles aussi numérotées en partant de 0.

 
Principe de la pagination.

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 x86.

La mémoire virtuelle : le swapping et le remplacement des pages mémoires modifier

Le système d'exploitation mémorise des informations sur toutes les pages existantes dans une table des pages. C'est un tableau où chaque ligne est associée à une page logique. Une ligne contient un bit Valid qui indique si la page logique associée est swappée sur le disque dur ou non, et la position de la page physique correspondante en mémoire RAM. Elle peut aussi contenir des bits pour la protection mémoire, et bien d'autres. Les lignes sont aussi appelées des entrées de la table des pages

 
Table des pages.

Les défauts de page modifier

Lorsque l'on veut traduire l'adresse logique d'une page mémoire, le processeur vérifie le bit Valid et l'adresse physique. Si le bit Valid est à 1 et que l'adresse physique est présente, la traduction d'adresse s'effectue normalement. Mais si ce n'est pas le cas, l'entrée de la table des pages ne contient pas de quoi faire la traduction d'adresse. Soit parce que la page est swappée sur le disque dur et qu'il faut la copier en RAM, soit parce que les droits d'accès ne le permettent pas, soit parce que la page n'a pas encore été allouée, etc. On fait alors face à un défaut de page. Un défaut de page a lieu quand la MMU ne peut pas associer l'adresse logique à une adresse physique, quelque qu'en soit la raison.

Il existe deux types de défauts de page : mineurs et majeurs. Un défaut de page mineur a lieu dans des circonstances pas très intuitives : la page est en mémoire physique, mais l'adresse physique de la page n'est pas accessible. Par pas accessible, on veut dire qu'il est possible qu'elle soit dans la table des pages, mais que des sécurités empêchent de faire la traduction d'adresse pour des raisons de protection mémoire. Une autre raison est que la page a été allouée à un programme par le système d'exploitation, mais qu'il n'a pas encore attribué sa position en mémoire, ce qui correspond à une allocation paresseuse parfois utilisée par les OS. Une autre raison est la gestion des adresses synonymes, qui surviennent quand on utilise des libraires partagées entre programmes, de la communication inter-processus, des optimisations de type copy-on-write, etc.

Un défaut de page majeur a lieu quand on veut accéder à une page déplacée sur le disque dur. Un défaut de page majeur lève une exception matérielle dont la routine rapatriera la page en mémoire RAM. S'il y a de la place en mémoire RAM, il suffit d'allouer une page vide et d'y copier la page chargée depuis le disque dur. Mais si ce n'est par le cas, on va devoir faire de la place en RAM en déplaçant une page mémoire de la RAM vers le disque dur. Dans tous les cas, c'est le système d'exploitation qui s'occupe du chargement de la page, le processeur n'est pas impliqué. Une fois la page chargée, la table des pages est mise à jour et la traduction d'adresse peut recommencer. Si je dis recommencer, c'est car l'accès mémoire initial est rejoué à l'identique, sauf que la traduction d'adresse réussit cette fois-ci.

Je viens de dire que le système d'exploitation gère les défauts de page majeurs/mineurs. Un défaut de page déclenche une exception matérielle, qui passe la main au système d'exploitation. Le système d'exploitation doit alors déterminer ce qui a levé l'exception, notamment identifier si c'est un défaut de page mineur ou majeur. Pour cela, le processeur a un ou plusieurs registres de statut qui indique l'état du processeur, qui sont utiles pour gérer les défauts de page. Ils indiquent quelle est l'adresse fautive, si l'accès était une lecture ou écriture, si l'accès a eu lieu en espace noyau ou utilisateur (les espaces mémoire ne sont pas les mêmes), etc. Les registres en question varient grandement d'une architecture de processeur à l'autre, aussi on ne peut pas dire grand chose de plus sur le sujet. Le reste est de toute façon à voir dans un cours sur les systèmes d'exploitation.

Le remplacement des pages modifier

Les pages virtuelles vont ainsi faire référence soit à une page en mémoire physique, soit à une page sur le disque dur. Mais l'on ne peut pas lire une page directement depuis le disque dur. Les pages sur le disque dur doivent être chargées en RAM, avant d'être utilisables. Du moins, c'est le cas si on a une page mémoire vide, libre. Si ce n'est pas le cas, on doit faire de la place en swappant une page sur le disque dur. Les pages font ainsi une sorte de va et vient entre le fichier d'échange et la RAM, suivant les besoins. Tout cela est effectué par une routine d'interruption du système d'exploitation, le processeur n'ayant pas vraiment de rôle là-dedans.

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 l'interruption pour les défauts de page alors que la page contenant le code de l'interruption est placée sur le disque dur !

La traduction d'adresse avec la pagination modifier

Comme dit plus haut, 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é. 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.

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, ce qui est le rôle de la table des pages.

Les tables des pages simples modifier

Dans le cas le plus simple, il n'y a qu'une seule table des pages, 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.

 
Table des pages.

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.

 
Address translation (32-bit)

Les tables des pages inversées modifier

Sur certains systèmes, notamment sur les architectures 64 bits ou plus, le nombre de pages 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, la table des pages inversée est ce que l'on appelle une table de hachage. C'est cette solution qui est utilisée sur les processeurs Power PC.

 
Table des pages inversée.

Les tables des pages multiples par espace d'adressage modifier

Dans les deux cas précédents, il y a une table des pages unique. 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és à 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, toutes 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 x86 modifier

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

L'abstraction matérielle des processus : une table des pages par processus modifier

 
Mémoire virtuelle

Il est possible d'implémenter la mémoire virtuelle avec la pagination. Pour cela, il faut utiliser une table des pages pour chaque programme. Chaque programme lancé sur l'ordinateur dispose de son propre espace d'adressage, ce qui fait que la même adresse logique ne pointera pas sur la même adresse physique dans deux programmes différents. Et cela implique qu'il y a une table des pages par processus 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. L'idée est qu'une ou plusieurs pages sont mappées dans l'espace d'adressage de plusieurs processus. La page partagée est présente dans les espaces d'adressage des processus partageant, mais pas forcément au même endroit, pas forcément dans les mêmes adresses logiques. On peut placer la page partagée à l'adresse logique 0x0FFF pour un processus, à l'adresse logique 0xFF00 pour un autre processus, etc. Par contre, les entrées de la table des pages pour ces adresses pointent vers la même adresse physique.

 
Tables des pages de plusieurs processus.

La protection mémoire avec la pagination modifier

Avec la pagination, 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, sous la forme d'une suite de bits où chaque bit autorise/interdit 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, avant le passage au 64 bits, 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'a é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. 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.

Une amélioration de cette protection est la technique dite du Write XOR Execute, abréviée WxX. Elle consiste à interdire les pages d'être à la fois accessibles en écriture et exécutables. Il est possible de changer les autorisations en cours de route, ceci dit.

La taille des pages modifier

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.

Comparaison des différentes techniques d'abstraction mémoire modifier

L'abstraction matérielle sert à implémenter beaucoup de fonctionnalités, et ces techniques sont souvent implémentées en même temps. Ce qui fait qu'elles sont souvent confondues, alors que ce sont des concepts sont différents. Pour résumer, l'abstraction mémoire permet de gérer : la relocation, la protection mémoire, l'isolation des processus, la mémoire virtuelle, l'extension de l'espace d'adressage, etc. Ces liens sont résumés dans le tableau ci-dessous.

Avec abstraction mémoire Sans abstraction mémoire
Relocation matérielle Segmentation en mode réel (x86) Segmentation, général Pagination
Abstraction matérielle des processus Oui, relocation matérielle Oui, liée à la traduction d'adresse Impossible
Mémoire virtuelle Non, sauf émulation logicielle Oui, gérée par le processeur et l'OS Non, sauf émulation logicielle
Extension de l'espace d'adressage Oui : registre de base élargi Physical Adress Extension des processeurs 32 bits Commutation de banques
Protection mémoire Registre limite Aucune Registre limite, droits d'accès aux segments Gestion des droits d'accès aux pages Possible, méthodes variées
Partage de mémoire Segments qui se recouvrent, peu pratique Segment partagés Pages partagées Possible, méthodes variées

Par rapport à la pagination, la segmentation a des avantages et des inconvénients. Tous sont liés aux propriétés des segments et pages : les segments sont de grande taille et de taille variable, les pages sont petites et de taille fixe.

L'avantage principal de la segmentation est sa rapidité. Le fait que les segments sont de grande taille fait qu'on a pas besoin d'équivalent aux tables des pages inversée ou multiple, juste d'une table des segments toute simple. De plus, les échanges entre table des pages/segments et registres sont plus rares avec la segmentation. Par exemple, si un programme utilise un segment de 2 gigas, tous les accès dans le segment se feront avec une seule consultation de la table des segments. Alors qu'avec la pagination, il faudra une consultation de la table des pages chaque bloc de 4 kibioctet, au minimum.

Mais les désavantages sont nombreux. Le système d'exploitation doit agencer les segments en RAM, et c'est une tâche complexe. Le fait que les segments puisse changer de taille rend le tout encore plus complexe. Par exemple, si on colle les segments les uns à la suite des autres, changer la taille d'un segment demande de réorganiser tous les segments en RAM, ce qui demande énormément de copies RAM-RAM. Une autre possibilité est de laisser assez d'espace entre les segments, mais cet espace est alors gâché, dans le sens où on ne peut pas y placer un nouveau segment.

Swapper un segment est aussi très long, vu que les segments sont de grande taille, alors que swapper une page est très rapide.