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. Intuitivement, 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.

L'abstraction mémoire implémente plusieurs fonctionnalités complémentaires

L'utilité de l'abstraction matérielle n'est pas évidente, mais sachez qu'elle est si que tous les processeurs modernes la prennent en charge. Elle sert notamment à implémenter les techniques d'abstraction matérielle des processus vues au chapitre précédent, à savoir le fait que chaque processus a son propre espace d'adressage rien que pour lui. Mais elle sert aussi pour d'autres fonctionnalités, comme la mémoire virtuelle, que nous aborderons 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 beaucoup de fonctionnalités avancées ne respectent pas cette règle.

L'abstraction matérielle des processus

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

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

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.

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. Un espace d'adressage de 4 gigas ne contient que 3 gigas de RAM, ce qui fait 1 giga d'adresses inutilisées. Les accès mémoire aux 3 gigas de RAM se font normalement, mais l'accès aux adresses inutilisées lève une exception matérielle "Memory Unavailable". La routine d'interruption de cette exception 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 que l'accès au giga manquant est toujours très lent, parce qu'il se fait depuis le disque dur. D'autres techniques de mémoire virtuelle logicielle font beaucoup mieux, mais nous allons les passer sous silence, vu qu'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. 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 swapfile.

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. Du fait de la localité temporelle, le programme utilise les données chargées depuis le swapfile durant un bon moment avant de passer au bloc 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.

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

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.

Il y a quelques chapitres, 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.

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.

La MMU

La traduction des adresses logiques en adresses physiques se fait par un circuit spécialisé appelé la Memory Management Unit (MMU), qui est souvent intégré directement dans l'interface mémoire. La MMU est souvent associée à une ou plusieurs mémoires caches, qui visent à accélérer la traduction d'adresses logiques en adresses physiques. En effet, nous verrons plus bas que la traduction d'adresse demande d'accéder à des tableaux, gérés par le système d'exploitation, qui sont en mémoire RAM. Aussi, les processeurs modernes incorporent des mémoires caches appelées des Translation Lookaside Buffers, ou encore TLB. Nous nous pouvons pas parler des TLB pour le moment, car nous n'avons pas encore abordé le chapitre sur les mémoires caches, mais un chapitre entier sera dédié aux TLB d'ici peu.

Les MMU intégrées au processeur

D'ordinaire, la MMU est intégrée au processeur. Et elle peut l'être de deux manières. La première en fait un circuit séparé, relié au bus d'adresse. La seconde fusionne la MMU avec l'unité de calcul d'adresse. La première solution est surtout utilisée avec une technique d'abstraction mémoire appelée la pagination, alors que l'autre l'est avec une autre méthode appelée la segmentation. La raison est que la traduction d'adresse avec la segmentation est assez simple : elle demande d'additionner le contenu d'un registre avec l'adresse logique, ce qui est le genre de calcul qu'une unité de calcul d'adresse sait déjà faire. La fusion est donc assez évidente.

Pour donner un exemple, l'Intel 8086 fusionnait l'unité de calcul d'adresse et la MMU. Précisément, il utilisait un même additionneur pour incrémenter le program counter et effectuer des calculs d'adresse liés à la segmentation. Il aurait été logique d'ajouter les pointeurs de pile avec, mais ce n'était pas possible. La raison est que le pointeur de pile ne peut pas être envoyé directement sur le bus d'adresse, vu qu'il doit passer par une phase de traduction en adresse physique liée à la segmentation.

Les MMU séparées du processeur, sur la carte mère

Il a existé des processeurs avec une MMU externe, soudée sur la carte mère.

Par exemple, les processeurs Motorola 68000 et 68010 pouvaient être combinés avec une MMU de type Motorola 68451. Elle supportait des versions simplifiées de la segmentation et de la pagination. Au minimum, elle ajoutait un support de la protection mémoire contre certains accès non-autorisés. La gestion de la mémoire virtuelle proprement dit n'était possible que si le processeur utilisé était un Motorola 68010, en raison de la manière dont le 68000 gérait ses accès mémoire. La MMU 68451 gérait un espace d'adressage de 16 mébioctets, découpé en maximum 32 pages/segments. On pouvait dépasser cette limite de 32 segments/pages en combinant plusieurs 68451.

Le Motorola 68851 était une MMU qui était prévue pour fonctionner de paire avec le Motorola 68020. Elle gérait la pagination pour un espace d'adressage de 32 bits.

Les processeurs suivants, les 68030, 68040, et 68060, avaient une MMU interne au processeur.

La relocation matérielle

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.

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.

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

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.

La relocation matérielle fait que la relocation est faite par le processeur, pas par l'OS. 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.

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

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.

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.

Pour information, la relocation matérielle avec un registre limite a été implémentée sur plusieurs processeurs assez anciens, notamment sur les anciens supercalculateurs de marque CDC. Un exemple est le fameux CDC 6600, qui implémentait cette technique.

La mémoire virtuelle avec la relocation matérielle

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

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.

La segmentation en mode réel des processeurs x86

Avant de passer à la suite, nous allons voir la technique de segmentation 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, ce qui le place à part des autres formes de segmentation. Il s'agit d'une amélioration de la relocation matérielle, qui 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 protégé rajoute la protection mémoire, en ajoutant des registres limite et une gestion des droits d'accès aux segments, absents en mode réel. De plus, il ajoute un support de la mémoire virtuelle grâce à l'utilisation d'une des segments digne de ce nom, table qui est absente en mode réel ! Mais nous ne pouvons pas parler du mode protégé à ce moment du cours, ni le voir en même temps que le mode réel, à cause d'une différence très importante : l'interprétation des adresses change complètement, comme on le verra dans la suite du cours. Les registres de segment ne mémorisent pas des adresses de base en mode protégé, la relocation se fait de manière moins directe. Nous allons voir le mode réel seul, dans cette section.

Les segments en mode réel

L'idée de la segmentation en mode réel est d'offrir à chaque programme plusieurs espaces d'adressage. Pour cela, la segmentation en mode réel sépare la pile, le tas, le code machine et les données constantes dans quatre segments distincts.

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.

Un point important est que sur ces processeurs, il n'y a pas de table des segments proprement dit. Chaque programme gére de lui-même les adresses de base des segments qu'il manipule. Il n'est en rien aidé par une table des segments gérée par le système d'exploitation.

Chaque segment subit la relocation indépendamment des autres. Pour cela, la meilleure solution est d'utiliser plusieurs registres de base, un par segment. Notons que 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.

Les registres de segments en mode réel

Les processeurs 8086 et le 286 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). Le 386 rajouta deux registres, les registres FS et GS, qui sont utilisés pour les segments de données.

Les registres CS et SS sont adressés implicitement, en fonction de l'instruction exécutée. Les instructions de la pile manipulent le segment associé à la pile, le chargement des instructions se fait dans le segment de code, les instructions arithmétiques et logiques vont chercher leurs opérandes sur le tas, etc. Et donc, 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.

Les segments DS et ES sont, eux aussi, adressés implicitement. Pour cela, les instructions LOAD/STORE sont dupliquées : il y a une instruction LOAD pour le segment DS, une autre pour le segment ES. D'autres instructions lisent leurs opérandes dans un segment par défaut, mais on peut changer ce choix par défaut en précisant le segment voulu. Un exemple est celui de l'instruction CMPSB, qui compare deux octets/bytes : le premier est chargé depuis le segment DS, le second depuis le segment ES.

Un autre exemple est celui de l'instruction MOV avec un opérande en mémoire. Elle lit l'opérande en mémoire depuis le segment DS par défaut. Il est possible de préciser le segment de destination si celui-ci n'est pas DS. Par exemple, l'instruction MOV [A], AX écrit le contenu du registre AX dans l'adresse A du segment DS. Par contre, l'instruction MOV ES:[A], copie le contenu du registre AX das l'adresse A, mais dans le segment ES.

La traduction d'adresse en mode réel

La segmentation en mode réel a pour seul but de permettre à un programme de dépasser la limite des 64 KB autorisée par les adresses de 16 bits. L'idée est que chaque segment a droit à son propre espace de 64 KB. On a ainsi 64 Kb pour le code machine, 64 KB pour la pile, 64 KB pour un segment de données, etc. Les registres de segment mémorisaient la base du segment, les adresses calculées par l'ALU étant des offsets. Ce sont tous des registres de 16 bits, mais ils ne mémorisent pas des adresses physiques de 16 bits, comme nous allons le voir.

L'Intel 8086 utilisait des adresses de 20 bits, ce qui permet d'adresser 1 mébioctet de RAM. Vous pouvez vous demander comment on peut obtenir des adresses de 20 bits alors que les registres de segments font tous 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 décalage de 4 rangs vers la gauche fait que chaque segment a une adresse qui est multiple de 16. Le fait que le décalage soit de 16 bits fait que les segments ont une taille de 64 kibioctets.

