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

18

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…)

Stéphane Gimenez
la source
la vérification d'une liste ne serait-elle plus à temps constant, car la liste pourrait augmenter ou diminuer en raison de certaines allocations / désallocations effectuées précédemment?
Sim
@Sim, je supposais que c'était une liste chaînée et avec elle les opérations seraient , parce que vous ne travaillez toujours qu'avec la tête. O(N)
svick
Je pense que votre «meilleure approche» utilisera déjà une quantité optimale de mémoire, c'est-à-dire qu'elle n'allouera jamais de mémoire supplémentaire s'il y a un bloc libre. Comment pensez-vous que l'approche «intelligente» pourrait améliorer cela? Voulez-vous dire qu'il doit être alloué près du début afin qu'il y ait de meilleures chances que vous puissiez réduire le segment après les désallocations?
svick
@Sim: Désolé, j'aurais peut-être dû utiliser le terme pile (mais je pensais que cela pouvait prêter à confusion), `` deallocate '' est push et `` allocate '' est pop, ou dans le cas où il échoue, revenez simplement à l'incrémentation du compteur. Les deux sont à temps constant.
Stéphane Gimenez
Avez-vous des contraintes de temps réel ou êtes-vous d'accord avec le temps constant amorti? Les réponses seront probablement assez différentes.
Gilles 'SO- arrête d'être méchant'

Réponses:

11

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.

Thomas Pornin
la source
4
Comment trouvez-vous les trous les plus proches d'un site de désallocation en temps constant?
Raphael
1
Dans la deuxième méthode que je décris, un trou est un en-tête (une paire de pointeurs, pour la liste des trous) avec un espace pour zéro, un ou plusieurs blocs de données. Entre deux blocs alloués, il y a toujours un trou, même s'il s'agit d'un micro-trou composé uniquement d'un en-tête de trou. Il est donc facile de localiser les trous les plus proches: ils sont juste avant et juste après la fente. Bien entendu, les micro-trous ne font pas partie de la liste gratuite (la liste des trous éligibles à l'allocation). Une autre façon de le voir est d'ajouter un en-tête à chaque bloc et à chaque trou (non micro) (l'allocation sous Ms-Dos 16 bits fonctionnait comme ça).
Thomas Pornin
4

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.

rgrig
la source
Intéressant, je dois lire ceci en détail. Cependant, il semble que ces systèmes traitent spécifiquement des allocations de taille non constante, ce qui n'est pas un problème auquel je suis confronté.
Stéphane Gimenez
Droite. Désolé, j'ai lu votre question beaucoup trop vite.
rgrig
O(lgn)
s / plus petit bloc libre / bloc libre à la plus petite adresse /
rgrig
2

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.

gallais
la source
2
Et comment les tableaux dynamiques aideront-ils exactement à allouer de la mémoire?
svick
Vous alliez (dé) allouer des morceaux de cellules contiguës en utilisant le même type d'algorithme? Votre fichier entier serait une liste chaînée de morceaux de plus en plus gros.
gallais