Retour au cours.

1. Première exercice : Gestion mémoire par liste chaînée

On étudie d'abord l'algorithme le plus simple utilisé pour la gestion mémoire des processus et du noyau.

1.1.  Liste de zones libres (free list)

Le problème à résoudre est celui de la gestion des zones libres ou allouées par malloc(), ainsi que l'implémentation des allocations et libérations proprement dites. On va simuler notre propre gestion mémoire sur une zone de 16MO, soit 224 octets, initialement vide. Une solution simple et économique consiste à ne mémoriser que l'ensemble des zones libres, via une liste simplement chaînée :

1.1.1.  Question 1

Décrivez les étapes associées à l'allocation et à la libération d'une zone de mémoire.

Pour que cette méthode de gestion soit applicable, quelle hypothèse faut il faire sur la taille minimale des zones libres, et donc sur la taille minimale et l'alignement des zones allouées ?

Quelle est la complexité au pire de ces opérations ?

1.1.2.  Question 2

La fonction free() ne spécifie pas la taille de la zone à libérer. Étendez la gestion précédente pour permettre un tel comportement, sans utilisez plus de mémoire que le strict nécessaire pour stocker la taille de chaque zone allouée.

1.1.3.  Question 3

Étudiez l'évolution de la fragmentation externe de la mémoire, et construisez une séquence d'allocations et de libérations aboutissant à une occupation de moins de 1% de la mémoire mais l'impossibilité d'allouer une zone contiguë de plus de 1000 octets.

1.2.  Implémentation

On souhaite réaliser une bibliothèque partagée (voir td 1) et non un exécutable traditionnel (pour une raison qui apparaîtra à la question suivante). Cette bibliothèque déclare un tableau de caractères de taille 224 et exporte les fonctions suivantes :

Comment manipuler un tableau de caractères pour y stocker des entiers ?

Vous allez probablement dans l'exercice allouer statiquement un tableau de caractères, et avoir ensuite à écrire des entiers dedans. Pour cela, vous devez utiliser des cast un peu compliqués. L'idéal est donc de définir une macro :

#define MYMEM(x) ( *(int*)(&mem[x]) )

mem est un tableau d'octets (char), et l'argument x est l'indice du caractère où vous voulez écrire un entier (int). Vous pouvez ensuite utiliser cette macro dans votre programme :

MYMEM(0) = 42;
MYMEM(4) = 0;
...
s = MYMEM(0);
Utilisez le squelette contenu dans l'archive suivante pour réaliser cette implémentation. Vous effectuerez ensuite une compilation sous forme de bibliothèque partagée comme indiqué dans le TD n°1
Testez cette bibliotheque en compilant un programme principal effectuant des séquences d'allocation et de libération prédéterminées.
Pour faciliter le débuggage, vous pouvez utiliser la fonction fournie qui teste la validité de la structure mémoire à savoir l'agencement des zones libres et occupées. Vous pouvez également affichez la fragmentation à chaque allocation/libération de mémoire.

1.3.  Détournement de la gestion mémoire

Afin de tester notre gestionaire mémoire de façon plus appronfondie, on utilise un mécanisme général pour détourner les appels de fonction, celui de la variable d'environnement LD_PRELOAD (lisez le manuel de ld.so (8) pour plus d'informations). Mais avant de pouvoir remplacer totalement la gestion mémoire la libc, il nous faut rajouter les fonctions calloc et realloc à notre biblothèque.

Décrivez les étapes nécessaires à la réallocation de la mémoire.

Ajoutez ensuite les 2 fonctions manquantes à votre bibliothèque pour fournir toute les fonctions nécessaire à la gestion de la mémoire.

Enfin ajoutez la déclaration des fonctions malloc(), calloc(), realloc() et free(), en détournant leur implémentation par un appel aux fonctions my_pool_xxxxx() précédentes.

Pour utiliser LD_PRELOAD, dans un autre terminal , tapez la commande

setenv LD_PRELOAD ./memory.so

ou

export LD_PRELOAD=./memory.so

en fonction de votre shell.

Lancez des commandes, e.g., sleep 1, ls, xterm (en ordre croissant de complexité) et vérifiez leur fonctionnement. Si vous atteignez la limite de mémoire, recompilez la bibliothèque partagée avec une taille de tableau plus grande (mais pas trop afin de tester la fragmentation). Emacs comportant des erreurs mémoires, il n'est pas conseillé de le tester.
Étudiez à nouveau la fragmentation, en appelant my_pool_fragmentation() dans la fonction malloc(), par exemple.
La correction est disponible en suivant ce lien.

2. Deuxième exercice : Gestion mémoire par l'algorithme Buddy Allocation

Cliquez ici pour continuer le TD.