Mis à jour le 21 mars 2006

TD 9

TD 9

Mardi 22 mars 2005

L'objectif de ce td est d'ajouter un tas, géré par un mécanisme simple de mémoire virtuelle, à la machine virtuelle que nous développée lors du td précédent.

Commencez par copier dans votre répertoire de travail les fichiers instr.ml, machine.ml, system.ml et main.ml qui correspondent, à de petites différences près, à la solution du td précédent et à des exemples de code permettant de tester les accès mémoire.

Afin de permettre la simulation de l'accès à une mémoire, deux instructions ont été ajoutées à la machine virtuelle. L'instruction Load (addr, r) qui copie la valeur présente à l'adresse mémoire addr dans le registre r et l'instruction Store (r, addr) qui copie la valeur contenue dans le registre r à l'adresse addr.

Un fichier memory.ml a été ajouté. Il contient le code relatif à la gestion de la mémoire. Pour l'instant, ce fichier ne contient qu'une gestion directe de la mémoire sans mécanisme de mémoire virtuelle. Les fonctions get et set de ce module sont appelées par les instructions Load et Store de la machine pour accéder à la mémoire. Dans cette version, Memory.get et Memory.set accèdent donc directement aux cases du tableau Memory.memory.

Le but du td est donc de remplacer cette implantation pour utiliser un mécanisme de mémoire virtuelle, i.e. de traduire au vol les adresses virtuelles en adresses réelles (physiques, dans Memory.memory) en utilisant une table de pages.

Le système stocke le numéro de la page (en mémoire) physique qui contient la table des pages de chaque processus dans son registre preg.(pt). Cette table a la taille d'une page (Memory.page_size). Chaque entrée de la table des pages est constituée de deux entiers. Le premier représente le mode d'accès à la page du processus : UN non chargée en mémoire; RW chargée avec accès en lecture/écriture et COW chargée, mais doit être copiée avant la première écriture. Le second entier de l'entrée correspond au numéro de la page en mémoire physique (si cela a un sens).

Pour compiler, lancer :

ocamlc -o main instr.ml memory.ml machine.ml system.ml main.ml

Si vous lancez main 0, celui-ci doit afficher 12 et 13.

1 Gestion des pages

Dans cette partie, on se prépare à la gestion des pages physiques.

Définir un tableau Memory.free_pages qui permet de connaître, pour chaque page, le nombre de processus qui référencent cette page. Écrire également une fonction Memory.new_page : unit -> int qui recherche une page vide dans la mémoire (suite à des désallocations la mémoire peut se retrouver fragmentée), la réserve, la remplit de 0, puis retourne le numéro de cette page. Si la mémoire est pleine, lever une exception Out_of_memory.

En utilisant, les informations du tableau Memory.free_pages réécrire une fonction Memory.used_page : unit -> bool valide qui retourne false si toutes les pages sont libres. Cette fonction est utilisée dans main.ml pour vérifier à la fin que vous avez bien libéré la mémoire de chaque processus. Vérifiez que le programme de test main 0 n'affiche pas qu'il y a des pages non libérées.

2 Table des pages

On désire maintenant ajouter à notre machine une gestion de mémoire virtuelle. La mémoire physique Memory.memory est découpée en Memory.page_number pages physiques. Une page physique k (donc avec 0 < k < Memory.page_number) correspond donc aux adresses physiques entre k × page_size incluse et (k+1) × page_size exclue.

Chaque processus dispose d'une table de pages qui associe à chaque page virtuelle (entrée dans la table des pages) une page physique. La table des pages est elle-même maintenue en mémoire dans une page physique dont le numéro est placé dans le registre preg.(pt). Pour l'instant on se limitera à un seul processus (le processus initial). Une adresse physique est donc déterminée univoquement par le numéro physique de la table des pages et une adresse logique.

