Mémoire en C

Organisation mémoire d'un programme

Le schéma suivant montre l'organisation de l'espace d'adressage d'un processus.

                --------------
                |            |
 zone           |            |    instruction (texte)
 statique       |            |
                --------------      
                |            |
                |            |    variables statiques et externes
                |            |
               ================
                |            |
                |  tas       |   zone dynamique (tas)
                |            |
                --------------   point de rupture
                |            |
               ................ limite de la page superieure
                |            |
                |            |
                |            |

 zone          //           //   <----  adresses illegales

dynamique       |            |
                |            |
               ................ limite de page
                |            |
                --------------  sommet de pile
                | pile       |  
                |            |  
                --------------

En C la pile est gérée automatiquement par le système. Elle contient les déclarations locales, les paramètres des fonctions. Comme la portée de ces variables est connue, le compilateur C ajoute dans le code engendré les instructions de gestion de pile.

Le programmeur peut agir sur la zone des données (statique ou dynamique). L'accès à une adresse illégale engendre le signal SIGSEGV. Sous Unix, le point de rupture est l'adresse virtuelle la plus petite en dehors de cet espace de données. Comme l'allocation de mémoire s'effectue par page, il est possible d'accéder au delà du point de rupture si on reste dans la page allouée.

Il peut être utile de connaître et de modifier le point de rupture. Pour cela on utilise les fonctions brk et sbrk :

int brk(char *adr) positionne le point de rupture en adr retourne 0 ou -1

caddr_t sbrk(inc) ajoute inc au point de rupture retourne l'ancienne valeur ou (caddr_t)-1

On différencie la zone de variables statiques en deux zones : celle des variables initialisées et celle des variables non initialisées. Seule la première zone doit être effectivement stockée dans le fichier objet. En effet les valeurs d'initialisation doivent être conservées et non calculées à l'exécution. Pour les variables non initialisées, il n'est pas utile de les stocker sur fichier car le contenu n'est pas défini. L'espace nécessaire sera alloué à l'exécution. Voici l'organisation de la zone statique sous Linux :

                --------------  <---- _end 
                |            |
 zone           |            |    variables statiques et externes 
 statique       |            |     non initialisees
                --------------  <---- _edata      
                |            |
                |            |    variables statiques et externes
                |            |     initialisees 
                --------------  <---- _etext
                |            |
                |            |  code
               ================

Optimisation de l'allocation

On cherche à évaluer les performances de malloc et free. Pour cela on écrit tout d'abord un programme gourmand en mémoire, ensuite on écrit une gestion mémoire plus rapide que malloc en allouant en une seule fois une grande zone mémoire pour les listes d'entiers.

Crible d'Eratosthene

On travaillera sur le type liste_entier suivant :

struct cons {int car; struct cons *cdr;};
typedef struct cons *liste_entier;

1.

Ecrire une fonction cons qui ajoute un entier à une liste d'entier et retourne la nouvelle liste en utilisant malloc.

2.

Ecrire une fonction intervalle qui prend deux entiers a et b et construit la liste de tous les entiers entre a et b.

3.

Ecrire une fonction qui calcule la liste des nombres premiers inférieurs à un n donné. On utilisera l'algorithme du crible d'Eratosthene. Ecrire une version sans récupération mémoire et une autre version avec récupération mémoire.

4.

Que pouvez-vous dire sur l'occupation mémoire après l'appel de eratosthene(1000) dans ces deux cas?

Allocation optimisée

1.

Ecrire une fonction init_alloc qui alloue en une fois une zone mémoire pouvant contenir n cons. Que faut-il faire sur cette zone pour pouvoir l'utiliser ensuite par un malloc utilisateur?

2.

Ecrire une fonction mon_malloc qui utilise la zone déclarée par init_alloc.

3.

Ecrire une fonction mon_free qui libère une cellule de cette zone.

Récupération automatique de liste_entier

Généralités sur les algorithmes explorateurs

• algorithmes explorateurs : techniques utilisables pour explorer à un instant donné l'ensemble des objets accessibles (graphe orienté).
• pointeur externe : un pointeur mémorisé dans un objet inaccessible au GC.
• racines de ce graphe :
  un sous-ensemble des pointeurs externes à partir duquel on atteint tous les objets du graphe.

Mark & Sweep : 2 étapes

