6. Structures dynamiques
linéaires non récursives : les fichiers
Lorsqu'un traitement implique, non seulement la création dynamique
d'objets à l'aide, par exemple, de la procédure "new", mais
aussi la destruction, en cours d'exécution, de certains de ces objets,
l'occupation mémoire risque de ne plus être contiguë, mais
a de forts risques de devenir fragmentée :
| Obj1 | Obj2 | Obj3 | Obj4 | libre |
| Obj1 | Obj2 | libre | Obj4 | libre |
La réutilisation de l'espace mémoire libéré peut
se faire de différentes manières :
La première solution, appelée "ramassage des miettes" (Garbage Collection), ne peut se faire que si le système gère l'ensemble des objets alloués dynamiquement à l'aide d'informations supplémentaires adjointes à chaque objet, permettant ainsi de tous les parcourir pour voir à quels autres objets ils font référence.
Chaque nouvelle allocation dynamique est effectuée en utilisant une place mémoire jusque là inoccupée. Ce n'est que lorsque cette place fera défaut qu'une réorganisation globale de l'espace mémoire sera entreprise pour regrouper en une seule zone contiguë l'ensemble des places libérées en cours d'exécution. Cette procédure est assez difficile à implanter et, qui plus est, assez longue à exécuter.
On trouve souvent l'emploi de cette solution dans des environnements associés à des langages de programmation où les listes sont des structures privilégiées (Lisp par exemple). L'intérêt de cette solution est de fournir la certitude qu'un objet sera créé s'il existe assez de place en mémoire pour cela. Un de ses inconvénients est que le processus de récupération peut intervenir à n'importe quel moment et provoquer un ralentissement provisoire mais notable des temps de réponses du système. Ceci peut être très gênant si l'on a une application temps réel, qui nécessite des temps de réponse prévisibles.
La deuxième solution est plus facile à mettre en oeuvre mais ne résout pas tous les problèmes pour autant. Elle consiste à chaîner les trous entre eux avec, pour chaque trou, l'indication de sa taille et de l'emplacement du trou suivant.
Si tous les objets créés dynamiquement ont la même taille, on peut chaîner les zones libres entre elles dans n'importe quel ordre. La procédure d'allocation dynamique n'aura qu'à utiliser le premier de cette chaîne pour allouer de la place à un nouvel objet.
Si les objets créés dynamiquement ont des tailles différentes, on risque d'arriver à une situation où la totalité de l'espace libre permettrait de créer un nouvel objet, mais où aucun trou n'est assez grand pour le contenir. Pour minimiser cet effet, il est donc important de pouvoir regrouper, en un seul bloc, des trous contigus. Pour ce faire, il est nécessaire de chaîner les trous dans l'ordre d'apparition en mémoire. Chaque fois qu'un objet dynamique est détruit, la "chaîne libre" est parcourue pour voir où ranger ce nouveau trou. S'il se trouve juste à côté d'un autre trou, ou entre deux trous, les deux ou trois trous sont alors regroupés pour ne plus en former qu'un.
Deux principales possibilités d'utilisation des trous peuvent être envisagées. La méthode dite de la première convenance (first fit) et celle de la meilleure convenance (best fit). La première consistant à parcourir la chaîne libre depuis son début et à utiliser le premier trou suffisamment grand pour contenir le nouvel objet; la deuxième méthode consiste, elle aussi, à parcourir la chaîne libre, mais cette fois jusqu'à la fin de la chaîne pour déterminer quel est le plus petit trou suffisamment grand pour contenir le nouvel objet, à moins que l'on ne rencontre, en cours de route, un trou ayant la taille exacte de ce nouvel objet. La méthode du "best fit" semble de prime abord plus intéressante. Elle a toutefois l'inconvénient d'impliquer une plus longue recherche et de générer des trous de plus en plus petits qui seront difficilement réutilisables. C'est donc la méthode de la première convenance (first fit) qui est généralement choisie.
Les avantages principaux du chaînage de trous sont la simplicité d'implantation et la rapidité d'exécution. L'inconvénient principal est que l'on ne peut pas garantir la création d'un nouvel objet, même s'il y a assez de place en mémoire. La fragmentation de l'espace libre peut en effet être telle qu'aucun morceau n'est assez grand pour contenir l'objet à créer.
Certains systèmes combinent les deux solutions (ramassage des miettes et chaînage des trous) pour avoir les avantages de chacune. Le chaînage des trous est utilisé jusqu'à ce que l'on arrive à une situation où aucun trou n'est assez grand pour le nouvel objet à créer. Ce n'est qu'alors que le processus de ramassage des miettes est amorcé.
6. Structures dynamiques
linéaires non récursives : les fichiers
Site Hosting: Bronco
Table des
matières.