Année universitaire 2000-2001

 espace

Licence d'informatique
Module 4 - partie « C / shell »


Projet de C (version 1.03) :

Système de gestion de la mémoire
et techniques de « ramasse-miettes ».

  Le projet qui est décrit ci-après doit être réalisé en binôme. Exceptionnellement, la réalisation en monôme pourra être acceptée, mais ce choix devra être justifié et vous est fortement déconseillé. La constitution des binômes sera relevée lors de la dernière séance de TP. Le projet de chaque binôme sera évalué par un oral, durant la deuxième quinzaine de janvier 2001, une fois les examens du module 4 terminés, à une date et selon des horaires de passage qui vous seront précisés ultérieurement. Le projet comporte quatre niveaux de difficulté croissante, numérotés de 1 à 4. La réalisation complète et exacte de chaque niveau donne la possibilité d'obtenir une certaine note maximale, comme cela est indiqué dans le tableau suivant :
 

Niveau :  Questions à réaliser :  Note maximale : 
1  Jusqu'à la question 6 incluse  12 
2  Jusqu'à la question 10 incluse  15 
3  Jusqu'à la question 14 incluse  18 
4  Jusqu'à la question 16 incluse  20

  Notez que « commencer un niveau » implique d'avoir complètement réalisé le niveau précédent. Il est conseillé de découper le projet en modules, en rajoutant un module par niveau abordé.

  Le jour de l'évaluation, chaque binôme devra :

  Des tests supplémentaires pourront être demandés par les enseignants. La note obtenue par chaque membre du binôme prendra en compte tous ces éléments.

Objectif du projet.

  La mémoire est l'espace où sont stockées les applications des utilisateurs pour être exécutées, ainsi que les données qui leur sont associées. L'allocation (ainsi que la libération) des zones mémoires se fait de façon dynamique, au fur et à mesure que les demandes parviennent au « système de gestion de la mémoire ». À tout instant, la mémoire peut être vue comme une succession de zones mémoires libres et de zones mémoires occupées, comme cela est décrit par la figure suivante :

  Les zones libres (parties non grisées) indiquent que ces espaces peuvent être alloués à de nouvelles applications. Les parties grisées indiquent que ces zones sont déjà réservées et ne peuvent pas être allouées. Chaque zone mémoire occupée sera appelée, dans la suite, un « tas ». Un tas peut contenir un programme, un sous-programme ou tout simplement des données (variables, etc...).

  On supposera dans ce projet que la taille de la mémoire est fixe et égale à une valeur qui sera demandée à l'utilisateur et stockée dans une variable globale taille_memoire de type int. Cette valeur indique le nombre maximal d'octets qui peuvent être alloués aux applications. La mémoire est indexée de 0 à taille_memoire-1. Chaque indice sera appelé une « adresse mémoire ».

Attention :

1. Premier niveau : primitives de base d'un système de gestion de la mémoire.

Le premier niveau consiste à réaliser la gestion simplifiée des zones mémoires libres et des tas. Ces zones seront représentées par deux listes chaînées (une pour les zones libres et une pour les tas) et on utilisera des structures très similaires à celles qui ont été utilisées dans la séance 4 de travaux pratiques (gestion d'un agenda).

1.1. Représentation des zones libres et des tas.

  Chaque cellule de la première liste chaînée correspond à une zone libre de la mémoire. On définit les structures suivantes : 

struct zone_libre
{
   int adresse;
   int taille;
};

struct liste_libre
{
   struct zone_libre bloc;
   struct liste_libre *p_suivant;
};

  où :

Remarque :

  De manière équivalente, chaque cellule de la deuxième liste chaînée correspond à un tas. On définit les nouvelles structures suivantes : 

struct tas_occupe
{
   char ident[TAILLE_IDENT];
   int adresse;
   int taille;
};

struct liste_tas
{
   struct tas_occupe tas;
   struct liste_tas *p_suivant;
};
où :

1.2. Exemple.

  Supposons que taille_memoire vaille 600 et qu'à un certain instant, la mémoire ait la configuration suivante :

  Les zones libres sont alors représentées par la liste chaînée suivante :

  Quant aux tas, ils sont représentés par la liste chaînée suivante :

  Dans cet exemple, on suppose que la constante TAILLE_IDENT vaut 7, que le premier tas s'appelle "toto" et le deuxième tas "var"

1.3. Initialisation des listes chaînées.

Question 1 :

  À l'état initial (au début de l'exécution du programme), la liste des zones libres est composée d'une seule cellule où le champ adresse est initialisé à 0, et où le champ taille est initialisé à taille_memoire. Quant à la liste des tas, elle ne contient aucune cellule. Écrire la fonction d'initialisation des données servant à gérer la mémoire, ayant l'en-tête suivant : 

   int initialiser(struct liste_libre **pp_liste_libre,
			struct liste_tas **pp_liste_tas)

  Cette fonction renverra 0 si tout se passe bien et -1 en cas de problème.

