IFT-17583

Structure interne des ordinateurs

Mémoire virtuelle

 

Nous avons vu que la mémoire cache est une méthode permettant des accès rapides à des parties de la mémoire centrale utilisées récemment. De la même façon, la mémoire centrale peut sevir de cache pour le stockage de masse, habituellement implémenté sous forme de disques durs. Cette technique s'appelle mémoire virtuelle.  Elle permet une gestion efficace et sécuritaire de la mémoire entre plusieurs programmes et élimine la lourde tâche d'avoir à gérer par programmation une quantité limitée et faible de mémoire centrale.

Considérons un ensemble de plusieurs programmes fonctionnant simultanément sur une ordinateur. La mémoire totale requise par tous ces programmes peut être bien plus grande que la quantité de mémoire centrale disponible dans la machine, mais en fait, à un instant donné, seule une petite partie de cette mémoire est utilisée activement. Le mémoire centrale n'a besoin de garder que la partie active de chacun de ces programmes, tout comme une mémoire cache ne contient que la partie active d'un seul programme. Évidemment, pour permettre à de multiples programmes de partager la même mémoire, il faut pouvoir protéger ces programmes l'un de l'autre, en s'assurant qu'un programme ne peut lire ou écrire que dans les portions de la mémoire centrale qui lui ont été attribuées. En effet, on ne peut pas savoir à l'avance quels programmes partageront la mémoire avec d'autres programmes.

Même si les concepts à l'úuvre dans la mémoire cache et dans la mémoire virtuelle sont les mêmes, leurs racines historiques différentes font que la terminologie n'est pas la même. Un bloc de mémoire virtuelle s'appelle une page, et un échec de mémoire virtuelle (miss) s'appelle une besoin de page (page fault). Le CPU produit une adresse virtuelle qui est traduite par une combinaison de matériel et de logiciel en une adresse physique qui est utilisée pour accéder à la mémoire principale.

Le principe est illustré dans la figure suivante. L'adresse virtuelle représente l'espace total de mémoire virtuelle désirée, qui doit se trouver sur le disque dur. L'espace disque, et donc la mémoire virtuelle, est découpé en un certain nombre de pages virtuelles. La mémoire physique est beaucoup plus petite et est découpée en pages physiques. Les pages physiques ont la même taille que les pages virtuelles.
 

 
 
Figure 1
 
Quand le processeur demande une adresse (virtuelle), le système de gestion de mémoire virtuelle détermine si cette page se trouve en mémoire physique. Si oui, il traduit l'adresse virtuelle en adresse physique et la lecture ou l'écriture s'effectue. Si non, alors il y a page-fault. Le processeur prend la page demandée sur le disque et place son contenu en mémoire physique.

