1. 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 2²⁴ 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 :

chaque zone libre commence par un noeud de cette liste ;
chaque noeud contient la taille de la zone libre et le pointeur sur la zone libre suivante.

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 100 octets.

1.2. Implantation

Réalisez une bibliothèque partagée (et non un exécutable traditionnel, pour une raison qui apparaîtra à la queston suivante) qui déclare un tableau de caractères de taille 2²⁴ et qui exporte les fonctions suivantes :

void *my_pool_malloc (size_t size); qui simule malloc() dans le tableau réservé ; lors du premier appel, cette fonction doit initialise le tableau avec la liste de zones libres (pointée depuis une variable globale) ;
void my_pool_free (void *); qui simule free ;
double my_pool_fragmentation (); retourne 1 moins le ratio entre taille de la plus grande zone libre contiguë et la mémoire totale restant disponible (en pourcents).

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(tab,x) ( *(int*)(&tab[x]) )

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

MYMEM(tab,0) = size;
MYMEM(tab,4) = NULL;
...
size = MYMEM(tab,0);

Vous appellerez votre programme memory.c et vous créerez votre bibliothèque partagée avec la commande

gcc -shared -g -o memory.so memory.c

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, 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, 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 pour plus d'informations).

Ajoutez la déclaration des fonctions malloc() et free(), en détournant leur implémentation par un appel des fonctions my_pool_malloc() et my_pool_free() précédentes.

Dans un autre terminal , tapez la commande

setenv LD_PRELOAD ./memory.so

export LD_PRELOAD=./memory.so

en fonction de votre shell.

Puis lancez des commandes, e.g., sleep 1, ls, emacs (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).

Étudiez à nouveau la fragmentation, en appelant my_pool_fragmentation() dans la fonction malloc(), par exemple.

2. Gestion mémoire par l'algorithme du Buddy System

On cherche à la fois à réduire la complexité au pire et la fragmentation. L'idée consiste à gérer un arbre binaire de zones libres et occupées, en ne considérant que des décompositions en puissances de 2, et en favorisant l'allocation dans la zone libre la plus petite possible.

Pour cela, on commence par se ramener à des allocations mémoire de taille 2ⁿ octets, par approximation supérieure. Cela cause une autre forme de fragmentation, appelée interne, mais cette dernière est bornée par construction (typiquement 50% dans le pire cas).

Pour minimiser la fragmentation interne, il convient d'autoriser des allocations de taille aussi petite que possible. Comme nous allons devoir représenter l'arbre binaire des zones libres et occupés, il convient de ne pas décomposer trop finement ces zones afin de limiter la taille de l'arbre. En pratique, l'algorithme est typiquement réservé à la gestion des pages mémoire, et on considèrera ici que les zones manipulées sont de taille minimale 2¹² octets (la taille des pages par défaut sur x86) et de taille maximale 2²⁴ octets (toute la mémoire).

Lors de l'allocation, l'algorithme recherche le buddy libre de taille minimale mais supérieure ou égale à la taille demandée. Si celui-ci est plus grand, il est découpé récursivement jusqu'à obtenir un "buddy feuille" de la taille demandée. Lors de la libération, les buddies libres adjacents sont fusionnés tant que leurs adresses de base sont multiples de leur taille (contrainte de struture des buddies). Voici un exemple :

	64KO	64KO	64KO	64KO	64KO	64KO
t=0	1024KO
t=1	A-64KO	64KO	128KO	256KO		512KO
t=2	A-64KO	64KO	B-128KO	256KO		512KO
t=3	A-64KO	C-64KO	B-128KO	256KO		512KO
t=4	A-64KO	C-64KO	B-128KO	D-128KO	128KO	512KO
t=5	A-64KO	64KO	B-128KO	D-128KO	128KO	512KO
t=6	128KO		B-128KO	D-128KO	128KO	512KO
t=7	256KO			D-128KO	128KO	512KO
t=8	1024KO

Ce schéma d'allocation correspond à la séquence suivante :

allocation A de 33KO à 64KO,
allocation B de 65KO à 128KO,
allocation C de 33KO à 64KO,
allocation D de 65KO à 128KO,
libération de C,
libération de A,
libération de B,
libération de D.

On pourra utiliser arbre binaire de 2¹³-1 noeuds, ou 12 tableaux de taille 2⁰ à 2¹² (au choix). Un noeud ayant la valeur 0 sera considéré comme un buddy inutilisé (potentiellement père ou frère d'un buddy utilisé), sinon il contient la taille effective de la zone réservée, inférieure ou égale à 2^24-k où k est la profondeur du noeud.

2.1. Conception

Reprenez les questions de l'exercice (1.1) ; vous étudierez la complexité en fonction de la taille demandée.

En supposant que toutes les allocations concernent des zones de taille supérieure ou égale à 2¹², quelle est le degré de fragmentation externe maximal pour cet algorithme ?

2.2. Implantation

Reprenez les questions de l'exercice (1.2) avec un programme appelé buddy.c et une bibliothèque buddy.so.

Pour faciliter le codage de l'arbre de buddies, on pourra le stocker dans un tableau de 2¹³ entiers 32 bits, les fils du noeud i étant conventionnellement rangés dans les éléments 2i et 2i+1 du tableau.

2.3. Fragmentation interne

Afin de lutter contre la fragmentation interne, on combine les deux algorithmes. L'idée consiste ainsi à munir chaque buddy libre de taille 2¹²d'une liste de zones libres, afin de gérer les allocations/libérations de petites zones.

Pourquoi ne munit on pas les buddies plus grands de listes de zones libres de la même manière ?

Implantez cette solution hybride et évaluez à nouveau la fragmentation.