thumb|Schéma de principe de la mémoire virtuelle. En informatique, la mémoire virtuelle est une abstraction idéalisée des ressources de stockage réellement disponibles sur une machine donnée. Il repose sur l'utilisation de traduction à la volée des adresses (virtuelles) vues du logiciel, en adresses physiques de mémoire vive ou de mémoire de masse. La mémoire virtuelle permet : d'utiliser de la mémoire de masse comme extension de la mémoire vive ; d'augmenter le taux de multiprogrammation ; de mettre en place des mécanismes de protection de la mémoire ; de partager la mémoire entre processus. Ce mécanisme a été mis au point dans les années 1960.
Historique L'article de référence de James Kilburn, paru en 1962, décrit le premier ordinateur doté d'un système de gestion de mémoire virtuelle paginée et utilisant un tambour comme extension de la mémoire centrale à tores de ferrite : l'Atlas.
Aujourd'hui, tous les ordinateurs ont un mécanisme de gestion de la mémoire virtuelle, sauf certains supercalculateurs ou systèmes embarqués temps réel.
Mémoire virtuelle paginée Le principe est le suivant : Les adresses mémoires émises par le processeur sont des adresses virtuelles, indiquant la position d'un mot dans la mémoire virtuelle. Cette mémoire virtuelle est formée de zones de même taille, appelées pages. Une adresse virtuelle est donc un couple (numéro de page, déplacement dans la page). La taille des pages est une puissance entière de deux, de façon à déterminer sans calcul le déplacement (10 bits de poids faible de l'adresse virtuelle pour des pages de mots), et le numéro de page (les autres bits). La mémoire vive est également composée de zones de même taille, appelées cadres ( en anglais), dans lesquelles prennent place les pages (un cadre contient une page : taille d'un cadre = taille d'une page). La taille de l'ensemble des cadres en mémoire vive utilisés par un processus est appelé . Un mécanisme de traduction (translation, ou génération d'adresse) assure la conversion des adresses virtuelles en adresses physiques, en consultant une table des pages (page table en anglais) pour connaître le numéro du cadre qui contient la page recherchée. L'adresse physique obtenue est le couple (numéro de cadre, déplacement). Il peut y avoir plus de pages que de cadres (c'est là tout l'intérêt) : les pages qui ne sont pas en mémoire sont stockées sur un autre support (disque), elles seront ramenées dans un cadre quand on en aura besoin.
La table des pages est indexée par le numéro de page. Chaque ligne est appelée « entrée dans la table des pages » (, abrégé PTE), et contient le numéro de cadre. La table des pages pouvant être située n'importe où en mémoire, un registre spécial (PTBR pour ) conserve son adresse.
En pratique, le mécanisme de traduction fait partie d'un circuit électronique appelé MMU () qui contient également une partie de la table des pages, stockée dans une mémoire associative formée de registres rapides. Ceci évite d'avoir à consulter la table des pages (en mémoire) pour chaque accès mémoire.
Voici un exemple réel d'une machine dont le processeur génère des adresses virtuelles sur , pouvant ainsi accéder à de mémoire. La taille de la page est de . On en déduit que le champ déplacement occupe les de poids faible, et le champ numéro de page les de poids fort.
On notera la présence d'un champ spécial appartenant à chaque PTE. Pour simplifier, nous avons réduit la largeur de ce champ à un bit : le bit de validité. Si celui-ci est à 0, cela signifie que le numéro de cadre est invalide. Il faut donc se doter d'une technique permettant de mettre à jour cette PTE pour la rendre valide.
Trois cas peuvent se produire :
L'entrée est valide : elle se substitue au numéro de page pour former l'adresse physique. L'entrée dans la table des pages est invalide. Dans ce cas il faut trouver un cadre libre en mémoire vive et mettre son numéro dans cette entrée de la table des pages. L'entrée dans la table des pages est valide mais correspond à une adresse sur la mémoire de masse où se trouve le contenu du cadre. Un mécanisme devra ramener ces données pour les placer en mémoire vive.
Allocation à la demande Dans les deux derniers cas, une interruption – appelée défaut de page (ou parfois faute de page, traduction de l'anglais ) est générée par le matériel et donne la main au système d'exploitation. Celui-ci a la charge de trouver un cadre disponible en mémoire centrale afin de l'allouer au processus responsable de ce défaut de page, et éventuellement de recharger le contenu de cette par le contenu sauvé sur la mémoire de masse (couramment le disque dur, sur une zone appelée zone d'échange ou ).
Il se peut qu'il n'y ait plus aucun cadre libre en mémoire centrale : celle-ci est alors occupée à 100 %. Dans ce cas un algorithme de pagination a la responsabilité de choisir une page « victime ». Cette page se verra soit immédiatement réaffectée au processus demandeur, soit elle sera d'abord sauvegardée sur disque dur, et l'entrée de la table des pages qui la référence sera mise à jour. La page victime peut très bien appartenir au processus qui manque de place.
Ci-dessous sont listés quelques exemples d'algorithmes. La première ligne correspond à la chaîne de références, c’est-à-dire l'ordre dans lequel le processus va accéder aux pages. On suppose que la mémoire centrale est composée de trois . La victime apparaîtra soulignée. Les défauts de page initiaux ne sont pas comptés (ils sont en nombre identique quel que soit l'algorithme choisi).
L'algorithme optimal : le nombre de défauts de page est réduit à 6. La règle de remplacement est « remplacer la qui ne sera pas utilisée pendant la durée la plus longue ». Malheureusement, cet algorithme nécessiterait de connaître l'avenir. Les autres algorithmes essayeront donc d'approcher cette solution optimale.
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1772222700000013311
FIFO ( ou « Premier rentré, premier sorti ») : le cadre victime est celui qui a été amené en mémoire il y a le plus longtemps (le plus « ancien »). Notez qu'il n'est pas nécessaire de conserver l'instant auquel un cadre a été remplacé : il suffit de maintenir une structure FIFO, de remplacer le cadre dont le numéro apparaît en tête, et d'insérer le numéro du nouveau cadre en dernière position. Cet algorithme donne lieu à 12 remplacements :
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1772244007770033221100110033221
L'algorithme le plus souvent utilisé est appelé LRU (, soit « la moins récemment utilisée »). Il consiste à choisir comme victime le cadre qui n'a pas été référencé depuis le plus longtemps. On peut l'implémenter soit en rajoutant des bits dans chaque entrée de la table des pages qui indiquent quand a eu lieu la dernière référence à cette entrée, soit via une structure de liste où l'on amènera en première position le cadre récemment référencé, les cadres victimes restant donc en dernières positions. Cet algorithme donne lieu à 9 remplacements :
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1772441110000033001322227
Autres algorithmes : Remplacement aléatoire : où la victime est choisie au hasard. LFU ( soit « la moins souvent utilisée ») : on garde un compteur qui est incrémenté à chaque fois que le cadre est référencé, et la victime sera le cadre dont le compteur est le plus bas. Inconvénient : au démarrage du programme quelques pages peuvent être intensément utilisées, puis plus jamais par la suite. La valeur du compteur sera si élevée qu'ils ne seront remplacés que trop tardivement. Il faut aussi gérer le cas de dépassement de capacité du compteur…
Il peut être relativement facile de trouver des cas pathologiques qui rendent un algorithme inutilisable. Par exemple, pour l'algorithme LRU, il s'agirait d'un programme qui utilise 5 pages dans une boucle sur une machine qui ne compte que 4 cadres'. Il va d'abord utiliser les 4 premiers cadres séquentiellement (1, 2, 3, 4) puis un défaut de page va survenir et c'est la page 1, la plus anciennement chargée, qui sera la victime. Les pages utilisées sont maintenant (5, 2, 3, 4). Puisque le programme boucle, il a besoin de la page 1 (à la suite de la page 5). Cette fois-ci, la page victime est la page 2, remplacée par la 1 : (5, 1, 3, 4), puis (5, 1, 2, 4), (5, 1, 2, 3), etc. Un défaut de page est généré à chaque itération…
Anomalie de Belady
Intuitivement, augmenter le nombre de cadres de pages (c'est-à-dire agrandir la mémoire centrale) doit réduire le nombre de défauts de page.
L'anomalie de Belady (1970) est un contre-exemple qui montre que ce n'est pas absolument vrai avec l'algorithme FIFO, en effet le lecteur pourra vérifier par lui-même que la séquence de références (3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4) conduit à 9 défauts de page avec 3 cadres, 10 défauts de page avec 4 cadres.
Remarque : il ne faut pas exagérer la portée de cette curiosité. Elle montre certes que l'algorithme FIFO n'a pas en général une propriété à laquelle on se serait attendu (ajouter de la mémoire réduit les défauts de page) mais elle ne montre pas qu'elle ne l'a pas en moyenne. Et de toute façon l'algorithme FIFO n'est jamais utilisé pour le remplacement de page.
Par ailleurs, on peut démontrer que certains algorithmes de remplacement de pages (LRU par exemple) ne sont pas sujets à ce type d'anomalie.
Méthode d'allocation dans un système multiprogrammé Les méthodes de sélection de la page victime évoquées ci-dessus peuvent s'appliquer soit aux pages appartenant à un processus (on parle alors d'« allocation locale »), soit à toutes les pages et donc à toute la mémoire (dans ce cas la technique d'allocation est dite « globale »).
Dans un système d'allocation globale, le temps d'exécution d'un processus peut grandement varier d'une instance à l'autre car le nombre de défauts de page ne dépend pas du processus lui-même. D'un autre côté, ce système permet au nombre de cadres alloués à un processus d'évoluer.
Partage de mémoire dans un système paginé Le schéma suivant montre trois processus en cours d'exécution, par exemple un éditeur de texte nommé Ed. Les trois instances sont toutes situées aux mêmes adresses virtuelles (1, 2, 3, 4, 5). Ce programme utilise deux zones mémoire distinctes : les pages qui contiennent le code, c’est-à-dire les instructions décrivant le programme, et la zone de données, le fichier en cours d'édition. Il suffit de garder les mêmes entrées dans la table des pages pour que les trois instances se partagent la zone de code. Par contre, les entrées correspondantes aux pages de données sont, elles, distinctes.
Protection Des bits de protections sont ajoutés à chaque entrée de la table des pages. Ainsi on pourra aisément faire la distinction entre les pages allouées au noyau, en lecture seule, etc. Voir l'exemple ci-dessous.
Efficacité On rencontre trois problèmes majeurs : La taille de la table des pages : pour une architecture où sont réservés pour le numéro de page, la table occupera de mémoire minimum (220 = 1 Mio de PTE, chaque PTE ayant une longueur de 4 octets). Ce problème est résolu par l'utilisation de plusieurs tables de pages : le champ numéro de page sera décomposé en plusieurs, chacun indiquant un déplacement dans la table de plus bas niveau. Les VAX et les Pentiums supportent deux niveaux, le SPARC trois, les Motorola 680x0 quatre… On peut aussi segmenter la table des pages.