L'implantation de la mémoire virtuelle

Pour chaque processus, le VMM met en œuvre plusieurs structures de données permettant la gestion de la mémoire virtuelle privée du processus.

Cette structure de données permet au VMM de connaître l’état des pages physiques.

· En attente (Standby) : un processus utilisait la page physique, mais elle a été retirée de son jeu de pages de travail. La page est valide en transition,

· Modifié (Modified) : cet état est semblable à l’état d’attente, mais le processus a également écrit dans la page physique qui n’a pas encore été recopiée sur le disque,

· Mauvais (Bad) : la page physique a généré des erreurs de parité ou d’autres erreurs physiques.

La base de données des pages physiques est une table dont chaque entrée correspond à une case. Le nombre d’entrées de cette table est donc le nombre de cases de la mémoire physique.

Les entrées de la base sont chaînées entre elles pour former cinq listes regroupant les pages physiques dans un même état ; listes des pages à zéro, des pages libres, des pages en attente, des pages modifiées et des pages mauvaises. La Figure 5-3 illustre les listes des états des pages physiques. Ces listes couvrent toutes les pages non utilisées de la base.

Quand un processus n’a plus besoin d’une page physique, ou quand le VMM en recopie le contenu sur le disque, la page devient libre.

Chaque fois que le nombre de pages des listes des pages à zéro, libres ou en attente, passe au-dessous d’un seuil minimum, un thread, appelé modified page writer ou unité d’écriture de pages modifiées, est réveillé. Ce thread écrit alors le contenu des pages modifiées sur le disque et les place dans la liste des pages en attente.

Si le nombre de pages modifiées devient trop faible, le VMM commence à réduire le jeu de pages de travail de chaque processus jusqu'à la taille minimale (automatic working-set trimming). Les pages ainsi libérées sont placées dans la liste des pages modifiées ou en attente, afin de pouvoir être réutilisées à la demande.

La liste des pages à zéro : le niveau de sécurité C2 impose que les threads en mode utilisateur ne reçoivent que des pages physiques initialisées pour qu’ils ne puissent pas lire le contenu de la mémoire d’un thread précédent.

Chaque entrée, appelée PDE, Page Directory Entry, de cette table contient l’adresse de la table des pages correspondantes.

Une PDE de cette table peut être représentée par la Figure 4. Le répertoire des pages comprend au maximum 1024 PDE. Chaque PDE peut être valide ou invalide (flag P).

Le répertoire des pages du processus est stocké dans l’espace système paginé du processus.

Une entrée de la table des pages, appelée PTE, Page Table Entry, permet d’accéder à l’adresse de la case associée au PTE, c’est-à-dire à la page qui se trouve chargée dans cette case. La table des pages contient d’autres informations sur la page associée au PTE : la protection de la page, la page correspondante sur le disque et l’état de la page.

La table des pages comprend au maximum 1024 PTE. Le format d’un PTE est décrit dans la Figure 5.

Les trois premiers bits représentent l’état de la case, donc de la page en mémoire physique. Les différents états son regroupés dans le Tableau 1.

Le PTE contient ensuite l’adresse de la case associée à la page qui s’y trouve chargée.

Le champ PtrBase est l’entrée dans la base de données des pages physiques, si la case associée au PTE est dans l’état valide ou dans l’état invalide en transition. Ce pointeur est appelé pointeur avant. De la même façon, la base aura un pointeur sur l’entrée de la table des pages dont le PtrBase n’est pas Null. Ce pointeur est le pointeur arrière. Avant que le VMM ne puisse utiliser une page physique de la liste des pages modifiées ou en attente (connaissance qu’il trouve dans la base de données des pages physiques), il doit vérifier que la page est marquée « invalide » dans la table des pages. Ceci est possible grâce au pointeur arrière.

Enfin, chaque case dispose d’un mécanisme de protection. Le dernier champ représente cette protection et peut prendre les valeurs :

Une page valide est une page physique, utilisée par un processus. Cette page a pu être modifiée par le thread qui y accède - page valide modifiée - ou non - page valide. Une page invalide est une page qui est présente en mémoire physique mais qui n’est plus utilisée. Enfin, une page en transition est une page qui a été rendue inaccessible, mais qui est toujours présente en mémoire physique, lors de la réduction automatique du jeu de pages de travail du processus. Cette page a pu être modifiée - page invalide modifiée en transition - ou non - page invalide en transition.

