L'objectif de ce TP est d'utiliser le langage A6000 tel que vous l'avez développé jusqu'ici, avec fonctions et tableaux, pour écrire un programme intéressant.
Le programme proposé manipule un grand tableau, dans lequel il simule un gestionnaire de mémoire. Une fois ce programme écrit, vous pourrez récupérer le code assembleur produit par la version actuelle de votre compilateur et l'intégrer dans une nouvelle version de votre compilateur, de sorte que les programmes compilés avec cette nouvelle version utilisent votre système de gestion de mémoire.
On propose quatre stratégies : B étend A, C est indépendante des deux premières, et D regroupe B et C.
Remarque : pour faire tout cela, mieux vaut avoir implémenté l'extension variables globales. À défaut, il faudra modifier toutes les fonctions pour qu'elles prennent en paramètres supplémentaires les données du gestionnaire de mémoire. En outre, les gestionnaires automatiques nécessitent l'extension distinction valeurs/pointeurs.
A. Gestionnaire manuel Malloc/Free
Vous avez besoin de :
- Un tableau de type []integer dans lequel chaque case correspond à un mot mémoire.
- Une variable globale membase donnant l'adresse réelle de la première case du tableaux, pour les conversions entre indices dans le tableau et adresses en mémoire.
B. Gestionnaire automatique Mark & Sweep
À partir du gestionnaire A, déclencher une phase de récupération automatique lors d'une allocation pour laquelle il n'existe pas de bloc assez grand disponible.
Pour cela, chaque bloc doit avoir dans son entête une indication de son statut (non vu, vu, traité). Vous devez alors écrire un parcours des blocs mémoire, qui doit nécessairement être en style itératif (c'est-à-dire : pas de fonctions récursives) et travailler sans autre espace mémoire que le tableau auquel il est appliqué.
Dans l'écriture de la fonction de récupération vous supposerez que les racines ont déjà été marquées comme vues. Ensuite, au moment d'intégrer le code obtenu à votre compilateur principal, il faudra ajouter à la main un morceau de code qui, au début de chaque phase de récupération, parcourt la pile et les registres et marque toutes les racines.
Remarquez en passant que le parcours de la pile peut lui-même être simulé par le parcours d'un tableau bien choisi, et que les registres eux-mêmes peuvent être copiés dans la pile et donc intégrés à ce tableau. Cela vous permettra de réduire drastiquement la quantité (et la complexité) du code assembleur à écrire à la main.
C. Gestionnaire automatique Stop & Copy
Vous avez besoin de :
- Deux tableaux de type []integer, dans lesquels chaque case correspond à un mot mémoire.
- Des variables globales basea et baseb donnant l'adresse réelle de la première case de chacun de ces tableaux, pour les conversions entre indices dans le tableau et adresses en mémoire.
- Une variable globale membase contenant soit basea soit baseb, selon le tableau utilisé.
- Deux variables globales memcurrent et memlimit donnant respectivement les adresses de la première case libre et de la limite supérieure du tableau utilisé.
L'allocation d'un bloc de n mots (4*n octets) consiste à incrémenter memcurrent de n, à condition que cela ne conduise pas à dépasser memlimit.
En cas de dépassement, déclencher une phase de récupération de mémoire, en prenant comme espace de destination le tableau non utilisé. Pour cela, implémenter l'algorithme de Cheney et modifier les variables mem* pour rendre effectif le remplacement d'un tableau par l'autre.
S'il n'y a toujours pas suffisamment d'espace disponible après récupération de la mémoire, interrompre le programme.
Comme commenté dans la stratégie B, vous pourrez aussi avoir un tableau représentant la pile, ou écrire à la main une passe de marquage préalable des racines à appliquer avant l'algorithme de Cheney. Ici, il faudra de plus ajouter une passe finale modifiant dans la pile et les registres les adresses de tous les blocs copiés.
D. Gestionnaire automatique à deux niveaux
Utiliser un tas "mineur" de type Stop & Copy (de taille modérée) et un tas "majeur" de type Mark & Sweep (la mémoire principale).
L'allocation se fait dans le tas mineur. En cas de dépassement, déclencher une phase Stop & Copy, modifiée de sorte que les blocs copiés dans l'espace de destination soient en réalité alloués dans le tas majeur (et que le tableau courant reste le tableau d'origine, maintenant considéré comme vide).