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.
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.
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.
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.
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.
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.
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.
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.