Le schéma suivant![[*]](http://cadillac.lip6.fr/~emmanuel/icons/foot_motif.gif){kind=icon}
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
================
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.
liste_entier suivant :
struct cons {int car; struct cons *cdr;};
typedef struct cons *liste_entier;
cons qui ajoute un entier à une liste d'entier et retourne la nouvelle liste en utilisant malloc.
intervalle qui prend deux entiers a et b
et construit la liste de tous les entiers entre a et b.
eratosthene(1000) dans ces deux cas?
}
\newcommand{\addverb}{
}
\newcommand{\addverb}{
La compilation et l'exécution :
$ gcc -o crible crible.c $ crible 100 [ 97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2 ]
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?
mon_malloc qui utilise la zone
déclarée par init_alloc.
mon_free qui libère une cellule de cette zone.
}
\newcommand{\addverb}{
}
\newcommand{\addverb}{
Et la ligne de commande
$ gcc -o crible_mm alloc_man.c crible_mm.c $ crible_mm 100 100 [ 97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2 ] $ crible_mm 98 100 Plus d'espace
Mark & Sweep : 2 étapes
nécessite une information sur la taille des objets :
caractéristiques
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.
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.
sweep qui explore le tas et reconstruit
la liste des cellules libres en enlevant les marques des cellules à conserver.
gc qui récupère automatiquement
l'espace disponible dans le tas.
mon_malloc qui déclenche le GC s'il n'y a plus de
place disponible et qui retourne l'espace libéré.
struct?
}
\newcommand{\addverb}{
}
\newcommand{\addverb}{
Compilation et exécution :
$ gcc -DTRACE -o crible_gc gc_alloc.c crible_gc.c $ crible_gc 30 10 l1=[ 7 5 3 2 ] Apres GC numero 1, 16 cellules sont libres l_g=[ 7 5 3 2 ] l1=[ 7 5 3 2 ] Apres GC numero 2, 16 cellules sont libres l_g=[ 7 5 3 2 ] l1=[ 7 5 3 2 ] l2=[ 7 5 3 2 ] $ crible_gc 20 10 l1=[ 7 5 3 2 ] Apres GC numero 1, 14 cellules sont libres Apres GC numero 2, 2 cellules sont libres Apres GC numero 3, 0 cellules sont libres Plus d'espace
S'il n'y toujours pas assez de place après un GC, le programme doit s'arreter. Une manière de contourner ce problème serait d'augmenter le tas à ce moment là. De toute manière il existe toujours une limite non franchissable.
Si un entier correspondant à la valeur d'un pointeur valide est scanné par le GC, la zone pointée sera conservée (ainssi que ses descendants).
Comme le GC explore tous les mots de la zone statique et de la pile, cette information sera récupérée.
On trouvera sur la machine maya.cicrp.jussieu.fr les
programmes suivants :
Mark&Sweep pour les listes d'entiers;
dans le catalogue /users/p6ipens/chaillou/enseignements/97-98/programmation/TD2.
N'hésitez pas à les compiler, les tester, les lire et les modifier!!!
Stop & Copy
to-space) pour recopier et compacter la mémoire à conserver (from-space).
from-space est recopiée dans l'espace to-space.
caractéristiques
cdr
la nouvelle adresse de la cellule déplacée.