`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

Vous aurez peut-être remarqué que le calcul peut déborder, dépasser 20 bits. Mais nous reviendrons là-dessus plus bas. L'essentiel est que la MMU pour la segmentation en mode réel se résume à quelques registres et des additionneurs/soustracteurs.

Un exemple est l'Intel 8086, un des tout premier processeur Intel. Le processeur était découpé en deux portions : l'interface mémoire et le reste du processeur. L'interface mémoire est appelée la Bus Interface Unit, et le reste du processeur est appelé l'Execution Unit. L'interface mémoire contenait les registres de segment, au nombre de 4, ainsi qu'un additionneur utilisé pour traduire les adresses logiques en adresses physiques. Elle contenait aussi une file d'attente où étaient préchargées les instructions.

Sur le 8086, la MMU est fusionnée avec les circuits de gestion du program counter. Les registres de segment sont regroupés avec le program counter dans un même banc de registres. 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. L'idée était de partager l'additionneur, qui servait à la fois à incrémenter le program counter et pour gérer la segmentation. 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. Nous en reparlerons au chapitre suivant.

La MMU du 286 était fusionnée avec l'unité de calcul d'adresse. Elle contient les registres de segments, un comparateur pour détecter les accès hors-segment, et plusieurs additionneurs. Il y a un additionneur pour les calculs d'adresse proprement dit, suivi d'un additionneur pour la relocation.

L'occupation de l'espace d'adressage par les segments

Vous remarquerez qu'avec des registres de segments de 16 bits, on peut gérer 65536 segments différents, chacun de 64 KB. Et cela ne rentre pas dans le mébioctet de mémoire permis avec des adresses de 20 bits. La raison est que plusieurs couples segment+offset pointent vers la même adresse. En tout, chaque adresse peut être adressée par 4096 couples segment+offset différents.

Vous remarquerez aussi qu'avec 4 registres de segment et des segments de 64 KB, on peut remplir au maximum 64 * 6 = 384 KB de RAM, soit bien moins que le mébioctet de mémoire théoriquement adressable. La raison à cela est que plusieurs processus peuvent s'exécuter sur un seul processeur, si l'OS le permet. Mais ce n'était pas le cas à l'époque, le DOS était un OS mono-programmé. La raison est tout autre, comme nous allons le voir dans ce qui suit.

La segmentation en mode réel accepte plusieurs segments par programme

Les programmes peuvent parfaitement répartir leur code machine dans plusieurs segments de code, et faire de même pour les données. La limite de 64 KB par segment est en effet assez limitante, et il n'était pas rare qu'un programme ait besoin de plus juste stocker son code machine ou ses données. La seule contrainte à respecter est que tous les segments doivent être chargés en RAM, il n'y a pas de mémoire virtuelle en mode réel. La seule exception est la pile : elle est forcément dans un segment unique et ne peut pas dépasser 64 KB.

Il faut alors changer de segment à la volée, en remplaçant le segment de code/données par un autre, en modifiant les registres de segment. Pour cela, tous les registres de segment, à l'exception de CS, peuvent être altérés par une instruction d'accès mémoire. Il est possible d'écrire dedans, sans restriction particulière, soit avec une instruction MOV, soit en y copiant le sommet de la pile avec une instruction de dépilage POP. L'absence de sécurité fait que la gestion de ces registres est le fait du programmeur, qui doit redoubler de prudence pour ne pas faire n'importe quoi.

Pour le code machine, le répartir dans plusieurs segments posait des problèmes au niveau des branchements. Si la plupart des branchements sautaient vers une instruction dans le même segment, quelques rares branchements sautaient vers du code machine dans un autre segment. Intel avait prévu le coup et disposait de deux instructions de branchement différentes pour ces deux situations : les near jumps et les far jumps. Les premiers sont des branchements normaux, qui précisent juste l'adresse à laquelle brancher, qui correspond à la position de la fonction dans le segment. Les seconds branchent vers une instruction dans un autre segment, et doivent préciser deux choses : l'adresse de base du segment de destination, et la position de la destination dans le segment. Le branchement met à jour le registre CS avec l'adresse de base, avant de faire le branchement. Ces derniers étaient plus lents, car on n'avait pas à changer de segment et mettre à jour l'état du processeur.

Il y avait la même pour l'instruction d'appel de fonction, avec deux versions de cette instruction. La première version, le near call est un appel de fonction normal, la fonction appelée est dans le segment en cours. Avec la seconde version, le far call, la fonction appelée est dans un segment différent. L'instruction a là aussi besoin de deux opérandes : l'adresse de base du segment de destination, et la position de la fonction dans le segment. Un far call met à jour le registre CS avec l'adresse de base, ce qui fait que les far call sont plus lents que les near call. Il existe aussi la même chose, pour les instructions de retour de fonction, avec une instruction de retour de fonction normale et une instruction de retour qui renvoie vers un autre segment, qui sont respectivement appelées near return et far return. Là encore, il faut préciser l'adresse du segment de destination dans le second cas.

La même chose est possible pour les segments de données. Sauf que cette fois-ci, ce sont les pointeurs qui sont modifiés. pour rappel, les pointeurs sont, en programmation, des variables qui contiennent des adresses. Lors de la compilation, ces pointeurs sont placés soit dans un registre, soit dans les instructions (adressage absolu), ou autres. Ici, il existe deux types de pointeurs, appelés near pointer et far pointer. Vous l'avez deviné, les premiers sont utilisés pour localiser les données dans le segment en cours d'utilisation, alors que les seconds pointent vers une donnée dans un autre segment. Là encore, la différence est que le premier se contente de donner la position dans le segment, alors que les seconds rajoutent l'adresse de base du segment. Les premiers font 16 bits, alors que les seconds en font 32 : 16 bits pour l'adresse de base et 16 pour l'offset.

Les modèles mémoire en mode réel

Il n'était pas nécessaire d'avoir 4 à 6 segments différents, un programme pouvait se débrouiller avec seulement 1 ou 2 segments. D'autres programmes faisaient l'inverse, à savoir qu'ils avaient plus de 6 segments. Suivant le nombre de segments utilisés, la configuration des registres n'était pas la même. Les configurations possibles sont appélées des modèle mémoire, et il y en a en tout 6. En voici la liste :

Modèle mémoire	Configuration des segments	Configuration des registres	Pointeurs utilisés	Branchements utilisés
Tiny*	Segment unique pour tout le programme	CS=DS=SS	near uniquement	near uniquement
Small	Segment de donnée séparé du segment de code, pile dans le segment de données	DS=SS	near uniquement	near uniquement
Medium	Plusieurs segments de code unique, un seul segment de données	CS, DS et SS sont différents	near et far	near uniquement
Compact	Segment de code unique, plusieurs segments de données	CS, DS et SS sont différents	near uniquement	near et far
Large	Plusieurs segments de code, plusieurs segments de données	CS, DS et SS sont différents	near et far	near et far

Le mode réel sur les 286 et plus : la ligne d'adresse A20

Pour résumer, le registre de segment contient des adresses de 20 bits, dont les 4 bits de poids faible sont à 0. Et il se voit ajouter un offset de 16 bits. Intéressons-nous un peu à l'adresse maximale que l'on peut calculer avec ce système. Nous allons l'appeler l'adresse maximale de segmentation. Elle vaut :

`1111 1111 1111 11110000`	Registre de segment -	16 bits, décalé de 4 bits vers la gauche
`+` `1111 1111 1111 1111`	Décalage/Offset	16 bits

`1 0000 1111 1111 1110 1111`	Adresse finale	20 bits

Le résultat n'est pas l'adresse maximale codée sur 20 bits, car l'addition déborde. Elle donne un résultat qui dépasse l'adresse maximale permis par les 20 bits, il y a un 21ème bit en plus. De plus, les 20 bits de poids faible ont une valeur bien précise. Ils donnent la différence entre l'adresse maximale permise sur 20 bit, et l'adresse maximale de segmentation. Les bits 1111 1111 1110 1111 traduits en binaire donnent 65 519; auxquels il faut ajouter l'adresse 1 0000 0000 0000 0000. En tout, cela fait 65 520 octets adressables en trop. En clair : on dépasse la limite du mébioctet de 65 520 octets. Le résultat est alors très différent selon que l'on parle des processeurs avant le 286 ou après.

Avant le 286, le bus d'adresse faisait exactement 20 bits. Les adresses calculées ne pouvaient pas dépasser 20 bits. L'addition générait donc un débordement d'entier, géré en arithmétique modulaire. En clair, les bits de poids fort au-delà du vingtième sont perdus. Le calcul de l'adresse débordait et retournait au début de la mémoire, sur les 65 520 premiers octets de la mémoire RAM.

Le 80286 en mode réel gère des adresses de base de 24 bits, soit 4 bits de plus que le 8086. Le résultat est qu'il n'y a pas de débordement. Les bits de poids fort sont conservés, même au-delà du 20ème. En clair, la segmentation permettait de réellement adresser 65 530 octets au-delà de la limite de 1 mébioctet. La portion de mémoire adressable était appelé la High memory area, qu'on va abrévier en HMA.

Espace d'adressage du 286
Adresses en héxadécimal	Zone de mémoire
10 FFF0 à FF FFFF	Mémoire étendue, au-delà du premier mébioctet
10 0000 à 10 FFEF	High Memory Area
0 à 0F FFFF	Mémoire adressable en mode réel

En conséquence, les applications peuvent utiliser plus d'un mébioctet de RAM, mais au prix d'une rétrocompatibilité imparfaite. Quelques programmes DOS ne marchaient pus à cause de ça. D'autres fonctionnaient convenablement et pouvaient adresser les 65 520 octets en plus.

Pour résoudre ce problème, les carte mères ajoutaient un petit circuit relié au 21ème bit d'adresse, nommé A20 (pas d'erreur, les fils du bus d'adresse sont numérotés à partir de 0). Le circuit en question pouvait mettre à zéro le fil d'adresse, ou au contraire le laisser tranquille. En le forçant à 0, le calcul des adresses déborde comme dans le mode réel des 8086. Mais s'il ne le fait pas, la high memory area est adressable. Le circuit était une simple porte ET, qui combinait le 21ème bit d'adresse avec un signal de commande A20 provenant d'ailleurs.

Le signal de commande A20 était géré par le contrôleur de clavier, qui était soudé à la carte mère. Le contrôleur en question ne gérait pas que le clavier, il pouvait aussi RESET le processeur, alors gérer le signal de commande A20 n'était pas si problématique. Quitte à avoir un microcontrôleur sur la carte mère, autant s'en servir au maximum... La gestion du bus d'adresse étaitdonc gérable au clavier. D'autres carte mères faisaient autrement et préféraient ajouter un interrupteur, pour activer ou non la mise à 0 du 21ème bit d'adresse.

Il faut noter que le signal de commande A20 était mis à 1 en mode protégé, afin que le 21ème bit d'adresse soit activé.

Le 80386 ajouta deux registres de segment, les registres FS et GS. Les processeurs 386 gèrent un mode réel similaire à celui du 286, mais émulé. Un autre mode de segmentation est ajouté avec le 386 : 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é (qui utilise une autre forme de segmentation). 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. Les processeurs x86 64 bits désactivent la segmentation en mode 64 bits.

La segmentation avec une table des segments

La segmentation avec une table des segments est apparue sur des processeurs assez anciens, le tout premier étant le Burrough 5000. Elle a ensuite été utilisée sur les processeurs x86 de nos PCs, à partir du 286 d'Intel. Tout comme la segmentation en mode réel, la segmentation attribue plusieurs segments par programmes ! Sauf que le nombre de segments géré par le processeur est plus important. Et cela a des répercutions sur la manière dont la traduction d'adresse est effectuée.

Pourquoi plusieurs segments par programme ?

La taille et le nombre des segments varie grandement d'un processeur à l'autre. Certains ne supportent qu'un petit nombre de segments par processus, les segments sont alors assez gros. D'autres utilisent un grand nombre de segments, qui sont individuellement plus petits. La différence entre ces deux méthodes permet de faire la différence entre segmentation à granularité grossière et segmentation à granularité fine.

La segmentation à granularité grossière

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. Les overlays les plus importants étaient en permanence en RAM, mais les autres étaient faisaient un va-et-vient entre RAM et disque dur. Ils étaient chargés en RAM lors de leur utilisation, puis sauvegardés sur le disque dur quand ils étaient inutilisés. Le va-et-vient des overlays entre RAM et 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.

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. Par contre, cela demande l'intervention du programmeur, qui doit découper le programme en segments/overlays de lui-même. Sans cela, la segmentation n'est pas très utile.

La segmentation à granularité fine

La segmentation à granularité fine pousse le concept encore plus loin. Avec elle, il y a idéalement un segment par entité manipulée par le programme, un segment pour chaque structure de donnée et/ou chaque objet. Par exemple, un tableau aura son propre segment, ce qui est idéal pour détecter les accès hors tableau. Pour les listes chainées, chaque élément de la liste aura son propre segment. Et ainsi de suite, chaque variable agrégée (non-primitive), chaque structure de donnée, chaque objet, chaque instance d'une classe, a son propre segment. Diverses fonctionnalités supplémentaires peuvent être ajoutées, ce qui transforme le processeur en véritable processeur orienté objet, mais passons ces détails pour le moment.

Vu que les segments correspondent à des objets manipulés par le programme, on peut deviner que leur nombre évolue au cours du temps. En effet, les programmes modernes peuvent demander au système d'exploitation du rab de mémoire pour allouer une nouvelle structure de données. Avec la segmentation à granularité fine, cela demande d'allouer un nouveau segment à chaque nouvelle allocation mémoire, à chaque création d'une nouvelle structure de données ou d'un objet. De plus, les programmes peuvent libérer de la mémoire, en supprimant les structures de données ou objets dont ils n'ont plus besoin. Avec la segmentation à granularité fine, cela revient à détruire le segment alloué pour ces objets/structures de données. Le nombre de segments est donc dynamique, il change au cours de l'exécution du programme.

La relocation avec la segmentation

La segmentation avec une table des segment utilise, comme son nom l'indique, une ou plusieurs tables des segments. Pour rappel, celle-ci est une table qui mémorise, pour chaque segment, quelles sont ses adresses de base et limite. Avec cette forme de segmentation, la table des segments doit respecter plusieurs contraintes. Premièrement, il y a plusieurs segments par programmes. Deuxièmement, le nombre de segments est variable : certains programmes se contenteront d'un seul segment, d'autres de dizaine, d'autres plusieurs centaines, etc. La solution la plus pratique est d'utiliser une table de segment par processus/programme.

La traduction d'adresse additionne 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 une par segment associé au programme. Il faut donc sélectionner la bonne adresse de base, le bon segment. Pour cela, les segments sont numérotés, le nombre s'appelant un indice de segment, appelé sélecteur de segment dans la terminologie Intel. Les segments sont placés dans la table des segments les uns après les autres, dans l'ordre de numérotation. La table des segments est donc un tableau de segment, et l'indice de segment n'est autre que l'indice du segment dans ce tableau.

Il n'y a pas de registre de segment proprement dit, qui mémoriserait l'adresse de base. A la place, les registres de segment mémorisent des sélecteurs de segment. De fait, tout se passe comme si les registres de relocation, qui mémorisent une adresse de base, étaient remplacés par des registres qui mémorisent des sélecteurs de segment. L'adresse manipulée par le processeur se déduit en combinant l'indice de segment qui sélectionne le segment voulu, avec un décalage (offset) qui donne la position de la donnée dans ce segment.

L'accès à la table des segments se fait automatiquement à chaque accès mémoire. 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.

Pour effectuer automatiquement l'accès à 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 l'indice de segment pour adresser le descripteur de segment adéquat.

Un point important est que la table des segments n'est pas accessible pour le programme en cours d'exécution. Il ne peut pas lire le contenu de la table des segments, et encore moins la modifier. L'accès se fait seulement de manière indirecte, en faisant usage des indices de segments, mais c'est un adressage indirect. Seul le système d'exploitation peut lire ou écrire la table des segments directement.

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

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, ou compare la taille limite avec le décalage. L'information est lue depuis la table des segments à chaque accès.

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.

La mémoire virtuelle avec la segmentation

La mémoire virtuelle 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. Il faut dire que l'implémentation de la mémoire virtuelle est beaucoup plus simple avec la segmentation, comparé à la relocation matérielle. Le remplacement des registres de base par des sélecteurs de segment facilite grandement l'implémentation.

Le problème de la mémoire virtuelle est que les segments peuvent être swappés sur le disque dur n'importe quand, sans que le programme soit prévu. Le swapping est réalisé par une interruption de l'OS, qui peut interrompre le programme n'importe quand. Et si un segment est swappé, le registre de base correspondant devient invalide, il point sur une adresse en RAM où le segment était, mais n'est plus. De plus, les segments peuvent être déplacés en mémoire, là encore n'importe quand et d'une manière invisible par le programme, ce qui fait que les registres de base adéquats doivent être modifiés.

Si le programme entier est swappé d'un coup, comme avec la relocation matérielle simple, cela ne pose pas de problèmes. Mais dès qu'on utilise plusieurs registres de base par programme, les choses deviennent soudainement plus compliquées. Le problème est qu'il n'y a pas de mécanismes pour choisir et invalider le registre de base adéquat quand un segment est déplacé/swappé. En théorie, on pourrait imaginer des systèmes qui résolvent le problème au niveau de l'OS, mais tous ont des problèmes qui font que l'implémentation est compliquée ou que les performances sont ridicules.

L'usage d'une table des segments accédée à chaque accès résout complètement le problème. La table des segments est accédée à chaque accès mémoire, elle sait si le segment est swappé ou non, chaque accès vérifie si le segment est en mémoire et quelle est son adresse de base. On peut changer le segment de place n'importe quand, le prochain accès récupérera des informations à jour dans la table des segments.

L'implémentation de la mémoire virtuelle avec la segmentation est simple : il suffit d'ajouter un bit dans les descripteurs de segments, qui indique si le segment est swappé ou non. Tout le reste, la gestion de ce bit, du swap, et tout ce qui est nécessaire, est délégué au système d'exploitation. Lors de chaque accès mémoire, le processeur vérifie ce bit avant de faire la traduction d'adresse, et déclenche une exception matérielle si le bit indique que le segment est swappé. L'exception matérielle est gérée par l'OS.

Le partage de segments

Il est possible de partager un segment entre plusieurs applications. 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.

La première solution pour cela est de configurer les tables de segment convenablement. 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. Mais cette méthode de partage des segments a plusieurs défauts.

Premièrement, les sélecteurs de segments ne sont pas les mêmes d'un processus à l'autre, pour un même segment. Le segment partagé peut correspondre au segment numéro 80 dans le premier processus, au segment numéro 1092 dans le second processus. Rien n'impose que les sélecteurs de segment soient les mêmes d'un processus à l'autre, pour un segment identique.

Deuxièmement, les adresses limite et de base sont dupliquées dans plusieurs tables de segments. En soi, cette redondance est un souci mineur. Mais une autre conséquence est une question de sécurité : que se passe-t-il si jamais un processus a une table des segments corrompue ? Il se peut que pour un segment identique, deux processus n'aient pas la même adresse limite, ce qui peut causer des failles de sécurité. Un processus peut alors subir un débordement de tampon, ou tout autre forme d'attaque.

Illustration du partage d'un segment entre deux applications.

Une seconde solution, complémentaire, utilise une table de segment globale, qui mémorise des segments partagés ou accessibles par tous les processus. Les défauts de la méthode précédente disparaissent avec cette technique : un segment est identifié par un sélecteur unique pour tous les processus, il n'y a pas de duplication des descripteurs de segment. Par contre, elle a plusieurs défauts.

Le défaut principal est que cette table des segments est accessible par tous les processus, impossible de ne partager ses segments qu'avec certains pas avec les autres. Un autre défaut est que les droits d'accès à un segment partagé sont identiques pour tous les processus. Impossible d'avoir un segment partagé accessible en lecture seule pour un processus, mais accessible en écriture pour un autre. Il est possible de corriger ces défauts, mais nous en parlerons dans la section sur les architectures à capacité.

L'extension d'adresse avec la segmentation

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 adresses de base soient 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.

Le mode protégé des processeurs x86

L'Intel 80286, aussi appelé 286, ajouta un mode de segmentation séparé du mode réel, qui ajoute une protection mémoire à la segmentation, ce qui lui vaut le nom de mode protégé. Dans ce mode, les registres de segment ne contiennent pas des adresses de base, mais des sélecteurs de segments qui sont utilisés pour l'accès à la table des segments en mémoire RAM.

Le 286 bootait en mode réel, puis le système d'exploitation devait faire quelques manipulations pour passer en mode protégé. Le 286 était pensé pour être rétrocompatible au maximum avec le 80186. Mais 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é. Un mode de compatibilité permettait cependant 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ées sur le 286.

Vint ensuite le processeur 80386, renommé en 386 quelques années plus tard. Sur ce processeur, les modes réel et protégé sont conservés tel quel, à une différence près : toutes les adresses passent à 32 bits, qu'il s'agisse de l'adresse physique envoyée sur le bus, de l'adresse de base du segment ou des offsets. Le processeur peut donc adresser un grand nombre de segments : 2^32, soit plus de 4 milliards. Les segments grandissent aussi et passent de 64 KB maximum à 4 gibioctets maximum. Mais surtout : le 386 ajouta le support de la pagination en plus de la segmentation. Ces modifications ont été conservées sur les processeurs 32 bits ultérieurs.

Les processeurs gèrent deux types de tables des segments : une table locale pour chaque processus, et une table globale partagée entre tous les processus.

La table globale est utilisée pour les segments du noyau et la mémoire partagée entre processus. Un défaut est qu'un segment partagé par la table globale est visible par tous les processus, avec les mêmes droits d'accès. Ce qui fait que cette méthode était peu utilisée en pratique. La table globale mémorise aussi des pointeurs vers les tables locales, avec un descripteur de segment par table locale.
La table locale gère les segments de son processus. Il est possible d'avoir plusieurs tables locales, mais une seule doit être active, vu que le processeur ne peut exécuter qu'un seul processus en même temps. Chaque table locale définit 8192 segments, pareil pour la table globale.

Sur les processeurs x86 32 bits, 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.

Les indices de segment sont appelés des sélecteurs de segment. Ils ont une taille de 16 bits. Les 16 bits sont organisés comme suit :

13 bits pour le numéro du segment dans la table des segments, l'indice de segment proprement dit ;
un bit qui précise s'il faut accéder à la table des segments globale ou locale ;
deux bits qui indiquent le niveau de privilège de l'accès au segment (les 4 niveaux de protection, dont l'espace noyau et utilisateur).

En tout, l'indice permet de gérer 8192 segments pour la table locale et 8192 segments de la table globale.

La segmentation sur les processeurs Burrough B5000 et plus

Le Burrough B5000 est un très vieil ordinateur, commercialisé à partir de l'année 1961. Ses successeurs reprennent globalement la même architecture. C'était une machine à pile, doublé d'une architecture taguée, choses très rare de nos jours. Mais ce qui va nous intéresser dans ce chapitre est que ce processeur incorporait la segmentation, avec cependant une différence de taille : un programme avait accès à un grand nombre de segments. La limite était de 1024 segments par programme ! Il va de soi que des segments plus petits favorise l'implémentation de la mémoire virtuelle, mais complexifie la relocation et le reste, comme nous allons le voir.

Le processeur gère deux types de segments : les segments de données et de procédure/fonction. Les premiers mémorisent un bloc de données, dont le contenu est laissé à l'appréciation du programmeur. Les seconds sont des segments qui contiennent chacun une procédure, une fonction. L'usage des segments est donc différent de ce qu'on a sur les processeurs x86, qui n'avaient qu'un segment unique pour l'intégralité du code machine. Un seul segment de code machine x86 est découpé en un grand nombre de segments de code sur les processeurs Burrough.

La table des segments contenait 1024 entrées de 48 bits chacune. Fait intéressant, chaque entrée de la table des segments pouvait mémoriser non seulement un descripteur de segment, mais aussi une valeur flottante ou d'autres types de données ! Parler de table des segments est donc quelque peu trompeur, car cette table ne gère pas que des segments, mais aussi des données. La documentation appelaiat cette table la Program Reference Table, ou PRT.

La raison de ce choix quelque peu bizarre est que les instructions ne gèrent pas d'adresses proprement dit. Tous les accès mémoire à des données en-dehors de la pile passent par la segmentation, ils précisent tous un indice de segment et un offset. Pour éviter d'allouer un segment pour chaque donnée, les concepteurs du processeur ont décidé qu'une entrée pouvait contenir directement la donnée entière à lire/écrire.

La PRT supporte trois types de segments/descripteurs : les descripteurs de données, les descripteurs de programme et les descripteurs d'entrées-sorties. Les premiers décrivent des segments de données. Les seconds sont associés aux segments de procédure/fonction et sont utilisés pour les appels de fonction (qui passent, eux aussi, par la segmentation). Le dernier type de descripteurs sert pour les appels systèmes et les communications avec l'OS ou les périphériques.

Chaque entrée de la PRT contient un tag, une suite de bit qui indique le type de l'entrée : est-ce qu'elle contient un descripteur de segment, une donnée, autre. Les descripteurs contiennent aussi un bit de présence qui indique si le segment a été swappé ou non. Car oui, les segments pouvaient être swappés sur ce processeur, ce qui n'est pas étonnant vu que les segments sont plus petits sur cette architecture. Le descripteur contient aussi l'adresse de base du segment ainsi que sa taille, et diverses informations pour le retrouver sur le disque dur s'il est swappé.

L'adresse mémorisée ne faisait que 15 bits, ce qui permettait d'adresse 32 kibi-mots, soit 192 kibioctets de mémoire. Diverses techniques d'extension d'adressage étaient disponibles pour contourner cette limitation. Outre l'usage de l'overlay, le processeur et l'OS géraient aussi des identifiants d'espace d'adressage et en fournissaient plusieurs par processus. Les processeurs Borrough suivants utilisaient des adresses plus grandes, de 20 bits, ce qui tempérait le problème.

Structure d'un mot mémoire sur le B6700.

Les architectures à capacités

Les architectures à capacité utilisent la segmentation à granularité fine, mais ajoutent des mécanismes de protection mémoire assez particuliers, qui font que les architectures à capacité se démarquent du reste. Les architectures de ce type sont très rares et sont des processeurs assez anciens. Le premier d'entre eux était le Plessey System 250, qui date de 1969. Il fu suivi par le CAP computer, vendu entre les années 70 et 77. En 1978, le System/38 d'IBM a eu un petit succès commercial. En 1980, la Flex machine a aussi été vendue, mais à très peu d'examplaires, comme les autres architectures à capacité. Et enfin, en 1981, l'architecture à capacité la plus connue, l'Intel iAPX 432 a été commercialisée. Depuis, la seule architecture de ce type est en cours de développement. Il s'agit de l'architecture CHERI, dont la mise en projet date de 2014.

Le partage de la mémoire sur les architectures à capacités

Le partage de segment est grandement modifié sur les architectures à capacité. Avec la segmentation normale, il y a une table de segment par processus. Les conséquences sont assez nombreuses, mais la principale est que partager un segment entre plusieurs processus est compliqué. Les défauts ont été évoqués plus haut. Les sélecteurs de segments ne sont pas les mêmes d'un processus à l'autre, pour un même segment. De plus, les adresses limite et de base sont dupliquées dans plusieurs tables de segments, et cela peut causer des problèmes de sécurité si une table des segments est modifiée et pas l'autre. Et il y a d'autres problèmes, tout aussi importants.

A l'opposé, les architectures à capacité utilisent une table des segments unique pour tous les processus. La table des segments unique sera appelée dans de ce qui suit la table des segments globale, ou encore la table globale. En conséquence, les adresses de base et limite ne sont présentes qu'en un seul exemplaire par segment, au lieu d'être dupliquées dans autant de processus que nécessaire. De plus, cela garantit que l'indice de segment est le même quelque soit le processus qui l'utilise.

Un défaut de cette approche est au niveau des droits d'accès. Avec la segmentation normale, les droits d'accès pour un segment sont censés changer d'un processus à l'autre. Par exemple, tel processus a accès en lecture seule au segment, l'autre seulement en écriture, etc. Mais ici, avec une table des segments uniques, cela ne marche plus : incorporer les droits d'accès dans la table des segments ferait que tous les processus auraient les mêmes droits d'accès au segment. Et il faut trouver une solution.

Les capacités sont des pointeurs protégés

Pour éviter cela, les droits d'accès sont combinés avec les sélecteurs de segments. Les sélecteurs des segments sont remplacés par des capacités, des pointeurs particuliers formés en concaténant l'indice de segment avec les droits d'accès à ce segment. Si un programme veut accéder à une adresse, il fournit une capacité de la forme "sélecteur:droits d'accès", et un décalage qui indique la position de l'adresse dans le segment.

Il est impossible d'accéder à un segment sans avoir la capacité associée, c'est là une sécurité importante. Un accès mémoire demande que l'on ait la capacité pour sélectionner le bon segment, mais aussi que les droits d'accès en permettent l'accès demandé. Par contre, les capacités peuvent être passées d'un programme à un autre sans problème, les deux programmes pourront accéder à un segment tant qu'ils disposent de la capacité associée.

Mais cette solution a deux problèmes très liés. Au niveau des sélecteurs de segment, le problème est que les sélecteur ont une portée globale. Avant, l'indice de segment était interne à un programme, un sélecteur ne permettait pas d'accéder au segment d'un autre programme. Sur les architectures à capacité, les sélecteurs ont une portée globale. Si un programme arrive à forger un sélecteur qui pointe vers un segment d'un autre programme, il peut théoriquement y accéder, à condition que les droits d'accès le permettent. Et c'est là qu'intervient le second problème : les droits d'accès ne sont plus protégés par l'espace noyau. Les droits d'accès étaient dans la table de segment, accessible uniquement en espace noyau, ce qui empêchait un processus de les modifier. Avec une capacité, il faut ajouter des mécanismes de protection qui empêchent un programme de modifier les droits d'accès à un segment et de générer un indice de segment non-prévu.

La première sécurité est qu'un programme ne peut pas créer une capacité, seul le système d'exploitation le peut. Les capacités sont forgées lors de l'allocation mémoire, ce qui est du ressort de l'OS. Pour rappel, un programme qui veut du rab de mémoire RAM peut demander au système d'exploitation de lui allouer de la mémoire supplémentaire. Le système d'exploitation renvoie alors un pointeurs qui pointe vers un nouveau segment. Le pointeur est une capacité. Il doit être impossible de forger une capacité, en-dehors d'une demande d'allocation mémoire effectuée par l'OS. Typiquement, la forge d'une capacité se fait avec des instructions du processeur, que seul l'OS peut éxecuter (pensez à une instruction qui n'est accessible qu'en espace noyau).

La seconde protection est que les capacités ne peuvent pas être modifiées sans raison valable, que ce soit pour l'indice de segment ou les droits d'accès. L'indice de segment ne peut pas être modifié, quelqu'en soit la raison. Pour les droits d'accès, la situation est plus compliquée. Il est possible de modifier ses droits d'accès, mais sous conditions. Réduire les droits d'accès d'une capacité est possible, que ce soit en espace noyau ou utilisateur, pas l'OS ou un programme utilisateur, avec une instruction dédiée. Mais augmenter les droits d'accès, seul l'OS peut le faire avec une instruction précise, souvent exécutable seulement en espace noyau.

Les capacités peuvent être copiées, et même transférées d'un processus à un autre. Les capacités peuvent être détruites, ce qui permet de libérer la mémoire utilisée par un segment. La copie d'une capacité est contrôlée par l'OS et ne peut se faire que sous conditions. La destruction d'une capacité est par contre possible par tous les processus. La destruction ne signifie pas que le segment est effacé, il est possible que d'autres processus utilisent encore des copies de la capacité, et donc le segment associé. On verra quand la mémoire est libérée plus bas.

Protéger les capacités demande plusieurs conditions. Premièrement, le processeur doit faire la distinction entre une capacité et une donnée. Deuxièmement, les capacités ne peuvent être modifiées que par des instructions spécifiques, dont l'exécution est protégée, réservée au noyau. En clair, il doit y avoir une séparation matérielle des capacités, qui sont placées dans des registres séparés. Pour cela, deux solutions sont possibles : soit les capacités remplacent les adresses et sont dispersées en mémoire, soit elles sont regroupées dans un segment protégé.

La liste des capacités

Avec la première solution, on regroupe les capacités dans un segment protégé. Chaque programme a accès à un certain nombre de segments et à autant de capacités. Les capacités d'un programme sont souvent regroupées dans une liste de capacités, appelée la C-list. Elle est généralement placée en mémoire RAM. Elle est ce qu'il reste de la table des segments du processus, sauf que cette table ne contient pas les adresses du segment, qui sont dans la table globale. Tout se passe comme si la table des segments de chaque processus est donc scindée en deux : la table globale partagée entre tous les processus contient les informations sur les limites des segments, la C-list mémorise les droits d'accès et les sélecteurs pour identifier chaque segment. C'est un niveau d'indirection supplémentaire par rapport à la segmentation usuelle.

La liste de capacité est lisible par le programme, qui peut copier librement les capacités dans les registres. Par contre, la liste des capacités est protégée en écriture. Pour le programme, il est impossible de modifier les capacités dedans, impossible d'en rajouter, d'en forger, d'en retirer. De même, il ne peut pas accéder aux segments des autres programmes : il n'a pas les capacités pour adresser ces segments.

Pour protéger la C-list en écriture, la solution la plus utilisée consiste à placer la C-list dans un segment dédié. Le processeur gère donc plusieurs types de segments : les segments de capacité pour les C-list, les autres types segments pour le reste. Un défaut de cette approche est que les adresses/capacités sont séparées des données. Or, les programmeurs mixent souvent adresses et données, notamment quand ils doivent manipuler des structures de données comme des listes chainées, des arbres, des graphes, etc.

L'usage d'une C-list permet de se passer de la séparation entre espace noyau et utilisateur ! Les segments de capacité sont eux-mêmes adressés par leur propre capacité, avec une capacité par segment de capacité. Le programme a accès à la liste de capacité, comme l'OS, mais leurs droits d'accès ne sont pas les mêmes. Le programme a une capacité vers la C-list qui n'autorise pas l'écriture, l'OS a une autre capacité qui accepte l'écriture. Les programmes ne pourront pas forger les capacités permettant de modifier les segments de capacité. Une méthode alternative est de ne permettre l'accès aux segments de capacité qu'en espace noyau, mais elle est redondante avec la méthode précédente et moins puissante.

Les capacités dispersées, les architectures taguées

Une solution alternative laisse les capacités dispersées en mémoire. Les capacités remplacent les adresses/pointeurs, et elles se trouvent aux mêmes endroits : sur la pile, dans le tas. Comme c'est le cas dans les programmes modernes, chaque allocation mémoire renvoie une capacité, que le programme gére comme il veut. Il peut les mettre dans des structures de données, les placer sur la pile, dans des variables en mémoire, etc. Mais il faut alors distinguer si un mot mémoire contient une capacité ou une autre donnée, les deux ne devant pas être mixés.

Pour cela, chaque mot mémoire se voit attribuer un certain bit qui indique s'il s'agit d'un pointeur/capacité ou d'autre chose. Mais cela demande un support matériel, ce qui fait que le processeur devient ce qu'on appelle une architecture à tags, ou tagged architectures. Ici, elles indiquent si le mot mémoire contient une adresse:capacité ou une donnée.

L'inconvénient est le cout en matériel de cette solution. Il faut ajouter un bit à chaque case mémoire, le processeur doit vérifier les tags avant chaque opération d'accès mémoire, etc. De plus, tous les mots mémoire ont la même taille, ce qui force les capacités à avoir la même taille qu'un entier. Ce qui est compliqué.

Les registres de capacité

Les architectures à capacité disposent de registres spécialisés pour les capacités, séparés pour les entiers. La raison principale est une question de sécurité, mais aussi une solution pragmatique au fait que capacités et entiers n'ont pas la même taille. Les registres dédiés aux capacités ne mémorisent pas toujours des capacités proprement dites. A la place, ils mémorisent des descripteurs de segment, qui contiennent l'adresse de base, limite et les droits d'accès. Ils sont utilisés pour la relocation des accès mémoire ultérieurs. Ils sont en réalité identiques aux registres de relocation, voire aux registres de segments. Leur utilité est d'accélérer la relocation, entre autres.

Les processeurs à capacité ne gèrent pas d'adresses proprement dit, comme pour la segmentation avec plusieurs registres de relocation. Les accès mémoire doivent préciser deux choses : à quel segment on veut accéder, à quelle position dans le segment se trouve la donnée accédée. La première information se trouve dans le mal nommé "registre de capacité", la seconde information est fournie par l'instruction d'accès mémoire soit dans un registre (Base+Index), soit en adressage base+offset.

Les registres de capacités sont accessibles à travers des instructions spécialisées. Le processeur ajoute des instructions LOAD/STORE pour les échanges entre table des segments et registres de capacité. Ces instructions sont disponibles en espace utilisateur, pas seulement en espace noyau. Lors du chargement d'une capacité dans ces registres, le processeur vérifie que la capacité chargée est valide, et que les droits d'accès sont corrects. Puis, il accède à la table des segments, récupère les adresses de base et limite, et les mémorise dans le registre de capacité. Les droits d'accès et d'autres méta-données sont aussi mémorisées dans le registre de capacité. En somme, l'instruction de chargement prend une capacité et charge un descripteur de segment dans le registre.

Avec ce genre de mécanismes, il devient difficile d’exécuter certains types d'attaques, ce qui est un gage de sureté de fonctionnement indéniable. Du moins, c'est la théorie, car tout repose sur l'intégrité des listes de capacité. Si on peut modifier celles-ci, alors il devient facile de pouvoir accéder à des objets auxquels on n’aurait pas eu droit.

Le recyclage de mémoire matériel

Les architectures à capacité séparent les adresses/capacités des nombres entiers. Et cela facilite grandement l'implémentation de la garbage collection, ou recyclage de la mémoire, à savoir un ensemble de techniques logicielles qui visent à libérer la mémoire inutilisée.

Rappelons que les programmes peuvent demander à l'OS un rab de mémoire pour y placer quelque chose, généralement une structure de donnée ou un objet. Mais il arrive un moment où cet objet n'est plus utilisé par le programme. Il peut alors demander à l'OS de libérer la portion de mémoire réservée. Sur les architectures à capacité, cela revient à libérer un segment, devenu inutile. La mémoire utilisée par ce segment est alors considérée comme libre, et peut être utilisée pour autre chose. Mais il arrive que les programmes ne libèrent pas le segment en question. Soit parce que le programmeur a mal codé son programme, soit parce que le compilateur n'a pas fait du bon travail ou pour d'autres raisons.

Pour éviter cela, les langages de programmation actuels incorporent des garbage collectors, des morceaux de code qui scannent la mémoire et détectent les segments inutiles. Pour cela, ils doivent identifier les adresses manipulées par le programme. Si une adresse pointe vers un objet, alors celui-ci est accessible, il sera potentiellement utilisé dans le futur. Mais si aucune adresse ne pointe vers l'objet, alors il est inaccessible et ne sera plus jamais utilisé dans le futur. On peut libérer les objets inaccessibles.

Identifier les adresses est cependant très compliqué sur les architectures normales. Sur les processeurs modernes, les garbage collectors scannent la pile à la recherche des adresses, et considèrent tout mot mémoire comme une adresse potentielle. Mais les architectures à capacité rendent le recyclage de la mémoire très facile. Un segment est accessible si le programme dispose d'une capacité qui pointe vers ce segment, rien de plus. Et les capacités sont facilement identifiables : soit elles sont dans la liste des capacités, soit on peut les identifier à partir de leur tag.

Le recyclage de mémoire était parfois implémenté directement en matériel. En soi, son implémentation est assez simple, et peu être réalisé dans le microcode d'un processeur. Une autre solution consiste à utiliser un second processeur, spécialement dédié au recyclage de mémoire, qui exécute un programme spécialement codé pour. Le programme en question est placé dans une mémoire ROM, reliée directement à ce second processeur.

L'intel iAPX 432

Voyons maintenat une architecture à capacité assez connue : l'Intel iAPX 432. Oui, vous avez bien lu : Intel a bel et bien réalisé un processeur orienté objet dans sa jeunesse. La conception du processeur Intel iAPX 432 commença en 1975, afin de créer un successeur digne de ce nom aux processeurs 8008 et 8080.

La conception du processeur Intel iAPX 432 commença en 1975, afin de créer un successeur digne de ce nom aux processeurs 8008 et 8080. Ce processeur s'est très faiblement vendu en raison de ses performances assez désastreuses et de défauts techniques certains. Par exemple, ce processeur était une machine à pile à une époque où celles-ci étaient tombées en désuétude, il ne pouvait pas effectuer directement de calculs avec des constantes entières autres que 0 et 1, ses instructions avaient un alignement bizarre (elles étaient bit-alignées). Il avait été conçu pour maximiser la compatibilité avec le langage ADA, un langage assez peu utilisé, sans compter que le compilateur pour ce processeur était mauvais.

Les segments prédéfinis de l'Intel iAPX 432

L'Intel iAPX432 gére plusieurs types de segments. Rien d'étonnant à cela, les Burrough géraient eux aussi plusieurs types de segments, à savoir des segments de programmes, des segments de données, et des segments d'I/O. C'est la même chose sur l'Intel iAPX 432, mais en bien pire !

Les segments de données sont des segments génériques, dans lequels on peut mettre ce qu'on veut, suivant les besoins du programmeur. Ils sont tous découpés en deux parties de tailles égales : une partie contenant les données de l'objet et une partie pour les capacités. Les capacités d'un segment pointent vers d'autres segments, ce qui permet de créer des structures de données assez complexes. La ligne de démarcation peut être placée n'importe où dans le segment, les deux portions ne sont pas de taille identique, elles ont des tailles qui varient de segment en segment. Il est même possible de réserver le segment entier à des données sans y mettre de capacités, ou inversement. Les capacités et données sont adressées à partir de la ligne de démarcation, qui sert d'adresse de base du segment. Suivant l'instruction utilisée, le processeur accède à la bonne portion du segment.

Le processeur supporte aussi d'autres segments pré-définis, qui sont surtout utilisés par le système d'exploitation :

Des segments d'instructions, qui contiennent du code exécutable, typiquement un programme ou des fonctions, parfois des threads.
Des segments de processus, qui mémorisent des processus entiers. Ces segments contiennent des capacités qui pointent vers d'autres segments, notamment un ou plusieurs segments de code, et des segments de données.
Des segments de domaine, pour les modules ou librairies dynamiques.
Des segments de contexte, utilisés pour mémoriser l'état d'un processus, utilisés par l'OS pour faire de la commutation de contexte.
Des segments de message, utilisés pour la communication entre processus par l'intermédiaire de messages.
Et bien d'autres encores.

Sur l'Intel iAPX 432, chaque processus est considéré comme un objet à part entière, qui a son propre segment de processus. De même, l'état du processeur (le programme qu'il est en train d’exécuter, son état, etc.) est stocké en mémoire dans un segment de contexte. Il en est de même pour chaque fonction présente en mémoire : elle était encapsulée dans un segment, sur lequel seules quelques manipulations étaient possibles (l’exécuter, notamment). Et ne parlons pas des appels de fonctions qui stockaient l'état de l'appelé directement dans un objet spécial. Bref, de nombreux objets système sont prédéfinis par le processeur : les objets stockant des fonctions, les objets stockant des processus, etc.

L'Intel 432 possédait dans ses circuits un garbage collector matériel. Pour faciliter son fonctionnement, certains bits de l'objet permettaient de savoir si l'objet en question pouvait être supprimé ou non.

Le support de la segmentation sur l'Intel iAPX 432

La table des segments est une table hiérarchique, à deux niveaux. Le premier niveau est une Object Table Directory, qui réside toujours en mémoire RAM. Elle contient des descripteurs qui pointent vers des tables secondaires, appelées des Object Table. Il y a plusieurs Object Table, typiquement une par processus. Plusieurs processus peuvent partager la même Object Table. Les Object Table peuvent être swappées, mais pas l'Object Table Directory.

Une capacité tient compte de l'organisation hiérarchique de la table des segments. Elle contient un indice qui précise quelle Object Table utiliser, et l'indice du segment dans cette Object Table. Le premier indice adresse l'Object Table Directory et récupère un descripteur de segment qui pointe sur la bonne Object Table. Le second indice est alors utilisé pour lire l'adresse de base adéquate dans cette Object Table. La capacité contient aussi des droits d'accès en lecture, écriture, suppression et copie. Il y a aussi un champ pour le type, qu'on verra plus bas. Au fait : les capacités étaient appelées des Access Descriptors dans la documentation officielle.

Une capacité fait 32 bits, avec un octet utilisé pour les droits d'accès, laissant 24 bits pour adresser les segments. Le processeur gérait jusqu'à 2^24 segments/objets différents, pouvant mesurer jusqu'à 64 kibioctets chacun, ce qui fait 2^40 adresses différentes, soit 1024 gibioctets. Les 24 bits pour adresser les segments sont partagés moitié-moitié pour l'adressage des tables, ce qui fait 4096 Object Table différentes dans l'Object Table Directory, et chaque Object Table contient 4096 segments.

Le jeu d'instruction de l'Intel iAPX 432

L'Intel iAPX 432 est une machine à pile. Le jeu d'instruction de l'Intel iAPX 432 gère pas moins de 230 instructions différentes. Il gére deux types d'instructions : les instructions normales, et celles qui manipulent des segments/objets. Les premières permettent de manipuler des nombres entiers, des caractères, des chaînes de caractères, des tableaux, etc.

Les secondes sont spécialement dédiées à la manipulation des capacités. Il y a une instruction pour copier une capacité, une autre pour invalider une capacité, une autre pour augmenter ses droits d'accès (instruction sécurisée, éxecutable seulement sous certaines conditions), une autre pour restreindre ses droits d'accès. deux autres instructions créent un segment et renvoient la capacité associée, la première créant un segment typé, l'autre non.

le processeur gérait aussi des instructions spécialement dédiées à la programmation système et idéales pour programmer des systèmes d'exploitation. De nombreuses instructions permettaient ainsi de commuter des processus, faire des transferts de messages entre processus, etc. Environ 40 % du micro-code était ainsi spécialement dédié à ces instructions spéciales.

Les instructions sont de longueur variable et peuvent prendre n'importe quelle taille comprise entre 10 et 300 bits, sans vraiment de restriction de taille. Les bits d'une instruction sont regroupés en 4 grands blocs, 4 champs, qui ont chacun une signification particulière.

Le premier est l'opcode de l'instruction.
Le champ reference, doit être interprété différemment suivant la donnée à manipuler. Si cette donnée est un entier, un caractère ou un flottant, ce champ indique l'emplacement de la donnée en mémoire. Alors que si l'instruction manipule un objet, ce champ spécifie la capacité de l'objet en question. Ce champ est assez complexe et il est sacrément bien organisé.
Le champ format, n'utilise que 4 bits et a pour but de préciser si les données à manipuler sont en mémoire ou sur la pile.
Le champ classe permet de dire combien de données différentes l'instruction va devoir manipuler, et quelles seront leurs tailles.

Le support de l'orienté objet sur l'Intel iAPX 432

L'Intel 432 permet de définir des objets, qui correspondent aux classes des langages orientés objets. L'Intel 432 permet, à partir de fonctions définies par le programmeur, de créer des domain objects, qui correspondent à une classe. Un domain object est un segment de capacité, dont les capacités pointent vers des fonctions ou un/plusieurs objets. Les fonctions et les objets sont chacun placés dans un segment. Une partie des fonctions/objets sont publics, ce qui signifie qu'ils sont accessibles en lecture par l'extérieur. Les autres sont privées, inaccessibles aussi bien en lecture qu'en écriture.

L'exécution d'une fonction demande que le branchement fournisse deux choses : une capacité vers le domain object, et la position de la fonction à exécuter dans le segment. La position permet de localiser la capacité de la fonction à exécuter. En clair, on accède au domain object d'abord, pour récupérer la capacité qui pointe vers la fonction à exécuter.

Il est aussi possible pour le programmeur de définir de nouveaux types non supportés par le processeur, en faisant appel au système d'exploitation de l'ordinateur. Au niveau du processeur, chaque objet est typé au niveau de son object descriptor : celui-ci contient des informations qui permettent de déterminer le type de l'objet. Chaque type se voit attribuer un domain object qui contient toutes les fonctions capables de manipuler les objets de ce type et que l'on appelle le type manager. Lorsque l'on veut manipuler un objet d'un certain type, il suffit d'accéder à une capacité spéciale (le TCO) qui pointera dans ce type manager et qui précisera quel est l'objet à manipuler (en sélectionnant la bonne entrée dans la liste de capacité). Le type d'un objet prédéfini par le processeur est ainsi spécifié par une suite de 8 bits, tandis que le type d'un objet défini par le programmeur est défini par la capacité spéciale pointant vers son type manager.

Conclusion

Pour ceux qui veulent en savoir plus, je conseille la lecture de ce livre, disponible gratuitement sur internet (merci à l'auteur pour cette mise à disposition) :

Capability-Based Computer Systems.

Voici un document qui décrit le fonctionnement de l'Intel iAPX432 :

The Intel iAPX 432

La pagination

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.

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.

Un point important est que la pagination implique une coopération entre OS et hardware, les deux étant fortement mélés. Une partie des informations de cette section auraient tout autant leur place dans le wikilivre sur les systèmes d'exploitation, mais il est plus simple d'en parler ici.

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

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

De plus, le système d'exploitation conserve une liste des pages vides. Le nom est assez clair : c'est une liste de toutes les pages de la mémoire physique qui sont inutilisées, qui ne sont allouées à aucun processus. Ces pages sont de la mémoire libre, utilisable à volonté. La liste des pages vides est mise à jour à chaque fois qu'un programme réserve de la mémoire, des pages sont alors prises dans cette liste et sont allouées au programme demandeur.

Les défauts de page

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

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 exemple, il est possible que des sécurités empêchent de faire la traduction d'adresse, pour des raisons de protection mémoire. 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. Enfin, une dernière 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. Pour comprendre comment c'est possible, parlons rapidement de l'allocation paresseuse.

Imaginons qu'un programme fasse une demande d'allocation mémoire et se voit donc attribuer une ou plusieurs pages logiques. L'OS peut alors réagir de deux manières différentes. La première est d'attribuer une page physique immédiatement, en même temps que la page logique. En faisant ainsi, on ne peut pas avoir de défaut mineur, sauf en cas de problème de protection mémoire. Cette solution est simple, on l'appelle l'allocation immédiate. Une autre solution consiste à attribuer une page logique, mais l'allocation de la page physique se fait plus tard. Elle a lieu la première fois que le programme tente d'écrire/lire dans la page physique. Un défaut mineur a lieu, et c'est lui qui force l'OS à attribuer une page physique pour la page logique demandée. On parle alors d'allocation paresseuse. L'avantage est que l'on gagne en performance si des pages logiques sont allouées mais utilisées, ce qui peut arriver.

Une optimisation permise par l'existence des défauts mineurs est le copy-on-write. Le but est d'optimiser la copie d'une page logique dans une autre. L'idée est que la copie est retardée quand elle est vraiment nécessaire, à savoir quand on écrit dans la copie. Tant que l'on ne modifie pas la copie, les deux pages logiques, originelle et copiée, pointent vers la même page physique. A quoi bon avoir deux copies avec le même contenu ? Par contre, la page physique est marquée en lecture seule. La moindre écriture déclenche une erreur de protection mémoire, et un défaut mineur. Celui-ci est géré par l'OS, qui effectue alors la copie dans une nouvelle page physique.

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

Les pages virtuelles font 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. Ce n'est possible que 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.

Supposons que l'on veuille faire de la place en RAM pour une nouvelle page. Dans une implémentation naïve, on trouve une page à évincer de la mémoire, qui est copiée dans le swapfile. Toutes les pages évincées sont alors copiées sur le disque dur, à chaque remplacement. Néanmoins, cette implémentation naïve peut cependant être améliorée si on tient compte d'un point important : si la page a été modifiée depuis le dernier accès. Si le programme/processeur a écrit dans la page, alors celle-ci a été modifiée et doit être sauvegardée sur le swapfile si elle est évincée. Par contre, si ce n'est pas le cas, la page est soit initialisée, soit déjà présente à l'identique dans le swapfile.

Mais cette optimisation demande de savoir si une écriture a eu lieu dans la page. Pour cela, on ajoute un dirty bit à chaque entrée de la table des pages, juste à côté du bit Valid. Il indique si une écriture a eu lieu dans la page depuis qu'elle a été chargée en RAM. Ce bit est mis à jour par le processeur, automatiquement, lors d'une écriture. Par contre, il est remis à zéro par le système d'exploitation, quand la page est chargée en RAM. Si le programme se voit allouer de la mémoire, il reçoit une page vide, et ce bit est initialisé à 0. Il est mis à 1 si la mémoire est utilisée. Quand la page est ensuite swappée sur le disque dur, ce bit est remis à 0 après la sauvegarde.

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 ! Là encore, cela demande d'ajouter un bit dans chaque entrée de la table des pages, qui indique si la page est swappable ou non. Le bit en question s'appelle souvent le bit swappable.

Les algorithmes de remplacement des pages pris en charge par l'OS

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. Leur but est de swapper des pages qui ne seront pas accédées dans le futur, pour éviter d'avoir à faire triop de va-et-vient entre RAM et swapfile. Les données qui sont censées être accédées dans le futur doivent rester en RAM et ne pas être swappées, autant que possible. Les algorithmes les plus simples pour le choix de page à évincer sont les suivants.

Le plus simple est un algorithme aléatoire : on choisit la page au hasard. Mine de rien, cet algorithme est très simple à implémenter et très rapide à exécuter. Il ne demande pas de modifier la table des pages, ni même d'accéder à celle-ci pour faire son choix. Ses performances sont surprenamment correctes, bien que largement en-dessous de tous les autres algorithmes.

L'algorithme FIFO supprime la donnée qui a été chargée dans la mémoire avant toutes les autres. Cet algorithme fonctionne bien quand un programme manipule des tableaux de grande taille, mais fonctionne assez mal dans le cas général.

L'algorithme LRU supprime la donnée qui été lue ou écrite pour la dernière fois avant toutes les autres. C'est théoriquement le plus efficace dans la majorité des situations. Malheureusement, son implémentation est assez complexe et les OS doivent modifier la table des pages pour l'implémenter.

L'algorithme le plus utilisé de nos jours est l'algorithme NRU (Not Recently Used), une simplification drastique du LRU. Il fait la différence entre les pages accédées il y a longtemps et celles accédées récemment, d'une manière très binaire. Les deux types de page sont appelés respectivement les pages froides et les pages chaudes. L'OS swappe en priorité les pages froides et ne swappe de page chaude que si aucune page froide n'est présente. L'algorithme est simple : il choisit la page à évincer au hasard parmi une page froide. Si aucune page froide n'est présente, alors il swappe au hasard une page chaude.

Pour implémenter l'algorithme NRU, l'OS mémorise, dans chaque entrée de la table des pages, si la page associée est froide ou chaude. Pour cela, il met à 0 ou 1 un bit dédié : le bit Accessed. La différence avec le bit dirty est que le bit dirty est mis à jour uniquement lors des écritures, alors que le bit Accessed l'est aussi lors d'une lecture. Uen lecture met à 1 le bit Accessed, mais ne touche pas au bit dirty. Les écritures mettent les deux bits à 1.

Implémenter l'algorithme NRU demande juste de mettre à jour le bit Accessed de chaque entrée de la table des pages. Et sur les architectures modernes, le processeur s'en charge automatiquement. A chaque accès mémoire, que ce soit en lecture ou en écriture, le processeur met à 1 ce bit. Par contre, le système d'exploitation le met à 0 à intervalles réguliers. En conséquence, quand un remplacement de page doit avoir lieu, les pages chaudes ont de bonnes chances d'avoir le bit Accessed à 1, alors que les pages froides l'ont à 0. Ce n'est pas certain, et on peut se trouver dans des cas où ce n'est pas le cas. Par exemple, si un remplacement a lieu juste après la remise à zéro des bits Accessed. Le choix de la page à remplacer est donc imparfait, mais fonctionne bien en pratique.

Tous les algorithmes précédents 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.

La protection mémoire avec la pagination

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. En pratique, les tables de pages modernes disposent de trois bits : un qui autorise/interdit les accès en lecture, un qui autorise/interdit les accès en écriture, un qui autorise/interdit l'éxecution du contenu de la page.

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 traduction d'adresse avec la pagination

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.

Les tables des pages simples

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.

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.

Les tables des pages inversées

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.

Les tables des pages multiples par espace d'adressage

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

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 pages désigne l'ensemble des différents niveaux de cette organisation, toutes les tables inclus. 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

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

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

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.

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.

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.

Les circuits liés à la gestion de la table des pages

En théorie, la table des pages est censée être accédée à chaque accès mémoire. Mais pour éviter d'avoir à lire la table des pages en mémoire RAM à chaque accès mémoire, les concepteurs de processeurs ont décidé d'implanter un cache dédié, le translation lookaside buffer, ou TLB. Le TLB stocke au minimum de quoi faire la traduction entre adresse virtuelle et adresse physique, à savoir une correspondance entre numéro de page logique et numéro de page physique. Pour faire plus général, il stocke des entrées de la table des pages.

Les accès à la table des pages sont gérés de deux façons : soit le processeur gère tout seul la situation, soit il délègue cette tâche au système d’exploitation. Sur les processeurs anciens, le système d'exploitation gère le parcours de la table des pages. Mais cette solution logicielle n'a pas de bonnes performances. D'autres processeurs gèrent eux-mêmes le défaut d'accès à la TLB et vont chercher d'eux-mêmes les informations nécessaires dans la table des pages. Ils disposent de circuits, les page table walkers (PTW), qui s'occupent eux-mêmes du défaut.

Les page table walkers contiennent des registres qui leur permettent de faire leur travail. Le plus important est celui qui mémorise la position de la table des pages en mémoire RAM, dont nous avons parlé plus haut. Les PTW ont besoin, pour faire leur travail, de mémoriser l'adresse physique de la table des pages, ou du moins l'adresse de la table des pages de niveau 1 pour des tables des pages hiérarchiques. Mais d'autres registres existent. Toutes les informations nécessaires pour gérer les défauts de TLB sont stockées dans des registres spécialisés appelés des tampons de PTW (PTW buffers).

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

Il est possible d'implémenter l'abstraction matérielle des processus avec la pagination. En clair, 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. Pour cela, il y a plusieurs méthodes.

L'usage d'une table des pages unique avec un identifiant de processus dans chaque entrée

La première solution n'utilise qu'une seule table des pages, mais chaque entrée est associée à un processus. Pour cela, chaque entrée contient un identifiant de processus, un numéro qui précise pour quel processus, pour quel espace d'adressage, la correspondance est valide.

La page des tables peut aussi contenir des entrées qui sont valides pour tous les processus en même temps. L'intérêt n'est pas évident, mais il le devient quand on se rappelle que le noyau de l'OS est mappé dans le haut de l'espace d'adressage. Et peu importe l'espace d'adressage, le noyau est toujours mappé de manière identique, les mêmes adresses logiques adressant la même adresse mémoire. En conséquence, les correspondances adresse physique-logique sont les mêmes pour le noyau, peu importe l'espace d'adressage. Dans ce cas, la correspondance est mémorisée dans une entrée, mais sans identifiant de processus. A la place, l'entrée contient un bit global, qui précise que cette correspondance est valide pour tous les processus. Le bit global accélère rapidement la traduction d'adresse pour l'accès au noyau.

Un défaut de cette méthode est que le partage d'une page entre plusieurs processus est presque impossible. Impossible de partager une page avec seulement certains processus et pas d'autres : soit on partage une page avec tous les processus, soit on l'alloue avec un seul processus.

L'usage de plusieurs tables des pages

Une solution alternative, plus simple, utilise une table des pages par processus lancé sur l'ordinateur, une table des pages unique par espace d'adressage. À chaque changement de processus, le registre qui mémorise la position de la table des pages est modifié pour pointer sur la bonne. C'est le système d'exploitation qui se charge de cette mise à jour.

Avec cette méthode, il est possible de partager une ou plusieurs pages entre plusieurs processus, en configurant les tables des pages convenablement. Les pages partagées sont mappées dans l'espace d'adressage de plusieurs processus, 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 taille des pages

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 gagnent à utiliser des pages larges, d'autres vont au contraire perdre drastiquement en performance en les utilisant.

Le 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 certaine 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.

Les entrées de la table des pages

Avant de poursuivre, faisons un rapide rappel sur les entrées de la table des pages. Nous venons de voir que la table des pages contient de nombreuses informations : un bit valid pour la mémoire virtuelle, des bits dirty et accessed utilisés par l'OS, des bits de protection mémoire, un bit global et un potentiellement un identifiant de processus, etc. Étudions rapidement le format de la table des pages sur un processeur x86 32 bits.

Elle contient d'abord le numéro de page physique.
Les bits AVL sont inutilisés et peuvent être configurés à loisir par l'OS.
Le bit G est le bit global.
Le bit PS vaut 0 pour une page de 4 kibioctets, mais est mis à 1 pour une page de 4 mébioctets dans le cas où le processus utilise des pages larges.
Le bit D est le bit dirty.
Le bit A est le bit accessed.
Le bit PCD indique que la page ne peut pas être cachée, dans le sens où le processeur ne peut copier son contenu dans le cache et doit toujours lire ou écrire cette page directement dans la RAM.
Le bit PWT indique que les écritures doivent mettre à jour le cache et la page en RAM (dans le chapitre sur le cache, on verra qu'il force le cache à se comporter comme un cache write-through pour cette page).
Le bit U/S précise si la page est accessible en mode noyau ou utilisateur.
Le bit R/W indique si la page est accessible en écriture, toutes les pages sont par défaut accessibles en lecture.
Le bit P est le bit valid.

Table des pages des processeurs Intel 32 bits.

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

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. 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	Architectures à capacités	Pagination	Sans abstraction mémoire
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		Oui : adresse de base élargie dans la table des segments		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	Non		Segment partagés		Pages partagées	Possible, méthodes variées

Les différents types de segmentation

La segmentation regroupe plusieurs techniques franchement différentes, qui auraient gagné à être nommées différemment. La principale différence est l'usage de registres de relocation versus des registres de sélecteurs de segments. L'usage de registres de relocation est le fait de la relocation matérielle, mais aussi de la segmentation en mode réel des CPU x86. Par contre, l'usage de sélecteurs de segments est le fait des autres formes de segmentation, architectures à capacité inclues.

La différence entre les deux est le nombre de segments. L'usage de registres de relocation fait que le CPU ne gère qu'un petit nombre de segments de grande taille. La mémoire virtuelle est donc rarement implémentée vu que swapper des segments de grande taille est trop long, l'impact sur les performances est trop important. Sans compter que l'usage de registres de base se marie très mal avec la mémoire virtuelle. Vu qu'un segment peut être swappé ou déplacée n'importe quand, il faut invalider les registres de base au moment du swap/déplacement, ce qui n'est pas chose aisée. Aucun processeur ne gère cela, les méthodes pour n'existent tout simplement pas. L'usage de registres de base implique que la mémoire virtuelle est absente.

La protection mémoire est aussi plus limitée avec l'usage de registres de relocation. Elle se limite à des registres limite, mais la gestion des droits d'accès est limitée. En théorie, la segmentation en mode réel pourrait implémenter une version limitée de protection mémoire, avec une protection de l'espace exécutable. Mais ca n'a jamais été fait en pratique sur les processeurs x86.

Le partage de la mémoire est aussi difficile sur les architectures avec des registres de base. L'absence de table des segments fait que le partage d'un segment est basiquement impossible sans utiliser des méthodes complétement tordues, qui ne sont jamais implémentées en pratique.

Segmentation versus pagination

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.

◄ Retour vers « Le partage de l'espace d'adressage : avec et sans multiprogrammation »

Sommaire du livre

Continuer vers « Les méthodes de synchronisation entre processeur et périphériques » ►