Par exemple, dans la figure précédente, si le processeur a besoin de la page virtuelle 5, il lira la page physique 1. Par contre, s'il a besoin de la page virtuelle 4, comme elle n'est pas en mémoire physique, il y aura besoin de page (page fault). Il prendra donc le contenu de la page 4 sur le disque et la copiera dans une des pages physiques, disons la page 2. Ensuite, il mettra à jour le tableau de gauche pour que la case 4 pointe vers la page physique 2. Il doit aussi effacer la flèche qui va de l'adresse virtuelle 3 à la page physique 2, puisque la page virtuelle 3 n'est plus en mémoire physique (on vient d'écrire la page 4 là où elle était).

Pour que ce processus soit utile, il doit être pratiquement aussi rapide que si on n'avait pas de mémoire virtuelle, quand la page virtuelle demandée se trouve en mémoire physique. La solution doit donc faire intervenir un matériel spécialisé. Toute ce qui suit sur la technologie de la mémoire virtuelle n'a qu'un but : rendre ce processus aussi efficace et sécuritaire que possible en raison du coût élevé d'un échec. Le traitement d'un besoin de page peut prendre des millions de cycles.

Pour découper l'espace d'adressage virtuel en pages, l'adresse virtuelle est découpée en deux champs : un numéro de page virtuelle et un offset dans cette page. Par exemple, une adresse virtuelle de 32 bits pourrait être découpée en un champ de 20 bits et un champ de 12 bits :

 
 
 
Figure 2
Ceci représente 1 M (220) pages de 4 Ko. (212) pour un total de 4 Go (232). Supposons que notre ordinateur a une mémoire physique de 32 Mo (225). Il aura donc 8 K (213) pages de 4 Ko. L'adresse physique aura donc l'air de ceci :
 
 
 
Figure 3
 
Le rôle du système de gestion de mémoire virtuelle est donc de traduire le No. de page virtuelle en No. de page physique.

Dams la figure 1, le tableau de gauche s'appelle table des pages. L'entrée de cette table pour chaque numéro de page virtuelle contient le numéro de page physique correspondant et un bit de validité indiquant si la page virtuelle en question est bien présente en mémoire physique. Pour trouver rapidement l'entrée appropriée, le numéro de page virtuelle sert d'indice dans cette table.

Chaque programme a sa table des pages qui traduit l'adresse virtuelle dans ce programme en adresse physique en mémoire. L'adresse de cette table est contenue dans un registre appelé registre de table des pages.

 
 
Figure 4. Contenu de la table des pages pour l'exemple de la figure 1.
 
Lorsque le système d'exploitation crée un processus, il crée sur disque l'espace pour toutes les pages du processus. En pratique, les pages virtuelles ne sont pas toutes contiguës sur le disque comme dans la figure 1. Le système d'exploitation doit donc aussi créer une structure de données pour enregistrrer l'endroit où chaque page virtuelle est enregistrée sur le disque. Cette structure peut faire partie de la table des pages ou être distincte.

Pour des adresses virtuelles de 32 bits, en supposant des entrées de 32 bits dans la table des pages, cette dernière devrait avoir une taille de :
220 entrées * 4 octets par entrée = 4 Mo. Si chaque processus en marche dans un ordinateur devait avoir une table des pages de 4 Mo, il ne resterait plus de mémoire disponible. Il faut donc trouver une façon de réduire la mémoire utilisée. Une des méthodes est de rendre la table des pages elle-même paginable, sauf pour une partie qui est toujours en mémoire centrale. Une autre méthode consiste à utiliser des tables initiales petites, mais qui peuvent croître si le processus a besoin de plus de mémoire.

Même en l'absence de besoins de page, ce système tel quel serait au moins deux fois plus lent que la mémoire physique, puisqu'il faut lire la table des pages pour obtenir l'adresse physique de la donnée à laquelle on veut accéder. Comment peut-on y remédier? On utilise une mémoire cache dans laquelle on enregistre les traductions de page les plus récemment utilisées. Cette mémoire cache s'appelle translation-lookaside buffer (TLB). Elle fonctionne comme toute mémoire cache et peut être associative, à correspondance directe ou associative par ensembles.

 
Figure 5. TLB
 
Si le numéro de page physique correspondant à l'adresse virtuelle demandée se trouve dans le TLB, on n'a pas besoin de le lire dans la mémoire centrale et l'accès est immédiat. En cas d'échec du cache, on va lire la donnée dans la table des pages et on la place dans le cache.

Dans la mémoire cache, il y a deux approches pour l'écriture :  l'écriture simultanée (write-through) et la récriture (write-back). Dans le premier cas, toute écriture est considérée comme un échec et on écrit simultanément dans le cache et dans la mémoire centrale. Dans le second cas, on n'écrit que dans le cache, et l'information n'est transférée en mémoire centrale que lorsque le bloc de cache où on a écrit doit être remplacé. Dans la mémoire virtuelle, le coût d'un échec est tellement élevé qu'on ne peut se permettre l'écriture simultanée. On utilise donc toujours la récriture.

En présence de mémoire cache, le processus est modifié comme suit. L'adresse virtuelle est d'abord envoyée au TLB. Dans le meilleur cas,  l'adresse physique recherchée s'y trouve et est envoyée à la mémoire cache. Dans le meilleur cas, la donnée correspondante s'y trouve, et est envoyée au CPU. Une lecture effectuée dans ces conditions se fera dans un temps minimal qui est le temps de réponse de la mémoire cache, tout au plus quelques cycles.

S'il y a échec du TLB, alors il faut effectuer une lecture dans la table des pages, ce qui implique une lecture en mémoire centrale et une mise à jour du TLB, donc plusieurs cycles. C'est donc passablement plus long. Il peut aussi y avoir échec de la mémoire cache. Dans ce cas, la donnée devra être chargée dans la cache après une lecture en mémoire centrale. Le pire cas survient quand la page demandée n'est pas en mémoire centrale. Il faut alors aller lire le disque, ce qui prend des milliers de cycles, puis mettre à jour la table des pages, la mémoire cache et le TLB.

S'il s'agit d'une écriture, si l'adresse physique recherchée se trouve dans le TLB et aussi cans la mémoire cache, alors la donnée est écrite dans la cache s'il s'agit d'une cache à récriture. Ce n'est qu'au prochain échec de cache impliquant le remplacement du bloc concerné que cette donnée sera transférée en mémoire centrale. Si l'adresse physique fournie par le TLB ne se trouve pas dans la cache, on doit alors lire le bloc correspondant en mémoire centrale pour le placer dans la cache, puis on y écrit la donnée. Finalement, si la page correspondant à cette adresse physique n'est pas en mémoire, il faudra la charger à partir du disque, puis mettre à jour la table des pages, la mémoire cache et le TLB.

Pour le remplacement d'une page en mémoire centrale à partir du disque, différents algorithmes sont utilisés, comme pour les mémoires caches.

 

Dernière mise à jour : 2000-09-18