• marquage des zones mémoires utiles à partir d'un ensemble de racines,
• récupération des zones mémoires non marquées.

nécessite une information sur la taille des objets :

• indiquée à l'allocation,
• ou calculée selon des pages mémoire d'objets de certaines tailles.

caractéristiques

• dépend de la taille totale du tas;
• récupère toute la mémoire;
• ne compacte pas la mémoire (fragmentation);
• localisation non assurée.

1.

Ecrire une fonction init_GC, version modifiée de init_alloc, qui conserve les informations de début et de fin du tas, ainsi que les informations sur la zone statique et sur la pile. On utilisera pour déterminer la zone statique les symboles globaux end et edata. On calculera l'adresse de début de pile et son sens en faisant un calcul sur les adresses des variables locales.

2.

Ecrire une fonction qui détermine si une valeur (un pointeur) est un pointeur sur une liste d'entier.

3.

Ecrire une fonction mark qui prend un pointeur valide en entrée et le marque dans le tas (| 1) sur le champ cdr) et marque les descendants s'il y en a de ce pointeur.

4.

Ecrire une fonction sweep qui explore le tas et reconstruit la liste des cellules libres en enlevant les marques des cellules à conserver.

5.

Ecrire une fonction gc qui récupère automatiquement l'espace disponible dans le tas.

6.

Utiliser les fonctions précédentes pour modifier la fonction mon_malloc qui déclenche le GC s'il n'y a plus de place disponible et qui retourne l'espace libéré.

7.

Que se passe-t-il s'il n'y a toujours pas assez de place après un GC?

8.

Que se passe-t-il si un entier (correspondant à la valeur d'un pointeur valide) se trouve dans la pile?

9.

Que se passe-t-il si une liste d'entiers apparaît comme champ d'une valeur struct?

Utilisation des programmes décrits

On trouvera sur la machine maya.cicrp.jussieu.fr les programmes suivants :

• stat.c : programme de calcul de la zone de données statiques;
• pile.c : programme de calcul du sens de la pile;
• crible.c : programme classique du crible (utilise crible_gen.c);
• crible_gen.c : le programme générique pour le crible;
• alloc_man.c : optimisation de l'allocation;
• crible_mm.c : utilise alloc_man.c et crible_gen.c;
• gc_alloc.c : GC Mark&Sweep pour les listes d'entiers;
• crible_gc.c : utilise gc_alloc.c et crible_gen.c.

dans le catalogue /users/p6ipens/chaillou/enseignements/97-98/programmation/TD2.

N'hésitez pas à les compiler, les tester, les lire et les modifier!!!

1.

Que faut-il changer au GC proposé pour l'intégrer dans votre projet sur les polynômes?

2.

Implanter ces modifications et tester les sur votre programme.

3.

Proposer une modification de l'algorithme pour qu'il fonctionne avec des listes d'entiers et des listes de mônomes.

4.

Comment faire pour récupérer automatiquement des arbres binaires?

5.

Réfléchissez à une solution pour tout type de données : listes, arbres, graphes et autres.

Exercice facultatif : Récupération automatique de liste_entier

Stop & Copy

• utiliser une mémoire secondaire (to-space) pour recopier et compacter la mémoire à conserver (from-space).
  
• à partir du l'ensemble de racines (rootset), la partie utile de la zone from-space est recopiée dans l'espace to-space.
  
• En cas de partage, indiquer dans l'objet déplacé sa nouvelle adresse, qui sera retournée en cas de nouvelle recopie.
  
• mise à jour du rootset

caractéristiques

• dépend de la taille des objets à conserver
• seule la moitié de la mémoire est disponible
• compacte la mémoire
• possibilité de localisation

1.

Modifier les fonctions d'allocation et de récupération pour implanter ce GC pour les listes d'entiers. Pour la copie, on inclura dans le champ cdr la nouvelle adresse de la cellule déplacée.

2.

Que se passe t-il si un entier correspond à une adresse valide? Comment peut-on différencier un pointeur d'un entier?

Bibliographie

• Eric Spir, "Gestion Dynamique de la mémoire dans les langages de Programmation", InterEditions, Science Informatique.
• Jean-Marie Rifflet, "La Communication sous Unix", EdiSciences.
• Rémy Card, Eric Dumas et Franck Mevel, "Programmation Linux 2.0", Eyrolles.