T (Transition)	D (Dirty)	P (Page)	Etat de la page
0	-	0	Page invalide
-	0	1	Page valide
-	1	1	Page valide modifiée
1	0	0	Page invalide en transition
1	1	0	Page invalide modifiée en transition

La table des pages du processus est stockée dans l’espace système paginé du processus.

Cet ensemble de structures de données permet d’accéder aux 4 Go réservés pour l’espace d’adressage virtuel d’un processus, comme le montre la Figure 6. Rappelons que chaque processus possède un répertoire des pages et plusieurs tables des pages.

Si nous considérons le cas où le répertoire des pages contient le maximum de PDE soit 1024 et la table des pages le maximum de PTE soit 1024 également, l’ensemble de l’espace d’adressage virtuel du processus est couvert. En effet, la taille d’une page est 4096 octets (4 Ko), l’espace d’adressage couvert par les structures est 1024 x 1024 x 4096, soit 4 Go.

La traduction de l’adresse virtuelle en adresse physique revient donc à parcourir un arbre dont la racine est le répertoire des pages, et les feuilles les pages physiques.

Une adresse virtuelle est codée sur 32 bits. Elle permet de référencer 2³² octets, soit la totalité de l’espace d’adressage virtuel d’un processus : 4 Go.

La traduction de l’adresse virtuelle est le mécanisme permettant d’accéder à une page physique grâce à l’adresse virtuelle. La Figure 7 décrit ce mécanisme. Elle est découpée en trois parties. Le champ PDE est le déplacement dans le répertoire des pages du processus. Le répertoire des pages fournit l’adresse de la table des pages associée au PDE. Le champ PTE est le déplacement dans la table des pages et permet d’accéder à la case où la page est chargée. Enfin le dernier champ est le déplacement dans la page physique pour atteindre l’adresse physique associée à l’adresse virtuelle.

La traduction de l’adresse virtuelle en adresse physique utilise en général un dispositif matériel d’accélération de la traduction : la TLB.

Pour le MIPS R4000 et les processeurs INTEL, la TLB est un tableau de mémoire associative, c’est-à-dire un vecteur dont les cellules peuvent être lues simultanément et comparées à une valeur cible.

Ce mécanisme est basé sur la théorie de la localité : une page récemment utilisée a une forte probabilité d’être utilisée dans un futur proche. La TLB recense les pages récemment utilisées et présentes en mémoire physique. Cette table est accédée à l’aide d’une fonction de hashcoding appliquée au numéro de page de l’adresse virtuelle. L’adresse virtuelle contenue dans la TLB permet la discrimination des synonymes.

La traduction par la TLB de l’adresse virtuelle est un mécanisme parallèle à celui de la traduction par le VMM. Si l’entrée de la TLB est valide et que l’adresse virtuelle correspond, alors l’accès à la page physique est possible si la protection l’autorise. Dans le cas contraire, le VMM se chargera de la traduction comme nous l’avons vu.

A chaque fois qu’une nouvelle page est chargée en mémoire physique, la TLB est mise à jour par le VMM. Si la TLB est pleine, une entrée de la table sera remplacée. Elle utilise une stratégie de remplacement LRU - Least Recently Used : l’entrée correspondant à une page physique, la plus ancienne à avoir été référencée, sera remplacée.

Si une page physique est recopiée sur le disque, le VMM marque « invalide » l’entrée de la TLB correspondant à cette page.

Lors d’un changement de contexte entre deux threads, la TLB peut devenir inutilisable. En effet, une traduction d’adresse pour un thread sera incorrecte pour le second, à moins que les deux threads appartiennent au même processus.

· Une information sur le « propriétaire » de chaque entrée de la TLB est fournie, c’est-à-dire quel processus est responsable de cette entrée (le MIPS R4000 fournit une adresse sur 36 bits ; les quatre bits supplémentaires permettent à Windows NT d’identifier le processus responsable de l’entrée). De cette façon, la TLB n’a pas besoin d’être vidée lors d’un changement de contexte.

