Le mécanisme de swap disque autorise la manipulation par un processus utilisateur d’un espace d’adressage mémoire de taille supérieure à l’espace mémoire physique disponible sur le matériel. Le principe est d’utiliser une partition de swap pour étendre l’espace mémoire physique.
Nous allons illustrer ce mécanisme sur des processus menant des calculs sur des matrices de très grande taille. Voir l’encart.
Dans un premier temps, nous allons présenter les fonctions utiles à la gestion de la partition de swap. Nous utiliserons ensuite ces fonctions pour supporter une mémoire virtuelle aussi grande que possible, malgré la taille réduite de la mémoire physique. Nous utiliserons enfin cette mémoire virtuelle pour différents algorithmes et allocations mémoire de matrices.
Une partition de swap est un ensemble de blocs pouvant être directement lus ou écrits sur un disque. À un bloc correspond une page virtuelle. La taille de la partition est égale à la taille de la plage mémoire adressable virtuellement.
On ne dispose d’une unique partition de swap. Les deux fonctions utilitaires suivante assure transfert de données entre le swap et la mémoire physique :
int store_to_swap(int vpage, int ppage); int fetch_from_swap(int vpage, int ppage);
Les fonctions retournent une valeur négative en cas d’échec, 0 en cas de succès.
Ces fonctions doivent bien entendu être exécutées en mode maître du microprocesseur.
On trouvera une implémentation de ces fonctions dans le fichier misc/swap.c accessible sur le dépôt
https://gitlab-etu.fil.univ-lille1.fr/ms1-ase/src
On se propose maintenant d’implémenter un nouveau handler d’interruption de la MMU capable de gérer un grand nombre de pages virtuelles dans une petite mémoire physique, à l’aide du swap disque. Dans un premier temps, la politique de remplacement est très simple : elle n’utilise qu’une seule page de mémoire physique. Toutes les pages de mémoire virtuelle sont mappées sur la page de mémoire physique numéro 1 (et pas la page 0 qui contient le vecteur d’interruptions).
Le handler d’interruptions associé à la MMU est donc appelé quand l’adresse accédée est fautive. Si elle est dans l’espace d’adressage virtuel, comme elle est fautive, elle ne correspond pas à la page qui est en actuellement en mémoire physique. On sauvegarde donc cette page dans le fichier de swap et on supprime le mapping dans la TLB pour cette page. Il s’agit ensuite de charger la page correspondant à l’adresse fautive et de mettre à jour la TLB en conséquence.
La première implémentation fournie est très lente car elle sous-exploite la mémoire physique disponible. À un instant donné, seule une page de données est stockée en mémoire. Toutes les autres données sont placées dans le fichier swap.
Nous allons maintenant étendre ce mécanisme afin d’utiliser toute la mémoire physique dont on dispose. Quand on a besoin d’une page de mémoire physique pour réaliser le mapping d’une nouvelle page de mémoire virtuelle, on vide une page de mémoire physique sur le fichier de swap.
On choisira la page de mémoire physique à vider sur le fichier de swap par un simple algorithme tourniquet (round robin).
Il est nécessaire de mémoriser les correspondances entre les pages virtuelles et les pages physiques, correspondances qui évoluent au fur et à mesure des accès mémoire réalisés. La TLB ne mémorisant que les associations récemment utilisées sous la forme d’un cache, nous nous devons de définir une structure permanente pour mémoriser ces associations. Il nous sera nécessaire d’accéder à cette information à la fois à partir de l’adresse de page virtuelle, mais aussi à partir de l’adresse de page physique.
L’implantation du handler d’interruptions de la MMU consiste maintenant à choisir, si nécessaire, une nouvelle page de mémoire physique pour la page de mémoire virtuelle fautive, à maintenir les deux tableaux vm_mapping[] et pm_mapping[], et à renseigner la TLB avec l’association résultante. On prendra garde à ne pas utiliser la page 0 de mémoire physique.
Multiplication de «grandes» matrices
Nous souhaitons donc manipuler de «grandes» matrices, c’est-à-dire des matrices dont la taille est supérieure à celle de la mémoire physique dont on dispose.
Nous manipulons des matrices carrés de dimension N. Pour ranger 3 matrices carrées, il nous faut 3 × N2 × sizeof(unsigned) octets de mémoire.
On vérifiera que la valeur de N (MATRIX_SIZE) définie assure en effet une utilisation mémoire de taille supérieure à la mémoire physique disponible.
Le code d’initialisation, addition, et multiplication de matrices vous est fourni. Le dépôt
https://gitlab-etu.fil.univ-lille1.fr/ms1-ase/srccontient dans matmul une base de travail pour le TP sur la virtualisation avec swap. Le Makefile construit deux binaires :
- Le programme mmu_manager issu de mmu_manager.c est un squelette que vous devrez compléter. Pour l’instant, il se contente d’appeler la fonction user_process() fournie dans le fichier user_process.c. Cette fonction doit être appelée en mode utilisateur du CPU, et se charge d’additionner ou de multiplier deux matrices de grande taille. Vous serez amenés à modifier les constantes définies dans matrix.h et user_process.c pour paramétrer la taille des matrices et le type de calcul à réaliser.
- Le programme oracle se charge de vérifier que le résultat du calcul matriciel est correct, afin de s’assurer que la mémoire virtuelle fonctionne correctement, sans compromettre les calculs. Ce programme lit sur l’entrée standard la sortie de la fonction user_process. Il effectue, sans émulation de MMU, les mêmes calculs matriciels, puis affiche OK ou KO après avoir comparé ses résultats aux résultats de user_process.
Le programme oracle analysant le résultat affichée par votre programme sur la sortie standard, ne modifiez par ce résultat, préférez donc l’utilisation de fprint(stderr, ...) à de simples printf().
Pour valider vos développements, utilisez par exemple
./mmu_manager | ./oracleafin de lancer les calculs, puis d’en vérifier les résultats.
On pourra aussi utiliser
./mmu_manager | tee /dev/stderr | ./oraclepour dupliquer la sortie standard vers le terminal et la commande oracle.
Programmeur, le matériel tu n’oublieras point !
On s’intéresse à la manipulation de la matrice suivante :
char matrix[N][N];
Exercice 10 (Défauts de page?) Avec des pages de taille P, combien de défauts de page se produisent lors de l’exécution du code suivant ?int i, j; for (i = 0; i < N; i++) for (j = 0; j < N; j++) matrix[i][j] = (i + j) % 128;
Exercice 11 (Inversion de boucles) On change légèrement le code précédent en accédant au tableau par simple échange de l’ordre d’imbrication des boucles. Comment cela affecte-t-il le nombre de défauts de pages ?int i, j; for (j = 0; j < N; j++) for (i = 0; i < N; i++) matrix[i][j] = (i + j) % 128;Rappelons que la multiplication de matrices C = A × B «bête et méchante» correspond au code
int i, j; for (i = 0; i < N; j++) for (j = 0; j < N; i++) for (k = 0; k < N; i++) C[i][j] += A[i,k] + B[k,j];
Exercice 12 (Allocation pour la multiplication de matrices) En s’inspirant des exercices précédents, proposez un moyen d’accélérer la multiplication de matrices dans notre mémoire virtuelle.[fin du document (pour cette année...)]