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

Date limite: 11 avril 2016 à 23h59

Ce travail pratique vaut 3% de la note totale du cours. À faire individuellement, il est à remettre au plus tard lundi le 4 avril 2016 à 23h59.

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

Pour ce travail pratique, nous réutiliserons l'environnement « IAR Embedded Workbench ». Si vous n'êtes pas familier avec ce système, ou si vous n'êtes plus certain des étapes à effectuer pour créer un nouveau projet, il est important que vous consultiez les notes pour le travail pratique 3 afin d'assurer que vous démarrez le TP dans un environnement adéquat.

Important: lisez attentivement tout l'énoncé avant de commencer à travailler! Il contient plusieurs informations qui vous seront très utiles.

Questionnaire

Ce TP ne contient pas de questions à répondre sur le portail des cours. Le fichier asm.s que vous remettrez compte donc pour 100% de la note de ce TP.

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:

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. Téléchargez le fichier asm.s pour obtenir le squelette de votre TP. Vous trouverez plus d'informations sur chacune de ces fonctions dans la section détails ci-bas.

Téléversez votre fichier asm.s qui contient votre réponse dans la boîte de dépôt qui est disponible dans le portail des cours.

La politique des retards mentionnée dans le plan de cours sera appliquée. Pour toutes questions concernant la procédure de remise ou le travail lui-même, posez vos questions sur le forum!

Détails

1. Présentation générale

IAR 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:

Afin de faciliter leur visualisation dans l'afficheur mémoire d'IAR, 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 d'IAR, à aller lire à l'adresse 0x100000 + 0x04 = 0x100004. 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:

; 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:

; 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'ils ne sont pas en mémoire.

Notez que chaque entrée de la table de pages fait 4 octets (32 bits).

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 fichier asm.s fourni, 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. Finalement, le nombre d'instructions utilisées pour implémenter cette fonction dans le solutionnaire. Ce nombre n'est donné qu'à titre indicatif et vous n'avez en aucun cas à vous limiter à ce nombre d'instructions. Aucun point ne sera retiré simplement parce qu'une de vos fonctions est trop longue. Toutefois, cette information peut vous aider à estimer si vous êtes sur la bonne voie : si le nombre d'instructions utilisées dans le solutionnaire est de 3 et que vous en êtes à votre 92e ligne d'assembleur pour cette fonction, c'est probablement parce que vous avez mal compris la tâche à effectuer.

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 n'est pas automatique : c'est à vous de le faire. Pour vous y aider, certaines lignes se terminent par des commentaires de la forme ; >>> condition. Ces commentaires signifient qu'une fois cette ligne exécutée, la condition devrait être valide. Par exemple, le premier test se lit comme suit : 

BL DecomposeAdresse     ; >>> R0 = 6, R1 = 4

Il signifie donc qu'une fois que la fonction DecomposeAdresse aura été appelée, la valeur de R0 devrait être de 6, et la valeur de R1 devrait être 4. Toute autre valeur indique une erreur dans la fonction DecomposeAdresse, que vous devriez régler avant de passer à la suite.

Ressources

Remerciements

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

Retour à la page web du cours.