1.4. Gestion des zones libres.

  Dans cette partie, on ne se préoccupe que de la première liste chaînée.

Question 2 :

 Écrire la fonction : 
   int allouer(int t,struct liste_libre **pp_liste_libre)
qui permet d'allouer une zone mémoire de taille t. L'allocation se fait selon l'algorithme suivant :

Question 3 :

  Écrire la fonction : 
   int liberer(int adresse_libre,int taille_libre,
			struct liste_libre **pp_liste_libre)
qui consiste à rajouter une zone libre dans la liste, d'adresse adresse_libre et de taille taille_libre. Cette fonction renvoie 0 si elle a pu mener l'opération à bien, et -1 si elle a rencontré un problème. Cette nouvelle zone doit être fusionnée avec les zones libres voisines, si cela est possible. Plus précisément, on suivra les étapes principales suivantes :

Remarque :

1.5. Gestion simultanée des zones libres et des tas.

  En fait, lorsqu'une zone passe de l'état libre à l'état occupé (et inversement), cela a des répercussions à la fois sur l'ensemble des zones libres et sur l'ensemble des tas, et donc aussi sur les listes chaînées qui les représentent. C'est ce phénomène qu'on se propose de gérer dans cette partie.

Question 4 :

  Écrire la fonction : 
   int allouer_tas(char identite_tas[],int taille_tas,
		struct liste_libre **pp_liste_libre,
			struct liste_tas **pp_liste_tas)
qui crée une nouvelle cellule dans la liste des tas. Cette fonction renvoie, si tout se passe bien, l'adresse de la zone allouée, et -1 sinon. La création suit les étapes principales suivantes :

Question 5 :

  Écrire la fonction : 
   int liberer_tas(char identite_tas[],struct liste_libre **pp_liste_libre,
			struct liste_tas **pp_liste_tas)
qui consiste à supprimer le tas identifié par identite_tas et à libérer l'espace qu'il occupe. Une fois de plus, cette fonction renvoie 0 en cas de succès et -1 en cas d'échec.

