TP5: Gestion d'une mémoire paginée

Ce travail pratique vaut 5% de la note totale du cours. Comme le stipule le plan de cours, le travail doit être fait individuellement.

Objectifs

Ce travail pratique vise les objectifs suivants:

1. Distinguer les adresses virtuelles et physiques;
2. Maîtriser le concept de la mémoire paginée;
3. Implémenter diverses fonctions nécessaires à l'utilisation de la mémoire paginée;
4. Comprendre pourquoi surviennent les fautes de pages et ce qu'il faut faire pour les traiter;
5. Utiliser une table des pages et une table des pages inversée dans un système réel.

Préparation

Survol

Dans ce TP, vous devrez mettre en place un système d'allocation pour une mémoire paginée. Ce système est très similaire à celui utilisé dans les ordinateurs modernes. Toutefois, dans le contexte de ce TP, nous utiliserons un système contenant beaucoup moins de mémoire que ce que doit gérer votre ordinateur ou votre téléphone intelligent. Ce système possède les caractéristiques suivantes:

• Taille des pages (et des trames) mémoire : 32 octets;
• Taille totale de la mémoire virtuelle : 640 octets, soit 20 pages distinctes;
• Taille de la mémoire vive (RAM) dans laquelle les trames (frames) sont stockées : 96 octets, soit 3 trames.

Afin de faciliter votre tâche, nous avons déjà découpé le code à produire en plusieurs fonctions, que vous pourrez programmer et tester indépendamment. Vous trouverez plus d'informations sur chacune de ces fonctions dans la section détails ci-bas.

Pour toutes questions concernant la procédure de remise ou le travail lui-même, posez vos questions sur Piazza!

Détails

1. Présentation générale

Le simulateur ne pouvant directement émuler un disque dur, nous utiliserons plusieurs zones dans sa mémoire de données pour simuler un système tel que décrit à la section précédente. Trois zones sont ainsi déclarées dans la mémoire de données:

• MaRAM : espace de 96 octets commençant à l'adresse 0x1000;
• MonDisqueDur : espace de 640 octets commençant à l'adresse 0x10E0;
• MaPile : espace de 200 octets commençant à l'adresse 0x1364.

Afin de faciliter leur visualisation dans l'afficheur mémoire du simulateur, toutes ces sections sont séparées par des espaces vides. MaRAM est l'espace que nous utiliserons pour simuler la RAM de votre système à mémoire paginé. Ainsi, lorsque l'on parlera d'aller lire une donnée à l'adresse 0x04 de la RAM, cela équivaut, dans le contexte du simulateur, à aller lire à l'adresse 0x1000 + 0x04 = 0x1004. De la même manière, MonDisqueDur est l'espace que nous utiliserons pour simuler une mémoire de stockage telle qu'un disque dur, sur laquelle le système peut décharger les pages de la RAM au besoin. Finalement, MaPile est un espace mémoire indépendant que vous pourrez utiliser pour sauvegarder les registres lors de l'exécution des fonctions que vous devez coder.

2. Accès à la mémoire paginée

Dans un "vrai" système à mémoire paginée, la pagination devrait être transparente aux programmes, c'est-à-dire que toutes les instructions LDR et STR devraient référer directement à des adresses virtuelles. Dans notre cas, afin de simplifier la mise en place du système, cette pagination ne sera pas transparente pour les programmes. Ainsi, un accès mémoire tel que LDR Rx, [Ry] devra être effectué par les étapes suivantes:

• Mettre dans R8 la valeur de l'adresse que l'on souhaite lire (Ry);
• Appeler la fonction LoadVirtuel, qui mettra dans R9 la valeur lue (Rx).

; Equivalent de LDR Rx, [Ry]
MOV R8, Ry
BL LoadVirtuel ; Effectue le "LDR". Après, R9 contient la valeur de Rx

De la même manière, une écriture en mémoire comme STR Rx, [Ry] sera simulée par les étapes suivantes:

• Mettre dans R8 la valeur de l'adresse à laquelle on souhaite écrire (Ry);
• Mettre dans R9 la valeur que l'on veut écrire (Rx);
• Appeler la fonction StoreVirtuel, qui effectuera cette écriture

; Equivalent de STR Rx, [Ry]
MOV R8, Ry
MOV R9, Rx
BL StoreVirtuel ; Effectue le "STR"

Les fonctions LoadVirtuel et StoreVirtuel sont déjà écrites pour vous, mais elles nécessitent l'implémentation des autres fonctions pour fonctionner!

3. Les structures de données

Afin de remplir la tâche demandée, vous aurez besoin de trois structures de données : la table de pages, la table de pages inverse et les compteurs d'accès. Ces structures correspondent à ce qui a été vu dans le cours sur la gestion de la mémoire.

3.1 La table de pages

La table de pages est la structure qui fait le lien entre les pages et les trames présentes en RAM. Dans ce TP, vous utilisez une mémoire virtuelle de 20 pages, il y a donc 20 entrées dans cette table. Elle est située à l'adresse 0x04. Lors de l'exécution de votre programme, cette table pourrait par exemple ressembler à ceci :

