Le tas est une partie de la mémoire qui est utilisé par la pile au
cours de l'interprétation. Il sert à stocker des tableaux, il est
utilisé lors de la déclaration et la suppression de ceux-ci, ainsi que lors
des accès et affectations d'une case de tableau. Pour réaliser ces opérations
le tas met à disposition de la pile quatre fonctions :
CreerTas(i,v)
permet d'allouer une place v dans le
tas pour un tableau nommé v .
RetirerTas(v,t)
libère la place du tableau situé à
l'adresse v .
AffecterTas(v1,v,v0)
affecte la case v0 du
tableau situé à l'adresse v1 du tas avec la valeur v .
ValeurTas(v1,v)
retourne la valeur de la case v
du tableau situé à l'adresse v1 dans le tas.
Le tas doit donc posséder une structure pour placer les
tableaux, mais aussi un système de garbage-collector afin d'optimiser les places libres du tas.
Afin de faire fonctionner le tas, il faudra gérer les places occupées
mais aussi les places libres. Lorsque l'on retire un tableau cela
provoque un espace libre au milieu du tas. Cet espace doit être utilisé
pour placer un autre tableau ou pour optimiser la place avec le
garbage-collector.
Pour gérer ceci, l'idée est d'utiliser trois structures : une structure
pour le tas lui-même, une autre pour les places occupées et une
dernière pour les places libres. Ces trois structures devant être
liées entre elles, on pourra prendre comme lien l'adresse de la
première case de l'espace concerné dans le tas.
La structure de places occupées va nous permettre d'accéder et
d'allouer les tableaux situés dans le tas. La structure de places
libres sera utilisé pour la recherche de place dans le tas mais aussi
pour le fonctionnement du garbage-collector.
Le tas fait partie de l'état mémoire, son fonctionnement est donc
indispensable pour la réalisation des interpréteurs. Dans un premier
temps, il a fallu créer une version du tas assez rapidement, c'est
pourquoi nous avons créé un tas simple avec les quatre fonctions détaillées
précédemment. Cette version plaçait bout à bout les tableaux dans le
tas sans se soucier des espaces vides.
Une fois la première version réalisée, nous sommes donc passé à la
réalisation de la version finale gérant les espaces vides et avec la
présence d'un garbage-collector.
Avant de livrer le tas pour l'intégrer au module d'état mémoire, ces
deux versions ont été testées avec des séries de tests que
nous allons présenter dans les sections suivantes.
Une structure représente le tas qui est un tableau
d'Object.
Une structure gère les espaces occupés dans le tas ; c'est un
tableau d'objet DescriptionTas.
Un structure gère les espaces vides dans le tas ;
c'est une structure en liste chaînée.
Nous avons vu que les espaces occupés étaient gérés avec l'objet
DescriptionTas, ce dernier est composé d'un identificateur (le
nom du tableau), d'une taille (la taille du tableau), d'une adresse
dans le tas (adresse de la première case du tableau) et d'une adresse
dans la pile (adresse dans la première case du tableau). Les deux
adresses permettent de faire une correspondance entre l'adresse du tas
qui peut changer pendant le travail du garbage-collector et l'adresse présente
dans la pile.
Les espaces libres sont gérés avec une liste chaînée d'objets
Case. L'objet Case contient l'adresse de la première case de
l'espace libre et la taille de l'espace libre.
Au début de l'interprétation, la structure d'espaces occupés ne
contient pas d'élément, tandis que la structure des espaces libres
posséde un seul élément qui est l'espace du tas puisque ce dernier est
vide.
Lorsqu'on insère un tableau on cherche un espace libre dans la
structure d'espaces libres, une fois l'espace trouvé on modifie les
espaces libres et on incrémente la structure d'espace occupé.
Si la recherche d'espace libre a échoué, le garbage-collector se
lance, et si le garbage-collector ne permet pas de faire une place
suffisante une exception est levée.
Le garbage-collector est déclenché lorsqu'il n'y a plus assez de place
pour placer le tableau que l'on souhaite allouer. Le
garbage-collector va alors parcourir les espaces libres et pour chaque
espace libre trouvé, il va effectuer une translation du tas de l'espace
libre. Une fois tous les espaces libres traités, le garbage-collector
aura créé un espace libre en fin de tas de la taille de
l'ensemble des espaces libres présents avant son lancement.
La seule erreur provoquée dans le tas est déclenchée lorsque le tas
est plein ou lorsque l'on veut allouer un tableau de taille supérieure
à la place libre dans le tas. Pour gérer cette erreur, nous avons créé
une exception tasplein qui va se déclencher lorsque le
garbage-collector ne peut plus faire assez de place pour placer le
tableau que l'on souhaite allouer.
Cet exemple (Fig 2.1 page ??) montre le fonctionnement du tas. Nous avons choisi une
taille de tas minime (soixante) afin que le garbage-collector se
déclenche facilement. Dans l'exemple des
tableaux sont alloués et désalloués afin de créer des trous dans le
tas. Ensuite, un tableau de taille supérieure à la taille de la plus grande
place libre est alloué, déclenchant ainsi le garbage-collector.
Afin de valider le fonctionnement du tas nous avons réalisé une série
de tests qui vérifient les fonctions du tas, les cas limite ou
encore le garbage-collector.
Une première série de tests concerne les fonctions utilisées dans la
pile RetirerTas, CreerTas, AffecterTas et
ValeurTas. Pour cela nous avons créé un programme Java
utilisant le tas comme devrait le faire la pile. Nous avons testé
l'allocation d'un tableau, son accès ainsi que son retrait.
Une deuxième série de tests concerne les cas limite avec le
déclenchement du garbage-collector, de l'exception tasplein,
mais aussi du fonctionnement de la structure des espaces libres et
des espaces occupés.
