Utilisation d’une liste implicite¶

L’algorithme le plus simple utilisant le principe de header dédiés utilise une liste implicite. Cet algorithme peut trouver un bloc libre d’une taille demandé, s’il existe, en suivant un à un les cases de header. Il parcoure ainsi l’ensemble des blocs réservés et libres, comme illustré par la figure ci-dessous.

Le parcours de cette liste peut ressembler alors au pseudo-code suivant, où p est un pointeur vers une case mémoire et start le début du heap :

p = start;
while (p < end &&           // fin de liste ?
       ((*p & 0x1) != 0 ||  // déjà alloué
        *p <= len))         // trou trop petit
    p = p + (*p & ~0x1);    // progresse vers le prochain bloc

On notera ici l’utilisation conjointe d’opérateurs binaires (&) pour accéder à la valeur du bit de poids faible du header, et des opérateurs logiques (&& et ||). Il ne faut pas les confondre !

Le parcours de la liste va trouver, s’il existe, un espace assez grand pour accueillir la zone dont la création est demandée. Cette zone peut être trop grande et doit alors être scindé en une zone réservée et une nouvelle zone libre, comme illustré par la figure ci-dessous.

La fonction de placement d’un nouveau bloc de taille len au pointeur pointé par p retourné précédemment peut ressembler au pseudo-code suivant :

void place_block(ptr p, int len) {
  int newsize = len + 1;                // ajoute 1 mot pour le header
  int oldsize = *p & ~0x1;              // récupère taille actuelle sans bit de poids faible
  *p = newsize | 0x1;                   // nouvelle taille avec bit de poids faible à 1
  if (newsize < oldsize)                // s'il reste de la place ...
    *(p + newsize) = oldsize - newsize; // nouveau bloc vide avec la taille restante
}

L’exécution de ce code est assez simple. Il faut simplement faire attention ici à ne pas laisser le bit de poids fort pour le header du nouveau bloc. Bien entendu, l’adresse qui est retournée au code client n’est pas p mais p-1 : le header n’a pas a être visible par l’application qui n’a accès qu’au bloc de données proprement dit.

La manière la plus simple de libérer un bloc avec une liste implicite consiste à passer le drapeau, stocké dans le bit de poids faible du header, à 0. Ainsi, un appel à free(p) peut simplement exécuter *(p-1)= *(p-1) & ~0x1;. Cette méthode naïve présente deux désavantages majeurs :

• Tout d’abord, elle ne vérifie pas que le pointeur passé à free() est un pointeur valide. Il est possible de simplement modifier un bit dans un mot utilisé pour stocker des données, ce qui peut entraîner des bogues particulièrement difficile à découvrir. Il est préférable de stopper l’exécution du programme si free() est appelé pour une adresse invalide. Pour cela toutefois, il est nécessaire de parcourir de nouveau la liste depuis le début pour savoir si l’adresse du header p-1 est bien valide. Le coût de free() devient donc O(n) où est le nombre de blocs, et plus O(1).
• Ensuite, cette méthode entraîne un problème de fausse fragmentation. On peut ainsi plusieurs blocs libres les uns à la suite des autres, mais aucun de ces blocs n’est suffisant pour accueillir une demande d’allocation. Cette situation est illustrée par la figure suivante. Une requête malloc(8) arrive, et bien qu’il existe deux blocs de tailles 5 et 7 contiguës, il n’y a pas de bloc de taille 9 disponible.

Il y a deux manières de répondre au problème de la fausse fragmentation. Une première serait de laisser les blocs contigus tels quels, et de modifier la fonction de recherche de bloc pour qu’elle prenne en compte leur existence lors de la recherche d’un bloc libre. Cette approche est dite paresseuse (lazy en anglais) car elle procrastine le travail jusqu’au dernier moment. Elle a ses avantages, mais elle complique la mise en œuvre de la fonction malloc(3). Nous laissons son développement en exercice au lecteur.

Une seconde approche est de regrouper les zones libres lors du traitement du free(3). Dans l’exemple de la figure précédente, il est possible de regrouper les deux blocs libres pour en former un seul.

Le pseudo-code de la fonction free_block, prenant en argument l’adresse du header à libérer, peut être :

void free_block(ptr p) {
  *p = *p & ~0x1;          // remise à 0 du drapeau
  next = p + *p;           // calcul de l'adresse du header du bloc suivant
  if ((*next & 0x1) == 0)  // si ce bloc est aussi libre ...
    *p = *p + *next;       // combiner les blocs
}

