Allocation et Libération d'espace : Cours Algorithme

- Méthodes de libération automatique.
- Système semi-automatique.

1 Allocation et Libération d'espace

Une allocation d'espace est nécessaire pour toute structure qui ne respecte pas les règles des variables locales des fonctions. De la même manière, une libération est aussi nécessaire lorsque la variable n’est plus utilisée, sinon une longue exécution du programme risque d'échouer, faute d'espace mémoire disponible .

Attention, libérer trop ou trop tôt une variable peut aussi être désastreux. La gestion de la mémoire peut être automatique, semi-automatique ou artisanale selon le langage de programmation et l'application.

1.1 Méthodes de libération automatiques

Deux types de méthodes ont été étudiés qui permettent de récupérer automatiquement l'espace qui ne sera plus utilisé par le programme. Un programme peut aussi utiliser les mêmes méthodes de « ramassage de miettes ».

Une première méthode consiste à compter les pointeurs :

Dans chaque bloc (structure, etc.), on maintient un champ caché qui est le nombre de pointeurs au bloc,

On met à jour ce champ à chaque fois qu’un pointeur est ajouté ou enlevé.

Quand le nombre tombe à 0, le bloc peut être libéré (car il n’est plus pointé, donc utilisé) avec éventuellement d'autres libérations (réaction en chaîne).

Cette méthode ne réussit pas à libérer toutes les structures circulaires (le cas simple d'un pointeur d'un bloc vers lui-même peut être traité).

1.1.1 Libération automatique marquer et balayer

Les structures accessibles à un moment donné sont celles directement connues du programme (valeurs de variables et paramètres) ainsi que celles accessibles indirectement de celles-ci par des chaînes de pointeurs. Une méthode de libération consiste à :

maintenir un bit dans chaque bloc : est-il accessible ou non?

de temps en temps remettre tous les bits à 0 ;

procéder récursivement à partir de chaque bloc directement accessible en mettant des bits à 1 à chaque bloc rencontré (et arrêtant quand un bloc trouvé est déjà marqué)

enfin, balayer toute la zone en récupérant tous les blocs non marqués (éventuellement en compactant tous les blocs survivants, mais ceci nécessite une modification de tous les pointeurs!). C’est ce qu’on appelle le ramassage.

Remarque : Ici, un problème se pose : le programme doit s'arrêter pendant ce temps de mise à jour !

1.1.2 Ramassage parallèle

Une famille d'algorithmes basés sur un premier algoritheme de Dijkstra permettent de ramasser sans arrêter les autres processus. Il s’agit en général d’algorithmes compliqués dont l’efficacité a été prouvée avec plusieurs démonstrations (dont certaines sont fausses). Le principe de fonctionnement de ce type d’algorithme peut être résumé ainsi :

On distingue trois types de bloc : des blocs non marqués (blancs), des blocs marqués mais dont les fils ne sont pas forcément marqués (gris) et des blocs marqués ainsi que ses fils (noirs)

Quand un pointeur dans un bloc change, le bloc et le nouveau fils deviennent gris.

C’est la méthode (garbage collector) utilisée en java.

1.1.3 Contraintes sur le langage de programmation pour qu'un système automatique soit possible

Il faut que le système puisse savoir où sont les pointeurs dans chaque bloc. On doit donc utiliser des règles strictes de typage et faire attention aux dangers d'arithmétique sur les pointeurs. De plus, il est nécessaire d’avoir des restrictions sur les types union.

1.2 Système semi-automatique

Un système semi-automatique peut être par exemple implémenté en C suivant l’algorithme en exalgo suivant :

Libération explicite par le programme (free() ou malloc() en C)

Parcours de listes ou d'arbres pour libérer chaque nœud inutilisé (mais cela reste difficile avec structures circulaires)

Danger subtil de parcours simple qui marque et libère!

Attention aussi aux structures partagées (globales)

1.2.1 Allocation « artisanale » avec blocs de la même taille

Si un programme n'utilise que des blocs d'une même taille (manipule un type de liste ou d'arbre, ...), il est facile de garder tous les blocs disponibles dans une liste. Dans ce cas :

L’allocation consiste à prendre le premier bloc de la liste (s'il y en a) ;

La libération : ajouter un élément au début de la liste.

1.2.2 Blocs de tailles différentes

Avec des blocs de taille différente, la tâche est plus compliqué : on a toujours une liste de blocs disponibles mais de tailles différentes et en ordre d'adresse. Dans ce cas :

L’allocation consiste prendre le premier (?) bloc suffisamment grand dans la liste, voire enlever d’autres éléments de la liste, ou les déplacer afin d’ajuster la taille nécessaire à la nouvelle allocation.

La libération consiste à trouver la bonne position dans la liste.

insérer et éventuellement fusionner avec son prédécesseur et/ou successeur

Remarque : le compactage est possible mais complexe !

-------------------------------------------------------------------------------------------------------
Précédent:Recherche d'occurrences d'une chaîne de caractères