Une amélioration apportée par Windows NT réside dans la gestion de la mémoire partagée. En effet, lorsque la page physique est partagée entre deux processus, le VMM insère un niveau supplémentaire d’indirection dans la table de gestion des pages : le PTE prototype - table des prototypes de page. La Figure 9 décrit ce mécanisme.

Le PTE prototype est une structure 32 bits semblable à une entrée de la table des pages qui permet au VMM de gérer le partage de pages sans avoir à mettre à jour les tables des pages de chaque processus. Comme le montre la Figure 10, chaque processus se partageant une page accède, par l’intermédiaire du prototype PTE et de sa table des pages, à la même page physique, tant que celle-ci n’est pas modifiée. Lorsqu’un processus modifie cette page, il suffit au VMM d’en faire une copie en mémoire physique (copy on write) et de modifier le prototype PTE du processus. La table des pages des processus n’est pas modifiée.

Les PTE prototypes sont alloués dans l’espace système paginé du processus, de sorte qu’ils peuvent éventuellement être eux-mêmes paginés.

Au début de ce chapitre, nous avons dit que le VMM utilisait le mécanisme de pagination à la demande. Une page n’est chargée en mémoire que lorsqu’un défaut de page se produit, c’est-à-dire, lorsqu’un thread d’un processus référence une page qui n’est pas chargée en mémoire physique ou n’est pas directement accessible. Le VMM utilise en fait un mécanisme de pagination à la demande avec regroupement. Lorsqu’un thread provoque un défaut de page, le VMM charge la page demandée en mémoire, plus quelques pages voisines. Cette technique permet de diminuer les défauts de pages. Elle s’appuie sur le principe qu’un programme a tendance à ne s’exécuter que dans une région localisée de son espace d’adressage, à un moment donné.

Lors d’un défaut de page, le choix de la case, dans laquelle la page sera chargée est déterminé suivant deux stratégies. Dans un premier temps, le VMM utilise la stratégie de placement. Si celle-ci échoue, il fera appel à la stratégie de remplacement.

Le VMM utilise une stratégie de remplacement local FIFO (First In First Out). A la création du processus, il lui alloue un nombre de cases fixes. Lorsque le processus a consommé toutes ses cases, le VMM libère une de ses cases à chaque défaut de page. Le choix de la case respecte la stratégie FIFO ; c’est-à-dire qu’il retire de la mémoire la page physique qui y est chargée depuis le plus longtemps, quelle que soit son utilisation.

Une optimisation apportée par Windows NT consiste à ne pas construire les tables des pages nécessaires pour l’ensemble de la mémoire allouée pour un thread. Cette technique s’appelle l’évaluation différée (lazy evaluation). Le VMM attend que le thread accède effectivement à la page pour construire les tables. L’évaluation différée apporte un gain de performance significatif pour des applications qui réservent beaucoup la mémoire mais qui l’utilisent peu.

Lorsqu’un thread alloue de la mémoire, le VMM doit retourner une plage d’adresses virtuelles qu’il peut utiliser. Cependant, du fait que la table des pages du processus n’est pas chargée avant que le thread accède effectivement à la mémoire, le VMM ne peut pas retrouver les adresses virtuelles libres dans la table. Il doit donc maintenir un autre ensemble de structures, les descripteurs d’adresses virtuelles, pour connaître celles qui sont déjà allouées dans l’espace d’adressage du processus et celles qui ne le sont pas encore.

Les descripteurs d’adresses virtuelles décrivent l’état de l’espace d’adressage du processus. Lorsqu’un processus alloue de la mémoire, le VMM crée un descripteur d’adresses virtuelles dans lequel il stocke les informations fournies lors de l’allocation de la mémoire :

Quand un thread accède pour la première fois à une adresse, le VMM met à jour une entrée de la table des pages du processus, pour la page contenant l’adresse. Pour cela, il recherche le descripteur d’adresse virtuelle dont la plage d’adresses contient l’adresse accédée et utilise les informations qui s’y trouvent pour remplir la rubrique de la table des pages.

Le gestionnaire de pages est le code du VMM chargé de transférer les pages entre le disque et la mémoire physique. Il est un intermédiaire important entre les mécanismes matériels et les règles du fonctionnement logiciel du VMM :

· Il fournit une protection pour les pages invalides et enrichit celles fournies par le matériel pour les pages valides,