On remarque toutefois que cette méthode est incomplète. En effet, elle permet de fusionner un bloc libre avec les blocs qui le suive, mais pas avec les blocs qui le précèdent. Ce problème est caractéristique d’une liste chaînée simple : on ne sait simplement pas revenir en arrière. Il y a deux solutions possibles à ce problème. Une première solution est de garder un historique des adresses des derniers headers vus lors du parcours (par exemple sur la pile), et de re-parcourir les blocs libres jusqu’à atteindre celui sélectionné, puis ses successeurs. Cette solution impose un surcoût en mémoire lors de l’exécution de free(3) mais ne nécessite pas de modifier Une deuxième méthode, plus simple à mettre en œuvre mais entrainant un surcoût d’utilisation mémoire, est d’utiliser un liste chaînée bi-directionnelle. Cette méthode est illustrée ci-dessous. Elle consiste simplement à répliquer le header avant et après le bloc de données (nécessitant ainsi 2 mots supplémentaires et plus un seul), ce qui permet le parcours, et donc la fusion des blocs libres dans les deux sens. Par exemple ici, la réservation du troisième bloc libre entraînera la fusion avec les deux blocs libres précédents. La figure suivante illustre ce principe.

Politique de placement¶

L’algorithme de sélection du bloc libre à utiliser présenté et utilisé jusqu’ici est assez basique. L’opération de recherche s’arrête dès qu’un bloc vide de taille suffisante pour héberger la nouvelle allocation est trouvée. On appelle cette politique de placement first fit. Celle-ci peut prendre un temps linéaire en le nombre de blocs (alloués et libres) mais termine dès qu’un bloc valide est trouvé, et donc assez rapidement en pratique. Toutefois, elle présente des désavantages en pratique, car elle entraîne de la fragmentation est n’a pas de bonnes propriétés de localité. En effet, les allocations de petits objets ont tendance à s’accumuler au début de la zone mémoire, et lorsque ceux-ci sont libérés il subsiste de nombreux petits blocs libres qui ralentissent les recherches ultérieures. Les allocations d’objets de taille plus importante, et en particulier les allocations successives, ne sont pas nécessairement placées dans des zones proches, ce qui entraîne une faible localité.

Il existe d’autres politiques, comme par exemple :

• La politique next fit se comporte de la même manière que first fit mais démarre la recherche depuis le dernier bloc alloué. Bien entendu, si aucun bloc de taille suffisante n’est trouvé, il est nécessaire de recommencer depuis le début du heap. Cette politique a de meilleures propriétés de localité que first fit mais les évaluations montrent qu’elle conduit à une encore plus grande fragmentation.
• La politique best fit cherche a répondre à une demande d’allocation avec un bloc donc la taille est la plus proche de celle demandée (juste nécessaire). Cette politique a l’avantage d’être optimale en terme de fragmentation. Toutefois, elle a deux désavantages : elle a potentiellement une mauvaise localité, les blocs libres de taille équivalente n’étant pas nécessairement proches les uns des autres, et elle nécessite un parcours complet de la liste dans tous les cas (sauf, bien sûr, si un bloc de la taille exactement demandée est trouvé).

Ces politiques représentent des compromis différents entre les critères que nous avons défini plus haut : rapidité d’exécution, fragmentation de la mémoire, et localité.

Utilisation d’une liste explicite¶

Nous allons maintenant étudier une autre alternative, qui consiste à créer une liste explicite liant uniquement les blocs libres entre eux. Le principe est ici d’utiliser l’espace disponible dans chaque blocs libre pour y stocker des pointeurs vers un prochain bloc libre. Le parcours de la liste chaînée permet donc de ne considérer que les blocs libres, ce qui est plus rapide en particulier lorsque de nombreux blocs sont déjà alloués. La figure suivante présente le principe avec une liste explicite simplement chaînée.

On notera l’utilisation du premier mot pour stocker un pointeur vers un premier bloc libre. Pour chaque bloc libre, deux mots sont utilisés. Le premier mot contient comme auparavant la taille du bloc libre. Le deuxième mot contient un pointeur vers le prochain bloc libre. Le parcours de la liste des blocs libres se fait en suivant ces pointeurs.

En pratique, une liste explicite est toujours une liste doublement chaînée, c’est à dire que chaque bloc libre contient un pointeur vers le prochain bloc dans la liste ainsi qu’un pointeur vers le bloc précédent. Par ailleurs, l’ordre des blocs libres dans la liste explicite ne suit pas forcément l’ordre des adresses de début de ces blocs. Une telle liste est illustrée par la figure suivante, qui présente seulement une partie du segment heap.