Dans ce cas-ci, la table de page indique que la page 0 est présente en RAM dans la trame 0, que la page 8 est dans la trame 1 et que le contenu de la page 16 est située dans la trame 2. Toutes les autres pages ont -1 (0xFFFFFFFF) comme valeur de trame pour indiquer qu'elles ne sont pas en mémoire.

3.2 La table de pages inverse

La table de pages inverse met en relation les trames et les pages qu'elles contiennent. Elle peut donc être vue comme l'inverse de la table de pages : au lieu de chercher quelle trame correspond à une page donnée, on cherche quelle page correspond à une trame donnée. Puisque nous utilisons 3 trames en RAM, cette table possède donc 3 entrées. Par exemple, son état pourrait être le suivant :

Dans ce cas-ci, la table indique que la trame 0 contient la page 0, que la trame 1 contient la page 8 et que la trame 2 contient la page 0x10=16. Cette représentation est exactement l'opposé de la table de page présentée plus haut. Cette table inverse vous sera utile lorsque vous voudrez évincer une page de la RAM, puisqu'il faut alors connaître le numéro de cette page pour pouvoir la copier sur le disque dur.

3.3 Les compteurs d'accès

La dernière structure est un tableau de compteurs d'accès. Chaque trame mémoire possède son propre compteur, si bien que cette table a donc 3 entrées. Chaque entrée indique combien de cycles d'accès mémoire se sont écoulés depuis que cette trame a été accédée. Par exemple, une trame qui vient d'être accédée verra son compteur remis à 0; toutes les autres verront leur compteur incrémenté. Un exemple type de l'état des compteurs est donnée à la figure suivante :

La mise à jour de ces compteurs est faite par la fonction AjusteCompteurAcces, qui est déjà codée pour vous. Vous devrez cependant déterminer la page à retirer de la RAM, sachant que l'on souhaite toujours retirer la page la moins récemment utilisée (algorithme LRU, pour « Least Recently Used »).

4. Détail des fonctions à écrire

La mise en place d'un système à mémoire paginée n'est pas simple, aussi la structure du code à écrire a déjà été établie pour vous. Cette structure est présentée à la figure suivante :

Dans ce diagramme, chaque boîte correspond à une fonction. Chaque ligne allant vers la droite correspond à un appel de fonction (BL nomdelafonction), et chaque ligne allant vers la gauche à un retour de fonction (BX LR). Les fonctions dont le nom est en blanc sont déjà écrites pour vous. Vous n'avez donc rien à faire pour ces dernières, si ce n'est les utiliser. Par contre, vous devez implémenter les fonctions dont le nom est de couleur orange sur ce diagramme. Ces fonctions sont décrites en détail dans le code fourni dans l'onglet simulation, avec des informations concernant:

1. Les paramètres d'entrée : quels registres contiendront les entrées requises pour l'exécution de la fonction;
2. Les valeurs de retour (sortie) : quels registres doivent être modifiés par la fonction. Tous les autres registres utilisés par la fonction doivent être préalablement sauvegardés puis restaurés avant la fin de la fonction;
3. Une description du comportement attendu de la part de la fonction;
4. Les suppositions que vous pouvez faire dans le cadre de cette fonction. Un exemple d'une telle supposition pourrait être la taille des pages mémoire;

5. Test de votre programme

Tester et déboguer un programme assembleur complexe n'est pas simple. Afin de vous aider dans ce travail, nous vous fournissons des tests pré-implémentés. Ceux-ci se situent dans le bloc main. Les premiers tests visent une seule fonction à la fois, de manière à vous permettre de programmer chaque fonction indépendamment. Une fois tous les tests individuels réussis avec succès, vous pouvez passer aux tests globaux, qui vérifient le bon comportement de votre système en utilisation réelle. Il ne sert à rien de passer aux tests globaux si un des tests précédents a échoué, puisque toutes les fonctions doivent fonctionner correctement pour que les tests globaux produisent des résultats valides.

La vérification de la réussite des tests est faite avec les commandes ASSERT. Par exemple, la ligne ASSERT R2=2 indique qu'après l'exécution de l'instruction précédente, R2 devrait contenir la valeur 2. Un « X » s'affichera à la gauche de cette ligne si la condition n'est pas rencontrée.

Si vous rencontrez des erreurs dans les tests, affairez-vous à régler ces erreurs avant de passer aux tests suivants, car plusieurs tests assument que toutes les fonctions précédentes fonctionnent correctement.

Pondération

Tel que mentionné précédemment, le code compte pour 100% de la note de ce TP. Chacune de vos fonctions sera tout d'abord évaluée indépendamment des autres en employant la pondération suivante:

• DecomposeAdresse: 10%
• TrouverPage: 15%
• TrouverValeurMaximum: 20%
• CopieMemoire: 5% (cela ayant déjà été évalué dans le TP3)
• ChargerPage: 20%
• EvincerPage: 20%

La réussite des tests globaux compte pour 10% de la note totale.

Ressources

• Manuel d'utilisateur du simulateur;
• Fichier d'information sur les instructions ARM;

Remerciements

Merci à Marc-André Gardner pour la création de ce TP!