Gestion intelligente de la mémoire avec des opérations à temps constant?

Considérons un segment de mémoire (dont la taille peut augmenter ou diminuer, comme un fichier, si nécessaire) sur lequel vous pouvez effectuer deux opérations d'allocation de mémoire de base impliquant des blocs de taille fixe:

• attribution d'un bloc
• libérer un bloc précédemment alloué qui n'est plus utilisé.

De plus, le système de gestion de la mémoire n'est pas autorisé à se déplacer dans les blocs actuellement alloués: leur index / adresse doit rester inchangé.

L'algorithme de gestion de mémoire le plus naïf incrémenterait un compteur global (avec la valeur initiale 0) et utiliserait sa nouvelle valeur comme adresse pour la prochaine allocation. Cependant, cela ne permettra jamais de raccourcir le segment lorsqu'il ne reste que quelques blocs alloués.

Meilleure approche: conservez le compteur, mais conservez une liste de blocs désalloués (ce qui peut être fait en temps constant) et utilisez-le comme source pour de nouvelles allocations tant qu'il n'est pas vide.

Et ensuite? Y a-t-il quelque chose d'intelligent qui puisse être fait, toujours avec des contraintes d'allocation de temps et de désallocation constantes, qui garderait le segment de mémoire aussi court que possible?

(Un objectif pourrait être de suivre le bloc actuellement non alloué avec la plus petite adresse, mais cela ne semble pas possible en temps constant…)

Avec des blocs de taille fixe, ce que vous avez décrit est une liste gratuite . C'est une technique très courante, avec la torsion suivante: la liste des blocs libres est stockée dans les blocs libres eux-mêmes. En code C, cela ressemblerait à ceci:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

Cela fonctionne bien tant que tous les blocs alloués ont la même taille et que cette taille est un multiple de la taille d'un pointeur, de sorte que l'alignement est préservé. L'allocation et la désallocation sont à temps constant (c'est-à-dire aussi à temps constant que les accès à la mémoire et les ajouts élémentaires - dans un ordinateur moderne, un accès à la mémoire peut impliquer des échecs de cache et même de la mémoire virtuelle, donc des accès au disque, donc le "temps constant" peut être assez gros). Il n'y a pas de surcharge de mémoire (pas de pointeurs par bloc supplémentaires ou des choses comme ça; les blocs alloués sont contigus). De plus, le pointeur d'allocation n'atteint un point donné que si, à un moment donné, de nombreux blocs ont dû être alloués: puisque l'allocation préfère utiliser la liste libre, le pointeur d'allocation n'est augmenté que si l'espace sous le pointeur actuel est plein d'horloge. Dans ce sens, technique.

Décroissantle pointeur d'allocation après une version peut être plus complexe, car les blocs libres ne peuvent être identifiés de manière fiable qu'en suivant la liste gratuite, qui les parcourt dans un ordre imprévisible. S'il est important pour vous de réduire la grande taille des segments, vous pouvez utiliser une technique alternative, avec plus de surcharge: entre deux blocs alloués, vous mettez un "trou". Les trous sont liés ensemble avec une liste doublement liée, dans l'ordre de la mémoire. Vous avez besoin d'un format de données pour un trou de sorte que vous puissiez localiser l'adresse de début du trou en sachant où il se termine, ainsi que la taille du trou si vous savez où le trou commence en mémoire. Ensuite, lorsque vous libérez un bloc, vous créez un trou que vous fusionnez avec le trou suivant et le trou précédent, reconstruisant (toujours en temps constant) la liste ordonnée de tous les trous. La surcharge est alors d'environ deux mots de la taille d'un pointeur par bloc alloué; mais, à ce prix, vous pouvez détecter de manière fiable l'occurrence d'un "trou final", c'est-à-dire une occasion de diminuer la taille du grand segment.

Il existe de nombreuses variantes possibles. Un bon document d'introduction est Dynamic Storage Allocation: A Survey and Critical Review par Wilson et al.

Cette réponse concerne les techniques génériques de gestion de la mémoire. J'ai manqué que la question pose sur le cas où tous les blocs ont la même taille (et sont alignés).

Les stratégies de base que vous devez connaître sont le premier ajustement, le prochain ajustement, le meilleur ajustement et le système de jumelage . J'ai écrit un court résumé une fois pour un cours que j'ai enseigné, j'espère qu'il est lisible. Je signale là une enquête assez exhaustive .

En pratique, vous verrez diverses modifications de ces stratégies de base. Mais rien de tout cela n'est vraiment un temps constant! Je ne pense pas que ce soit possible dans le pire des cas, tout en utilisant une quantité de mémoire limitée.

Vous voudrez peut-être jeter un œil à l' analyse amortie et en particulier aux tableaux dynamiques. Même si les opérations ne sont pas vraiment effectuées en temps constant à chaque étape, à long terme, il semble que ce soit le cas.