Les blocs libres A, B et C ne sont pas liés dans cet exemple dans l’ordre de leurs adresses. Il est donc nécessaire de dupliquer le header de bloc vide au début et à la fin de chaque bloc comme expliqué précédemment, afin de permettre la fusion de blocs vides contigus dans les deux sens. L’espace mémoire utilisée (fragmentation interne) est le même que dans le cas d’une liste implicite avec la duplication du header : deux mots supplémentaires sont nécessaires au début et à la fin de chaque bloc alloué. En revanche, quatre mots sont nécessaires pour chaque bloc libre. Ils servent à stocker les pointeurs vers le bloc successeur et prédécesseur de chaque bloc libre. Cela n’a pas d’impact sur la fragmentation interne, puisque ces méta-données sont stockées dans les blocs libres. En revanche, la taille minimum de bloc (libre ou alloué) est désormais de 4 mots. Il est donc nécessaire, dans cet exemple, d’aligner les allocations de blocs pour qu’ils utilisent un multiple de 4 mots, en utilisant du padding si nécessaire.

L’allocation d’un bloc de données avec une liste explicite suit le même principe qu’avec une liste implicite, et peut obéir à des politiques similaires. Il est nécessaire, bien entendu, de maintenir les propriétés de la liste doublement chaînée. Ceci nécessite de mettre à jour le pointeur vers le bloc successeur du bloc libre précédent le bloc alloué, et le pointeur vers le bloc prédécesseur du bloc libre suivant le bloc alloué. Ces opérations sont illustrés sur notre exemple dans la figure suivante, où les pointeurs en rouge représentent les pointeurs modifiés.

La libération d’un bloc est plus complexe qu’avec une liste implicite. Cela est du au fait que la liste des blocs libres ne représente pas nécessairement l’ordre des adresses de ces blocs en mémoire. Deux politiques sont possibles pour pallier cette difficulté :

• Une première politique, appelée address-ordered consiste à s’assurer que cette propriété d’ordre est assurée. Lors de la libération d’un bloc, celui-ci est inséré dans la liste chaînée exactement entre les deux blocs libres le précédent et le succédant dans l’ordre des adresses. Cette politique permet de fusionner très facilement les zones libres contigus (elles sont soit deux, soit trois, jamais plus). En revanche, elle a un défaut majeur : elle nécessite de parcourir la liste pour chercher l’endroit dans la liste où insérer le bloc vide.
• Une deuxième politique est de simplement insérer le bloc vide au début de la liste des blocs vides (on parle alors de politique LIFO, pour Last-In-First-Out). Cette approche a l’avantage indéniable que l’opération de libération est en temps constant. Toutefois, la fusion de zones libres contigus devient plus complexes et nécessite d’opérer des changements dans au plus trois éléments de la liste chaînée et leurs voisins respectifs. Nous n’en couvrirons pas les détails dans le cadre de ce cours.

En règle générale, la politique address-ordered entraîne une fragmentation externe moins importante que la politique LIFO. Son principal désavantage réside donc dans son temps d’exécution, qui peut devenir important lorsque de nombreux blocs vides sont présents.

Utilisation de listes multiples¶

Les mécanismes et politiques de gestion de la mémoire dynamique qui ont été présentées ne font pas de distinction entre les demandes d’allocation de blocs de petite et de grande tailles. Cela pose un inconvénient double. Tout d’abord, le temps de recherche d’un bloc vide augmente linéairement avec le nombre de blocs (total pour une liste implicite, ou seulement libres pour une liste explicite). Par ailleurs, le temps de recherche d’un bloc vide de grande taille peut prendre un temps plus important que la recherche d’un bloc vide de petite taille.

Une solution à ces défauts est d’utiliser non pas une, mais plusieurs listes. Chaque liste correspond alors à une classe de taille. Il peut ainsi y avoir une liste pour les blocs de taille 1, 2, 3, ou 4 octets, puis des listes pour les tailles correspondant aux puissances de 2 : 8, 16, 32, 64, etc. octets. La recherche d’une zone libre est faite dans la liste correspondant à la taille immédiatement supérieure à la taille demandée : une demande d’allocation pour un bloc de taille 67 octets sera ainsi servi en utilisant la liste des blocs libres de taille 128, c’est à dire parmi les blocs libres de 65 à 128 octets.

On notera que l’utilisation de listes multiples a une synergie avec l’utilisation de listes explicites. Il suffit, en effet, d’utiliser autant de pointeurs de début de liste que de listes, et de parcourir la liste adéquate. Les opérations de réservation et de libération de blocs peuvent entraîner, en revanche, des opérations de recherche sur plusieurs listes. Cela rend alors la politique address-ordered significativement plus coûteuse que la politique LIFO, qui peut alors être préférée dans ce cas.