Qu'est-ce qu'une liste libre?
Une liste libre est une structure de données contenant les adresses des emplacements de mémoire d'ordinateur disponibles pour une utilisation par un programme en cours lors de l'utilisation d'une allocation de mémoire dynamique. La liste devient nécessaire lorsqu'un programme doit allouer de l'espace. L’implémentation d’une liste libre peut consister en une simple liste chaînée ou en une structure de données plus complexe, telle que La plupart des langages de programmation informatiques de haut niveau gèrent automatiquement la liste libre, éliminant ainsi la nécessité d’une gestion manuelle.
Lorsqu'un programme nécessite de l'espace pour stocker des informations lors de son exécution, il doit demander au système d'exploitation sous-jacent une quantité de mémoire spécifique. Les emplacements des blocs de mémoire pouvant être utilisés sont stockés dans le répertoire libre. Pour que l’attribution réussisse, la quantité de mémoire demandée doit être disponible dans un ou plusieurs de ces blocs. Lorsqu'un pointeur sur un emplacement de mémoire approprié est renvoyé, cet élément de la liste est supprimé.
Une fois qu'un programme est terminé en utilisant la mémoire, il peut le désallouer, ce qui implique de remettre le pointeur du bloc de mémoire dans la liste des emplacements libres, où il sera disponible la prochaine fois qu'une allocation est effectuée. Il est possible que l'allocation de mémoire échoue parce que la liste est vide ou parce qu'il n'y a pas de blocs de mémoire disponibles suffisamment volumineux pour répondre à la demande du programme.
La forme la plus simple de gestion de la mémoire est appelée système de premier ajustement. Ce système conserve une liste unique d'emplacements de mémoire libres. Lorsqu'une demande de mémoire est envoyée, la liste est parcourue et le premier bloc Si le bloc a plus de deux fois la taille demandée, il est divisé en deux et la moitié inutilisée est rajoutée à la liste. Cette méthode permet d'échanger du code simple à le risque d'avoir des zones de mémoire fragmentées qui pourraient ne jamais être retournées à la liste.
Une autre forme de gestion de la mémoire est appelée système d’allocation des contacts. À la différence du premier système d’ajustement, l’allocation des contacts conserve plusieurs listes libres, chacune ne contenant que des blocs ouverts d’une taille donnée. lorsqu'une demande d'allocation est reçue, la liste contenant des blocs juste assez grands pour remplir la demande est consultée et un emplacement ouvert est renvoyé. Si aucun bloc libre inférieur à deux fois la taille sont disponibles, un bloc plus grand est divisé en deux pour répondre aux besoins.
Le terme "liste libre" peut faire référence à une seule liste d'adresses de mémoire, ou à un type de structure de données beaucoup plus complexe. Différents types d'arbres de tri, s'ils sont simples et équilibrés, peut aider à augmenter la vitesse de recherche des blocs de mémoire ouverte aux dépens de la complexité du code source.Une liste chaînée peut être plus lente qu'un arbre de tri spécialisé, mais crée un code de programmation beaucoup plus facile à lire, déboguer et modifier.
Certains langages de programmation et systèmes d'exploitation utilisent un mécanisme spécial appelé garbage collection, un processus permettant de récupérer les différentes entrées sur une liste libre et de consolider les espaces libres de manière à ce qu'ils soient contigus. l’effet de prévenir la fragmentation et de permettre l’allocation de blocs de mémoire plus importants.