Question 6 :

  On suppose que les instructions données par les utilisateurs au système de gestion de la mémoire sont stockées dans un fichier primitives.txt de type « fichier de texte ». Chaque ligne de ce fichier représente une « primitive » et doit être de l'une des formes suivantes : 
   initialiser
   allouer_tas nom_tas taille_tas
   liberer_tas nom_tas
   terminer
   ligne vide
   ligne de commentaire (ligne commençant par #)
  Écrire, dans le programme principal, la suite d'instructions C permettant d'exécuter les primitives qui se trouvent dans le fichier primitives.txt

  Par ailleurs, on veut garder une trace des différents traitements effectués par le système de gestion de la mémoire. Pour cela, on utilisera un fichier historique.txt (de type texte, ouvert en écriture) où, à chaque fois qu'une primitive est traitée, on écrira si la primitive a été exécutée avec succès ou non. Dans le deuxième cas, on demande d'afficher le type d'erreur rencontré (espace insuffisant, identificateur inexistant, primitive inconnue, etc...).

2. Deuxième niveau : ramasse-miettes à base de compteurs de références.

  Jusqu'à présent, on a supposé que les tas étaient des zones indépendantes. On va maintenant considérer que les tas peuvent se référencer entre eux. Par exemple, un tas contenant un programme peut référencer les tas où sont stockées les variables qu'il a créées dynamiquement. Le but de cette partie est de simuler un système de « ramasse-miettes », qui consiste à récupérer les tas inutilisables (ceux qui n'ont pas été libérés explicitement par l'utilisateur). Un tas est dit « inutilisable » s'il n'est pas accessible (ou « référencé »), de façon directe ou indirecte (c'est-à-dire par le biais de tas accessibles), à partir de « programmes », qui sont des tas particuliers censés représenter des zones de code exécutable (c'est-à-dire les programmes des utilisateurs).

  Les programmes seront représentés par une liste chaînée constituée de cellules du type suivant : 

struct programme
{
   char ident[TAILLE_IDENT];
   struct programme *p_suivant;
};
où ident est l'identificateur du tas (présent dans la liste des tas), qui désigne le code exécutable du programme en question.

  Une première technique pour récupérer les tas inutilisables consiste à associer à chaque tas un compteur, que l'on appellera "compteur de référence". Ce compteur indique le nombre de tas qui le référencent. Il est incrémenté de 1 dès qu'un nouveau tas le référence, et est décrémenté de 1 dès qu'un tas le libère (c'est-à-dire dès qu'un tas libère le lien). Un tas est inutilisable dès que son compteur est égal à 0.

On propose d'enrichir la structure tas_occupe, qui devient maintenant : 

struct tas_occupe
{
   char ident[TAILLE_IDENT];
   int adresse;
   int taille;
   int compteur_references;
   char liste_ident[MAX_REF][TAILLE_IDENT];
};
où :

Question 7 :

  Modifier la fonction initialiser de la question 1 pour que cette dernière initialise aussi la liste des programmes. Cette fonction doit maintenant avoir l'en-tête suivant : 
    int initialiser(struct liste_libre **pp_liste_libre,
		struct liste_tas **pp_liste_tas,
			struct programme **pp_liste_programmes)

Question 8 :

  Écrire les fonctions suivantes : qui consistent respectivement à :   Dans chacune des ces fonctions, on mettra à jour le compteur de références des tas référencés. Naturellement, ces fonctions renvoient 0 en cas de succès et -1 en cas d'échec.

  Mettre à jour le programme principal, de manière à pouvoir traiter les nouvelles primitives suivantes : 

   ajouter_programme nom_programme
   supprimer_programme nom_programme
   ajouter_lien nom_tas_referencant nom_tas_reference
   supprimer_lien nom_tas_referencant nom_tas_reference

  Ces nouvelles primitives devront bien sûr apparaître dans le fichier historique.txt

Question 9 :

  Écrire la fonction : 
   int ramasse_miettes_compteurs(struct liste_libre **pp_liste_libre,
		struct liste_tas **pp_liste_tas)
qui consiste à supprimer les tas ayant le compteur de référence à 0 et à rajouter les tas récupérés dans la liste des zones libres. Une fois de plus, cette fonction renvoie 0 en cas de succès et -1 en cas d'échec.

Question 10 :

3. Troisième niveau : ramasse-miettes à base de marquage/balayage.

  La technique de ramasse-miettes à base de compteurs de références a l'avantage de récupérer rapidement les tas inutilisables. Cependant, son inconvénient est qu'elle ne récupère pas les « cycles ».

  On propose d'utiliser une nouvelle technique de ramasse-miettes, qui procède en deux étapes :

  1. Étape de « marquage », qui consiste à marquer tous les objets accessibles depuis les programmes.


  2. Étape de « balayage », qui consiste à récupérer tous les tas qui n'ont pas été marqués lors de la première étape.

  Pour cela, on enrichit à nouveau la structure tas_occupe en lui rajoutant un nouveau champ : 

   char drapeau;
qui peut prendre deux valeurs : 'N' si le tas est « marqué » et 'B' sinon.

Question 11 :

  Modifier la fonction allouer_tas de manière à prendre en compte le champ drapeau.

Question 12 :

  Écrire la fonction : 
   int marquage(struct liste_tas *p_liste_tas,
		struct programme *p_liste_programmes)
qui consiste à marquer tous les objets accessibles depuis les programmes. On n'utilisera aucune nouvelle structure pour l'écriture de cette fonction. Au départ, on marquera (valeur du champ drapeau égale à 'N') tous les tas désignés par la liste des programmes. Ensuite, on utilisera un algorithme itératif qui parcourt plusieurs fois la liste des tas. À chaque parcours, et à chaque fois que l'on rencontre un tas marqué, on procède au marquage des tas qu'il référence. Cet algorithme s'arrête si, à la fin d'un parcours de la liste, aucun nouveau tas n'a été marqué. La fonction marquage renvoie 0 en cas de succès et -1 en cas d'échec.

Question 13 :

  Écrire la fonction : 
   int balayage(struct liste_libre **pp_liste_libre,
		struct liste_tas **pp_liste_tas)
qui récupère tous les tas inutilisables et renvoie un entier indiquant le succès de l'opération (0 pour un succès, -1 pour un échec). Cette fonction est identique à ramasse_miettes_compteurs à ceci près que le « test de tas récupérable » ne se fait pas par rapport au compteur de références, mais par rapport à la valeur du champ drapeau.

Question 14 :

  Écrire la fonction : 
   int ramasse_miettes_marquage_balayage(struct liste_libre **pp_liste_libre,
		struct liste_tas **pp_liste_tas,
			struct programme *p_liste_programmes)
qui combine les deux fonctions précédentes et, comme toujours, renvoie 0 ou -1 en fonction de son succès ou de son échec. Modifier la fonction allouer qui, s'il n'y a pas de zone disponible pour l'allocation après l'exécution de ramasse_miettes_compteurs, doit lancer la fonction ramasses_miettes_marquage_balayage.

4. Quatrième niveau : questions subsidiaires.

Question 15 :

  Au lieu de considérer le first fit pour la fonction allouer, on demande d'implémenter les deux alternatives suivantes : le best fit, qui minimise le résidu, et le worst fit, qui maximise le résidu, c'est-à-dire la taille de la cellule mémoire laissée libre lorsqu'on alloue une zone à l'intérieur d'une autre zone de taille strictement supérieure (cf. description de la question 2).

Question 16 :

  Regrouper les données servant à gérer la mémoire dans une structure du type suivant : 

struct memoire
{
   int taille_memoire;
   void *mem;
   struct liste_libre *p_liste_libre;
   struct liste_tas *p_liste_tas;
   struct programme *p_liste_programmes;
};
  Modifier les en-têtes des différentes fonctions du projet pour passer une structure memoire en paramètre, au lieu des différents pointeurs de listes chaînées. Allouer la mémoire (champ mem) à l'intérieur de la fonction initialiser.