Écrire une fonction entry_address ptable page_nb: int -> int -> int qui retourne l'adresse physique de l'entrée (mode et adresse physique) correspondant à la page logique page_nb, connaissant la page physique ptable de la table des pages.

Modifier les fonctions Memory.get: int -> int -> int et Memory.set: int -> int -> int -> unit afin de lire ou écrire le contenu d'une adresse logique, connaissant la page physique ptable de la table des pages. Lorsque la page n'est pas réservée (UN) les fonctions lèvent l'exception Page_fault avec le numéro de la page logique en argument. On supposera pour l'instant que les pages sont soit non réservées, soit réservées en écriture.

Écrire une fonction Memory.allocate_page ptable page_nb: int -> int -> unit qui réserve une nouvelle page physique pour la page logique page_nb connaissant la page physique ptable de la table des pages.

Écrire une fonction Memory.new_ptable: unit -> int qui retourne une nouvelle page physique après en avoir fait une table de pages vide.

Modifier la fonction System.init_state afin de réserver la table des pages du processus initial.

Modifier maintenant la fonction System.page_fault afin de réserver une page en cas de faute de page. Tester votre programme en vérifiant qu'après utilisation de la table des pages le programme main 0 affiche le même résultat que sans table de pages.

Normalement, le programme de test précédent doit indiquer qu'il reste des pages non libérées. En effet, les pages allouées dynamiquement par le système en fonction des besoins doivent être désallouées à la fin des processus.

Écrire une fonction Memory.release_ptable ptable size qui libère toutes les pages associées à la table des pages dont la page physique est ptable et dont le nombre de pages est size.

Modifier finalement l'appel système sys_Exit afin de libérer les pages mémoires réservées à la fin des processus. On vérifiera que toutes les pages sont bien désallouées en appelant main 0.

3 Multi-processus

On désire maintenant combiner la gestion de processus et la mémoire virtuelle. Pour cela, nous allons commencer par gérer la mémoire en recopiant toutes les pages au moment de l'appel à fork.

Écrire une fonction Memory.clone_ptable ptable size qui clone la table des pages dont la page physique est passée en argument et dont le nombre de pages est donné par size.

Modifier maintenant l'appel système sys_Fork pour prendre en compte l'utilisation de la mémoire virtuelle. Tester cette modification en appelant main 1 qui crée trois processus qui effectuent des accès mémoire et qui doivent normalement afficher 12, 12, 13, 12, 14, 12, 13, 12 et 14.

4 Copie paresseuse

Plutôt que de copier toutes les pages lors de la création d'un processus fils, la plupart des systèmes commence par partager les pages et attentent qu'ait lieu une écriture pour réaliser la copie effective (si l'accès a lieu en lecture, la copie n'est pas nécessaire). Pour cela, lors du fork les pages partagées sont marquées COW (Copy On Write) et elles sont recopiées lors d'un accès en écriture set.

Modifier les fonctions Memory.clone_ptable pour supporter la copie paresseuse.

Modifier la fonction Memory.set pour tenir compte de ce changement. Tester vos modifications en appelant à nouveau main 1.

5 Réservation de mémoire

Par défaut dans le système Unix, les processus ne peuvent pas accéder à n'importe quelle page de leur espace d'adressage. Avant de pouvoir accéder à une page, il faut d'abord qu'ils la réservent grâce à l'appel système brk en modifiant la valeur du champs ptable_size du processus.

Attention, l'appel système brk peut diminuer la taille de la table des pages et il faut alors désallouer les pages qui ne sont plus accessibles.

Écrire l'appel système sys_Brk.

Modifier enfin la fonction System.page_fault pour prendre en compte cette information lors d'une faute de page pour lever une exception Segmentation_fault lors de l'accès à une page hors limite. Testez vos modifications en appelant le programme de test main 2 qui doit afficher 12, 13, 12, 14, Segmentation fault, 12, 13, 12, 14, Segmentation fault.

Ce document a été traduit de L^AT_EX par H^EV^EA